パナソニックプログラミングコンテスト(AtCoder Beginner Contest 195)をPythonで解く-Shinoryo's Weblog

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

こんにちは, Shinoryoです.

今回はパナソニックプログラミングコンテスト(AtCoder Beginner Contest 195)を, Pythonで解いてみた結果を書き連ねていこうと思います.

1A - Health M Death
2B - Many Oranges
3C - Comma
4D - Shipping Center
5E以降
6参考にしたサイト等
7脚注

A - Health M Death

条件を書いてif文で分岐させれば問題ないです.

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

	# 出力
	if H % M == 0:
	print("Yes")
	else:
	print("No")

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

B - Many Oranges

最も少ない個数 $lower$ は, $B$ グラムのみかんで $W$ キログラム以上となるようにし, オーバーした分はより軽いみかんに置き換えることで得られます. 具体的には, $1000 W / B$ の小数点以下を切り上げることによって得られます.

最も多い個数 $upper$ は, $A$ グラムのみかんで $W$ キログラム以下となるようにし, 足りない分はより重いみかんに置き換えることで得られます. 具体的には, $1000 W / A$ の小数点以下を切り捨てることによって得られます.

切り上げ, 切り捨ての計算は, mathモジュールのceil()(切り上げ), floor()(切り捨て)を用いると楽です. 整数int型が返されます.

なお, $lower > upper$ の場合は, オーバーした分はより軽いみかんに置き換えても $W$ キログラムにならない場合に相当します.

	import math

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

	# lower(最も少ない個数)は、BグラムのみかんでWキログラム以上となるようにし、
	# オーバーした分はより軽いみかんに置き換えることで得られる
	lower = math.ceil(1000 * W / B)

	# upper(最も多い個数)は、AグラムのみかんでWキログラム以下となるようにし、
	# 足りない分はより重いみかんに置き換えることで得られる
	upper = math.floor(1000 * W / A)

	# もしupper < lowerなら、置き換えることができない
	# それを踏まえて出力する
	if upper < lower:
	print("UNSATISFIABLE")
	else:
	print(lower,upper)

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

C - Comma

一般に, $10^{3 i}$ から $10^{3 (i + 1)} - 1$ までのコンマの数は,

\begin{aligned} (1) & {ans}_{i} & = (10^{3 (i + 1)} - 10^{3 i}) \times i \end{aligned}

で得られます^*1. $N$ の桁数 $D$ に関して, $D - 1$ を $3$ で割った商を $A$ とすると, $1$ から $A$ までの $i$ に関して ${ans}_{i}$ を合計することによって, $1$ から $10^{3 A} - 1$ までのコンマの数を得ることができます. $10^{3 A}$ からのコンマの数は, 別に求める必要があります.

$A = 0, 1$ の場合も, range()の性質から, 同様のコードで求めることができます.

	# 入力(文字列型)
	N_str = input()

	# 10の何乗オーダーかを3で割った商
	N_len_3 = (len(N_str) - 1) // 3

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

	# 10^(3*N_len_3) - 1以下のコンマの数を調査
	for i in range(1, N_len_3):
	ans += (10*(3(i+1)) - 10*(3i)) * i

	# 10^(3*N_len_3)以上のコンマの数を調査
	if N_len_3 > 0:
	ans += (int(N_str) - 10*(3N_len_3) + 1) * N_len_3

	# 出力
	print(ans)

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

D - Shipping Center

価値の大きい荷物から順に, できる限り容量の小さい箱に詰めていくことで, 荷物の価値の合計が最大になります.

価値の大きい荷物から順に調べていく際に, $W$ と $V$ の値を格納した2次元配列を, $V$ の大きい順にソートする必要が出てくるかと思います. 多次元リストのソートでは, 1番目の値から順に比較されますので, $V$ の値を先頭にしておいた方が楽でしょう^*2.

下のコードでは, すでに荷物を入れた箱を, 使える箱のリストから除外するにあたって, del文を使用しています. もちろん, インデックスでスライスして上書きしても構わないと思います.

	# 入力
	N, M, Q = [int(x) for x in input().split()]
	VWmatrix = []
	for _ in range(N):
	Wi, Vi = [int(x) for x in input().split()]
	VWmatrix.append([Vi, Wi])
	X = [int(x) for x in input().split()]

	# VWmatrixをVの大きい順にソート
	VWmatrix.sort(reverse = True)

	# 各クエリに対してループ
	for query in range(Q):

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

	# L, Rを入力
	L, R = [int(x) for x in input().split()]

	# Xから使えないものを除外
	newX = X[:(L-1)] + X[R:]

	# 全ての荷物iに対してループ(Vの高い順に)
	for i in range(N):

	# 荷物iが入る最小の箱を探す
	# 使用する変数を用意
	minbox_size = 10**6 + 1
	minbox_number = None
	# newXの要素に対してループ(indexも欲しいのでこのように)
	for j in range(len(newX)):
	# 荷物iが入るかつ今までのものより小さいならば、上の変数に格納
	if newX[j] >= VWmatrix[i][1] and minbox_size > newX[j]:
	minbox_size = newX[j]
	minbox_number = j

	# 荷物が入ったら……
	if minbox_number != None:
	# ansに荷物iの価値を加える
	ans += VWmatrix[i][0]
	# newXからminbox_numberを除外
	del newX[minbox_number]

	# 答えを出力
	print(ans)

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

E以降

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

参考にしたサイト等

「解説 - パナソニックプログラミングコンテスト(AtCoder Beginner Contest 195)」
Editorial - Panasonic Programming Contest (AtCoder Beginner Contest 195)
AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.
nkmk様による「Pythonで小数点以下を切り捨て・切り上げ: math.floor(), math.ceil()」
Pythonで小数点以下を切り捨て・切り上げ: math.floor(), math.ceil() | note.nkmk.me
Pythonで浮動小数点数floatの小数点以下を切り捨て・切り上げするには, 標準ライブラリmathモジュールのfloor(), ceil()を使う. math.floor() --- 数学関数 — Python 3.8.1rc1 ドキュメント math.ceil() --- 数学関数 — Python 3.8.1rc1 ドキュメントここでは以下の内容について説明する. 小数点以下を切り捨て: math.fl...
nkmk様による「Pythonでリスト（配列）の要素を削除するclear, pop, remove, del」
Pythonでリスト（配列）の要素を削除するclear, pop, remove, del | note.nkmk.me
Pythonでlist型のリスト（配列）の要素を削除するには, リストのメソッドclear(), pop(), remove()を使う. そのほか, インデックスやスライスで位置・範囲を指定してdel文で削除する方法もある. すべての要素を削除: clear() 指定した位置の要素を削除し, 値を取得: pop() 指定した値と同じ要素を検索し, 最初の要素を削除:...

脚注

*1 : $10^{3 i}$ から $10^{3 (i + 1)} - 1$ までの自然数には, それぞれ $i$ 個のコンマがつくということを表した式になります. 例えば, $1, 000$ から $999, 999$ までの自然数には, コンマが $1$ 個つきます. $1, 000, 000$ から $999, 999, 999$ までの自然数には, コンマが $2$ 個つきます.

*2 :APG4bのEX-22に, 多次元配列のソートに関連した問題があります.

パナソニックプログラミングコンテスト(AtCoder Beginner Contest 195)をPythonで解く

A - Health M Death

B - Many Oranges

C - Comma

D - Shipping Center

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