ABC312 (ユニークビジョンプログラミングコンテスト2023 夏)
31分+2WA 4完 1504th performance:1338
4月以来の低パフォ叩き出しで1800が遠のく。悲しみ。
A 「ACE、BDF、CEG、DFA、EGB、FAC、GBD」をメモ帳にコピペします。「、」を「","」に置換します。エディタに貼り付けます。 (21:01)
atcoder.jp
B B〜Cっぽい実装が重い問題。こういうのは正規表現で殴るんだよぉ！と久々に正規表現を使おうとすると混乱する。始まりと終わりのパタンしか書いてないのに9文字に対しregex_matchして合わないなあとかやってた。regex_searchを使いましょう。エスケープ文字がややこしいのでraw string literalを使いましょう。MとするところにNを入れて1WA。サンプルで弾いてくれえ (21:14->21:14)
atcoder.jp
C 何も考えずにソートして答えを二分探索して、中でも二分探索で数えてやればOK。答えの二分探索を見るために、OKの初期値を小さな値にしたまま提出しWA。落ち着きましょう。(21:22->21:23)
atcoder.jp
全部合わせてソートして順番に見ていくやつ。売る側を先になるようにソートしましょう。
atcoder.jp
D シンプルDP。最初開き数マイナスも含めて計算したら合わなくてちょっと混乱。開き数がマイナスになった時点で破綻していることに気づき書き直し。(21:31)
atcoder.jp
E 言われてみれば簡単なんだけど、各面で考えようとして二次元imosか？いやvector<vector<vector<map<ぐわあ、、、諦め。順位表見て低さに死につつもFが解けそうな感じを出しているので挑戦
F 鍵を何個使うかを全探索して残りを二分探索や！……いやこれ最大を求めるタイプの二分探索？三分探索になるんだっけ？1個でも交換した場合に下がるとかいう条件でなんとかならんか……死ぬほどエラーが出る……Eもむずいしつらい……解けん……死……
終了後も貪欲戦略を優先度付きキューとかでなんとかやろうとしたがこちらもエラーWAしまくって死亡。こういうときは寝るに限る！
ベッドで缶切り必要缶詰の個数を全探索すればええやんということに気づき、実装。缶切り必要缶詰をx個開けるとき、必要な缶切りの数は降順ソートした缶切りの累積和を二分探索すれば求まり、残りの個数缶切り不要缶詰を開ければよい。いずれも降順ソートしたうえで累積和を持っておけば計算が速いのでそうする。必要な缶切りが用意できないとか用意したらM個超えてるとかに注意。
atcoder.jp
G 全方位木DPあんまわかってないんだよなあと思いつつ挑戦。そのままの通り数も計算できるっぽいが、頭が痛くなってきたので余事象を考える。パスになる3点のうち、中点を根とする木を考えると、残りの2点は異なる子部分木から選べばよい。これは、sum x_i * x_j なので、((sum x_i)^2 - sum x_i^2) / 2 で求まる。あとは子部分木の大きさが分かればよく、最初にDFSして0を根としたときの各子部分木の大きさを求めておく。根をuに張り替えたとき、元親のほうの子部分木の大きさはSize[0]-Size[u]である。もう一度DFSして数え上げていけばOK。
atcoder.jp
