AtCoder Beginner Contest 178をPythonで解く

こんにちは, Shinoryoです.

今回はAtCoder Beginner Contest 178を, Pythonで解いてみた結果を書き連ねていこうと思います.

A - Not

$0$なら$1$, $1$なら$0$を出力すればいいので, すなわち入力値を$x$とすれば$1 - x$を出力すればよいことになります.

B - Product Max

最大になりうるのは$a \times c$, $a \times d$, $b \times c$, $b \times d$のどれかです. それらの中で最大の値を出力します.

C - Ubiquity

• 全ての整数列：$10^N$通り
• $0$が存在しない整数列：$9^N$通り
• $9$が存在しない整数列：$9^N$通り
• $0$も$9$も存在しない整数列：$8^N$通り

以上から, 求めるべき値は$10^N - 2 \times 9^N + 8^N$を$10^9 + 7$で割った剰余であることが分かります.

Python3の場合は, とりあえず律儀にそれを求めても問題はないと思います.

整数の値が必要以上に大きくならないように, 累乗の処理の中に$10^9 + 7$で割った剰余を求める処理を組み込むこともできます.

D - Redistribution

動的計画法(dynamic programming)で解くことを考えます. $S=1$に対する求める解答を$A_1$, $S=2$に対する求める解答を$A_2$, ……のように書きます. $A_1 = 0$, $A_2 = 0$, $A_3 = 1$, $A_4 = 1$, $A_5 = 1$です. そして, $S = 6$に対して, 問題文の条件に当てはまる整数列は, 以下のものになります.

• その整数自身($\{ 6 \}$)
• $3$に対する整数列群(の右側)に$6$を加えたもの($\{ 3,3 \}$)

少し飛んで, $S = 9$に対して, 問題文の条件に当てはまる整数列は, 以下のものになります.

• その整数自身($\{ 9 \}$)
• $6$に対する整数列群(の右側)に$3$を加えたもの($\{ 6,3 \}$, $\{ 3,3,3 \}$)
• $5$に対する整数列群(の右側)に$4$を加えたもの($\{ 5,4 \}$)
• $4$に対する整数列群(の右側)に$5$を加えたもの($\{ 4,5 \}$)
• $3$に対する整数列群(の右側)に$6$を加えたもの($\{ 3,6 \}$)

より一般的に$S \geq 6$に対して言えば, 以下のようになります.

• その整数自身
• $S - 3$に対する整数列群(の右側)に$3$を加えたもの
• $S - 4$に対する整数列群(の右側)に$4$を加えたもの
• ……
• $3$に対する整数列群(の右側)に$S - 3$を加えたもの

したがって, $S \geq 6$に対する漸化式として,

が成り立つことが分かります. ここで, $A_1 = A_2 = 0$であることを利用し, また$A_0 = 1$と定義する(上の箇条書きにおける「その整数自身」の代わり)と, 漸化式\eqref{eq_atcoder-beginner-contest-178-1}は

のようになり, $S \geq 3$にまで拡張することができます.

また, 漸化式\eqref{eq_atcoder-beginner-contest-178-2}の添え字を$1$ずらすことによって,

となります. \eqref{eq_atcoder-beginner-contest-178-2}, \eqref{eq_atcoder-beginner-contest-178-3}より, 新たな漸化式

を得ることができます.

どちらの漸化式を用いても解くことができます.

まずは, 漸化式\eqref{eq_atcoder-beginner-contest-178-2}を用いた例.

そして, 漸化式\eqref{eq_atcoder-beginner-contest-178-4}を用いた例.

E以降

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

参考にしたサイト等

• 「解説 - AtCoder Beginner Contest 178」
  Editorial - AtCoder Beginner Contest 178

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

• nkmk様の「Python3の整数int型に最大値はない（上限なし）」
  Python3の整数int型に最大値はない（上限なし） | note.nkmk.me

  Python2の整数型にはintとlongの2つの型があったが, Python3にはintしかない. Python3のintはPython2のlongに相当し, 最大値の上限はなく, メモリの許す限り大きな値を扱うことが可能. ここでは以下の内容について説明する. Python2の整数int型と長整数long型 Python3の整数int型浮動小数点数floatとの関係 浮動小数点数flo...