AtCoder Beginner Contest 349 振り返り
はじめにスコア
２週間ぶりのコンテスト。 A~D までの 4完で、E も大きなずれない方針をたてれて、自分の成長を感じられて嬉しかった。
A - Zero Sum Game
まず問題を最初読んだときなんだか難しく感じて、何度も問題を読み返した。要は 1~N 人で ゼロサムゲームをするのだけれど、最終的な 1~N-1 番目の人の得点がわかったときに N 番目の人の得点を答えよというもの。
全員でゼロサムゲームを行っており、全員の得点を合わせると 0 になるはずなので、 1~N-1 番目の人の得点を合わせて 0 から差し引けば回答となる。
#!/usr/bin/env python3 import sys def solve(N: int, K: int, A: "List[int]"): result = [x // K for x in A if x % K == 0] print(" ".join(map(str, sorted(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 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()
B - Commencement
良い文字列 とは、すべての文字種の出現回数をとったあと、出現回数ごとに見たときに、0 または 2種類の文字があるものとする。そうしたときに与えられ他文字列が いい文字列 か判定せよというもの。
Python だと Counter があるのでまずそれを使用して、文字のカウントを取る。その後、出現回数ごとに改めて文字種のカウントを行うようにした。解説だと改めて Counter を取る方法も紹介されていて、そちらのほうが簡単にできそう。
#!/usr/bin/env python3 import sys from collections import Counter, defaultdict YES = "Yes" # type: str NO = "No" # type: str def solve(S: str): counter = Counter(S) d = defaultdict(int) for k, v in counter.items(): d[v] += 1 if all([x == 2 for x in d.values()]): print(YES) else: print(NO) return def main(): def iterate_tokens(): for line in sys.stdin: for word in line.split(): yield word tokens = iterate_tokens() S = next(tokens) # type: str solve(S) if __name__ == '__main__': main()
C - Airport Code
文字列 S, T が与えられる。 T は文字列をあるルールで変換したコードとする。 T が S から得られるコードであるかを判断せよというもの
i, j をそれぞれ S, T の index として、前から条件に合えば index を進めるものとする。どちらかの index が最後まで到達したときに、
jが最後まで到達しているかjが 2まで来ており、T の最後の文字が X であるか
をチェックして回答するようにした
#!/usr/bin/env python3 import sys YES = "Yes" # type: str NO = "No" # type: str def solve(S: str, T: str): i, j = 0, 0 while i < len(S) and j < len(T): if ord(S[i]) - ord('a') == ord(T[j]) - ord('A'): j += 1 i += 1 if j == 3: print(YES) elif j == 2 and T[2] == "X": print(YES) else: print(NO) return def main(): def iterate_tokens(): for line in sys.stdin: for word in line.split(): yield word tokens = iterate_tokens() S = next(tokens) # type: str T = next(tokens) # type: str solve(S, T) if __name__ == '__main__': main()
D - Divide Interval
S(l,r) を [l, r) で表される数列とする。 また、 で表される数列をいい数列とする。
をできるだけ少ない M 個のいい数列に分けるときの分け方を示せというもの。
最初に考えたのは "L と R の差を2進数で表して、ビットの立っている部分を区間にすれば最小になりそうだな" というもの。幅だけ見ればそうなのかもしれないが、L, R の差が 16 だからといって、常に で表せるとは限らない。
は非負整数となっているため、0, 16, 32.. と 決まった区間しか表せないのである。
つまり が取れる最大の幅は、
の値、特に2 の約数をいくつ持つかによって決まる。そのため、貪欲法で取れるだけ取り、取った幅で
を超える場合は幅を小さくすれば回答となる。
上記の方法だと、 が 0の場合だけ注意する必要があるのだが、その時の処理をミスしてしまい WA となってしまった。
が 0 の場合は
を超えない範囲でできるだけ取って、その後は同様の処理をすれば問題ない。
最初なぜこれでうまく解けるのか、取れる幅が広がっていくのかよくわかってなかった。 という式をよく見ると
のどちらかは必ず偶数となる。
としたときに、できるだけ大きい幅を取ろうとすると
は必ず奇数となるため、
は偶数となり、次の区間は
の幅を取れるようになる。と、考えると少し理解できた。
解説を見ると結果的にセグメントツリーのような形となり、再帰的に構築する方法だとセグメントツリー構築の方法とほぼ同様になるとのことだったのでそちらも試してみたい。
#!/usr/bin/env python3 import sys import math def power2_count(num: int) -> int: count = 0 while num and num % 2 == 0: count += 1 num //= 2 return count def solve(L: int, R: int): result = [] current = L if current == 0: add = 1 while add <= R: add *= 2 add //= 2 result.append((current, current+add)) current += add while current < R: max_power = power2_count(current) add = pow(2, max_power) while current + add > R: add = add // 2 result.append((current, current+add)) current += add print(len(result)) for l, r in result: print("{} {}".format(l, r)) return def main(): L, R = list(map(int, input().strip().split())) solve(L, R) if __name__ == '__main__': main()
E - Weighted Tic-Tac-Toe
TicTacToe だし、そのままシンプルに mini-max でトライしたものの、時間が間に合わずタイムアップに。minmax ってこれでよかったっけ? と悩みながら書いて時間がかかったので改めてさっと書けるようにしないといけない。
#!/usr/bin/env python3 from typing import List MAX_VALUE = pow(10, 10) + 1 MIN_VALUE = -1 * pow(10, 10) - 1 def main(): A = [] for _ in range(3): A.append(list(map(int, input().strip().split()))) board = [[0] * 3 for _ in range(3)] def minmax(cur: List[List[int]], score: int, takahashi: bool) -> int: r = wincheck(cur) if r != 0: return score + (MAX_VALUE if r == 1 else MIN_VALUE) if all([all([x != 0 for x in l]) for l in cur]): return score if takahashi: res = MIN_VALUE for i in range(3): for j in range(3): if cur[i][j] == 0: cur[i][j] = 1 res = max(res, minmax(cur, score + A[i][j], not takahashi)) cur[i][j] = 0 return res else: res = MAX_VALUE for i in range(3): for j in range(3): if cur[i][j] == 0: cur[i][j] = -1 res = min(res, minmax(cur, score - A[i][j], not takahashi)) cur[i][j] = 0 return res def wincheck(t: List[List[int]]) -> int: for l in t: if sum(l) == 3: return 1 elif sum(l) == -3: return -1 for j in range(3): total = sum(t[i][j] for i in range(3)) if total == 3: return 1 elif total == -3: return -1 diag1 = t[0][0] + t[1][1] + t[2][2] diag2 = t[2][0] + t[1][1] + t[0][2] if diag1 == 3 or diag2 == 3: return 1 elif diag1 == -3 or diag2 == -3: return -1 return 0 res = minmax(board, 0, True) if res > 0: print("Takahashi") else: print("Aoki") return if __name__ == '__main__': main()
まとめと最近の練習について
最近は Obsidian を使って、各問題の整理と、問題を解くときに使う基礎的なアルゴリズムをまとめている。 gcd lcm とかも、もちろんライブラリを使えばぱっと出せるのだけど、背景にある計算方法を知っているだけでもだいぶ理解の助けになっている気がする。
あとはアルゴリズムを書いてなるべく言葉で説明できるように心がけるようにしている。自分がどこをちゃんと理解できてないかわかりやすくなった気がしていて、どこの勉強をすればいいか理解するための助けになっている気がしている。
