AtCoder Regular Contest 176 （Sponsored by Mynavi）

　Cまで三完。ARCでこれくらいの順位が取れると嬉しい。

コンテストへのリンク

コンテスト後のツイート

AtCoder Regular Contest 176 （Sponsored by Mynavi） Cまで三完。
A (j-i)%NをM個選び斜めにおいていく。
B M=K+1の場合は別に計算。N<Mなら答えは2^N。そうでないとき、K=0に帰着。2^N%(2^M+1)は2^(N-M)%(2^M+1)と一致する。
C Cが小さい方から見て頑張って場合分け（ABより考え方は楽だと思った）

— titia (@titia_til) April 21, 2024

D - Swap Permutation

　けんちょんさんの解説記事を参考にAC。

　解法ツイートで行列累乗で解けるというのを目にしたが、ある(a,b)というペアが最終盤面でどのような位置にあるか？　という遷移を考えてしまい、上手くできなかった。

　index i, i+1が最終的にどの数字になっているか？　に着目するのは言われてみれば自然。コンテスト中に解けなかったのは仕方ないにせよ、行列累乗で解けると言われたら思いつきたかった。

Educational Codeforces Round 163 (Rated for Div. 2)

　Eまで五完。

コンテストへのリンク

コンテスト後のツイート

Educational Codeforces Round 163 (Rated for Div. 2) Eまで。
A AAとBBを繰り返し。
B 今までの最大値を管理。
C DPというかDFSした。
D 幅hでh個連続で一致していれば、答えをhにできる。
E たとえば頂点5k=5なら 4 5 1 2 3とすればクリークにできる。この繰り返し。

— titia (@titia_til) March 15, 2024

F. Rare Coins

　解説AC。

　自分になじみのない解法が必要かと思って解説を見たのだが、普通の方法で解けた。

　ちゃんと問題を整理し、1/2の確率で自分のお金が増える、相手のお金が増える、というのを元のお金を調整して、「1/2の確率で差を減らす」と解釈するとシンプルな二項係数の和になる。

Codeforces Round 940 (Div. 2) and CodeCraft-23

　Dまで四完。ARCの後だったこともあり、前半は休み休みやっていた。

コンテストへのリンク

コンテスト後のツイート

D A[i]の最上位bitがbだとすると、l～i+1の累積xorでbが立っている/立っていない個数、i+1～rの累積xorでbが立っている/立っていない個数を調べて、l～rの累積xorではbが立っていないような個数を掛け算して求める。方針が立ってから、添え字とかで非常に苦労した。

— titia (@titia_til) April 21, 2024

E. Carousel of Combinations

　解説AC。

　Combi(n, k)*(k-1)! mod k の和を求める問題。実験コードを書いてこれを計算してみると、k=4と素数のとき以外は0になること、かつ、規則的に値が変化することが分かる。ｋを固定したとき、最初に値が正になるのはn=kのときで、k-1。そこからkごとに-1し、0になったらまたk-1に戻る。（これはkが素数のとき。k=4は2と0を交互に取る）

　これが分かった後、埋め込みか？　などと考えてしまい解説を見てしまったが、累積和を二回やるのが正しかった。規則的に値が変化するのだから、累積和を考えるのは自然。

　大体解けたけどTLEが微妙ってとき、変な手法を考えてしまうのは悪い癖。まともに計算量を減らす手法を考えるようにしないといけない。

AtCoder Beginner Contest 350（Promotion of AtCoderJobs）

　G解けず。Fで苦戦したため順位は悪い。

コンテストへのリンク

コンテスト後のツイート

AtCoder Beginner Contest 350（Promotion of AtCoderJobs）Fまで
A ABC000はない！
C Aの逆関数を用意して頑張る
D Union-findで、各連結成分に含まれるノード数xに対してx*(x-1)/2の総和からMを引いた。
E 期待値DP。
F 構文解析。再帰でreturnして文字をつなげていくとTLE。dfsっぽく直してAC。

— titia (@titia_til) April 20, 2024

G - Mediator

　解説AC。

　マージテクで解いた。コンテスト終盤にマージテクが使えるんじゃないか？　というアイディアは思いついたけど、具体的な解法には思い至れなかった。

