ABC430 （2025/11/01）
〇A問題
Kaplam.iconやらかした しとけばよかった れーてっど かぷらむ心の俳句
N_N.icon きれいな5-7-5 (^^)
N_N.icon 凄いパフォーマンス出てたのでは？青？
Kaplam.icon前後の順位の人のパフォから考えると472位で1680程度だったみたいです、前回564位で1723だったのでそれを考えると思ったよりは出てないですが(今回からのレーティングシステム改修の影響？)それでも大分勿体なかったです_(:3」∠)_
N_N.icon 最初，YesとNoを反対にしてた．
CarpDay.icon昨日からの突発性腹痛のためUnrated（そのため広い部屋では入口近くに座る）．案の定，途中でお呼びがかかって（＋C問題が分からずに）モチベダウン．．．
CarpDay.icon N_N.iconさんと同じく，Yes/No逆にする．やっぱりそう思いますよね！
Kaplam.icon私も逆にしました！！
N_N.icon お呼びがかかるってそういうことでしたか．．．
〇B問題
Kaplam.icon見てる範囲について文字列にしてsetに入れてlen()
N_N.icon Javaだけど，Kaplam.iconさんと同じ．
CarpDay.icon 見ている範囲を1次元の01にして，2進数とみなして整数をsetに入れる．そこまでせんで良かったっぽい？
〇C問題
Kaplam.iconやらないといけないことのベクトルはわかりやすいけど実装が難しい aとbについて個数を累積和で持って、個数の変化点を辞書で持っておく。始点について全探索して、まずaの個数を満たせる最短の位置を求めて、その時にBが指定個数を超えてたらだめ、超えてない場合は超えないところまでの数を求める
N_N.icon 尺取り法でいけるかな，いけないかなと思いつつ尺取り法を少し改良したものを実装してTLE×11．多分，尺取り法に加えてランレングス圧縮をすればいいのかな？と想像してる．
CarpDay.icon N N.iconさんと同じくの方法で実装初めて途中であかんことに気付く．このタイミングで呼び出しがかかり，別室で考察するも思いつかず．戻って順位表を見たらKaplam.iconさんがCをスキップして，先にDもEも解き終わっているの見て，逆張りしてCを考え続けるも時間の無駄．諦めてDへ．
〇D問題
Kaplam.icon最近もあった、追加クエリ1回に対して追加した隣の値についてしかさわらなくていいって感じでSortedSetでこねこね
N_N.icon 到着済みの人のX座標をキーとして，その時点での最短距離をバリューとするTreeMap（Pythonでいうsortedmap）と各時点での最短距離の合計を保持してループする．人が到着するたびに，その左隣の人の最短距離と右隣の人の最短距離を更新するかどうかを判定して，更新する場合は最短距離の合計もそれに合わせて更新する．
CarpDay.icon SortedListで各点の座標を保持して，bisectで近くの点を獲得して，Xを更新する，みたいな．
〇E問題
Kaplam.iconaについて2周分持っておいて、Rolling hashでbと一致するものがあるか見るだけ 追記：Rolling hashはmodをとるアルゴリズムなのでちゃんと対策しないとcodonは落ちるので注意、今回はそんな高速化いらないけど
CarpDay.icon 残り5分だったので，6行の単純なコードで通るか試したらやっぱりTLEでした(^^;
〇F問題
Kaplam.icon値についての順序関係を木構造で持っておく、右に置かないといけないものを親、左に置かないといけないものを子とすると、自分の子より先に置いてはいけない、そして木を上下反転して親を子として扱うと同じように自分の親より後に置いてはいけない、のでその範囲に1を足す、最初にセグ木っぽいって考察から始めたので遅延セグ木を使って2回TLE引いたけどimosでいいことに気付いてAC,AC出た時にはまだTLE提出2個のjudgeが終わってなかったんだけどそれが終わったら100位ぐらい下がった_(:3」∠)_
Kaplam.icon計算量は問題ないけど遅延セグが重すぎることに気付く直前に、ここでCodonの出番じゃね！？ とコンパイル投げてみたら遅延セグ木が通らなくて諦めました、Codon使うならこういう所も準備しないとですね
〇G問題