Educational Codeforces Round 186 (Rated for Div. 2)

　Eまで。終了後F1は通った、と思ったらシステムテストで落ちた。

コンテストへのリンク

コンテスト後のツイート

D maxの最後のindexの位置がどこ以下が決まる。
E 貪欲。小さい箱から順に、その箱を使ったとき効率のよい（z-yが大きい）ものを詰める。
F1 必要なpower pに対して、cを使ったら(p-c)*2に更新（それが何個かは持つ）というDPで通った。TLEのつもりで書いたけど、よく考えたら計算量落ちてそうかも。

— titia (@titia_til) December 29, 2025

F2. Christmas Reindeer (hard version)

　自力AC。見直したら難しくなかった。

　各桁について、何個使うのがギリギリなのかが分かるので、ギリギリのときと、それ以上が確定したときに分けてDPしていく。ギリギリのときは何個使えば良いか？　が分かるので、それより大きい個数を使うときは確定。同じ個数を使うときはギリギリ。二項係数で計算する。

　これも桁DPの一種といって良いかな。

　コンテスト中、30分残っていたら解けて良かった気もするけど、問題把握に結構時間かかってしまったなぁ。

yukicoder contest 286

　Cまで。

コンテストへのリンク

No.1425 Yet Another Cyclic Shifts Sorting

　自力AC。

　二種類あれば隣接要素SWAPができそうなので、答えは高々2。0回の判定は簡単なので、1回でできるかどうかを調べれば良い。

　一回でできるかどうかは、ソートした配列と比較し、最大値が一致していれば消していく。

　残った配列について、ソートしたものを巡回したものになっていれば良いので、ローリングハッシュを使って判定した。

　が、解説を見たらもっと簡単にできたらしい。なるほど。

　ところで、なぜタグが「動的計画法」なのだろう？　解けたと思った後タグを見たらそう書いてあって、何か間違っているのでは？　と疑心暗鬼になりながら実装した。

（タグに頼るのはいけないかもしれないけど、yukicoderのタグはいつも出したまま問題を考えています）

Good Bye 2025

　Eまで。

コンテストへのリンク

コンテスト後のツイート

D maxと小さいものを対戦させていく。残りがm*2になったら順番にやる。しばらく部分和問題とか考えて迷走。
E 同じ和の二つに分けると、短い方に答えがある。Flatten操作でmaximalにしか操作しないことを見逃していたせいでずっと解けなかった。

— titia (@titia_til) December 27, 2025

F. Conquer or of Forest

　コンテスト中に考えていた方針でAC。

　まず、白いnodeと親nodeを切る。

　そして、それらを一列に並べれば条件を満たす。（どのnodeからどのnodeへ繋いでもOK）

　結構人工的な条件なので、そこから何かを考えようとするのではなく、それっぽい必要条件を探すのが大事だった。

　一列に並べた結果、問題文の条件を満たす証明は分からないけど、それっぽくはなっている。

　コンテスト終盤にこの条件では？　と思ったが、数え上げが間に合わなかった。

・ROOT以外の連結成分について、どの頂点を親と結ぶか

・葉以外の連結成分について、どの頂点を親にするか

・ROOTと葉以外の連結成分について並び替え

　を掛け合わせればOK。

　三番目がよく分からず時間切れ。

　（連結成分数）！みたいなのがいるとは思ったのだが、（連結成分数-2）!だったとは。落ち着けばできたと思うけれど、この条件自体が正しいという確証もないこともあり落ち着けなかった。

ユニークビジョンプログラミングコンテスト2025 クリスマス（AtCoder Beginner Contest 437）

　Fまで六完だがEに手こずった。

コンテストへのリンク

コンテスト後のツイート

E 同じ数列になるindexをUnion-findでまとめる→DFS。バグりやすい（ランダムテストを書いた）し実装大変だったので、良い解法ではなさそう。楽な解法が分からず。
F 範囲maxを取れるセグ木にx+y,x-y,-x+y,-x-yを載せる。

— titia (@titia_til) December 20, 2025

G - Colorful Christmas Tree

　解説放送を見てAC。

　コンテスト中、フローは少し考えたのだが、使い方が分からなかった。

　次数を見れば最終的に何の色になるか分かるとは思ったが、その間の色を全部使うと気付けなかったのが敗因か。それに気付ければ自力でフローに思い至れた可能性はある。

yukicoder contest 490

　Gのみ解いて撤退。

コンテストへのリンク

No.3391 Line up Dominoes

　一応自力AC。

　DPで解く。DPで遷移したときの要素は区間和になることが分かるので、毎回累積和を取って流し込んだ。

　PyPyだとMLEになってしまったので、RUSTに直してもらいAC（コンテスト中だとできないが……）。

　解説を読むとPyPyでも普通にACできるようなのだが、よく分かっていない。

No.3392 Count 23578 Sequence

　自力AC。

　階差数列を考えると、回文の個数を数える問題に帰着できるので、Manacherを使って解ける。

　しばらく気付けなかったが、階差数列を考えると気付けて良かった。

AtCoder Beginner Contest 436

　Eまで。Fが解けずダメでした。

コンテストへのリンク

コンテスト後のツイート

AtCoder Beginner Contest 436 Fが解けずひどい順位に。
C setで管理。
D 01BFS。たくさん行き先がある場合を慎重にケア。
E 連結成分に分け、その中で入れ替える。

— titia (@titia_til) December 13, 2025

F - Starry Landscape Photo

　使う数字の最大値を考えると、それ以下の数字は全て使い、それより大きい数字は消えている。

　なので、使う数字の最大値が大きい順に考えて、一つ一つ消していけばOK。

　コンテスト中は、左端を固定したり、DPを考えたり、使う数字の最小値を考えたりしていた。

　使う数字の最小値を固定する方針にしばらく時間を使った後、最大値を固定する方針も考えたはずなんだけど、なぜか上手くいかない気がしてしまった。

　今見ると、難しく思えないのだが……。なんで解けなかったのか分からない。

G - Linear Inequation

　解説放送を見てAC。

　形式的ベキ級数を使うと聞き、立式まではできたつもりだったのだが、1+x^a+x^(2a)+...をM次の項までで打ち切るなどと考えてしまったのがダメ。

　1+x^a+x^(2a)+...と無限に続くもの同士の積と考えるべき。

　そして、さらに重要なのは、「そのM次以下の係数の和」を、Aに1を付け加えることで、M次の係数と解釈できるようにするところ。全く思いつかなかったが、形式的ベキ級数に慣れている人にとっては典型なのでしょう。

　あとは、Bostan–Mori法を使って処理すればOK。久しぶりにこのライブラリを使う機会と出会った。

　形式的べき級数にもっと慣れないとダメですね。

Codeforces Round 1070 (Div. 2)

　Dまで。

コンテストへのリンク

コンテスト後のツイート

D A_iが小さい順に見てDP。行き先について見るときは、次の数字が何なら遷移できるか、と、行き先の数字の集合のリストをそれぞれソートし、尺取りで更新。

— titia (@titia_til) December 11, 2025

F. Omega Numbers

　こたつがめさんの放送を見てAC。

　滅茶苦茶苦労したが、WAを量産した一番の原因が、200000を20000と書き違えていたことだというね！　これで二時間以上使っているのひどすぎる。

　解法自体も難しかったが、必ず身に着けておくべきなのは、

「数列Aにおいて、約数がxになるような(A_i,A_j)のペアの個数」がカウントできるということ。それができたとしても難しいのだが、後は自力で思いつくべきなのだろう。