D. Connect the Dots
dが小さいので、dとその余りごとに分けて、各i in [1 , ... ,n]に対して、各dについて[x , ... ,y] が同じグループでiがその中に入るなら、xとiをUnion-findで繋げる、とやっていけば良い。
コンテスト時間ギリギリに実装し終わったのだが、d>=2だと勘違いしておりWAでした。そこを修正したらAC。Ratedでこんなことしたら酷いのでUnratedで良かった。
2024年9月30日月曜日
AtCoder Grand Contest 068
一問も解けず。
コンテスト後のツイート
AtCoder Grand Contest 068 0完
— titia (@titia_til) September 29, 2024
ずっとBを考えていたが、愚直っぽい構築が上手くいく気がしていて、それが勘違いだと終了間際に気付いた。何も分からず終了。
B - 01 Graph Construction
解説を見てAC。
何も思いつけなかったのは仕方ないのだが、愚直っぽい方法で上手くいきそう、と考えたのはダメ。メタ読みみたいになるけど、AGCなのだから何か上手い方法があるはず……と追求すべきだった。
愚直っぽい方法は、遅くても、最初に上手くいかなそうな例が見つかった時点で捨てるべきだった。
2024年9月29日日曜日
AtCoder Beginner Contest 373
Fまで六完。Fは未証明だったけど、この制約だと正当だったかも？（w=1や2がたくさんある場合が問題だけど、それはカバーできてそう）
コンテスト後のツイート
F CHTを使いそうだと思ったが分からず。ペナルティも含めて(v,w)を並べて、v/wが大きい順に並べた上位10000個に含まれるもの（それを1個でオーバーするなら1個は持つ）だけ使ったらACした。
— titia (@titia_til) September 28, 2024
G - No Cross Matching
解説AC。
最小費用流の方法でACした。
自分の最小費用流のライブラリはひどいと思っていたが、TLEが出たため久しぶりに見直した。多少は速くなったか。
ただ、今回のテストケースではたまたまACできただけで、簡単にTLEするケースは作れる模様。うーん。
2024年9月28日土曜日
Codeforces Round 973 (Div. 2)
Cまで三完。
D. Minimize the Difference
解説AC。
問題文で与えられた操作を用いて、広義単調増加にすれば良い（逆に、A[i]<=A[i+1]となったらそれ以上操作はしない）だろうことにはコンテスト中に気付いていた。
どういう操作でそれを実装できるかが分からなかった。
これは、[値, その要素の個数]を持って、配列の値を見たら後ろの要素とマージしていく……とすれば実装できる。
マージすることは思いつくけど、ランレングス圧縮のようなことをすると計算量が減るとは気付かなかった。
この方法を思い付けなかったのは悔しい。
E. Prefix GCD
自力AC。
直感的に正しそうな貪欲を実装したらそのままACだった。証明も、こんな感じかな？ と思ったもの（ちゃんと証明はしていない）で良さそうだった。
yukicoder contest 448
遅刻して、Aが分からず0完。
No.2902 ZERO!!
自力AC。コンテスト後、横になって考えていたら気付いた。
N!ではなく、一般のNについてこの値を求めることを考えていたら、約数の個数を求めることとかなり似ていることに気付いた。
たとえば、$N=2^8*3^{10}$のとき、約数の個数は(8+1)*(10+1)個だが、今回はそれに加えて、(8/2+1)*(10/2+1), (8/3+1)*(10/3+1), (8/4+1)*(10/4+1), ... といった値を加えれば良い。
2024年9月26日木曜日
AtCoder Regular Contest 184
Aしか解けず。
コンテスト後のツイート
AtCoder Regular Contest 184 Aしか解けず。
— titia (@titia_til) September 22, 2024
A 二枚ずつに分ける→一致しているものをマージしていき、12個になったら正しいコイン、他はダメなコイン！ という操作を続ける。最後に、正しいコインと分かっているものを使い、最初に一致しなかったものをチェック。
B - 123 Set
解説放送を見てAC。
解説を見ると、ステップは多いものの一つ一つの難易度は高くない。解けなくてはいけない問題だった。（実装が終わるか、という話はあるものの、少なくとも解法の概要は自力で分かるべきだった）
が、コンテスト本番では最初のステップすらできていなかった。2や3でギリギリまで割った値が異なれば互いに影響しない、ということには気付いていたが、それを考察に生かせていない。
Aを解いて気が抜けてしまったというところもあったと思う。最後まで気を抜かずにやり切るようにしたい。
C - Mountain and Valley Folds
解説放送を見てAC。
山折り、谷折りがどのようになるか？ というのが掴めれば、それ以降の考察は結構自然に思えた。
ただ、自分では山折り、谷折りの挙動が掴めなかったんだよね……。解説放送の最初に話していた、半分折り返せばできるんじゃない？ とは一応考えたが（それも形にできなかった）。
2024年9月25日水曜日
日立ヴァンタラプログラミングコンテスト2024（AtCoder Beginner Contest 368）
Eが解けなかった。
コンテスト後のツイート
G セグ木二本使う。Bについてはmaxを、Aについては和をもつ。Bで1が連続するようなら、セグ木上の二分探索で次の1でない値を探し、そこまでのAの和を加算。
— titia (@titia_til) August 24, 2024
E - Train Delay
解説・解説放送を見てACしたが、ACした後も自分のコードが正しいか自信が持てず乱択で比較したりしてしまった。（正しかったよう）
出発時刻が早い列車から見ていこうというのは良いが、それ以外に何を持てば良いのかが難しい。
各駅ごとに、（本来の到着時刻, 遅れたときの到着時刻）を全て持ってそれら全てについて調べればもちろん良いのだがそれでは計算量が間に合わない。
ある列車について、その発車時刻より以前に本来の到着時刻があった列車全てについて調べ、遅延に原因する列車が特定できたとき、（調べた範囲の他の列車については忘れて）その列車についてのみ覚えておけば良い。ここが重要。
なぜそれで良いのかが整理できなかったのだが、それ以降の発車時刻のものは、今回遅延原因だった列車とは本来乗り換え可能だったから、ということ。
ここで迷う人は結構いるんじゃないかと思う。ただ、自分が図を描いたり色々してもしばらく理解できなかったことをこうやって言葉だけで書いても伝わらないとは思うけれど……。
2024年9月21日土曜日
yukicoder contest 447 オムニバス
ABの二完。Bでxorの基底をちゃんと使えたのは良かったが、Cできなかったのはひどい。
No.2896 Monotonic Prime Factors
解説AC。
コンテスト中、素因数をソートして横に並べて、それらをn個に分ける場合の数だから重複組み合わせでできるはず……と思いながら、答えが合わず通せなかった。
x個をn個に分けるのは、x個の間x-1個のうちからn-1個を選ぶのだから、x-1Cn-1になる。これが考えても出てこなかった。
出てこないにしても、重複組み合わせというキーワードが思い出せているなら、検索とかでどうにかなったはずだよね。ちゃんとしよう。
No.2897 ２集合間距離
解説AC。
この制約ならBFSするだけと気付かなかったのも反省。また、tester解のように45度回転させて平面走査みたいなことを考えていたのに、二分探索を思いつかなかったのも反省。
2024年9月18日水曜日
RECRUIT 日本橋ハーフマラソン 2024夏（AtCoder Heuristic Contest 036）
pretest71位→システムテストリジャッジ前100位→リジャッジ後72位でした。
リジャッジありがとうございます！
システムテスト結果が出たとき、ジャッジおかしいんじゃないの？ というようなことをツイートしたけど、それほど確信はなかった。リジャッジでTLEが減り、順位が上がって良かった。
最終日まで300位前後で、最終日にAの別の作り方を試し、順位が大きく上がったのも嬉しかった。
大体ツイートのまとめです。
コンテスト後のツイート
RECRUIT 日本橋ハーフマラソン 2024夏（AtCoder Heuristic Contest 036）
— titia (@titia_til) September 2, 2024
最後まで提出を迷っていたのですが、明らかな点数の改善は見込めなそうなので提出を見送って終了。暫定71位。19:01にその提出を出したところ、元の点数53389点→53311点でした。WAじゃないけど、あまり変わらなかった。
前半四日くらい
Aを固定したとき、「Bの変更は全体取り換えのみ」とすれば最適解を求められそう……と思って書くが、色々バグらせた上PyPyじゃ間に合わない（あとでRUSTで書き換え、枝狩りをして一応間に合う。でもシステムテストだとTLEするかも→した）
最終日まで
Aとしては適当な評価値で山登り/焼きなましを考えていたが、それだと300位前後にしかならない。最終日に方針転換を迫られる。
最終日
t[i]からt[i+1]への最短距離での行き方を最初に調べ、それらを連続部分列として多くもつようにしたい。
まず、各点から各点までのBFSを使って、t[i]からt[i+1]まで進む頂点を列挙。この集合をNEEDとする
そのうち、長さが短いもの同士で、一番最初の文字＝一番最後の文字とかなったりするものを組み合わせていく。評価値は、「できあがったものの長さ/組み合わせた個数」のようにする。
評価値の小さい順にAにおいていく。ただし、Aの長さ+Aに出てきていないNEEDの個数<=LAとなるギリギリまでおき、その後はNEEDに入っているものをおいていく。
NEEDに入っているものxをおくときは、今までのAの中で、xのそばにxと隣接するものができるだけ多いような場所に置いた。
これが最終提出でした。
気になっていたこと
ところで、「自分のコードは、Aを与えられたら、Bを全取り換えするものだけ使うなら最善のものを出力しているつもりだったけど本当か？」が気になっていたので調べてみた。
上位の方のコードで出力しているAを入力し、そのときのスコア（そのコードでのスコア vs 自分のスコア）を比較すると、
・B全取り換えだけでやっている人には大体ちょっと勝ち（or引き分け）
・部分取り換えも使っている人には結構負け
という感じだった。
というわけで、自分のコードは、B全取り換えだけ使うなら多分最善だったけれど、
・厳密な最善を求める必要はない。多少スコアを犠牲にしても、計算量改善した方がメリットは大きい
・部分取り換えの使い道は少ないと思っていたけど、自分が思ったいたより大きく改善するらしい。
と分かった。
Aを決める部分の方がスコアに影響する度合いとしては大きいけど、そっちは発想力が求められた印象。今回はたとえば、「中心を決めて木構造にする」というAの取り方が強かったようだけど、コンテスト中に思いつけたか？ と考えると結構厳しく感じる。それに対して、「Aを求めた後何を出力するか？」の部分は発想よりアルゴの力が求められた気がする。
その部分で、（Bを全取り換えする場合の）最適解を求められていた（と思われる）という意味では、やるべきことはやっていたといえるけれど、もっと計算量を削減しなければヒューリスティックな手法は使えない。もっと考えなくてはいけなかったなぁ。
2024年9月17日火曜日
第11回 Asprova プログラミングコンテスト（AtCoder Heuristic Contest 037）
141位。
コンテスト後のツイート
第11回 Asprova プログラミングコンテスト（AtCoder Heuristic Contest 037）141位
— titia (@titia_til) September 15, 2024
x+yが大きい方から順に、
・z<=x,w<=yなる(z,w)から(x,y)を作る
・minx=min(x,z),miny=(y,w)とし、(minx,miny)から(x,y)と(z,w)を作り(minx,miny)を挿入
を全ての(z,w)について調べ、コストが一番低いものを選択。
マージした後のx+yの値が一番大きくなるような二点をマージする（マージの仕方はツイートと同じ）……という貪欲が強かった。
これを思いつかなくてはいけなかったのだが、厳しかった。
座標が大きい方から考えるのが良さそう、とは思ったけれど、コストをパラメーターに考えたくなってしまう。座標が大きいものをマージしたらコストも低くなる、とは考えにくかった。
AtCoder Beginner Contest 371
Eまで。
コンテスト後のツイート
AtCoder Beginner Contest 371 Eまで。最初に手をつけたCに20分かかった。
— titia (@titia_til) September 14, 2024
A 高い方に+1低い方に-1して、合計が0のもの。
B どの家で太郎とつけたか記録しておく。
C 対応する点をどうするか全部試す。
D 座標圧縮して累積和
E ある数字をこの前つかったのがいつだったかを覚えていれば計算できる。
F - Takahashi in Narrow Road
解説放送を見てAC。SortedSetを使った。
解説放送を見て衝撃だったのは、$X_i-i$、$G_i-T_i$と座標変換して良いというところだった。これは思いつけない。
これを思い付いていればそれ以降の部分は自力で解けた気がするので、ここが本質だと思う。しかし、言われてもかなり長いこと正当性が分からなかった。
こういう変換ができることもあると覚えておきたい。
G - Lexicographically Smallest Permutation
大体自力でACだけど、中国剰余定理などという単語はツイッターで見た。
順列を、どう巡回するかで分けるのはよくある方法。一つ決めるとその巡回部分は全て決まるので、それを使って最初の数字から決めていく。辻褄を合わせることができるか？ とい部分で中国剰余定理を使えばOK。
Fでなくこっちを解いていればコンテスト中に解けた気もする。
ただ、コンテスト中は、Gの「辞書順」という単語を見て避けてしまったんだよね。もうちょっとちゃんと問題を把握してから解くか避けるか決めた方が良いね。
2024年9月14日土曜日
yukicoder contest 446
Dまで。
No.2891 Mint
結構解かれていたのに解き方が分からず、今話題のChatGPTに聞いたところ、商が同じものをまとめて計算すれば良い、と教えてもらった。なるほど！ と思ったものの、コードは若干間違っていたため自分で書いたらかなり時間がかかった。
2024年9月13日金曜日
Codeforces Round 958 (Div. 2)
Dまで。
コンテスト後のツイート
Codeforces Round 958 (Div. 2) Dまで。
— titia (@titia_til) July 15, 2024
A k-1個ずつ増やせる
B 複数の0を一つに圧縮した後、1の個数>0の個数
C 立っているbit一個を削ったものたちで構成
D 使う回数の最大値が分かれば木DPできる。6回だとWA、大きくするとTLE→20回にしてChatGPTにC++に直してもらったらAC。
E. Range Minimum Sum
解説AC。こたつがめさんの放送の振り返りも参考にした。
また、Cartesian Treeはけんちょんさんのブログを参考にした。
なかなか解説を理解できず、苦労した。
まず、A[i]を取り除かない場合は、各iに対して、A[i]の左側で、A[i]より初めて小さい値が出てくるindexはどこか？（右側についても同じもの）を調べれば計算できる。
その上で、差分計算で求めたい。
このときの差分計算というのは、iを除いた場合とi+1を除いた場合で比較するというもの。全く取り除かない場合と比較するのではない。（結構後者を考えてしまったが、前者が自然ですね）
そのとき、変更される部分がたいして多くない、というのが重要。取り除くindexがiからi+1へ変更したとき、Cartesian Treeにおいてiの左の子と、そのさらに右の子孫たち（及び、その逆側）、及び、i+1の左の子と、そのさらに右の子孫たち（及び、その逆側）しか変更されない。それらを変更すればOK。
ただ、どこまで変更すれば良いかもO(1)でできるらしいのだがよく分からず、範囲最小値を求められるSparse tableを使って二分探索で求めた（Segment treeだとTLE）。
2024年9月9日月曜日
トヨタ自動車プログラミングコンテスト2024#9（AtCoder Beginner Contest 370）
Eまで五完の上、ペナルティをたくさん出してまずい。
コンテスト後のツイート
E 累積和Sを取り、S[i+K]以外の箇所に現在の場合の数を加算。累積和を使って加算する個数は処理できる。減産についても累積和を考え、dict Dを使ってD[i+K]-=（現在の場合の数）のようにする。
— titia (@titia_til) September 7, 2024
F - Cake Division
解説AC。
二分探索するのは分かるが、全点から試さなくてはいけなそうで、どうすれば良いか分からなかった。コンテスト中はそこを高速化することは思いつかず、全部試さなくてもいくつか点を試せば良いのかなぁ、というのを提出してWA。
ダブリングで高速化できるのはなるほど、でした。
あと、コンテスト中は、全点を試す→二分探索の順番で考えていたことも思いつかなかった原因かも。順番を変え、二分探索→全点を試すで考えるのが重要だった。
結構難しいが、以前、類題を解いたことがあったことを考えると解けなくてはいけない問題だった。
2024年9月8日日曜日
yukicoder contest 444
Aを解いた後、Bを読んでいたら目が痛くなって撤退。
No.2871 Universal Serial Bus
解説AC。
コンテスト後、解こうとしたらWAを量産してしまった。
二つ罠があった。
・全ての場合に確率が0のとき、期待値は無限になる。
期待値の定義を考えれば当たり前で、これに気付かないのはまずい。
・「ケーブルを 180度回転させて上下ひっくり返した状態」は左右も反転する！！
これ。
testcaseを読んだり解説を読んでもしばらく気付かなかった。コンテスト中ACするのは難しかったのでは。
No.2872 Depth of the Parentheses
自力AC。
二次元DPで計算量はKの三乗にはなった。
evilケースどうやるの？
No.2873 Kendall's Tau
自力AC。
「ケンドールの順位相関係数」は初耳でした。
どういうときに使うのかな～と思ったら、順位の相関を計ると知り納得。（名前が「順位相関係数」だから当たり前なのだけど、定義だけ読んだら分からなかった）
2024年9月7日土曜日
yukicoder contest 443
ABを解いた後、AHCの最中ということもあって疲労により撤退。
No.2864 String of yuusaan
解法ツイートを見てAC。
パッと問題を見たとき、周期性があるとは思わなかった。色々頑張れば（周期性がなくても）解けると思ったが、頑張る気力がなく撤退。
周期性がなくても解けそうな問題だけに、実験しようという気持ちにもあまりなれないから、周期性があると気付くのは難しい気がするのだけど……疲れていてちゃんと考察できなかったからなのかなぁ。
No.2865 Base 10 Subsets 2
自力AC。
これは苦労せず解けました。
No.2866 yuusaan's Knapsack
自力AC。
やり方は割合すぐに分かったのだが、バグってしまいACまで時間がかかった。「Pythonのlistは参照の値渡しであること」が原因でこれ自体は知っているのだけど、値を渡しているつもりで間違えてしまうと、どこでミスっているか気付くのは大変ですね。
No.2867 NOT FOUND 404 Again
自力AC。
解法が桁DPなのは分かりやすい。最近は桁DPは下の桁からやっていたが、今回久しぶりに上の桁から実装した。
DPの遷移で、"4"が一致しているところから、"40"が一致しているところだけでなく、"4"だけ一致しているところにもいけることに気付けず、愚直を書いて比較して気付いた。
2024年9月1日日曜日
AtCoder Beginner Contest 369
Eまで五完。
コンテスト後のツイート
E クエリごとにbit DPしながらダイクストラでいいと勘違い。予め全頂点間の移動時間を前計算して、橋の渡り方を全探索すると間に合う。
— titia (@titia_til) August 31, 2024
F セグ木DPを復元する感じかと思ったが、上手くいかないまま終了。
F - Gather Coins
セグ木DPで答えを求められるのはあっていたが、復元方法が分からなかった。
コインをソートした状態で考え、各コインが何回で取れるかという情報を持っておけば良い……というシンプルな方法だった。
G - As far as possible
解説放送を見てAC。
貪欲に長いpathを取っていけばいいというのは分かったが、実装が分からなかった。
木DPでそういうpath分解ができるというのは思いつかなかった。典型のようなので身に着けておきたい。
登録:
投稿 (Atom)