ABC426 （2025/10/04）
CarpDay.icon生成AIで別言語のコードに変換（例：C++→Python）も禁止されたよ！参照先：こちら 〇A問題
Kaplam.icon .index()で
まーす.icon ["Ocelot","Serval","Lynx"]というlistをつくり，$ X, Yの添え字の大小関係で判断．
CarpDay.iconベタにif文を書き続ける．案の定，スペルミスでWAになりそうになる．．
N_N.icon 写像を作る．Map<String, Integer> version = Map.of("Ocelot", 1, "Serval", 2, "Lynx", 3);
〇B問題
Kaplam.icon .count() == 1で
まーす.icon 制約的にあり得る場合は，(i) $ Sの1文字目のみが異なる場合，(ii) $ Sの$ n \ (n > 1)文字目のみが異なる場合に限られるので，$ Sの中に，文字$ S_{1}が何回出たか，$ S_{1}とは異なる文字$ S_{k}が何回出たかを数え挙げて，その両者の大小関係を比較する．
CarpDay.iconlist(set(s))して2文字を獲得して，最初の3文字で判定．
N_N.icon 各文字が出た回数を覚えて，一回しか出ていない文字を表示．
〇C問題
Kaplam.icon最初にSortedSetで書いたコードがなぜか大量にTLE、その後も色々試したけど全く収まらずに一旦Dへ、その後戻ってheapqで投げたら普通に通った、とっても謎、1回のクエリでアップデートした分全体の個数が減るのでそんな感じで
Kaplam.iconEもギリギリTLEしてたのでもしかしてとC見てみたらこっちも20xxmsとか21xxmsとかがいくつもあったからデータ構造がちょっと重くて落ちてたっぽい、ねえぇぇぇ...
まーす.icon 方法は，多分Kaplam.iconさんと同じ．(現在のバージョンX, バージョンXの台数)を格納した heapqを用いて実装．計算量が少し不安だったので，頭の中で証明をした（形式的には証明していないが，イメージは上と同じ）．
まーす.icon 上でKaplam.iconさんと同じと書いたが，少し違う．Kaplam.iconさんはクエリ$ q時点でのバージョンの list を考えているのだけれど，自分はそんなことは考えてない．考えやすさの面では，Kaplam.iconさんの方が分かりやすいかも．
CarpDay.icon全然分かりませんでした！！各バージョンの個数を保持して，バージョンアップしてなくなったバージョンを全て0にするために遅延セグ木を使うもTLE．．．バージョンアップした最大のバージョンを保持して，それ以外は各バージョンの個数を保持するセグ木で実装しなおして何とかAC．でもC問題でこんな方法使うわけない！どうやるんだ？？
まーす.icon どうやら，←これは伏字対応していないらしいです......listとか，tupleみたいなやつです．
CarpDay.iconなるほど．対応できるように修正できるか，検討してみます．
まーす.icon <(_ _)>
CarpDay.iconいろいろ試したけど，バッククオート（`）で囲まれた部分を伏字にするのは難しいみたい．すまん．
CarpDay.icon上の伏字が付される前に視界に入った情報がヒントになり，実装したら素直にAC．うーん．何でこんなこと気付かなかったんだろう．．．自分に残念．
まーす.icon オーダーでいうと，$ O((N + Q) \log N)で少し複雑だったので，仕方ないです．
CarpDay.icon解説見たら，配列だけで素直に解ける問題，ということを知ってショック．反省．
N_N.icon 私も全然わからず．WA×6をなくせたが，TLE×9を消せず．セグ木を使うのかな？C問題なのに？$ X_i を $ Y_i に更新するときに，$ Y_i - 1 以下のバージョンが何台アップデートされたか（何台減ったか）を覚えていくようにしたんだけど，それだけではTLEが取れなかった．緑がどんどん遠ざかる... orz
TLE×3まできたけど，まだ駄目．
一晩寝て，最初から素直に解きなおしたら（配列を使うだけ）すぐAC．解いてみたら確かにC問題の難易度ですね．勘に頼らずに，計算量を冷静に分析していれば良かったと反省．
〇D問題
Kaplam.iconある添え字についてみて、左右をその添え字の値と同じに統一することを考える、見ている値と異なる値は1回の操作で裏返して見ている添え字の隣につければいい、同じ値は2回ひっくり返さないといけない、でも見ている添え字と連結している同じ文字については触らなくていい、ってのを累積で情報持って添え字1個につきO(1)で
まーす.icon ずっと沼ってた．「右側と左側の両方向から攻めていくんだろうな」と思い，実行するも00001みたいなケースで詰まったりしてた．
CarpDay.icon何となくi文字目まで前から順に処理するときの回数と，i文字目まで後ろから順に処理する回数を計算しておいて，i-1文字目までは前へ，i文字目以降は後ろへ移動するという処理で対応できるかな？と考える．ただし，i文字目近辺が目標とする文字の場合，処理する必要がないことも考慮する，みたいな．コンテスト終了後17分後に提出するもWAでした．．もう少し考えよう．
CarpDay.icon まーす.iconさんご指摘の00001のようなケースでWAだしつつ，上記の方法で何とかAC．解説見たら何となく直感的にそうではないかと思っていたこと（0か1が連続する長さを考える）でシンプルに解けることを知ってがっかり．考察ゲーに負けました．．
kakip.iconAI規制で最近問題読んで考察して満足してる。Dは連長圧縮で短く書けそう
〇E問題
Kaplam.icon三分探索でサンプルは合ったんだけどサンプル以外TLEと1個だけWA、極値が複数ある場合かな～とか思いつつ色々調整してたんだけど、そもそも探索切り詰めないとすぐTLEが出ちゃうのでダメだった
Kaplam.icon終了後通った方針はそのままで、解説見て探索の区切りは片方が止まるまでと、その後の2つだけでいいことを理解したのでそこだけ調整してTLE、ただ実行時間を見ると過半数がTLEだったのに実際はギリギリのTLEが殆どだったので色んなところをちまちま高速化してAC、う～～～ん...三分探索のコード2年ぐらい前に作って初めての出番だったからACさせて上げたかった...
CarpDay.iconこれはきっと数学系だ！wataumi.iconさんいたら解いてるぞ！と思って，紙に頑張って数式を書きまくる．2つの動点をtで表して，2動点の距離（の2乗）をtで微分して=0を解いた答えを距離に代入！式ぐちゃぐちゃ．うまく消えるかと思ったのに．．しかも，高橋君と青木君でtの範囲が違うことに対応できていないことに気付き諦めてD問題に戻る．
CarpDay.icon今週はC問題・D問題だけでフラフラなのでE問題はKaplam.iconさんの伏字見た後，解説も見る．何と，wataumi.iconさんが以前使っていた相対ベクトル求めて，一方を固定するテクが出てきて驚愕．以前見たとき，便利だから覚えておこう，と思っていたのに実行できず．無念．コンテスト翌日無事ACできました．このテク重要．
wataumi.icon👀
kakip.iconにぶたん？
〇F問題
Kaplam.iconEのサンプルが早い段階で通ってたので主にそっちやってたけどこっちもチラ見はした、どう見たって遅延セグだけど何個足りないかに変な持ち方しないといけないパターンかな～と思ってやめた
CarpDay.iconコンテスト翌日に確認．確かに遅延セグ木っぽいけど，詳細分からないから早々にギブアップして解説確認．セグ木も併用して，二度と品切れ起こさないように大量在庫補充する方法．なるほどね．
〇G問題