ABC370 （2024/09/07）
〇A問題
まーす.icon問題文の通りに条件分岐．
Kaplam.icon9月になったのでrated復帰、ifするだけ
tako.icon 以下同文
CarpDay.icon疲労で直前まで熟睡のため，unrated．tako.iconさん，入水か！？
tako.icon 入水しました！といってもE問題をgptパワーで通したので思うところはありますが入水は入水です
まーす.iconおめでとうございます！
CarpDay.iconおめでとう！GPT活用する力も重要！
tako.icon ありがとうございます！
yuichang.icon やる
〇B問題
まーす.iconfor文で更新していくだけ．
tako.icon 以下同b
Kaplam.icon以下同
CarpDay.icon以下同だけど，0-index／1-index処理に手間取る．
yuichang.icon やる。初手1と1の合成し忘れでペナ。サンプル><
〇C問題
まーす.icon文字列$ Sを幾度か（$ 0回でもよい）更新した文字列を$ curとする．$ curと$ Tが同じなら，以下を終了する．$ cur_{i} > T_{i} を満たす最小の$ 1 \leq i \leq |S|と$ cur_{j} < T_{i} を満たす最大の$ 1 \leq j \leq |S|を求める．$ cur_{\min(i, j)}を$ T_{\min(i,j)}に更新．
tako.icon 一文字ずつ比較してtが小さかったやつを前から書き換え、そのあとsが小さかったやつを後ろから書き換え
Kaplam.icon違う所を1文字ずつ変えたのを全部listに入れて辞書順で一番前だったものを選ぶのを繰り返す、Cまでは早かったね.
CarpDay.icontako.iconさんと完全に同じ．
yuichang.icontako.iconさんと完全に同じ．
〇D問題
tako.icon 各行、各列で壁の状態を記録してにぶたんするのがめんどくさかったからSortedSetで実装したら1TLE.二ブタン方式にするもWAが取れず仕方がないので最初に実装したものをGPTにC++にしてもらう。言語を変えてもらうのは個人的にあまり信用してなかったけど普通にできてスゴイ
tako.icon 追記 ネットにある誰かが作ったSortedSet使ったら普通に通りました。SortedContainersは少し遅いのか
CarpDay.iconSortedContainersで通りましたよ！使ったのはSortedSetでなくSortedListです！
tako.icon SortedListにしたら普通に通りました。要素が重複しない場合はSortedSetのほうが早いと思っていたけどSortedListのほうが早いのか...
Kaplam.icon誤読もあったけどそもそも普通ににぶたんとremoveしてTLE(ちょっと謎のWAも出てた)、解説見てそういやそんなのあったねって
CarpDay.iconSortedListで二分探索
まーす.icon今回，個人的にむずかしい......
yuichang.icon めっちゃ大きいグリッドはmap<int,vector<int>|set<int>>でマスだけ見る典型
〇E問題
tako.icon 時間もなくdp臭いのでどうせ解けないだろうなと思ってgptとお話してたら解けてびっくり
CarpDay.iconF問題とG問題を見て戻る．単純なDPでは状態数多くなりすぎるので別方法を検討．1～nまで順に処理．累積和を辞書で記憶しておいて，累積和-kが辞書に存在するなら，その分を個数から引くという方針で実装するも，実装力足りず時間かかりすぎ．やっとできたと思ったらサンプルも通らず．今からデバッグします～
CarpDay.iconうまくいかず断念して解説読む．DP遷移の理解が甘かった！今回の問題は分割なので，解説のようにN+1本の区切に関するDPとするのが理解しやすいし構築しやすい．N個の要素に関するDPと考えると，DPの初期状態の設定が難しい（$A_1$だけの状態を初期状態としても，$A_1=K$かどうか，$K=0$かどうかで初期状態が異なるのが厄介）
まーす.icon累積和とかSegTree 使っていろいろ考えてみたけど，sum(A[i:j) == K, 1 <= i < j <= Nとなる(i, j)の探索は結局，$ O(N^2)でしんどい......
yuichang.icon それっぽいdpするも解けず
〇F問題
〇G問題