AtCoder Beginner Contest 347 振り返り

前々回開催のコンテストになるが、 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()