ABC245

7完。久しぶりにGが解けていい順位。ただ全体としてはミスが多く4ペナ。たぶん天気のせいで今朝は調子が最悪だったが、今は普通。おそらくAHCの疲労が原因だと思うが、関係なくて普通にミスっただけかも。

A - Good morning

0時から何分経ったかに変換して比較。長いTakahashiだけコピペしてAokiは手打ち(スペルミスはサンプルで確認されるから手打ちでもいい)。

B - Mex

その数が現れたかチェックしておいて0から順に現れてないものを探していく。問題名の通りで好き。

C - Choose Elements

けっこう難しい。見た目DPなのでDPする。最初はABどちらも選ぶことができて、次はAだけ選べて~みたいにしていく。左から順に構築していって、その過程で今の場所のABがそれぞれ選べるかどうか4通りの状態しかないのでそれを更新していく。

更新忘れ(新しい値を求めたのに代入してない)でサンプルが通らなかった。

D - Polynomial division

ずいぶん攻めてるなあ。まあ多項式の割り算の筆算は学校でやった。上から合わせていく。まあできるんだけど、こういうのいきなり出されるとビビる。

E - Wrapping Chocolate

平面走査みを感じるが、具体的にどうするか。横幅が大きい順に見ていく(横が同じものの順番はどうでもいい)。一番横が長いチョコを入れる箱として、候補に横幅がそれ以上の箱だけを追加する。そのうち、入る箱がなければNo、あればその中で最も縦が短いものに入れる(これは他の全ての選択に劣らない)。横は考慮しなくていい(これより横が長いチョコはないので、候補になった箱はどれも残った全てのチョコに対して横幅は足りている)。これをチョコがなくなるまで繰り返す。実装上は、箱の縦の長さだけをmultisetに突っ込んでいく。

箱を追加していくとき添字をインクリメントしてなくてサンプル通らず。setではなくmultisetが必要なことに気づかずWA。AとBが別々の行で与えられるのを忘れてWA。

F - Endless Walk

簡単そうで難しいやつか?いや、ACLのSCCを貼ればいいじゃん。んでここからが面倒なんだよな。まず、サイズが1より大きい強連結成分に属するものは全部OK。そこへ到達できる頂点もOK。他はNG(ループはどれも「サイズが1より大きい強連結成分」に属している(閉路以外に無限に続くものはないのかという不安はあるがまあ同じ頂点に来たら同じ移動ができるので))。逆辺を持っておき、各頂点がどの強連結成分に属するかのテーブルを作り、OKな強連結成分に属する全ての頂点から逆辺を辿って行き先の強連結成分にOKマークを付ける。

テーブルの長さをNではなくKにしていてRE。

G - Foreign Friends

国が関係ないならダイクストラするだけ(ここまで読むのもけっこう大変)。ダメな国が1個だけなのでどうにかなりそうではあるが。平方分割とか考えていると、ビットで半々にしていくのを思いつく。これはチャンスがありそうだ。国の個数は2^17以下なので17bitで表せる。各ビットが立っているかどうかで国を半分に分けて、選ばれた半分の国の人気者だけを始点としてダイクストラしてその結果を保存しておく。ダイクストラ法を34回やるということ(最初よくわかってなくて17回だと思ってた)。各人について答えを求めるときは、その人の国の番号の各ビットを見て自分が属さない側の半分のコストを取得し全ビットについて最小値をとる。自分が属さない全ての国の人気者からのコストの最小値になっている(と願っていた)。どっちを見るかは添字ガチャをした(2通りなので)(ガチャに頼るくらい頭が熱くなっている)。

国を半分に分けてどちらを使うか2通りやるとき、xorで選び方を逆にしたつもりが相手が0か1とは限らなかったので間違っていてWA(&&や||みたいな感覚で使ってしまった)。