AtCoder Beginner Contest 453

　Eまで五完。

　順位表を見てGまで行ったが、Gは未履修で、思い付くのは不可能だったように思う。実装も非常に大変だった。

コンテストへのリンク

コンテスト後のツイート

E a人とN-a人に分けるとする。どちらにも入れない人がいる場合は双対セグメント木を使って除く。a人とN-a人が可能な人数を累積和で前計算しておくと、鶴亀算でどちらにでも入れていい人数が分かる。二項係数で計算。

— titia (@titia_til) April 11, 2026

G - Copy Query

　解説AC。

　永続セグメント木を初めて勉強し実装した。

　遅延セグメント木などを理解していれば理解することは難しくないが、実装はかなり大変だった。

　セグ木の値、各nodeの左側の子、右側の子、親、その区間の左端と右端、各Versionの根の値などを更新があるごとに追加していく。ちょっとTrie木のような実装を行った。

　

AtCoder Beginner Contest 452

　Fまで解けたが遅かった。

コンテストへのリンク

コンテスト後のツイート

AtCoder Beginner Contest 452 Fまで。
C len(S)ごとにSを列挙し、(Ai,Bi)の候補を挙げておく。
D 久しぶり。https://t.co/NeYvsecE9N
E Bのindexを固定とすると、0 1 2 0 1 2……みたいな係数をA[i]にかけて和を取るものになる。累積和で頑張る。計算量に調和級数のlogがついた。

— titia (@titia_til) April 4, 2026

G - 221 Substring

　自力AC。

　コンテスト中の方針であっていた。数字の個数＝数字の大きさならそのまま、個数が数字の大きさより大きければ、k 0 kと置き換えて並べる。

　その上で、Suffix array、各indexから0までの個数を調べていく。そのままだと重複が出るが、LCP配列を使えば重複は除ける。

　コンテスト中に失敗していたのは、自分のライブラリだと文字列Sの後ろに、最も小さい文字（今回は数字）を置いておかねばいけないところだった。あとは、SA[i]でi番目に小さいindexを表すのだが、その逆関数なのかどちらか分からなくなって混乱したところ。ただ、これは久しぶりにSuffix arrayを使ったのだからしょうがない気もする。

　後はすんなりできた。

　Fより時間かからなかったと思うので、F捨ててG行けば通せてたかなぁ。

Codeforces Round 1091 (Div. 2) and CodeCraft 26

　Cまで三完。過去最悪に近い成績。しかし、DもEも難しい気がしたが……。

コンテストへのリンク

コンテスト後のツイート

D ランレングス圧縮した後、左右の端から削っていくとか考えたが上手くいかず。
E 大きい数字を後ろから入れる貪欲を考えたが上手くいかず。正当性もまずそうだし、計算量も三乗になりそう。

— titia (@titia_til) April 7, 2026

D. Flip the Bit (Hard Version)

　解説AC。

　隣接する値が異なる場合は1、同じ場合は0とする配列を持っておく。

「ある区間の反転は、この配列の二項を反転させるもの」と捉えるのは（この前のARCのAで出題されたので）覚えていた。

　さらに、この問題のようにindex iを含む区間の反転は、

★「iより左側とiより右側で反転させる」と捉えることができる。

　ここで、P[i]で配列を区切っていくつかの区間を持つと、

★「二つの別の区間から反転する」という操作なら全て行えることが分かる。

★ところで、最終的な値を0にしたいなら、Aの左右に0が広がっていると考えても同じ。

　そう捉えて区間を分割し、隣接項が違うものの個数を数えたものをSとすると、

・Sの異なる項から1ずつ引く

・Sの一つの項から1を引く

　の操作を行ってSの全ての要素を0にするとき、最低何回必要か？　という問題になり、これは、最大値で場合分けしたりheapqを使ってシミュレーションしたりすれば解ける。

　難しかった。

　★で書いた三つとも自力では思いつけなかった。隣接xorを取る部分は定石だけど、それ以降の処理にも難しい部分があると、なかなか正解まではたどり着けない。

