AtCoder Beginners Contest 332 (ABC332) をPythonで解きました。
見やすいコードを書く練習も兼ねてます。
A - Online Shopping
問題
オンラインショップで、 $P_i$ 円の商品を $Q_i$ 個だけ購入します。 ( $1 \leq i \leq N$ )
送料は $K$ 円ですが、購入金額が $S$ 円以上なら送料は無料です。
いくらかかるでしょうか？
考察
$P_i$ 円の商品を $Q_i$ 個だけ購入すると、 $P_i \times Q_i$ 円かかります。
これをfor文を利用して、全商品に対して計算して、いくらかかるかを計算します。
その後、if文を用いて、その金額が $S$ 円未満であれば送料の $K$ 円をプラスします。
コード
N, S, K = map(int, input().split())
ans = 0
for _ in range(N):
p, q = map(int, input().split())
ans += p * q
if ans < S:
ans += K
print(ans)
B - Glass and Mug
問題
容量 $G$ mlのグラスと容量 $M$ mlのマグカップが1つずつあります。
指定された操作を $K$ 回行った後、グラスとマグカップの中に水がそれぞれ何ml入っていますか？
考察
問題文の操作がごちゃごちゃしているので、1つ1つ見ていきましょう。
- グラスが水で満たされているとき、すなわちグラスにちょうど $G$ ml 入っているとき、グラスの水をすべて捨てる。
- そうでなく、マグカップが空であるとき、マグカップを水で満たす。
- 上のいずれでもないとき、マグカップが空になるかグラスが水で満たされるまで、マグカップからグラスに水を移す。
以下、グラス・マグカップに入っている水の量をそれぞれ $g, m$ とします。
1つ目の条件はこう書けます。
"""グラスにちょうど G ml 入っているとき、グラスの水をすべて捨てる。"""
if g == G:
g = 0
2つ目の条件はこうです。
"""マグカップが空であるとき、マグカップを水で満たす。"""
elif m == 0:
m = M
3つ目の条件は、移動する水の量に注目すると、マグカップが空になるときは $m$ mlだけ移動して、グラスが水で満たされるときは $G-g$ mlだけ移動します。これの小さい方が実際に移動する水の量になるので、こう書けます。
"""マグカップが空になるかグラスが水で満たされるまで、マグカップからグラスに水を移す。"""
else:
move = min(G - g, m) # 移動する水の量
m -= move
g += move
これで操作1回分です。
この操作をfor文で $K$ 回だけ行えば正解できます。
コード
K, G, M = map(int, input().split())
g, m = 0, 0
for _ in range(K):
if g == G:
g = 0
elif m == 0:
m = M
else:
move = min(G - g, m)
m -= move
g += move
print(g, m)
C - T-shirts
問題
食事に行く日は無地Tシャツorロゴ付きTシャツを、競プロのイベントの日はロゴ付きTシャツを着ます。それ以外の日はすべてのTシャツを洗濯し、次の日にはそのTシャツはすべて使えます。
いくつロゴ付きTシャツを買えばいいですか？
考察
実際にシミュレートします。
何枚買えばいいかすぐには分かりませんが、シミュレートしている中でロゴ付きTシャツが足りなかったらその都度買うことにしてしまえば、最終的に必要なロゴ付きTシャツの数が分かります。
コード
N, M = map(int, input().split())
S = input()
ans = 0 # 購入したロゴTシャツの数
muji, logo = M, 0 # 洗濯済みの無地Tシャツ、ロゴ付きTシャツの数
for s in S:
match s:
case '0':
muji = M
logo = ans
case '1':
if muji > 0:
muji -= 1
elif logo > 0:
logo -= 1
else:
ans += 1
case '2':
if logo > 0:
logo -= 1
else:
ans += 1
print(ans)
D - Swapping Puzzle
問題
2つのグリッド $A, B$ が与えられます。
$A$ について、「隣り合った行を入れかえる」という操作を何回でもできます。列に関しても同様の操作が何回でもできます。
この操作をして、$A$ を $B$ に一致させられますか？一致させられるなら、そのときの操作の回数の最小値はいくつですか？
考察
$2 \leq H,W \leq 5$ とサイズがかなり小さいので、 $A$ を操作して得られるグリッドを全探索します。
行番号のリスト $(0,1, \cdots , H-1)$ と列番号のリスト $(0,1,\cdots W-1)$ を用意します。
たとえば、 $0$ 行目と $1$ 行目をスワップしたとき、行番号のリストは $(0,1,2,3,4)$ から $(1, 0, 2, 3, 4)$ になるとします。列番号のリストに関しても同様です。
この順列を全探索します。
順列全探索は itertools.permutations() が便利です。(使い方は下のコードを参考にしてね)
行番号・列番号のリストから操作後の $A$ を復元し、 $B$ と一致するかどうかを確認します。
もし一致していたら、何度スワップすれば行番号・列番号のリストを得られるのかを計算します。
これは転倒数を計算すればいいというのが典型です。
転倒数とは
数列 $P=(P_1, P_2, \cdots P_N)$ の転倒数は、 $ 1 \leq i < j \leq N$ かつ $P_i > P_j$ を満たす $(i,j)$ の数です。たとえば、$(0,1,4,2,3)$ は、 $4>2, 4>3$ の部分があるので、転倒数は $2$ になります。
コード
from itertools import permutations
# 操作回数(転倒数を計算する)
def move_cnt(tup):
n = len(tup)
result = 0
for i in range(n - 1):
for j in range(i + 1, n):
if tup[i] > tup[j]:
result += 1
return result
H, W = map(int, input().split())
A = [list(map(int, input().split())) for _ in range(H)]
B = [list(map(int, input().split())) for _ in range(H)]
ans = 1000
for i_perm in permutations(range(H), H):
for j_perm in permutations(range(W), W):
C = [[A[i][j] for j in j_perm] for i in i_perm] # 操作後のA
if C == B:
ans = min(ans, move_cnt(i_perm) + move_cnt(j_perm))
if ans == 1000:
ans = -1
print(ans)