問題はこちら
4完
A
愚直実装
N = int(input()) # S = 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())) # N, K = [2*10**5, 2*10**9] # A = list(range(1,2*10**5+1)) numbers_set = set(A) # K以上の要素を除去する 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() # Indexとi文字目をそろえる C = ["-"] + list(map(int, input().split())) # Indexとi文字目をそろえる # print(S,C) import numpy as np dp = [[ np.inf for _ in range(4)]] # print(dp) # 1文字目の処理 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 # これが返ってくるときはエラー # 2文字目以降の処理 for i in range(2,N+1): ## 各遷移のコストを求める # 遷移1：悪01→悪01 cost1 = func1(i, S[i], C) # 遷移2：悪10→悪10 cost2 = func2(i, S[i], C) # 遷移3：悪01→良01 cost3 = func2(i, S[i], C) # 遷移4：悪10→良01 cost4 = func1(i, S[i], C) # 遷移5：良01→良01 cost5 = func2(i, S[i], C) # 遷移6：良01→良01 cost6 = func1(i, S[i], C) ## dpの結果を求める 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) ] # appendする用の文字列 dp.append(temp) print(min(dp[-1][2], dp[-1][3]))
E
解説AC
後ろから考えることで効率的に考えられる。
また実際のグリッドではなく、未処理の行・列数を管理することで効率的に計算できる。
H, W, M = list(map(int, input().split())) T, A, X = [[],[],[]] # input for _ in range(M): t, a, x = list(map(int, input().split())) T.append(t) A.append(a-1) X.append(x) # print(grid) # 何色が何マスあるか管理する 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 # valueが0でないものを取り出す 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
