ABC328 （2023/11/11）
〇A問題
TK.iconSで回してX以下のみ加算
Kaplam.iconそのまま書く
まーす.iconおたふく.icon TK.iconさんと同じ．
CarpDay.icon内包表記したリストの合計．結構早くできたと思ったけど，C++組に勝てないなぁ．
tako.icon適当
yuichang.icon やる
Yuto.icon やるだけ
kakip.iconいいかんじにやる
〇B問題
TK.iconDの中身をループのrangeの値に使いつつ日付を回す。数値を文字列になおして、setにキャストして集合のサイズを調べるというやり方で強引に突破した。ループのレンジの取り方をミスして時間食った
Kaplam.icon月と日付をlistにしてlen(set)、WA2で後からみたら変なこと書いてた
まーす.icon1<=月<=9のときとそれ以外のときとで処理をわけて実装．前者は日 in {月,月*11}でカウント．後者は日 in {月の下一桁,月の下一桁*11}でカウント．インデックスを間違えて1ペナ．
CarpDay.icon多分，TK.iconさんやKaplam.iconさんと同じ．意外に主流派？
tako.iconTK.iconさんと同じ
yuichang.icon 日にちを回す、月と日にちを文字に直してsetに文字入れてset.size()==1?
おたふく.icon python勢の多数派？？かな
Yuto.icon 調子に乗って，問題文を英語表示してたせいで誤読．やるだけなのにめっちゃ時間かかった
kakip.iconlen(set)
〇C問題
TK.icon連続した部分が何個あるかの累積和取って差を取る
Kaplam.iconここまでで何個作れるかのlist作って引き算
まーす.iconTK.iconさんと同じ．
CarpDay.iconみなさんと同じく累積和．端っこの処理で間違えたトラウマがあって，慎重になってしまう．
tako.iconbisect.bisectleft
yuichang.icon累積和！！
おたふく.icon ここまでTK.iconとことごとく方針被り
Yuto.icon 加算が静的で，区間和が何回も欲しい → 累積和．調子に乗って問題文を...（以下略）
kakip.icon累積和
〇D問題
TK.icon最初はreplaceで脳死コード提出。無事TLE。その後dequeとかで登場のタイミングを覚えておいて、3つの尺取りで進めてみたが、結局削れなかった。とりあえず問題文の言われた通りに左から追加していって"ABC"になったら削除で実装したら通った。
Kaplam.iconABCを見つけたらそこから前の方のアルファベット最大2個と後ろのアルファベット最大2個を探してそれがABCになるかって広げていく、結果AC29、TLE1、1個だけ実行時間ずば抜けてでかいので落とす用みたい、かなしみ、解説見たら言われてみればすごい簡単で更にかなしかった
tako.iconスタックを使いました
CarpDay.icontako.iconさんと同じく，リストでスタック処理．もう少しシンプルに作れたかな．それにしても，tako.iconさん，むっちゃ早いなぁ．スタック系得意だよね．コンテスト終了後に落ち着いて素直に実装したら，むっちゃシンプルにAC．素直な心，大切．
yuichang.icon dequeに文字とindexをぶちこむ（後ろからしかとらないけど）
おたふく.icon 自分はリストで素直に実装。まず空のリストを用意しておき、削除すべき文字でないならば追加していき、後からまたABCとなり得る文字をリストに追加している可能性があるので、最後尾から1文字目と2文字目は追加した後、popする可能性有り。
Yuto.icon 答えの文字列を作っていく．特に工夫することも無く，Dなのにこれで良いんか？と思いながら提出．
kakip.iconリストにABCを二進変換していれていっていろいろやって戻してというかんじで遠回りして時間かかった
〇E問題
TK.icon最小全域木問題だから、クラスカル 法かプリム法 の2択でライブラリにまだ置いてなかったからプリム法 を調べながら用意して、そこからMODをどう考慮するか考えたが思いつかなかった。
tako.iconわかりませんでした
まーす.iconDとばしてEに来た．scrapboxにあったやつUnion Find→(2) グラフの最小全域木をまんまじゃんと思い，それを使用．入力3がなかなか通らずに苦戦．WAも半分近く通らなかったので，根本的に問題がありそう......
yuichang.icon 最小全域木作るだけじゃmodの最小化をするのでダメで、結局全部試せますっていうノリだと思って再帰関数作る。何がだめかわからなくて発狂。全域木なるものをよく理解していません><
CarpDay.iconyuichang.iconが（伏字で）言う通りなので，TK.iconさんやまーす.iconさんの方法だとうまくいきません．Nが極端に小さいのが怪しいよね．計算量評価するとギリギリ行ける！例3がローカルで10秒ぐらいかかったので，TLE覚悟で出したらすんなりACでした．
おたふく.icon 最初に問題を見て、ネットに何か情報が有りそうと思い調べるとクラスカル法なるものを知り、簡単な問題だなあと実装すると、入力例が合わず実装ミスがあるか必死に考え時間を潰す。落ち着いて考えるとmodを取った余りなので、上記の解法では求まらないことに気付き、1<= N <= 8よりbitDPを方針として考えるも上手い実装法が思い付かず...。頂点の数も辺の本数も制約が軽いのでもしやと思い、N = 8, M = 28という最大のケースで計算量を考えると...。コンテスト終了数秒前でギリギリAC。バーチャルだと調子が良いなぁ...。
CarpDay.icon 伏字の方法，ScrapboxのUnion Findのページ内の「最小全域木」に書いていますよ～
Yuto.icon 最初は，全域木を全列挙できないか考えていたが，計算量的に無理そう（全ての辺を使うか全探索すると，2^M = 2^28なので厳しい）．発想を変えて，bitDPで解けないか考えてみた．dp[S] := 頂点集合Sを被覆する全域木の最小コストとして，遷移はu -> v の辺がある時，chmin(dp[S ^ (1<<v)], dp[S]+cost[u][v])という感じ．これなら計算量はO(2^N)なのでいけそう．提出してみたら半分くらい通った．惜しそうだけど何も分からんまま，バーチャル参加終了．
Yuto.icon 解説見た．magurofly さんのユーザー解説 と同じことをしたかった．解説を読むと「元のコストが小さいほど良いとは限らないため、あり得るすべてのコストを保持する必要がある」らしい．dpテーブルをdp[S] := 頂点集合Sを被覆する全域木のコストの集合に変更して提出すると1TLE．無駄な状態を保持してしまっているのか，PyPyが遅いのか分からないので，Rustで書き直して提出．無事にAC．PyPyが遅かったみたい． 〇F問題
CarpDay.iconUnionFindで連結情報を持ちながら，2点間の上下関係を保持する方針を考えたが，unionしたときの上下関係の更新処理をO(1)で行う方法が思いつかない．ネットで調べたが分からず終了．
おたふく.icon CarpDay.iconさんのコメントを見て、面白そうなのでF問題を見てみると重み付きUnionFindで一発ACでした!!! ライブラリを作った甲斐がありました!!!!!!
CarpDay.icon 上のコメント見て驚愕！コンテスト中に一度はscrapboxチェックしたものの，使えることに気付きませんでした． 使用したら簡単にAC．．．初の6問AC＆水色入りの好機を逃しました．．．ライブラリ，不備修正（sameが無かった）＆コメント補足しておきました．
おたふく.icon すいません、自分のライブラリにはシンプルバージョンのメソッドを追加していたみたいですが、scrapboxの方に追加するのを忘れていたみたいです...。
kakip.icon最初から見て行ってUnion Findで非連結だった辺だけでXの値を確定して、連結だった辺が矛盾がないか判定。コンテスト中に思いついたけど時間内に実装できず。