ユニークビジョンプログラミングコンテスト2024 春（AtCoder Beginner Contest 346）振り返り
はじめに振り返り
一度ミスはあったものの、スムーズに A~E の5問解けた。ミスも防げたミスだったように感じているので、ちょっと悔しい。 F はなんとなく解き方は想像できたものの、すぐに正しい実装までたどり着くことができなかったので練習あるのみですね。
A - Adjacent Product
問題の指示通り出力すればOK。A の配列の最後の一つ前まで走査して結果を計算して出力する形に。
#!/usr/bin/env python3 import sys def solve(N: int, A: "List[int]"): result = [] for i in range(N-1): result.append(A[i] * A[i+1]) print(" ".join([str(x) for x in result])) return def main(): def iterate_tokens(): for line in sys.stdin: for word in line.split(): yield word tokens = iterate_tokens() N = int(next(tokens)) # type: int A = [int(next(tokens)) for _ in range(N)] # type: "List[int]" solve(N, A) if __name__ == '__main__': main()
B - Piano
難しく考えて地味に時間をかけてしまった。白鍵 と黒鍵の数は繰り返しになるので、辞書配列で保持してアップデートする形に。 解説でもあったが、入力が W も B も 100 程度なので、文字列展開したうえで、1オクターブ分ループするだけで良さそう。
#!/usr/bin/env python3 import sys import math from collections import Counter YES = "Yes" # type: str NO = "No" # type: str def solve(W: int, B: int): length = W + B blocks = math.ceil(length / 12) s = "wbwbwwbwbwbw" S = s * 2 div, mod = divmod((length - 1), 12) left = 0 right = mod count_w = 7 * div count_b = 5 * div count_mod = Counter(S[:right+1]) for k, v in count_mod.items(): if k == "w": count_w += v else: count_b += v if count_w == W and count_b == B: print(YES) return for i in range(1, 12): left_c = S[(left+i-1)%12] if left_c == "w": count_w -= 1 else: count_b -= 1 right_c = S[(right+i)%12] if right_c == "w": count_w += 1 else: count_b += 1 if count_w == W and count_b == B: print(YES) return print(NO) return def main(): def iterate_tokens(): for line in sys.stdin: for word in line.split(): yield word tokens = iterate_tokens() W = int(next(tokens)) # type: int B = int(next(tokens)) # type: int solve(W, B) if __name__ == '__main__': main()
C - Σ
1~ K のうち、数列 A に含まれない整数の合計値を計算せよというもの。 1~K の合計値を先に計算しておき、数列 A をひと通り見て、 1~K に含まれるものの場合は合計値から差し引くことで対応
#!/usr/bin/env python3 import sys def solve(N: int, K: int, A: "List[int]"): total = K*(1+K)//2 passed = set() for a in A: if a > K: continue if a in passed: continue passed.add(a) total -= a print(total) return def main(): def iterate_tokens(): for line in sys.stdin: for word in line.split(): yield word tokens = iterate_tokens() N = int(next(tokens)) # type: int K = int(next(tokens)) # type: int A = [int(next(tokens)) for _ in range(N)] # type: "List[int]" solve(N, K, A) if __name__ == '__main__': main()
D - Gomamayo Sequence
0 と 1 からなる文字列が与えられ、 0 か 1 が2文字並ぶ部分が1つだけ含まれるような文字列を作るためのコストの最小値を計算するといったもの。
- 最後の値が 0 で、まだ2文字の並びを作れていない
- 最後の値が 0 で、すでに並びを作れている
- 最後の値が 1 で、まだ2文字の並びを作れていない
- 最後の値が 1 で、すでに並びを作れている
の４つのパターンに分けて状態遷移させ、最小値を計算するようにした。
文字列を走査したとき、"今の値を変更するか" 次第でコストを追加する必要があるか分かれるだけで、状態遷移は同じになる。なので、分岐の部分はもう少しシンプルに書けそう。
#!/usr/bin/env python3 import sys def solve(N: int, S: str, C: "List[int]"): dp = [[float('inf')] * 4 for _ in range(N)] s = S[0] if s == "0": dp[0][0] = 0 dp[0][2] = C[0] else: dp[0][0] = C[0] dp[0][2] = 0 for i in range(1, N): s = S[i] if s == "0": dp[i][0] = dp[i-1][2] dp[i][1] = min(dp[i-1][0], dp[i-1][3]) dp[i][2] = dp[i-1][0] + C[i] dp[i][3] = min(dp[i-1][1], dp[i-1][2]) + C[i] else: dp[i][0] = dp[i-1][2] + C[i] dp[i][1] = min(dp[i-1][0], dp[i-1][3]) + C[i] dp[i][2] = dp[i-1][0] dp[i][3] = min(dp[i-1][1], dp[i-1][2]) print(min(dp[N-1][1], dp[N-1][3])) return def main(): def iterate_tokens(): for line in sys.stdin: for word in line.split(): yield word tokens = iterate_tokens() N = int(next(tokens)) # type: int S = next(tokens) # type: str C = [int(next(tokens)) for _ in range(N)] # type: "List[int]" solve(N, S, C) if __name__ == '__main__': main()
E - Paint
１行もしくは、１列同じ色で塗る操作を繰り返して、最後に残った色と個数を答えるもの。 最終的に塗った色で上書きされていくので、色の塗り順を逆から見ていき、色を塗る際にはまだ塗られていないマスの個数を数えることで解決した。
最初、連想配列ではなくただの配列で記録していってしまい、逆順に見て色を塗った時点で確定としてしまっており、同じ色のマス目を結果として合計できずに WA になってしまった。
#!/usr/bin/env python3 import sys from collections import defaultdict def solve(H: int, W: int, M: int, T: "List[List[int]]"): passed_row = set() passed_col = set() total = H * W result = defaultdict(int) result[0] = total for t, a, x in reversed(T): if t == 1: if a in passed_row: continue passed_row.add(a) res = W - len(passed_col) if res: result[0] -= res result[x] += res else: if a in passed_col: continue passed_col.add(a) res = H - len(passed_row) if res: result[0] -= res result[x] += res for_print = [] for k, v in sorted(result.items()): if v == 0: continue for_print.append((k, v)) print(len(for_print)) for k, v in for_print: print(k, v) return def main(): H, W, M = list(map(int, input().strip().split())) T = [] for _ in range(M): T.append(list(map(int, input().strip().split()))) solve(H, W, M, T) if __name__ == '__main__': main()
