AtCoder Beginner Contest 239 E - Subtree K-th Max【Python】
https://atcoder.jp/contests/abc239/tasks/abc239_e
AtCoder ProblemsでDifficulty: 1084、Solve Probability: 10%でした。
解けませんでした。クエリのKの制約が20以下のため、部分木に含まれる頂点に書かれた数のリストの長さは20まで持っておけば良いという事に気づきませんでした。
import sys sys.setrecursionlimit(10 ** 7) N, Q = map(int, input().split()) X = list(map(int, input().split())) G = [[] for _ in range(N)] for i in range(N-1): a, b = map(int, input().split()) a-=1 b-=1 G[a].append(b) G[b].append(a) visited = [False]*N ans = [] for i in range(N): a = list() ans.append(a) def dfs(i): global ans visited[i] = True ans[i].append(X[i]) for i2 in G[i]: if not visited[i2]: dfs(i2) ans[i] += ans[i2] ans[i] = sorted(ans[i], reverse=True)[:20] dfs(0) for i in range(Q): v, k= map(int, input().split()) v-=1 k-=1 print(ans[v][k])
AtCoder Beginner Contest 212 D - Querying Multiset【Python】
https://atcoder.jp/contests/abc212/tasks/abc212_d
AtCoder ProblemsでDifficulty: 775、Solve Probability: 31%でした。
操作2の足された数の和を記録しておき、操作1でその和をXiから引いたものをheapqで管理、操作3ではその和をXiに足したものを取り出すようにしたところ解くことができました。
import heapq as hq Q = int(input()) q = [] sum_add = 0 for i in range(Q): query = list(map(int, input().split())) if query[0] == 1: hq.heappush(q, query[1] - sum_add) elif query[0] == 2: sum_add += query[1] else: print(hq.heappop(q) + sum_add)
AtCoder Beginner Contest 136 D - Gathering Children【Python】
https://atcoder.jp/contests/abc136/tasks/abc136_d
AtCoder ProblemsでDifficulty: 794、Solve Probability: 30%でした。
解けませんでした。
10**100回後の移動なので偶数マス離れたところにしか行けないという考え方は勉強になりました。
コードは以下のブログを参考にしました。
nemurin-blog.hatenablog.com
S = input() ans = [0] * len(S) right = 0 for i in range(len(S)-1): if S[i] == "R" and S[i+1] == "R": ans[i] = 0 right += 1 if S[i] == "R" and S[i+1] == "L": ans[i] = right // 2 + 1 ans[i+1] = right // 2 + right % 2 + 1 right = 0 left = 0 for i in range(len(S)-1, -1, -1): if S[i-1] == "L" and S[i] == "L": ans[i] = 0 left += 1 if S[i-1] == "R" and S[i] == "L": ans[i-1] += left // 2 + left % 2 ans[i] += left // 2 left = 0 print(*ans)
AtCoder Beginner Contest 189 D - Logical Expression【Python】
https://atcoder.jp/contests/abc189/tasks/abc189_d
AtCoder ProblemsでDifficulty: 769、Solve Probability: 32%でした。
動的計画法で解くことができましたが、思いつくのと実装に時間がかかってしまいました。
最近のABCでも桁DPなるもので解ける問題が出ていることもあるため、動的計画法全般について慣れていきたいです。
N = int(input()) S = [] for i in range(N): s = input() S.append(s) # dp[i][j]: 文字列Siまで見たときの状態がj(False or True)のときの数 dp = [[0] * 2 for _ in range(N + 1)] dp[0] = [1, 1] for i in range(1, N+1): if S[i-1] == "AND": # F∧T, F∧F, T∧F（1つ前のFからの遷移が2つ、1つ前のTからの遷移が1つ) dp[i][0] += dp[i-1][0] * 2 + dp[i-1][1] # T∧T（1つ前のTからの遷移が1つ) dp[i][1] += dp[i-1][1] else: # F∨F（1つ前のFからの遷移が1つ) dp[i][0] += dp[i-1][0] # F∨T, T∨F, T∨T（1つ前のFからの遷移が1つ、1つ前のTからの遷移が2つ) dp[i][1] += dp[i-1][0] + dp[i-1][1] * 2 print(dp[N][1])
AtCoder Beginner Contest 162 D - RGB Triplets【Python】
https://atcoder.jp/contests/abc162/tasks/abc162_d
AtCoder ProblemsでDifficulty: 757、Solve Probability: 33%でした。
先にR,G,Bそれぞれの数の累積和を求めて、i, jについて全探索してkについては累積和から条件に合う数を求めました。
解説を見たところ、R,G,Bそれぞれの数をかけたものから２つ目の条件のものを引けばよかったようです。
N = int(input()) S = input() sum_R = [0] sum_G = [0] sum_B = [0] for i in range(N): if S[i] == "R": sum_R.append(sum_R[i] + 1) sum_G.append(sum_G[i]) sum_B.append(sum_B[i]) elif S[i] == "G": sum_R.append(sum_R[i]) sum_G.append(sum_G[i] + 1) sum_B.append(sum_B[i]) else: sum_R.append(sum_R[i]) sum_G.append(sum_G[i]) sum_B.append(sum_B[i] + 1) ans = 0 for i in range(N): for j in range(i+1, N): s1 = S[i] s2 = S[j] ji_diff = j - i if (s1 == "R" and s2 =="G") or (s1 == "G" and s2 =="R"): ans += sum_B[N] - sum_B[j+1] # ２つ目の条件を満たすようにする if j + ji_diff < N: if S[j+ji_diff] == "B": ans -= 1 elif (s1 == "R" and s2 =="B") or (s1 == "B" and s2 =="R"): ans += sum_G[N] - sum_G[j+1] if j + ji_diff < N: if S[j+ji_diff] == "G": ans -= 1 elif (s1 == "G" and s2 =="B") or (s1 == "B" and s2 =="G"): ans += sum_R[N] - sum_R[j+1] if j + ji_diff < N: if S[j+ji_diff] == "R": ans -= 1 print(ans)
解説を見ての実装
N = int(input()) S = input() num_R = S.count("R") num_G = S.count("G") num_B = S.count("B") All = num_R * num_G * num_B ans = All for i in range(N): for j in range(i+1, N): s1 = S[i] s2 = S[j] if j + (j - i) >= N: continue k = j + (j - i) s3 = S[k] if s1 == s2: continue if s1 == s3: continue if s2 == s3: continue ans -= 1 print(ans)
AtCoder Beginner Contest 174 C - Repsept【Python】
https://atcoder.jp/contests/abc174/tasks/abc174_c
AtCoder ProblemsでDifficulty: 902、Solve Probability: 21%でした。
解けませんでした。
mod K後の値で考えると、同じ値が出るとループになり、そうでない場合は、K項目までには０が出てくるはずなのでK回探索すれば良いということのようです。
K = int(input()) a = [-1] * (10 ** 6 + 1) a[1] = 7 % K for i in range(2, K + 1): a[i] = (a[i-1] * 10 + 7) % K for i in range(1, K + 1): if a[i] == 0: print(i) exit() print(-1)
AtCoder Beginner Contest 180 D - Takahashi Unevolved【Python】
https://atcoder.jp/contests/abc180/tasks/abc180_d
AtCoder ProblemsでDifficulty: 752、Solve Probability: 34%でした。
始めにカコモンジムに可能な限り(強さの変化量がAtCoderジムのもの以下で、強さがY以下）通い、その後AtCoderジムに通うことができる回数を求めて解くことができました。
X, Y, A, B = map(int, input().split()) ans = 0 s = X # カコモンジムに通ったときの強さの変化量 kakomon = (A - 1) * s while kakomon < B and s + kakomon < Y: s += kakomon ans += 1 kakomon = (A - 1) * s if (Y - s) % B == 0: ans += (Y - s) // B - 1 else: ans += (Y - s) // B # 解説を見たところ場合分けしなくても良かった # ans += (Y - 1 - s) // B print(ans)
