AtCoder Beginner Contest 433

　Fまで六完。

コンテストへのリンク

コンテスト後のツイート

E 大きい数字から埋める。後で邪魔しなそうな、既に使ってある場所から埋めて行く。自分の実装は計算量怪しい。
F 左にある1の個数と右にある2の個数だけで答えは決まるが、二項係数の和になりそう。→実験したら二項係数一個になった！
G suffix arrayを使って再帰で解けそうなんだけどまとめられず。

— titia (@titia_til) November 22, 2025

G - Substring Game

　コンテスト中は、Suffix arrayやLCP配列を使う、というところは合っていたけど、木になるということは理解していなかった。再帰で解けると思っているんだから、木構造になると分かってはいたはずではあるけれど……。

　解説放送を見てSuffix treeを使ってAC。

　Suffix treeは初めて書いたけれど、Suffix array・LCP配列・Trie木を理解していれば難しいところはなく、時間をかければ自力で解けたはず、とは思う。

　ただ、解けたとしてもEやFより時間かかっただろうから仕方ないか。

yukicoder contest 489

　Cまで三完。

コンテストへのリンク

No.3375 Binary Grid

　解説を見てもよく分からず、テストケースを見てデバッグしてAC。苦労した。

　再帰構造は明らかなので、それを使って計算するしかない。

　しかし、帰り道でどう再帰するかが難しい。

　(x,y) から(R,C)へ移動するとき（x>=R,y>=Cとする）、R行の中で、yからCの間に通れないマスがあるか？　を考える。

　なければ、max(x-R,y-C)が答え。

　R行の中で、最も大きい通れないマスの列番号kとしたとき、（R,k）から下に行った先で初めて進めるマス、そこを必ず通らなくてはいけない。

　それを使えば再帰できる。

Codeforces Round 1065 (Div. 3)

　pretestは全完したが、HをHackされてしまった。

コンテストへのリンク

コンテスト後のツイート

H (score,それまでの最大値)をもって大きいnから見て行った。scoreが小さいのに最大値も小さいものは削除。さらに、scoreがMAX-10より小さいものを消すという枝狩りをしたら通った。

— titia (@titia_til) November 20, 2025

H. Shiori Miyagi and Maximum Array Score

　枝狩りの値を20→15にしたらHack caseは通った。

　正しい解法は、セグ木（or BIT）を使ってDPの高速化らしい。理解できていないけれど、そう言われると確かにできそうな気はしてきた。

オムロンプログラミングコンテスト2025 #2（AtCoder Beginner Contest 432）

　ABCEFの五完。レートを上げるためにはもう一問必要だった。

コンテストへのリンク

コンテスト後のツイート

D - Suddenly, A Tempest

　自力AC。

　長方形のxmin,xmax,ymin,ymaxをもって分割していき、連結性はUnion-findで求めた。公式解説を見たところ大体同じ方針だった。

　実際にやろうと思えば難しくない方針だけど、実装はそれなりに大変だし、飛ばしたのは正解だと思う。

G - Sum of Binom(A, B)

　FFTを使うと聞いても分からず、解説放送を見てAC。頻度を見てFFTする手法は既知だったのだが……。

・FFTを使いそうだと気付く

・FFTが使えるように式変形する

　のどちらもできていなかった。

　が、こういう二乗の形を畳み込みしてFFTに持っていく問題は結構あるし、式変形も言われてみれば納得できるもので、分かりづらくはない。

　FFTに慣れていないのが出てしまった、という感じ。

　

Codeforces Round 1063 (Div. 2)

　D2まで。

コンテストへのリンク

コンテスト後のツイート

D1 区間のうち意味のあるものはn個程度なので、まずそれを絞る。0の位置を二回二分探索で絞る。その範囲と重なる区間だけ投げる。
D2 意味のある区間がn個なので、それを左右に分け、mex（合併）を比較すれば二分探索できる。
E 適当にやれば通りそうに見えたが思いつけなかった……。

