7/29 ARC079

AtCoder Regular Contest 079

C, Dを解いて2完. Eはにぶたんとかいろいろ試したけれどダメだった. Fは問題さらっとしか読んでないです.

• C: Cat Snuke and a Voyage - AtCoder Regular Contest 079 | AtCoder [解答]

  島1から繋がっている島すべてに対して, Nと繋がっているかどうかを調べる.

• D: Decrease (Contestant ver.) - AtCoder Regular Contest 079 | AtCoder [解答]
  K回操作を行った後に0, 1, 2, 3, ..., N - 1という長さNの数列になるような数列を作る. 1回操作を行ってこの数列が得られるような列の中にはN, 0, 1, 2, ..., N - 2という列がある. 同様に, 2回操作を行ってこの数列が得られるような列の中にはN - 1, N, 0, 1, ..., N - 3というものがある. これを一般化すると, A[i] = K / N + (N - i - 1) + (i < K % N)とすれば良い. Nはとりあえず50にしておいた.

• E: Decrease (Judge ver.) - AtCoder Regular Contest 079 | AtCoder [解答]
  最大になるものを選んでとあるが, 実は操作する順番を変えても答えは一緒になる. なので, A[i]がN未満になるまで減らして他の要素には+1をするというのを全要素がN未満になるまで繰り返せば良い.
  コンテスト中は二分探索をしようと思ったのだけれどどうやら, 解の付近で単調性が崩れるらしくて正しく答えが求められなかった. ちなみに, 解の範囲をある程度絞った後で範囲のしたから解を探すってことをしたら通った(提出コード).
  周辺まで見る二分探索をしているレッドコーダーの方もいたみたいで, その正当性をTwitterで話していたけれど正直よくわからなかった.