AtCoder Regular Contest #010 本番
http://arc010.contest.atcoder.jp/assignments
ARCは今の自分にとってちょうどいい難易度(うまくいったら全完程度)で楽しいです
Coding
A
シミュる
B
やる。
振替休日はカウンタを持っておくといい
C
(何番目か * 一つ前の色 * 2^mで出た色)でDP。
メモリが危なそうだったので何番目かは2つだけ覚えるやつにした
D
スパイに聞こえないように仲間iからjに伝えられるか？をグラフにする。求めたいのはこれの最小パス被覆。
まず、そのグラフを作らなければいけないが、これは(仲間iと全てのスパイとの最小距離 < 仲間iと仲間jの距離)なら良い。
ここで最小距離を求める方法だが、単に全探索すれば間に合う。
(5000*100000 = 5*10^8)で相当かかるようにも思えてしまうが、最内ループの中が結構軽い要素ばかり(わかってない)ので、またAtCoderサーバーもそれなりに速いのか(わかってない)、2secくらいと結構間に合う。
入力がランダムなので枝刈りが普通にできるようだが、自分は苦手だから実装に少しかかりそうでもあった。
次にその最小パス被覆をどう求めるか？
これは強連結成分(=Sとして)してそれをDAGにするやつをやって、その根を全部使う。
この解法は"SRM 312 DIV1 Medium AntarcticaPolice"のEditorialを前に読んだ時に今まで見た問題の表に書き留めておいたのを思い出した。
結果
A: +100 (02:49)
B: +100 (16:51)
C: +100 (32:27)
D: +100 (80:08)
Total: +400 (-0) (80:08)
Rank: 5/287
コメント
全完おめでとう。
ARC程度の難易度ではコンスタントに全完できるようになりたいですね。
WA無しはいいよね。もっと速く書けたらいいよね！
