AtCoder Beginner Contest 419

　Dまで四完でレートを大きく下げる。

　ABC二回でレート100落しているのだが。

コンテストへのリンク

コンテスト後のツイート

AtCoder Beginner Contest 419 E分からず飛ばしたらFも解けず終わり。最近の中でもひどい成績。今日は調子悪くないと思ったんだが。
C 各座標は独立。平均値にまとめる。
D imos法でSになるかTになるかを見る。
E iとi+Lの関係に着目したが解けず。
F DPしようとしたが答えが合わない。

— titia (@titia_til) August 16, 2025

E - Subarray Sum Divisibility

　解説AC。

　コンテスト中は、

　B=[sum(A[i:i+L]) for i in range(N-L)]

　みたいな配列を作り、あるindexへのplusはBの区間にplusすること……と考えていた。こう考えると、連立方程式ができ、そこから、index iへ足す量が決まれば、i+x*Lに足す量も決まっていくことは分かる。が、そこからどうして良いか分からず混乱した。

　（iとi+x*Lの関係に着目するのは良いのだが）Bを作らずに考えた方が良かった。

　上で書いた関係は、A[i]とA[i+L]がmod Mで一致する、ということを意味している。そうすると、もう一つ、sum(A[i:i+L])の和が0になれば条件を満たすことが分かる。

　同等の条件は上の連立方程式から出すこともできる（後者の条件は、B[0]=0ならOKとなる）が、その解釈が分かりにくく混乱しやすい。

　Aのままの方が考えやすかったと思う。

F - All Included

　コンテスト中書いていた実装のバグを直し、ChatGPTにC++に直してもらってAC。

　添え字のミスでした。

　が、コンテスト中も添え字のミスだろうと思って懸命に探したのだが……。

　Aho-Corasick法との関係がよく分かっていないけど、復習した方が良いのかなぁ。

G - Count Simple Paths 2

　解説放送を見てAC。言われてみれば……という感じ。

　ただ、結構高速化を頑張らないとACできなかった。頂点数が22個（くらい）に抑えられるはずなので、C++に直したらTLE取れるはず……と思ったらPyPyより遅くなったりしてよく分からなかった。

　結局、頂点数を削減した後、座標圧縮してbitsetを使ってAC。