第四回日本最強プログラマー学生選手権-予選-（AtCoder Beginner Contest 313）に参加しました。
結果
A,B,C問題の3問正解でした。
B問題でだいぶ沼った… ちょっと難しく考えすぎてた。
A - To Be Saikyo
問題文の通り処理を実装すれば良い問題。 問題文を言い換えると、1番目の値にどれだけ下駄を履かせれば２～N番目全部より大きな値になれるかを答える問題。
N個の値が与えられるので２～N番目の値の最大値を求めて、 最大値-1番目の値+1を出力する。この値が負の時はかわりに0を出力する。
B - Who is Saikyo?
N人のうち2人組の強弱関係がいくつか与えられるので1番強い人が誰かを答える問題。
問題文を読むと有向グラフっぽくみえて上下関係があるので、 強弱関係でUnionFind木を作って連結成分ごとの1番上が何人いるか、1人ならそれが誰かを答えれば良いのかなと思って解き始めた。
結局この考え方は間違ってはないと思うけど難しく考えすぎていて、結局解ききれなかった。（微妙なコーナーケースとかの対応が面倒…）
よくよく考えると、自分より強い人が何人いるかをカウントして、自分より強い人がいない人を答えれば良さそうと気づいたのでその方針で解き直した。
C - Approximate Equalization 2
数列が与えられるので2項を選び一方を+1して他方を-1するという処理を何回実行すれば、数列の最大値と最小値の差を1にできるかを答える問題。
読んで思ったこととしては以下。
- 操作によって数列の総和は変わらない
- 数列の平均値に近づけるように操作すれば良さそう
- 結局、各項と平均値との差を積み上げていけば良さそう
とりあえず数列の平均値（小数点以下切り捨て）を求めてそれを最小値、＋１したものを最大値として一旦解いていくことにした。
各項の値と最小値、最大値それぞれの差を求めて 差だけ1減らす/1増やす処理をしたとして数えていった。 全項を一通り処理してから、 増やした回数、減らした回数を比較して、一致していればその回数それが答えで、一致していなければ差分/2だけ余分に操作が必要ということになるので差分/2だけ補正した回数を答えとした。