yukicoder contest 428

　Dまでの四完。Eが解けそうで解けず、FはTLEに苦しむ。

コンテストへのリンク

No.2732 Similar Permutations

　4で割った余りで分類し、同じものが二つあれば1,2を入れ替えて置けばOK。

　ただし、Nが5以上ならこれでOKだが、Nが小さいときはこれだと答えが探せない場合があるため全探索。

　コンテスト中、こういう解法を考えたがWAが出たので、何か考察ミスがあるのだろうと別の解法を探してしまった。

　が、コンテスト後、改めて考えて見ると正しそうな気がし、コードを見直したら実装ミスに気付いた。（Nが小さいとき全探索する部分でミスがあった）

　これで提出したがWA。

　Xで割った余りが3や4の場合は、1,2を置くのではダメですね。2,3を置くようにしてAC。

　解説を見たら、2で割った余り（つまり偶奇）が同じものが二つあれば、上と同じような議論ができるらしくびっくりした。

No.2733 Just K-times TSP

　各頂点を何回通ったかと、最後に通った頂点を持ってDPすれば良い。PyPyだと制限時間が厳しく、コンテスト後に定数倍高速化を頑張ってなんとか通した。

　しかし、writer解がPyPyで、シンプルかつ高速に書けていた。こういう風に書けば良かったのか……。

　同じような風に書こうとして上手くできず、itertools.productを使ったのだが。

No.2734 Addition and Multiplication in yukicoder (Hard)

　自力AC。

　ちょっと実験してみると、最終的にできる数字はA[i]たちを適切に並び替えたものになると分かった。

　なら、A[i]を文字列とみてソートし、その順に置いて行けば良いのかと思ったがこれだとWA。

　よく考えると、"2"と"21"なら"21"の方が先に置いた方がお得。

　じゃあ、"2"は"22222222222222222"として"21"は”212121212121212121"のように元の数字を繰り返したものとして判定すれば良さそう。こうみなしてソートした後、並べていったら（TLE、MLEにちょっと苦しんだけど）ACできました。

AtCoder Beginner Contest 349

　Eまで五完。Eまでが速かったのでギリギリ黄色に復帰できました。

コンテストへのリンク

コンテスト後のツイート

AtCoder Beginner Contest 349 Eまで五完。F高速化すればいける？　と思ってWAを量産。
A -sum(A)
B Counterで頑張る
C 部分列を判定
D セグ木のイメージでやったけど貪欲でいいよね。
E 再帰で実装
F 約数の個数^2のDPにはなった。約数じゃなくて素数でいけそうと終了間際に気付いた。

— titia (@titia_til) April 13, 2024

F - Subsequence LCM

　素数の個数でいけるというのを手掛かりにAC。

　ゼータ変換を使う方法は思いつかなくても、DPで素数の個数^2でやる方法は難しくなかった。これはコンテスト中に落ち着いて考え直していたら通せていたはず……。

　

Educational Codeforces Round 164 (Rated for Div. 2)

　Dまで四完。

コンテストへのリンク

コンテスト後のツイート

Educational Codeforces Round 164 (Rated for Div. 2)
A m個均等に分けて一番大きいのを除く
B A[0]ではない数のindexの間にある個数
C できるだけ差を小さくする
D 難読。理解できればDP[i]でi個の場合は何通りか持ってDP
E 加算される箇所が√max(A)になるはずと思って実装したがWAでした。

— titia (@titia_til) April 12, 2024

E. Chain Reaction

　解説ツイートを見たところ、√max(A)回加算するというところは合っているみたい。

　→落ち着いて書き直したら答えがあった。

　ただし、PyPyだと制限時間が厳しく、PyPy2で2999msでACした。ルートだけでなくlogもかかっているからねぇ。二分探索使わない方法はあるのだろうか……と書いていたら、使わなずにできそうな気がしてきた。

　a/xの繰り上げが変化する場所をメモしていけばいい（後で累積和を取る）ので、前半はxを一個ずつ増やし、後半はa/xの値を一個ずつ減らしていけば良さそうです。