京セラプログラミングコンテスト2021（AtCoder Beginner Contest 200）をPythonで解く-Shinoryo's Weblog

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

こんにちは, Shinoryoです.

今回は京セラプログラミングコンテスト2021（AtCoder Beginner Contest 200）を, Pythonで解いてみた結果を書き連ねていこうと思います.

1A - Century
2B - 200th ABC-200
3C - Ringo's Favorite Numbers 2
4D - Happy Birthday! 2
5E以降
6参考にしたサイト等

A - Century

求めるのは, $N / 100$ を小数点以下切り上げた値になります. 世紀の定義そのままですね.

	import math

	# 入力
	N = int(input())

	# 出力
	print(math.ceil(N / 100))

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

B - 200th ABC-200

問題文に書かれていることをそのまま実行すればよいです. 「整数 $N$ を, $N$ の後ろに文字列として $200$ を付け加えた整数に置き換える」というのは,

$N$ をstr型にして
後ろに「200」(文字列)を付け加えて
int型にする

という操作によって実行できます.

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

	# K回のループ
	for _ in range(K):
	# 200で割り切れる場合の操作
	if N % 200 == 0:
	N //= 200
	# 200で割り切れない場合の操作
	else:
	N = int(str(N) + "200")

	# 出力
	print(N)

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

C - Ringo's Favorite Numbers 2

数列 $A$ から2つを取り出す全ての組み合わせを全通り探索して, $A_{i} - A_{j}$ が $200$ の倍数であるかどうかを確かめてしまうと, 時間計算量が $O (N^{2})$ となりTLE.

	import itertools

	# 入力
	N = int(input())
	A = [int(x) for x in input().split()]

	# 答えを格納する変数
	ans = 0

	# iとjの組み合わせを全探索
	for Ai, Aj in itertools.combinations(A, 2):
	ans += not((Ai - Aj) % 200)

	# 出力
	print(ans)

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

さて, $A_{i} - A_{j}$ が $200$ の倍数であるならば, $A_{i}$ を $200$ で割った余りと $A_{j}$ を $200$ で割った余りが等しいということを利用します. $A$ の配列全てを $200$ で割った余りにしておき, $A$ に含まれている $0$ の個数, $1$ の個数, ……を順に確かめていきます. そして, $A$ に含まれている $i$ の項目から2個を選ぶ場合の数を加えていきます.

ここでは, 組み合わせの場合の数を計算するのにscipy.special.combを使用しています. int型を貫くために, 第3引数で「exact=True」とします(「exact=True」だとint型, 「exact=False」(デフォルト)だとfloat型を返します).

	from scipy.special import comb

	# 入力
	# Aの配列全てを200で割った余りにしておく
	N = int(input())
	A = [int(x) % 200 for x in input().split()]

	# 答えを格納する変数
	ans = 0

	# Aに含まれている0の個数、1の個数、……を順に確かめていく
	for i in range(200):
	# Aに含まれているiの項目から2個を選ぶ場合の数を、ansに加える
	ans += comb(A.count(i), 2, exact=True)

	# 出力
	print(ans)

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

D - Happy Birthday! 2

鳩の巣原理(Pigeonhole principle)より, $201$ 個以上の $B$ または $C$ の候補を用意すれば, $200$ で割った余り(の合計)が同じになるものが2つ以上存在することになります. 数列 $A$ の長さ $N$ に対して, $B$ または $C$ の候補は $(2^{N} - 1)$ 個あるので, 数列 $A$ は $8$ 個分だけ調べれば十分となります( $2^{7} - 1 = 127$ , $2^{8} - 1 = 255$ ).

$N = \min (N, 8)$ として, $1 \leq i < 2^{N - 1}$ を満たす $i$ に対して, それを2進数にした表現を利用します. このような全探索方法(bit全探索)に関しては, 「AtCoder Beginner Contest 197（Sponsored by Panasonic）をPythonで解く」の「C - ORXOR」でも行っています.

$B$ の候補に関して, $200$ で割った余りが一致すれば, それを出力します. 一致するものがあるかどうかは, 「余りが $\mod$ になる $B$ の候補」を $bcand_record [\mod]$ に記録し, $\mod_count [\mod]$ のフラグを $+ 1$ することによって, $\mod_count [\mod]$ が $2$ になるかどうかで確かめます. 余りが一致するもう1つの $B$ の候補は $bcand_record [\mod]$ に記録されているので, それを再現すればよいです.

最後の出力では, .joinでいい感じにつなぎます.

	# 入力
	N = int(input())
	A = [int(x) for x in input().split()]

	# 鳩の巣原理
	# 201個以上のBまたはCの候補を用意すれば、
	# 200で割った余りが同じになるものが2つ以上存在する
	# 数列Aの長さNに対して、BまたはCの候補は(2^N - 1)個あるので、
	# 数列Aは8個分だけ調べれば十分である
	N = min(N, 8)

	# 記録用変数
	mod_count = [0 for _ in range(200)]
	bcand_record = [[] for _ in range(200)]

	# 答えを格納する変数
	ans_x = []
	ans_y = []

	# bit全探索
	for bit in range(1, 1 << N):
	# 記録用変数
	mod = 0
	bcand = []

	# bitの値から数列Bを作成(x) & Aの中の対応する数値をsに加えていく
	for i in range(N):
	if bit & (1 << i):
	bcand.append(i)
	mod += A[i]
	mod %= 200

	# sを200で割った余りをrestableに記録しておく
	mod_count[mod] += 1

	# sを200で割った余りが同じものが2つあれば……
	if mod_count[mod] == 2:
	# 1つは今調査している数列B(x)
	ans_y = bcand
	# もう1つはxsから記録を取り出す
	ans_x = bcand_record[mod]
	break

	# 数列Bの値をxsに記録しておく
	# その場合の200で割った余りが分かるように
	bcand_record[mod] = bcand

	# もしans_x, ans_yに記録されなければNoを出力
	if len(ans_x) == 0 or len(ans_y) == 0:
	print('No')
	# そうでなければYesを出力
	else:
	print('Yes')
	# 出力
	print(' '.join([str(len(ans_x))] + [str(j + 1) for j in ans_x]))
	print(' '.join([str(len(ans_y))] + [str(j + 1) for j in ans_y]))

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

E以降

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

参考にしたサイト等

「解説 - 京セラプログラミングコンテスト2021（AtCoder Beginner Contest 200）」
Editorial - KYOCERA Programming Contest 2021（AtCoder Beginner Contest 200）
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の数学関数の標準モジュールmathを使うと階乗を計算できる. これを利用して順列・組み合わせの総数を算出できる. SciPyの関数にも順列・組み合わせの総数を算出するものがある. また, itertoolsモジュールを使うとリスト（配列）などから順列・組み合わせを生成して列挙できる. ここでは, 階乗: math.factorial() 順...

京セラプログラミングコンテスト2021（AtCoder Beginner Contest 200）をPythonで解く

A - Century

B - 200th ABC-200

C - Ringo's Favorite Numbers 2

D - Happy Birthday! 2

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