前々回開催のコンテストになるが、 ABC 347 の記事を書けてなかったので振り返り。
結果としては、A, B の 2問しか解けなかった。 C はなんとか通そうとしたものの、結局時間内には解けず...。頑張りましょう。
A - Divisible
数列の剰余を取って 0 になるものだけ抽出して、割ってあげたものを出力してあげればOK
#!/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 - Substring
制約が小さいので、全パターンを列挙して Set で管理して出力する形で対応した。i
, j
の範囲をどこからどこまで取るかを間違えそうになった。
for i in range(n+1)
のところは range(1, n+1)
で良さそう。
#!/usr/bin/env python3 import sys def solve(S: str): s = set() n = len(S) for i in range(n+1): for j in range(i): s.add(S[j:i]) print(len(s)) 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 - Ideal Holidays
当初は "剰余の最大と最小の差が 以下であればOK" と単純に考えてしまって WA となってしまった。これだと剰余の値が小さい値と大きい値に偏っているようなパターンで間違った回答となってしまう。
解説動画や他の方の解説などを見ながら - 二分探索で条件を満たすものがあるかチェックする例 - 剰余の差が を超えるようなパターンがあるかチェックする例 で、AC となるかを確認した。
二分探索の例では、ある日付 からスタートするとして、そこから 個すべてが に収まるかを確認する。
#!/usr/bin/env python3 import sys import bisect YES = "Yes" # type: str NO = "No" # type: str def solve(N: int, A: int, B: int, D: "List[int]"): cal = [0] * (2 * N) for i, d in enumerate(D): cal[i] = d % (A+B) cal[i+N] = cal[i] + A + B cal.sort() for i in range(N): left = bisect.bisect_left(cal, cal[i]+A) if left == i+N: print(YES) return print(NO) return def main(): N, A, B = list(map(int, input().strip().split())) D = list(map(int, input().strip().split())) solve(N, A, B, D) if __name__ == '__main__': main()
剰余の差を見るパターンの場合、剰余の差が 平日である 日を超えるようなパターンがあるかをチェックする。
#!/usr/bin/env python3 import sys import bisect YES = "Yes" # type: str NO = "No" # type: str def solve(N: int, A: int, B: int, D: "List[int]"): D = [d % (A+B) for d in D] D.sort() cal = [] for d in D: if not cal: cal.append(d) else: if d != cal[-1]: cal.append(d) cal.append(cal[0]+A+B) for i in range(len(cal)-1): if (cal[i+1] - cal[i]) > B: print(YES) return print(NO) return def main(): N, A, B = list(map(int, input().strip().split())) D = list(map(int, input().strip().split())) solve(N, A, B, D) if __name__ == '__main__': main()