Panasonic Programming Contest (AtCoder Beginner Contest 186)をPythonで解く-Shinoryo's Weblog

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

こんにちは, Shinoryoです.

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

1A - Brick
2B - Blocks on Grid
3C - Unlucky 7
4D - Sum of difference
5E以降
6参考にしたサイト等

A - Brick

$N$ を $W$ で割った商を出力すればよいです.

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

	# 出力
	print(N // W)

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

B - Blocks on Grid

2次元配列 $A$ の最小値を求め, 2次元配列 $A$ の各成分からその最小値を差し引いた残差を全て足し合わせればよいです.

下の例では, 多次元リストを1次元に平坦化するためにitertools.chain.from_iterable()を用いています. 単に2次元配列をmin()の引数にとるだけでは, list型の和になってしまいます.

	import itertools

	# 入力
	H, W = [int(x) for x in input().split()]
	Amatrix = [[int(x) for x in input().split()] for _ in range(H)]

	# Amatrixの最小値を求める
	# itertools.chain.from_iterableで1次元化
	minA = min(itertools.chain.from_iterable(Amatrix))

	# 各々のマスで取り除くべきブロックの数を計算する
	Amatrix_remain = [[Amatrix[i][j] - minA for j in range(W)] for i in range(H)]

	# Amatrix_remainの合計を求める
	# itertools.chain.from_iterableで1次元化
	print(sum(itertools.chain.from_iterable(Amatrix_remain)))

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

C - Unlucky 7

Pythonには数値を8進数の文字列に変換できる関数oct()があるので, それをありがたく使わせていただこうと思います.

	# 入力
	N = int(input())

	# 答えの格納
	ans = 0

	# 7チェック
	for i in range(1, N+1):
	if ("7" not in str(i)) and ("7" not in oct(i)):
	ans += 1

	# 答えを出力
	print(ans)

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

oct()を使わないのだとすれば, 定義に則って10進数を8進数に変換することになります. 関数化した方が楽だと思います.

	# 8進数に変換する関数(int型を受け取ってstr型を返す)
	def to_oct(n):
	# 8進数に変換した文字列を記録していく
	s = ""
	while(n):
	# 下の位から順に8で割った余りを計算していく
	s = str(n % 8) + s
	n //= 8
	return s

	# 入力
	N = int(input())

	# 答えの格納
	ans = 0

	# 7チェック
	for i in range(1, N+1):
	if ("7" not in str(i)) and ("7" not in to_oct(i)):
	ans += 1

	# 答えを出力
	print(ans)

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

D - Sum of difference

この結果は $A_{1}, \dots, A_{N}$ の順序に依存しないので, ソートして並べ替えてしまってよいです. $A_{1} \leq \dots \leq A_{N}$ とすれば, $| A_{i} - A_{j} | = A_{j} - A_{i}$ になります.

まずぱっと思いつくのは, 律儀に全パターン計算する方法です. しかし, この方法だと $O (N^{2})$ となり, TLE.

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

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

	# 全場合を足していく
	for i in range(N-1):
	for j in range(i+1,N):
	ans += A[j] - A[i]

	# 答えを出力
	print(ans)

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

そこで, 若干工夫をします. 求めるのは

\begin{array}{r} (1) & \sum_{i = 1}^{N - 1} \sum_{j = i + 1}^{N} | A_{i} - A_{j} | \end{array}

ですが, $A_{1} \leq \dots \leq A_{N}$ とできることを利用すれば,

\begin{aligned} \sum_{i = 1}^{N - 1} \sum_{j = i + 1}^{N} | A_{i} - A_{j} | & = \sum_{i = 1}^{N - 1} \sum_{j = i + 1}^{N} (A_{j} - A_{i}) \\ = \sum_{i = 1}^{N - 1} (\sum_{j = i + 1}^{N} A_{j} - A_{i} \sum_{j = i + 1}^{N}) \\ (2) & = \sum_{i = 1}^{N - 1} (\sum_{j = i + 1}^{N} A_{j} - (N - i) A_{i}) \end{aligned}

となります. $\sum_{j = i + 1}^{N} A_{j}$ はあらかじめ累積和を $O (N)$ で求めておくことで対応できます. これを用いることで, (ソートでかかる時間計算量を考慮して) $O (N \log N)$ でできます.

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

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

	# Aの累積和を格納する配列
	Aruiseki = [[] for _ in range(N)]

	# Aの累積和を計算しておく
	Aruiseki[N-1] = A[N-1]
	for i in range(N-2,-1,-1):
	Aruiseki[i] = Aruiseki[i+1] + A[i]

	# Aの累積和を利用して計算する
	# 配列のindexに注意
	for i in range(N-1):
	ans += Aruiseki[i+1] - (N - i - 1) * A[i]

	# 答えを出力
	print(ans)

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

E以降

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

参考にしたサイト等

「解説 - Panasonic Programming Contest (AtCoder Beginner Contest 186)」
Editorial - Panasonic Programming Contest (AtCoder Beginner Contest 186)
AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.
nkmk様による「Pythonでflatten（多次元リストを一次元に平坦化）」
Pythonでflatten（多次元リストを一次元に平坦化） | note.nkmk.me
Pythonで多次元のリスト（リストのリスト, ネストしたリスト）を一次元に平坦化する方法について説明する. 2次元のリストを平坦化itertools.chain.from_iterable()sum()処理速度の差 itertools.chain.from_iterable() sum() 処理速度の差 3次元以上のリストや不規則なリストを平坦化 NumPy配列ndarrayの場合はflatten()また...
nkmk様による「Pythonで2進数, 8進数, 16進数の数値・文字列を相互に変換」
Pythonで2進数, 8進数, 16進数の数値・文字列を相互に変換 | note.nkmk.me
Pythonでは通常の10進数だけでなく2進数, 8進数, 16進数として数値や文字列を扱うことができる. 相互に変換するのも簡単. ここでは, 以下の内容についてサンプルコードとともに説明する. 整数を2進数, 8進数, 16進数で記述数値を2進数, 8進数, 16進数表記の文字列に変換組み込み関数bin(), oct(), hex()組み込み関数format...
bluepost59様による「リストから和のリストを得る（累積和）」
リストから和のリストを得る（累積和） - Qiita
はじめに数値計算をしていると, 積分のために総和を取ることはよくある. たとえば, 物理でメッシュごとの電場のデータからポテンシャルを求めるには, 総和を取ってメッシュ幅をかける. リストAがあるとして, 総和を取るだけならsum(A...
nkmk様による「Pythonのrange関数の使い方」
Pythonのrange関数の使い方 | note.nkmk.me
Pythonで連番や等差数列を生成してfor文で使ったり, それらのリストを取得するには, range()を使う. 組み込み関数: range() — Python 3.7.2 ドキュメントここでは以下の内容について説明する. Python2とPython3でのrange()の違いPython2のrange()とxrange()Python3のrange() Python2のrange()とxrange() Python3のrange()...

Panasonic Programming Contest (AtCoder Beginner Contest 186)をPythonで解く

A - Brick

B - Blocks on Grid

C - Unlucky 7

D - Sum of difference

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