問題はこちら
4完
A
愚直実装
N = int(input())
A = list(map(int, input().split()))
result = []
for i in range(N-1):
result.append(A[i]*A[i+1])
print(*result)
B
条件を満たす文字列があると仮定したとき、その文字列が12文字以上であれば "wbwbwwbwbwbw" を含む。
それを取り除いたあとの文字列を考えることで少ない探索回数で答えを求められると考えた。
W, B = list(map(int, input().split()))
Q = (W+B)//12
W -= 7*Q
B -= 5*Q
S = "wbwbwwbwbwbw" + "wbwbwwbwbwbw"
flag = "No"
for i in range(len(S)):
for j in range(i,len(S)):
t = S[i:j+1]
if t.count("w") == W and t.count("b") == B:
flag = "Yes"
print(flag)
C
Setを使って重複を取り除く。
Bのほうが難しいと感じた。
PythonのSetやDictでは悪意のあるケースで極端に遅くなる場合があるらしいので、注意する必要があるとのこと。
https://atcoder.jp/contests/abc346/editorial/9635
N, K = list(map(int, input().split()))
A = list(map(int, input().split()))
numbers_set = set(A)
numbers_set = {x for x in numbers_set if x <= K}
sum_set = sum(numbers_set)
sum_from_1_to_K = K*(K+1)//2
print(sum_from_1_to_K - sum_set)
D
初めてDPを通すことができた。
下記のように事象を分けて、それぞれ遷移するときのコストの増分などを考えた。
（解説のように事象を分けるほうが汎用的で賢いと思う）
事象0 : dp[i][0]:0から始まり、i文字目まで01の繰り返しになっているときのコスト（悪い文字列）
事象1 : dp[i][1]:1から始まり、i文字目まで10の繰り返しになっているときのコスト（悪い文字列）
事象2 : dp[i][2]:0から始まり、i文字目までで良い文字列となっているときのコスト
事象3 : dp[i][3]:1から始まり、i文字目までで良い文字列となっているときのコスト
N = int(input())
S = "-" + input()
C = ["-"] + list(map(int, input().split()))
import numpy as np
dp = [[ np.inf for _ in range(4)]]
if S[1] == "0":
dp.append([0, C[1], np.inf, np.inf])
else:
dp.append([C[1], 0, np.inf, np.inf])
def func1(n_i, str_i, C_):
"""
偶数番目なら1、奇数番目なら0にするときのコストを返す関数
"""
if n_i %2 == 0:
if str_i == "0":
return C_[n_i]
if str_i == "1":
return 0
elif n_i %2 == 1:
if str_i == "0":
return 0
if str_i == "1":
return C_[n_i]
return ValueError
def func2(n_i, str_i, C_):
"""
偶数番目なら0、奇数番目なら1にするときのコストを返す関数
"""
if n_i %2 == 0:
if str_i == "0":
return 0
if str_i == "1":
return C_[n_i]
elif n_i %2 == 1:
if str_i == "0":
return C_[n_i]
if str_i == "1":
return 0
return ValueError
for i in range(2,N+1):
cost1 = func1(i, S[i], C)
cost2 = func2(i, S[i], C)
cost3 = func2(i, S[i], C)
cost4 = func1(i, S[i], C)
cost5 = func2(i, S[i], C)
cost6 = func1(i, S[i], C)
temp = [
dp[-1][0] + cost1,
dp[-1][1] + cost2,
min(dp[-1][0] + cost3, dp[-1][2] + cost5),
min(dp[-1][1] + cost4, dp[-1][3] + cost6)
]
dp.append(temp)
print(min(dp[-1][2], dp[-1][3]))
E
解説AC
後ろから考えることで効率的に考えられる。
また実際のグリッドではなく、未処理の行・列数を管理することで効率的に計算できる。
H, W, M = list(map(int, input().split()))
T, A, X = [[],[],[]]
for _ in range(M):
t, a, x = list(map(int, input().split()))
T.append(t)
A.append(a-1)
X.append(x)
dict_result = {0:0}
for x in set(X):
dict_result[x] = 0
done_rows = [False for _ in range(H)]
done_cols = [False for _ in range(W)]
not_done_rows = H -sum(done_rows)
not_done_cols = W -sum(done_cols)
for m in range(M-1, -1, -1):
t,a,x = T[m], A[m], X[m]
if t == 1:
if not done_rows[a]:
dict_result[x] += not_done_cols
done_rows[a] = True
not_done_rows -= 1
if t == 2:
if not done_cols[a]:
dict_result[x] += not_done_rows
done_cols[a] = True
not_done_cols -= 1
dict_result[0] += not_done_rows * not_done_cols
result = {k: v for k, v in dict_result.items() if v != 0}
print(len(result))
for k,v in sorted(result.items()):
print(k, v)
F