— titia (@titia_til) November 10, 2025

E. Plegma

　何をやっても通りそうな問題なのに通せなかった。

　物理好きさんの方針でAC。

　思いつくかどうかの問題なのであまり反省しようがない。

　secondへ持っていく情報を最大限生かすにはどうしたらいいだろうか？　みたいなことを考えるべきだったか。

AtCoder Beginner Contest 430

　Fまで。

コンテストへのリンク

コンテスト後のツイート

AtCoder Beginner Contest 430 Fまで。
A 論理の問題だけど、読解が難しい
B 全列挙
C 尺取り。
D tatyamさんのSortedSetで。
E Rolling Hash。mod一個で投げてWAを出した。
F グラフにして子孫の数を数えると、左右から何番目以降になるかが分かる。
G x<=60を使いそうだが、何も分からない。

— titia (@titia_til) November 1, 2025

G - Range Set Modifying Query

　解説放送を見てAC。

　Segment Tree Beatsを初めて実装した。非常に苦労した。

　そもそも、何を持つ必要があるか理解するのが難しい。

SEG=[0]*(2*seg_el) # max(bit_count)が最大なものの素の値

SEG2=[ALL]*(2*seg_el)# SEG[i*2]とSEG[i*2+1]での共通bit

SEG3=[0]*(2*seg_el) # bit_count()の最大値

SEG4=[0]*(2*seg_el) # 最大値を取る要素数

LAZY0=[0]*(2*seg_el) # 遅延伝搬すべき要素。追加の場合。SEG2が1のbitのみ、下へ伝播する。

LAZY1=[0]*(2*seg_el) # 遅延伝搬すべき要素。削除の場合。SEG2が1のbitのみ、下へ伝播する。

　と定義してやったが、LAZYが二つ必要なことに気付かず、ずっと悩んでしまった。

　ちゃんと抽象化していたとしても、ここで悩んでしまったと思う。

　そして、最後まで引っ掛かったのは、[L,R)の範囲外でも、updates内で下のノードへ行かなくてはいけないときも、遅延伝搬を行わなくてはいけないところでした。

　ここはデータ構造を理解していれば（あるいは、ライブラリを整備していれば）引っ掛からなかったはずのところ。こっちのミスは減らせますね。

Pinely Round 5 (Div. 1 + Div. 2)

　Dまで。

コンテストへのリンク

コンテスト後のツイート

E 0/1が続いた後、「0が(k-1)/2個、1が(k-1)/2個のパターン」がずっと続く。ただし、切り替わるのが最後k-1個以内なら、その後は別の数字が(k-1)/2個を超えない範囲で何でもOK。
だと思ったが、数え上げが難しくて、答えが合わないし、今のままだと多分計算量もダメ。

— titia (@titia_til) October 30, 2025

E. Left is Always Right

　非常に苦労してAC。

　コンテスト中の考察は正しかった。あとはそれを数え上げるだけだった。

　ただ、自分は、index i-1まで0が続き、index iで初めて1が登場するという、このindex iで場合分けしてた仕上げようとしていた。

　すると、終盤が繰り返しのパターンではないとき、それぞれについて、計算量が[i,n)の長さ程度かかってしまう。その中にある0,1,？の個数を見て、?が何個以下0になる……という二項係数の和になってしまうため。

　そうではなく、計算量を良くするためには、繰り返しパターンでないときは一気に数え上げられる、という発想の転換が必要だった。

　index n-kまで0が続いたのなら、残りは、0や1がk/2個以下ならどんな並びでも良い。なので、場合分けをしないことで一気に数え上げることができる。

　こうすると計算量を減らせる。

　このことに長いこと気付けなかった。公式解説を見ても、二項係数の和で表せる、としか書いていないのが辛い……。二乗ではあるけれど二項係数の和では表せたので、公式でどうにかなるのでは？　などと考えてしまった。