ABC373 （2024/09/28）
〇A問題
まーす.iconfor文まわして，i + 1 == len(input())がTrueとなるときをカウント．
tako.icon やるだけ
CarpDay.icon「1-linerでできそう！」と欲張りそうになるも，落ち着いて素直に書く．
Kaplam.icon21時半から参加したい集まりを見つけたのでunratedでCDだけやってそっち行ってた(休憩時間にABもやった)
kakip.iconsumで1行
CarpDay.iconやりたかったの，これこれ！(^o^)/
〇B問題
tako.icon 制約を見ずににループを回す
まーす.icon前回に押したキーの位置を$ pre，今回押すキーの位置を$ nowとして，逐次$ |pre - now|を加算していくだけ．最初，キーボードと打つキーの順番を反対にしていてタイムロス．
CarpDay.iconまーす.iconさんと同じ誤読して，入力例2が合わずに慌てる．開始位置がAの場所なのに0のままにして答えが合わずに慌てる．
Kaplam.iconchr(ord("A")+i)みたく書くと楽なのかも
kakip.icon毎回str.index()
〇C問題
tako.icon max(A)+max(B)。こんな簡単でいいの？
まーす.iconprint(max(A) + max(B))．A，Bより簡単．
CarpDay.icon簡単すぎて，むっちゃ心配になった．AC出て本当に安心した．．
Kaplam.icon実際BよりAC数多くなってるしなんだったんだろ
kakip.icon250点？
〇D問題
tako.icon 連結になっている所の頂点を各一つ適当にとって0にしてbfsして埋めていく。いろいろあって変数iを使いまわしてる（途中で別の値を代入している）けど、pythonだとこれができる
まーす.iconグラフなのでスキップ．
CarpDay.iconスキップすな！(^^)/
Kaplam.iconICPCを見越して食わず嫌いはやめましょう( ˘ω˘)
CarpDay.icon未確定の点を0にして（あまり意識しなかったけど）BFSで埋めていく．tako.iconさんと同じっぽい．
Kaplam.icon多分上の人たちと一緒
kakip.icon同じです
〇E問題
まーす.iconずっとこれ考えてた．自分の考えでは，inputの状態で$ M番目に大きいAの値を基準に場合分け．多分，ここまでは合ってるハズ（あってて願望）．ただ，場合分け後の処理がかなり面倒でずっとペンを動かしてた感じ．数式を導けたら良かったのだが......
CarpDay.iconすぐに思いつかなかったのでスキップ．F問題から戻って，素直に思いついた方法で実装．まーす.iconさんと同じく，あとは各メンバーが上位$ M人に入っているかどうかで場合分けしたがWA．
CarpDay.iconコンテスト後，追加投票0でも当選確定がいるケースが漏れていたことに気付き修正．制限時間の怪しさから二分探索×2と推測．やっと実装して投稿するもWA．諦めて解説見たら，完全に想定解法．原因が変わらないので，適当に入力例作って試したところ，上の伏字の対応漏れが発覚．修正してやっとAC．シンプルな問題なのに厄介．
kakip.iconむずい。evimaさんのABC解説動画が最終回で悲しい
Kaplam.iconわかる
〇F問題
CarpDay.icon各品物について各個数入れたときの(重さ, 価値)のペアを作ってDPで解くがTLE．$ wが小さい品が多いと無理なことに気付いて諦めてE問題に戻る．
CarpDay.icon値だけでなく，採用した個数も保持すれば？と思って実装したが間違いでした．．諦めて解説見る．結論，E問題に戻る決断は正しかった（解けなかったけど）．解説の方法は思いつかないな．まーす.iconさんが伏せている別解の方法，数学的に面白いのでいずれ勉強したい．
まーす.icon最後の方にチラ見して，コンテスト後に挑戦してみる．defaultdict使って一次元DPを行うのだけれど，CarpDay.iconさんと同じく$ wが小さいと更新する回数が増えてしんどい．2次関数の軸による対称性の利用と$ wの大きい品から更新する方法を考えて，TLE21個まで減らせたものの行き詰まり感がすごい......．解説見たところ，別解に近い考え方．convex hull trick とかいうのがあるらしい......知らんけど
〇G問題