AtCoder APG4bをPythonで解く(Ex19~21)-Shinoryo's Weblog

こんにちは, Shinoryoです.

今回はC++入門 AtCoder Programming Guide for beginners(APG4b)を, Pythonで無理やり解いてみた結果を書き連ねていこうと思います.

EX19 - 九九の採点

前提として, 「Pythonでは関数への引数は全て参照渡しされます」が, 「変数の型によって, 関数内で受けた変更が関数外で保存されるかどうかが変わります」.

この問題では, 関数内で受けた変更が関数外で保存されるmutable型を使うことによって, 記述することを考えます. 問題文でのプログラムと異なり, int型の変数「correct_count」「wrong_count」をまとめてリストにすることによって, プログラムを完成させることができます.

	def saiten(a, correct_wrong_count):
	for i in range(9):
	for j in range(9):
	if a[i][j] != (i+1)*(j+1):
	a[i][j] = (i+1)*(j+1)
	correct_wrong_count[1] += 1
	else:
	correct_wrong_count[0] += 1

	a = [[int(x) for x in input().split()] for _ in range(9)]

	correct_wrong_count = [0, 0]

	saiten(a, correct_wrong_count)

	for i in range(9):
	for j in range(9):
	if j < 8:
	print(a[i][j], end=" ")
	else:
	print(a[i][j])

	print(correct_wrong_count[0])
	print(correct_wrong_count[1])

問題にあるプログラムをPythonで書き直すと以下のようになるでしょうか.

	def count_report_num(children, x):
	# プログラムをここに書く

	n = int(input())

	# 各組織の親組織を示す配列 0番組織の親組織は存在しないので-1を入れておく
	p = [-1] + [int(x) for x in input().split()]

	# 組織の関係から2次元配列を作る
	children = [[] for _ in range(n)] # ある組織の子組織の番号一覧
	for i in range(1,n):
	children[p[i]] += [i] # parentの子組織一覧にi番を追加

	#各組織について, 答えを出力
	for i in range(n):
	print(count_report_num(children, i))

「count_report_num(children, x)」は, 組織番号xの子組織一覧children[x]をもとに, 提出する報告書の枚数を計算する関数です.

再帰関数を利用して報告書の枚数を求めます.

	def count_report_num(children, x):
	if len(children[x]) == 0:
	return 1

	sum = 0
	for j in children[x]:
	sum += count_report_num(children, j)
	sum += 1
	return sum

	n = int(input())

	# 各組織の親組織を示す配列 0番組織の親組織は存在しないので-1を入れておく
	p = [-1] + [int(x) for x in input().split()]

	# 組織の関係から2次元配列を作る
	children = [[] for _ in range(n)] # ある組織の子組織の番号一覧
	for i in range(1,n):
	children[p[i]] += [i] # parentの子組織一覧にi番を追加

	#各組織について, 答えを出力
	for i in range(n):
	print(count_report_num(children, i))

問題にあるプログラムをPythonで書き直すと以下のようになるでしょうか.

各関数における時間計算量は, 次のように計算されます.

ゆえに, 消すべきは「a4 = f4(n)」になります. しかし, Pythonでは計算が重いからかTLEになってしまいました.