AtCoder Beginner Contest 178をPythonで解く-Shinoryo's Weblog

Daniel AgreloによるPixabay(https://pixabay.com/)からの画像

こんにちは, Shinoryoです.

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

目次[非表示]

1A - Not
2B - Product Max
3C - Ubiquity
4D - Redistribution
5E以降
6参考にしたサイト等

A - Not

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

print(1-int(input()))

view raw atcoder-abc-178-a.py hosted with ❤ by GitHub

B - Product Max

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

	a, b, c, d = [int(x) for x in input().split()]
	print(max(ac, ad, bc, bd))

view raw atcoder-abc-178-b.py hosted with ❤ by GitHub

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の場合は, とりあえず律儀にそれを求めても問題はないと思います.

	N = int(input())
	print((10*N - 29N + 8N) % (10**9 + 7))

view raw atcoder-abc-178-c.py hosted with ❤ by GitHub

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

	# 累乗したものをmodで除した剰余を求める関数を定義
	def ruijo(a, k):
	ans = 1
	for _ in range(k):
	ans *= a
	# 掛け算を行うたびに剰余を求める処理を行う
	ans %= mod
	return ans

	# 簡単のため, modに10**9 + 7を格納
	mod = 10**9 + 7

	# 入力
	N = int(input())

	# 出力
	print((ruijo(10,N) - 2*ruijo(9,N) + ruijo(8,N)) % mod)

view raw atcoder-abc-178-c-2.py hosted with ❤ by GitHub

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$ に対する漸化式として,

\begin{array}{r} (1) & A_{n} = A_{n - 3} + A_{n - 4} + \dots + A_{3} + 1 \end{array}

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

\begin{array}{r} (2) & A_{n} = A_{n - 3} + A_{n - 4} + \dots + A_{3} + A_{2} + A_{1} + A_{0} \end{array}

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

また, 漸化式 $(2)$ の添え字を $1$ ずらすことによって,

\begin{array}{r} (3) & A_{n - 1} = A_{n - 4} + A_{n - 5} + \dots + A_{3} + A_{2} + A_{1} + A_{0} \end{array}

となります. $(2)$ , $(3)$ より, 新たな漸化式

\begin{array}{r} (4) & A_{n} = A_{n - 1} + A_{n - 3} \end{array}

を得ることができます.

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

まずは, 漸化式 $(2)$ を用いた例.

	def dp(n):
	# 割る数を格納しておく
	mod = 10**9 + 7

	# Sが3以上かそうでないかで場合分け
	if n > 2:
	# 3以上であれば漸化式を用いる
	dp = [0] * (n+1)

	# 初期値
	dp[0] = 1
	dp[1] = 0
	dp[2] = 0

	# 漸化式の計算
	for i in range(3, n+1):
	for j in range(i - 2):
	dp[i] += dp[j] % mod

	# 出力
	return dp[n] % mod
	else:
	# 2以下であれば0を出力
	return 0

	# 入力と出力
	print(dp(int(input())))

view raw atcoder-abc-178-d.py hosted with ❤ by GitHub

そして, 漸化式 $(4)$ を用いた例.

	def dp(n):
	# 割る数を格納しておく
	mod = 10**9 + 7

	# Sが3以上かそうでないかで場合分け
	if n > 2:
	# 3以上であれば漸化式を用いる
	dp = [0] * (n+1)

	# 初期値
	dp[0] = 1
	dp[1] = 0
	dp[2] = 0

	# 漸化式の計算
	for i in range(3, n+1):
	dp[i] = (dp[i-1] + dp[i-3]) % mod

	# 出力
	return dp[n]
	else:
	# 2以下であれば0を出力
	return 0

	# 入力と出力
	print(dp(int(input())))

view raw atcoder-abc-178-d-2.py hosted with ❤ by GitHub

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...

AtCoder Beginner Contest 178をPythonで解く

A - Not

B - Product Max

C - Ubiquity

D - Redistribution

E以降

参考にしたサイト等

0 件のコメント:

コメントを投稿 (Please feel free to ask me about your questions! You can use Japanese or English in the comments.)

Search

About Me

Labels

Blog Archives

Twitter