AtCoder Regular Contest 217

　AB二完。Bはまあまあ速かった。実験したら解ける問題はある程度速く解ける（こともある）らしい。

コンテストへのリンク

コンテスト後のツイート

AtCoder Regular Contest 217 AB二完。Bはまあまあ速かったがCもDも解けず。
A sampleがヒント。0 1 3 2 4 5 7 6……。
B 実験。各iを動かせると+2^i。iの左により大きいものが置いてある確率。
D Mが大きい方から考えると、ある品物を買うときの挙動が繰り返されるからメモ化できる気がしたが解けず。

— titia (@titia_til) April 5, 2026

C - Greedy Customers 2

　公式解説を読み、解説放送を見てAC。

・所持金のmultisetが同じなら、人がどういう順番で来ても買う商品のsetは変わらない

　というのが気付くべきポイント。これにも気付いていなかったので、コンテスト中のACは遠い。

　その後はDPなのだが……。

　品物がk個以上売れる確率を求めたいというのは良い。

　が、k回そういうDPを行うというのは意外だった。

　DP[i][j]でA[i]以上のお金をj人が持っている確率、とすれば、kを固定していれば遷移が回るというのは分かりやすい。が、kを固定しないと回らない（のか？　少なくとも解説ではそうなっている）というのが混乱しやすい気がした。

　なお、PyPyではTLEしたため、codonでACした。

キーサイト・テクノロジープログラミングコンテスト（AtCoder Beginner Contest 454）

　Eまで五完。

コンテストへのリンク

コンテスト後のツイート

E 市松模様に色分けすることでNoの条件は分かるが、構築に苦戦。(A,B)を含む二行を特別視することで構築できた。
F 区間+1/-1加算によりmod Mで全ての要素を0にする操作回数の最小化になった。この問題が解けない。

— titia (@titia_til) April 18, 2026

F - Make it Palindrome 2

　解説放送を見てAC。

　結局のところ、「区間加算がきたら差分を取って考える」ができていなかった。この典型にはいつもやられている気がする。

　今回は忘れていたわけではなくて、コンテスト中、差分を取って考えてみようとはしたのだが上手くいかないと思ってやめてしまっている。

　しかし、区間の話を二点の足し引きにできているという時点で前進しているのだから、捨てたりせずちゃんと思考を進めるべきだった。

　あまり意味のない言い換えに思えたとしても、やっておかなくてはいけない。

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。

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

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