ABC372 （2024/09/21）
〇A問題
まーす.icon瞬殺．
まーす.iconやらかした．CとDで大事故．
CarpDay.iconドンマイ！互いに頑張ろう！
まーす.icon最近，レートの増減がCauchy 列みたくなってる......収束しないように頑張るます．
tako.icon replace
CarpDay.icon同じくreplaceで1-liner！
Kaplam.iconremove派は私だけか
kakip.icon同じくreplace
〇B問題
まーす.icon$ 3^{10} > Mのときの処理を忘れてWA．
tako.icon 三進数に変換して適当
Kaplam.iconなんか1WAが出た、n > now*3 をn >= now*3にしたら通ったから20個越えちゃったのかな
CarpDay.icon$ 3^k \leq Mの範囲で最大の$ k（ただし$ k\leq 10）を見つけて，$ Mから$ 3^kを引き続ける．
kakip.iconMを3で割ってあまりの数だけappend
〇C問題
tako.icon 変更された箇所の付近だけ見る。ぐちゃぐちゃ実装
Kaplam.icon同上
CarpDay.icon同上．素直ではあるが，ぐちゃぐちゃ．
kakip.icon同上、inで書くとすっきり
CarpDay.iconコード拝見．文字列のcountメソッド，番兵，文字列のinなど，参考になります！初学者に見せます！
まーす.icon"A", "B", "C"からなる文字の集合を$ S = \{"A", "B", "C"\}として，その冪集合$ \mathfrak{P}(S)をクエリーによる操作でいじっていく問題．この操作を辞書使ってやってるつもりがWA全く消えない......
CarpDay.icon初期設定で辞書dを作っているけど，キー"AB"が抜けているよ～
まーす.iconありがとうございます．
〇D問題
tako.icon ビルの高さの降順に並び替えてから順番に見ていって、今まで見た中で自分のインデックスより小さい一番大きいインデックスの所を+1するimos
Kaplam.icon後ろから見て行って今sortedsetに入ってる数字で今見ている所より大きいものの個数がそこの答え、その後今見ている数字より小さいものを取り除いてから今見ている数字をsortedsetに入れるのを繰り返す
CarpDay.icon自分より後の部分がLISになると思って，LISのライブラリ持ってくるも追加する数が小さい数になるので苦戦（先にE問題へ行く）．高さを-1倍して負数にしてbisect使えるようにしてやっと実装できたら，数値例3がおかしい．LISでない（追加した高さは必ず入れる）ことに気付いて修正．ギリギリで間に合う．難しく考えすぎた．
kakip.icon後ろからH_iより小さいものを除いてスタックして要素数が答え
CarpDay.iconシンプルですばらしい．
〇E問題
tako.icon sortedListをN個持っておいて、ufでグラフ管理。mergeする時、親になった方にsortedListを合体させる。TLEなるかなと思っていたけど間に合ってよかった。
Kaplam.icondefaultdict(sortedset)とunionfindで要素数少ない方の要素を全部多い方に入れるようにmergeしてAC64,TLE7だったからこれPythonで通らないやつかなと諦めたのになんでみんな通ってんの！？ あっk <= 10 あっ k<=10に対応させて(1828msだけど)通りました、ｽｩｰ_(:3」∠)_
CarpDay.iconよかったね！
CarpDay.icon自作UnionFindにメンバーを格納するリストを追加．リストを結合＋ソートもするけど$ k\leq 10のおかげで通った．自作がなかったら無理じゃね？と思ってたけど，別に作ればいいんか．なるほど．
kakip.iconpythonのdsuをいじったけどTLE出たのでC++に翻訳してもらってRE、頑張って直す。pythonで3変数を1文で代入しているところが翻訳でバグった、K<=10を完全に見落としてた
〇F問題
CarpDay.iconラスト数分で読んだだけ．追加枝なければぐるぐる回るだけか．．
CarpDay.icon諦めて解説読む．新しいDPを学ぶ．なるほど，発想の転換でした．円環なので解説コードの方法よりも，MOD使う方がシンプルな気がする．kakip.iconさんのはもう1つの方の解法ね．
kakip.icon2M(+1)本の重み付き有向辺にするとO(MK)でDPできるけどdefaultdict使うとTLE→座標圧縮すると2次元リストで書けて間に合った。辺のコストの計算がむずい
〇G問題