Codeforces Round 1090 (Div. 4)

　全完したが順位はあまり良くなかった。そんなに遅かった気もしないのに厳しい。

コンテストへのリンク

コンテスト後のツイート

F x=0のときは、yが奇数なら二分木みたいにして作れる。そうでないときは、y>=xならYES。最初に直線で並べたあと、二つずつ枝分かれさせる。
G B_iの値が小さい方から見る。Counterと隣接する値で決まる。

— titia (@titia_til) April 4, 2026

yukicoder contest 496

　Fを考えたが解けなかった。

コンテストへのリンク

No.3492 区間冪乗加算一点取得

　解説AC。

　まず、D<=100に気付かなかったのが敗因。だが、解説を見ても、なかなか理解できなかったのは良くない。内容的には、D<=100に気付いたなら解けなくてはいけない問題だった。

　ただ、D<=100でクエリ問題だからやることが決まってくるから解法に気付きやすいというだけで、(i+C)^Dののd次数目が、CやDが変わっても似た形で表せるというのは意外だった。立式をすれば分かることとはいえ、こういう観点で見たことがなかったので面白かった。

No.3493 等比数列の和の素因数

　解説AC。

　いまだにフェルマーの小定理やオイラーの定理があやふやなのが敗因。

　等比数列の和の公式を考えた後、オイラーの定理を使う方向で考察を進めなくてはいけなかった。ちゃんと立式して、落ち着いて考えるべき。

　

Nebius Round 2 (Codeforces Round 1088, Div. 1 + Div. 2)

　C1までとDの四完。

コンテストへのリンク

コンテスト後のツイート

C1 -1には使っていない数を順番に入れて良い。A[i]がBのどの範囲にあれば良いか分かるのでチェック。
D bitごとに考えて良い。後ろから見るとk個以上入っているbitが確定していく。
E 木DPするしかなさそう。そこまでのスコアと、gcdとして必要そうな値を持ったがTLE on pretest30でした。

— titia (@titia_til) March 28, 2026

E. Minimum Path Cover

　解法ツイートを見てAC。

　gcdたちのうち必要な値を何個か持たなくてはいけないと思ったが、それらをlcmで代用することが可能だった。

　言われれば確かに……。

　木DPのとき持つ値は一個で良いはず！　という気持ちになれば思いつけたはず。TLEになるだろう提出の結果を待っていたのはダメでどうにか一個の値にできないか？　と粘るべきだった。

　

yukicoder contest 495

　BとEの二完。あとはFを考えていたが分からず。Eは上手い方法が分からず、a,b全探索でcの範囲を定め、その後、ミラー・ラビン素数判定法を使って判定、で通ってしまった。良かったのかなぁ。

コンテストへのリンク

No.3483 A Forbidden Fruit

　自力AC。

　自力ではあるのだけど、たとえば、「M個の中からr個選んだとき、外れ（の一個）が含まれない確率」が1-r/Mであることも計算しないと気付かなかった。

　確率について直感が働いてないなぁ。

No.3484 Just a Maze Game

　大体自力ACだが、Wと書くべきところをMと書いたり、W=5, 7だけ書いてW=3の場合を書き忘れたりと、ミスが多かった。

No.3486 Draw a Rainbow

　解説AC。

　最初解説を見て、ゼータ変換やメビウス変換を理解できていないから解けなかったのかと思ったが、実際はDPの方針が立てられなかっただけでした。反省。

　ゼータ変換やメビウス変換は、（今回のように集合に関するものの場合）bitごとの累積和やimos法なだけなので、全く恐れる必要はない。フーリエ変換と違って集合や約数の畳み込みは難しくない。（フーリエ変換はいまだに難しい……）

　なお、今回の自分の解答ではBitwise OR Convolution自体は使わず、DPとして累積和を取ったとき（ゼータ変換したときの値）をそのまま持って計算し、最後に一回だけメビウス変換を行った。

　集合に関するこのあたりの変換が分からなくなったときは、この問題のりんごさんの解説放送を見るのが手っ取り早いと思う。