ABC420 （2025/08/24）
〇A問題
まーす.iconprint((X + Y - 1) % 12 + 1)．
Kaplam.icon同上
CarpDay.icon同じ．当初(X + Y) % 12としていて，入力例3で間違い教えてもらって助かった．
N_N.icon 同じです．
yuichang.icon 難しすぎるのでfor文まわす、、
〇B問題
まーす.icon問題文が長いけど，問題文に書いてある通りに従うだけ．$ S_{i} \ (i = 1, \dots, N)の$ j \ (j = 1, \dots, M)文字目について多数決（厳密には少数決？）を行ってる感じかな．
CarpDay.icon少数決と聞いて，ちょっとワクワクするの，私だけ？
まーす.icon テストで一人だけ満点みたいな優越感？がありますよね
CarpDay.iconそれもそうなんだけど，某漫画（ライアーゲーム）で「少数決」というゲームがあったのです(^ ^;
Kaplam.icon1の数とか0の数を見て条件分岐する、頭回らなかった_(:3」∠)_
CarpDay.icon行と列間違えて読んで実装して結果が合わず悩む．zipして対応．
N_N.icon 愚直に解いたので時間が掛かった．
yuichang.icon 誤読して横で見てた
〇C問題
まーす.icon最初，$ i番目のクエリについて，$ X_{i}番目までの和$ \sum_{k = 1} ^ {X_{i}} \min(A_{k},\ B_{k})を 出力するものだと勘違いして，遅延セグ木を考えていたけれど，$ \sum_{k = 1} ^ {{\color{red} N}} \min(A_{k},\ B_{k})を求めるということに気が付くのに時間がかかった．
Kaplam.icon1回の変更でクエリの答えに影響を与えるのは1か所だけなのでそこについて見る
CarpDay.iconKaplam.iconさんのおっしゃる通り．
N_N.icon たぶん同じだけど，最初に $ \Sigma^N_{k=1} \rm{min}(A_k, B_k) を求めておき，$ A_{X_1} または $ B_{X_1} を更新するたびに，必要に応じて再計算をしていく．
yuichang.icon 答え持っておく
〇D問題
Kaplam.iconボタンを押したかどうかをもってBFSするだけ、だったのに1か所のバグに気付かず、更に1から再実装しても同じバグを仕込み、結果25分で5完出来たはずが80分、得意な早解き回だったはずなのにかなしい_(:3」∠)_
まーす.icon ICPC の練習でいっぱいやったね！「スイッチを押した回数の偶奇」という情報も保持したBFS．
CarpDay.icon伏字感謝．共通祖先（LCA）使うんかな？BFSの中にBFS書いたりで迷走中．
まーす.icon LCA という言葉を初めて聞きました......（いや，見たことはあるが，昔のFとかG問題でしか💦）
CarpDay.iconそうか，やっぱりLCA使わないんやな．．
まーす.icon定義をちゃんと見れば，LCA がなにを指しているか分かるかもしれませんが......．私はもっと基礎的な考え方で解きました．
N_N.icon Lowest Common Ancestor ?
まーす.icon こんなん使ってないな.......
CarpDay.iconはい．Lowerest Common Ancestorです．BFSの探索木を作って，?に出会ったら，過去に出会ったxに戻るまでの距離を求めるためにLCAが必要になるのかな？と考えていました．
CarpDay.icon諦めて皆さんの伏字をチラ見して，やっと理解しました．ノードの状態が2種類ある最短経路問題と同じ考えだったか．．．ギラティナの反転世界を考える，って昔勉強会で偉そうに説明していたのに，気付かずに残念．
N_N.icon 基本的に，幅優先探索 でゴールを探す．問題は開閉する扉の扱い．これは，全部の扉が同時に開閉するので，スイッチを偶数回通ったか奇数回通ったかだけを覚えておけば十分．各場所について，その場所をスイッチ偶数回通過で訪問したか，スイッチ奇数回で訪問したかを，2ビットで覚えるようにする．
yuichang.iconフラグ挿入位置間違えてて終わった
〇E問題
Kaplam.iconunionfindで各連結成分が黒を持っているかを覚える、unionの時に個数足したりしてうんにゃら[
まーす.iconUnionFind を用いる．このとき，「各親頂点 i に対して， i と同じ連結成分である頂点の中で，黒色の頂点の個数」という情報を保持する
CarpDay.icon Kaplam.iconさんがD問題より先に解いているのに気付いてから取り掛かる．もっと早く気付いていたら良かった．．UnionFind 使って，リーダーにそのグループ内の黒数を．管理させる
まーす.icon 同じく！
Kaplam.iconDのWAの原因がわからなくて軽くパニくったので頭冷やすために飛ばしてました_(:3」∠)_
N_N.icon D問題が解けそうだったので，皆さん動向に惑わされず先にDを解く．E問題は時間不足だったけど，Union Findを使って途中まで書く．なるほど，黒色の頂点の個数を覚えるだけでいいのね．確かに．勉強になりました．
yuichang.icon 終了4分前に閃いたけど多分ギリギリ間に合わず、レート59溶かして動けません
〇F問題
Kaplam.iconセグ木4本立ててどうこうしたら行けそうな気がしなくもなかったけど解説見たら知らない名前の木が立ってるので多分無理
CarpDay.icon Kaplam.iconさんが無理なら後回し，とコンテスト翌日に問題確認．しかも橙レート．こりゃ無理だ，と解説を見る．Cartesian Tree？大昔に一度聞いたことがあるけど．．アルゴリズム自体はそんなに複雑じゃなさそうだから理解したらいいことあるかも？（他人任せ）
〇G問題
Kaplam.icon式変形したらなんとかなりそうだな～ってFよりはこっち見てたけど上手く行かなかった
まーす.iconなにこれ，面白そう．$ \sqrt{\cdot}は単調増加で，非有界なのでそこをどうするか......
まーす.icon$ k := \sqrt{n ^ 2 + n + X} \ (k = 0, 1, 2, \dots) とおくと，$ \left(n + \frac{1}{2} \right) ^ {2} - k ^ {2} = - X + \frac{1}{4} となるので，双曲線を書いて実験かな......?
まーす.icon というかあれか．$ \left(2 n + 1 - 2 k\right) \left(2 n + 1 + 2 k \right) = \left(2 n + 1 \right) ^ {2} - 4 k ^ {2} = - 4 X + 1 で，最左辺が積の形作れたね．けど $ Xが負の場合が結構めんどくさそう．
まーす.icon AC でました．結構さっくり解ける問題です．
CarpDay.iconなにこれ，面白そう！式変形したら．．．でもそこからどうする？？
CarpDay.icon分からないので解説見る．そんな因数分解思いつくか！と憤っていたら，kyopro_friendsさんのユーザ解説読んですっきり．さすが．って，まーす.iconさんも上でほぼ思いついているやん．さすが．