第四回日本最強プログラマー学生選手権-予選-（AtCoder Beginner Contest 313）をPythonで解く

こんにちは, Shinoryoです.

今回は第四回日本最強プログラマー学生選手権-予選-（AtCoder Beginner Contest 313）を, Pythonで解いてみた結果を書き連ねていこうと思います.

AtCoder Beginner Contest 313 - AtCoder

AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.

A - To Be Saikyo

$1$人のみの場合と$2$人以上の場合で分けて考えると, 分かりやすいです.

B - Who is Saikyo?

ある人$X$が最強であるための必要条件は, $X$より誰かが強いという情報がないことです. したがって, 強さに関する情報を用いて弱い人を脱落させていって, 残った人数が1人かどうかで出力を分岐させればよいです.

C - Approximate Equalization 2

今回の操作では, 整数列$A$の総和は変化しません. これを考慮すると, 最小値と最大値の差が$1$以下になったとき, $A$の各項は$A$の平均値の切り捨て値または切り上げ値のいずれかにならなければなりません. そこで, 以下のような操作をすることを考えます.

• $A$の平均値よりも大きい項：$A$の平均値の切り上げ値になるまで減算する(減算回数$\mathrm{decrement}$)
• $A$の平均値以下の項：$A$の平均値の切り捨て値になるまで加算する(加算回数$\mathrm{increment}$)

問題文の制約によって, $\mathrm{decrement} = \mathrm{increment}$が求められます. しかし, $A$の最小値と最大値を変化させないように少ない方の操作を行えばよいです. したがって, 最終的な出力は$\mathrm{decrement}$と$\mathrm{increment}$のうち大きい方となります.

D - Odd or Even

解説にある解法の通りです. 偶奇の計算の際には排他的論理和 XORを適切に用いることができます.

E以降

E以降は私の能力不足故に省略いたします.

参考にしたサイト等

• 「解説 - 第四回日本最強プログラマー学生選手権-予選-（AtCoder Beginner Contest 313）」
  Editorial - AtCoder Beginner Contest 313

  AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.

• nkmk様による「Pythonのビット演算子（論理積, 論理和, 排他的論理和, 反転, シフト）」
  Pythonのビット演算子（論理積, 論理和, 排他的論理和, 反転, シフト ） | note.nkmk.me

  Pythonにはビット演算子として&, |, ^, ~, <<, >>が用意されている. 2進数で表した整数intの各ビットに対して, それぞれ論理積, 論理和, 排他的論理和, ビット反転, 左ビットシフト, 右ビットシフトを行う. 論理積（AND）, 論理和（OR）, 排他的論理和（XOR）の入出力 ビット単位論理積（bitwise AND）: &演算子 ビット単位...