遅くなってしまったが、途中まで書き掛けとなってしまっていたので、前回の AtCoder Beginner Contest 343 の振り返り。
全体としては A~D までは比較的簡単な問題が続いたので(一回 WA 出してしまったものの) 今回こそ 5完ぐらいいけるかな？と思っていたのだけれどそんなに甘くはなかった。
Dまで解いた時点で、E, F を比べると F のほうが回答者数が多かったのでそちらから解くことに。結果解答方針はわかる問題だったので功を奏したものの、TLE ばかりで間に合わず… 悔しい
A - Wrong Answer
“0以上9以下の整数で、与えられた A+B に等しくないもの” なので、0~9 まで試して A+B でないものが見つかればOK
#!/usr/bin/env python3 import sys def solve(A: int, B: int): for i in range(10): if i != A+B: print(i) return return def main(): def iterate_tokens(): for line in sys.stdin: for word in line.split(): yield word tokens = iterate_tokens() A = int(next(tokens)) # type: int B = int(next(tokens)) # type: int solve(A, B) if __name__ == '__main__': main()
B - Adjacency Matrix
N 頂点の単純無向グラフで、頂点 i, j を結ぶ辺の隣接行列が与えられる。各頂点 i とつながっている頂点番号を昇順で出力せよという問題。
問題解くときに転置行列にして解いたけど、無向グラフで対照になるので特にする必要はなかったやつ
#!/usr/bin/env python3 import sys def solve(N: int, A: "List[List[int]]"): for j in range(N): result = [] for i in range(N): if A[i][j] == 1: result.append(i+1) if len(result) > 0: print(" ".join([str(x) for x in result])) else: print("") 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)] for _ in range(N)] # type: "List[List[int]]" solve(N, A) if __name__ == '__main__': main()
C - 343
三乗して K を満たす正整数を見つけるということなので、 N の 1/3 乗をとってそこまでチェッｋする、といった方法で書いてみたけど WA に。 $N$ が最大 $10^{18}$ でループ回しても $106$ 程度なのでそのままループ回すようにして AC。
#!/usr/bin/env python3 import sys import math def solve(N: int): candidate = 0 for i in range(1, N+1): triple = pow(i, 3) if triple > N: break striple = str(triple) if striple == striple[::-1] and triple <= N: candidate = max(candidate, triple) print(candidate) 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 solve(N) if __name__ == '__main__': main()
D - Diversity of Scores
毎秒ごとに得点を取った選手と、スコアの種類数をカウント。最初は 0 点の人が N 人いるところからスタートして、新しい種類の得点が増える or カウントしていた種類の得点の数が 0 になる場合にカウントをずらすことで AC
#!/usr/bin/env python3 import sys from collections import defaultdict def solve(N: int, T: int, A: "List[int]", B: "List[int]"): man_to_score = [0] * N score_to_man = defaultdict(int) score_to_man[0] = N item_count = 1 for a, b in zip(A, B): index = a - 1 current_score = man_to_score[index] next_score = current_score + b man_to_score[index] = next_score score_to_man[current_score] -= 1 if score_to_man[current_score] == 0: item_count -= 1 score_to_man[next_score] += 1 if score_to_man[next_score] == 1: item_count += 1 print(item_count) 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 T = int(next(tokens)) # type: int A = [int()] * (T) # type: "List[int]" B = [int()] * (T) # type: "List[int]" for i in range(T): A[i] = int(next(tokens)) B[i] = int(next(tokens)) solve(N, T, A, B) if __name__ == '__main__': main()
E - 7x7x7
ここまできたときに順位表見ると明らかに E 問題解いてる人が少なかったので先にF問題に。解説見ても Python だと間に合わない問題のようだったので先に避けて正解だったかもしれない。
F - Second Largest Query
セグメント木の問題は練習したことあるのもあり、見てセグメント木で解けそうとわかったあとなんとかして解きたかったのだけど1時間位かかってもACとれず。
初めはノードにすべての数のカウントを dict で持つようにしてしまっていて TLE に。２番目に大きい値の個数を出力すればいいので、上位２つの数のカウントだけ持つようにしたのだけど引き続き TLE。
当初は ノード間の値の結合のときに
def op(x, y): res = {k: x.get(k, 0) + y.get(k, 0) for k in set(x) | set(y)} keys = list(set(x) | set(y)) keys.sort(reverse=True) if len(keys) == 0: return {} elif len(keys) == 1: key = keys[0] return {key: x.get(key, 0) + y.get(key, 0)} else: key1, key2 = keys[0], keys[1] return { key1: x.get(key1, 0) + y.get(key1, 0), key2: x.get(key2, 0) + y.get(key2, 0) }
のように dict のまま計算するようにしていたのだけど、このままだと TLE に。数の種類も4種類ぐらいなので問題ないかと思っていたが甘かったみたい。
競技終了後、タプルにして解くようにしたら通った
#!/usr/bin/env python3 class SegTree: def __init__(self, op, e, n, v=None): self._n = n self._op = op self._e = e self._log = (n - 1).bit_length() self._size = 1 << self._log self._d = [self._e()] * (2 * self._size) if v is not None: for i in range(self._n): self._d[self._size + i] = v[i] for i in range(self._size - 1, 0, -1): self._update(i) def set(self, p, x): p += self._size self._d[p] = x for i in range(1, self._log + 1): self._update(p >> i) def get(self, p): return self._d[p + self._size] def prod(self, l, r): sml, smr = self._e(), self._e() l += self._size r += self._size while l < r: if l & 1: sml = self._op(sml, self._d[l]) l += 1 if r & 1: r -= 1 smr = self._op(self._d[r], smr) l >>= 1 r >>= 1 return self._op(sml, smr) def all_prod(self): return self._d[1] def _update(self, k): self._d[k] = self._op(self._d[2 * k], self._d[2 * k + 1]) def main(): N, Q = map(int, input().strip().split()) A = map(int, input().strip().split()) def op(x, y): if x[0] < y[0]: x, y = y, x i2 = 0 c1 = x[1] if x[0] == y[i2]: i2 = 2 c1 += y[1] if x[2] == y[i2]: return (x[0], c1, x[2], x[3] + y[i2 + 1]) elif x[2] < y[i2]: return (x[0], c1, y[i2], y[i2+1]) else: return (x[0], c1, x[2], x[3]) def e(): return (0, 0, 0, 0) stree = SegTree(op, e, N, [(a, 1, 0, 0) for a in A]) for _ in range(Q): a, b, c = map(int, input().strip().split()) if a == 1: stree.set(b-1, (c, 1, 0, 0)) else: res = stree.prod(b-1, c) if res[2] == 0: print(0) else: print(res[3]) if __name__ == '__main__': main()
まとめ
A~D は比較的容易だったのだけど、その分順位も団子状態になってしまっていた。F 問題は最初解けそうとおもっただけに悔しい。SegTree はまだそらで書こうと思っても書けないのでもう少し練習しないと
