ABC435 （2025/12/06）
まーす.icon 今日勝って，明日のモチベをあげる！！
まーす.icon 懸念点：キーボードの電池が切れる（やっぱりRated はやめた方がいいかな......）
〇A問題
まーす.icon $ \sum_{k = 1} ^ {N} k = \frac{N (N + 1)}{2}.
まーす.icon ついでに1line いただき～
CarpDay.icon 1日遅れでのバチャコン．まーす.iconさんと同じ．これ1lineじゃなくて2linesじゃね？？
まーす.icon 実はコンテスト後に1line も出しました～
CarpDay.iconなるほど，公式使わない方なら1-linerできましたね！ちょっと悔しい(^^)
〇B問題
まーす.icon 文章がちゃんと読めているかを確かめる問題．題意は，「$ l \leq rであって，$ \forall i ; l \leq i \leq rに対して，$ \sum_{k = l} ^ {r} A_{k}が$ A_{i}の倍数である$ \color{red}(l, r)の組の個数」を求めること． まーす.icon LaTeX の部分を含めると赤字（えせlink）での強調は出来ないっぽい．LaTeXの\colorコマンドでどうにかできるかな？
まーす.icon やったぜ！
CarpDay.icon $ \color{red}やったね！ あれ？フォント変わるね．
まーす.icon にせlinkを使ってやったね！とすると，フォントは変りません．下をコピペするとLaTeX じゃないので，いつものフォントになります． CarpDay.icon文章がちゃんと読めておらず，「すべての$ A_iが約数でない」と「どれかが約数でない」としてサンプル通らず．すぐに気付いてAC.
〇C問題
まーす.icon 初期値を$ c := A_{1}とする．ドミノ$ i ~ (i = 2, 3, \dots, N)が倒れる場合は，$ cを$ \max\{c, i + A_{i} \}に更新．倒れない場合は打ち切り．
CarpDay.icon まーす.iconさんと同じっぽい．「未満」の処理で少し手間取って無駄に-1があちこちに登場．
〇D問題
まーす.icon 考え方：頂点$ eは黒頂点（黒頂点ならなんでもよい）にたどり着けるかという（問題文そのままですね）視点が重要．
まーす.icon 実際にやった事：頂点$ e ~ (e = 1, 2, \dots, N)が何かしらの黒頂点に到達できるか否かを表すlist （True，Falseの要素から成る）を作成する．クエリタイプ２は自明なので，クエリタイプ１のみを説明する．まず，今回黒にする頂点$ vをTrue に変更．そして，その頂点から遡れる頂点（$ M個の$ X_{i}から$ Y_{i}への辺が与えられるが，これの逆向きの辺を張ったグラフを考えることによって可能）全てをTrue に変更する．新たに辺を追加したり，既にある辺を削除したりということはないので，枝刈りの発想自体は簡単（がんばるんば）．
まーす.icon WAの理由：クエリタイプ1のときに黒にする頂点$ vを変更していなかった．お酒のせいにしておこう．
CarpDay.icon 多分まーす.iconさんと同じ．逆向きに枝張って，クエリ1でvからDFSして到達した点を黒もする．無駄にUnionFindまで実装して，結局使わず．（お酒は入っていない）
〇E問題
まーす.icon この問題，個人的にめっちゃ難しく感じたのだが，結構解いている人が多くてびっくり．D まではすらすら解けたので，E 問題も出来るだろと思い込んでいたらあっけなく撃沈．
まーす.icon 解説見たが，方針は合ってたっぽい．まぁ，実装段階で躓いて，途中で何を書いているのかとか，場合分けはこれで十分なのかとかを考えるようになって，混乱していました．
CarpDay.icon リストに区間の区切り目を保存しておけば，偶数番目か奇数番目かで白／黒の開始始点が分かる．二分探索を使えば無駄な処理を防げる．要素をベタに削除しても，黒区間は広がるだけなので時間的に間に合う．という考えはできたものの実装うまくいかず．リストの代わりにSortedSetを使うことも考えたが，使い慣れておらず踏み切れず．この機に使い慣れるとしよう．
CarpDay.icon別解の座標圧縮＋遅延セグメント木を使う方法．その方がプログラムはシンプルになりそう（Pythonだと重そうだけど．．）
CarpDay.icon 別解で実装したらシンプルになったけど，2ケースTLEでした．．
〇F問題
CarpDay.icon （バチャコンということもあり）E問題の実装する気合が出ずにF問題も除く．猫の問題だから解こう！と思うも，方針が立たず．区間DPか？と思うもO(N^2)は無理だし．．
〇G問題