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

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

こんにちは, Shinoryoです.

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

1A - Plural Form
2B - Go to Jail
3C - A x B + C
4D - Leaping Tak
5E以降
6参考にしたサイト等

A - Plural Form

文字列に対して, リストのように[1]や[2], [-1]等をつけることによって, ○文字目の文字を抽出することができます.

	s = input()
	if s[-1] == "s":
	s += "es"
	else:
	s += "s"
	print(s)

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

B - Go to Jail

問題文にあるゾロ目の条件を順に確かめればよいです. ループの条件に注意しましょう.

	N = int(input())

	# 配列Dの作成
	D = []
	for i in range(N):
	D += [[int(x) for x in input().split()]]

	# ゾロ目判定
	for i in range(N-2):
	if D[i][0] == D[i][1] :
	if D[i+1][0] == D[i+1][1] :
	if D[i+2][0] == D[i+2][1] :
	print("Yes")
	exit()

	# ゾロ目が出なかったらNo
	print("No")

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

C - A x B + C

$A \times B < N$ を満たす自然数の組 $(A, B)$ に対して, ある自然数 $C$ を適当に選ぶことで $A \times B + C = N$ となります. ゆえに, 自然数の組 $(A, B)$ に関してだけ気にすればよいです.

$A$ を固定した場合, $A \times B < N$ を満たす $B$ は $⌊ \frac{N - 1}{A} ⌋$ 個だけあります(ただし, $⌊ ⌋$ はGauss記号で, $⌊ x ⌋$ は $x$ を超えない最大の整数です). それを $A = 1$ から $A = N - 1$ まで足し上げればよいでしょう.

	N = int(input())
	ans = 0

	# 最初にAを固定する
	# Aは1からN-1まで可能性がある
	for i in range(1,N):
	# Bは(N-1)//A(N-1をAで割った商)の個数だけある
	# Cは残りを足すだけなので, 上記のA, Bの組に対してあるCが1つ定まる
	ans += (N-1) // i

	print(ans)

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

D - Leaping Tak

動的計画法(dynamic programming)による簡単な解決方法として, 以下のようなものが考えられます.

$[L_{i}, R_{i}]$ の和集合として $S$ を作る.
配列dpを, 「dp[i]： $(i + 1)$ 番目のマス目に到達する場合の数」として定義する.
dp[0]に関して, $1$ 番目のマス目に到達する場合の数は「高橋君は現在マス $1$ にいる」という意味で $1$ 通りとする.
$1$ 番目のマス目から $(N - 1)$ 番目のマスに関して, 集合 $S$ で定められた $d (\in S)$ マス分の移動移動を試す. その際, $i$ 番目のマス目に到達する場合の数を $(i + d)$ 番目のマス目に到達する場合の数に加えていく.

最終的に, 配列dpに「dp[i]： $(i + 1)$ 番目のマス目に到達する場合の数」が入るようになります. しかし, これでは計算量が $O (N^{2})$ (集合 $S$ の要素数も高々 $N$ 個存在する)になってしまうので, TLE.

	# 入力
	N, K = [int(x) for x in input().split()]
	MOD = 998244353

	# [L, R]の和集合となる集合Sを作成
	S = []
	for i in range(K):
	L, R = [int(x) for x in input().split()]
	for j in range(L, R+1):
	S.append(j)

	# dp[i]：(i + 1)番目のマス目に到達する場合の数
	# dp[0] = 1：1番目のマス目に到達する場合の数は「高橋君は現在マス1にいる」という意味で1通り
	dp = [0]*N
	dp[0] = 1

	# 1番目のマス目から(N - 1)番目のマスに関して, 集合Sで定められた移動を試す
	for i in range(N - 1):
	if dp[i] > 0:
	for d in S:
	# 移動によってN番目のマス目を超えないかチェック
	if i + d < N:
	# i番目のマス目に到達する場合の数を(i + d)番目のマス目に到達する場合の数に加える
	dp[i + d] += dp[i]

	# 出力
	print(dp[N - 1] % MOD)

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

これを解決する方法については, まだ私の理解が追い付いていないので記載しません. 理解できたときに記載します.

E以降

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

参考にしたサイト等

「解説 - AtCoder Beginner Contest 179」
Editorial - AtCoder Beginner Contest 179
AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.
Tomotaka Ito様の「Python文字列操作マスター」
Python文字列操作マスター - Qiita
Pythonにおける基本的な文字列操作をまとめました. 経験豊富な人には物足りない内容かもしれませんが... (追記2018.12.23: print の文法をPython3対応にしました. Python2でコピペしたコードが動かない場...
マスオ(難波博之; 高校数学の美しい物語)様の「ガウス記号の定義と３つの性質」
ガウス記号の定義と３つの性質
ガウス記号の定義. および覚えておくと役に立つガウス記号の性質を３つ紹介. その証明も解説します.

AtCoder Beginner Contest 179をPythonで解く

A - Plural Form

B - Go to Jail

C - A x B + C

D - Leaping Tak

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