A: Online Shopping
問題文の通りに実装します。
コード
N, S, K = map(int, input().split())
cost = 0
for _ in range(N):
p, q = map(int, input().split())
cost += p * q
if cost >= S:
print(cost)
else:
print(cost+K)
B: Glass and Mug
問題文に従って丁寧に実装していきます。
まずはグラスに入っている水の量とマグカップに入っている水の量を表す変数gcとmcを用意します。操作を順番に見ていきます。
1: グラスが水で満たされているとき、すなわちグラスにちょうど
G ml 入っているとき、グラスの水をすべて捨てる。
コード
if gc == G:
gc = 0
2: そうでなく、マグカップが空であるとき、マグカップを水で満たす。
コード
elif mc == 0:
mc = M
3: 上のいずれでもないとき、マグカップが空になるかグラスが水で満たされるまで、マグカップからグラスに水を移す。
マグカップが空になるということは、今のマグカップの水量とグラスの水量を足してもグラスが水で満たされないということです。
その場合は、グラスにマグカップの水量を足してマグカップの水量を０にします。
グラスが先に満たされる場合は、グラスがいっぱいになるまでに必要な水量(G-今の水量)だけマグカップから注ぎます。
コード
else:
if mc + gc < G:
gc += mc
mc = 0
else:
mc = mc - (G-gc)
gc = G
これをk回繰り返します。まとめたコードが下記のものです。
コード
K, G, M = map(int, input().split())
gc = 0
mc = 0
for i in range(K):
if gc == G:
gc = 0
elif mc == 0:
mc = M
else:
if mc + gc < G:
gc += mc
mc = 0
else:
mc = mc - (G-gc)
gc = G
print(gc, mc)
C: T-shirts
0の日には全てのシャツが洗濯されるので、日程を0の日で区切ってそれぞれの区間を考えます。
具体的には、
[1,1,2,0,1,1,0,1,2,2,2,1,0,1]
を
[[1,1,2], [1,1], [1,2,2,2,1], [1]]
のように分割して考えます。
このようにすると、各区間で必要になるロゴ入りTシャツの枚数の最大値を取れば答えが求められます。
必要なTシャツの枚数は、「１の日数-持っている無地Tシャツの枚数」+「２の日数」です。持っている無地Tシャツの枚数が１の日数より多い場合は２の日数だけ考えればよいことに注意します。
コード
def split_list_by_zero(input_list):
result = []
sublist = []
for value in input_list:
if value == "0":
if sublist: # Check if the sublist is not empty
result.append(sublist)
sublist = [] # Reset the sublist
else:
sublist.append(value)
if sublist: # Append the last sublist if not empty
result.append(sublist)
return result
def main():
N, M = map(int, input().split())
S = list(input())
li = split_list_by_zero(S)
ans = 0
for i in li:
one = i.count("1")
two = i.count("2")
one_needs = max(one-M, 0)
needs = two+one_needs
ans = max(ans, needs)
print(ans)
main()
D: Swapping Puzzle
制約がとても小さいので、それぞれ列と行を入れ替えてできる盤面を全探索できそうです。
好きな行同士、列同士を入れ替えることが可能なことに注意します。
まずは可能な列の並べなおし方、行の並べなおし方を列挙します。itertoolsのpermutationsを使うと簡単に書くことができます。
例えば、行(H)の並べ方は
list(permutations(range(H)))
で列挙ができます。
リストの中身はイミュータブルなタプル型なことに注意します。
行の並べ方と列の並べ方のペアを全探索します。共に最悪で$5!$通りの並べ方があるので、ペアは$(5!)^2=14400$通りできます。十分に全探索可能です。
盤面が一致した場合、その盤面にするのに最低で何手必要かを計算します。
これは並び替えられたリストの要素を何回入れ替えればもとのリストに戻るのか考えると、ある要素の右にあってその要素より小さいものは必ず入れ替えなければいけないので、そのような要素の数を数えることによって計算できます。
これは一般に転倒数と呼ばれ、このブログが参考になります。ちなみにこの問題を解くのに$O(N^2)$のコードをお借りしています。
列と行で最低何回入れ替える必要があるのか計算して足し、それらの最小値を求めれば答えです。
コード
def InversionNumberByBubleSort(A):
ans = [] #転倒数
for i in range(len(A)):
for j in range(len(A) - i - 1):
#左側の方が小さい場合
if A[j] > A[j + 1]:
ans.append((A[j], A[j+1]))
A[j], A[j + 1] = A[j + 1], A[j]
return len(ans)
from itertools import permutations
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)]
h_perm = list(permutations(range(H)))
w_perm = list(permutations(range(W)))
ans = 10**18
for h in h_perm:
for w in w_perm:
flag = True
for r in range(H):
for c in range(W):
if A[r][c] != B[h[r]][w[c]]:
flag = False
if flag:
ans = min(ans, InversionNumberByBubleSort(list(h))+InversionNumberByBubleSort(list(w)))
print(ans if ans != 10**18 else -1)
別解でBFSを使うこともできます。