結果

問題 No.1242 高橋君とすごろく
コンテスト
ユーザー lam6er
提出日時 2025-04-09 21:02:53
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 4,228 bytes
コンパイル時間 377 ms
コンパイル使用メモリ 82,364 KB
実行使用メモリ 148,616 KB
最終ジャッジ日時 2025-04-09 21:04:22
合計ジャッジ時間 4,213 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 6 TLE * 1 -- * 17
権限があれば一括ダウンロードができます

ソースコード

diff # 

def main():
    import sys
    from bisect import bisect_left

    def merge_intervals(intervals):
        if not intervals:
            return []
        intervals.sort()
        merged = [intervals[0].copy()]
        for current in intervals[1:]:
            last = merged[-1]
            if current[0] <= last[1] + 1:
                last[1] = max(last[1], current[1])
            else:
                merged.append(current.copy())
        return merged

    def subtract_points_from_interval(interval, points):
        start, end = interval
        points = sorted(points)
        res = []
        current_start = start
        for p in points:
            if p < current_start:
                continue
            if current_start < p:
                res.append([current_start, p - 1])
            current_start = p + 1
        if current_start <= end:
            res.append([current_start, end])
        return res

    def interval_intersection(a, b):
        res = []
        i = j = 0
        len_a = len(a)
        len_b = len(b)
        while i < len_a and j < len_b:
            a_start, a_end = a[i]
            b_start, b_end = b[j]

            start = max(a_start, b_start)
            end = min(a_end, b_end)
            if start <= end:
                res.append([start, end])
            if a_end < b_end:
                i += 1
            else:
                j += 1
        return merge_intervals(res)

    N, K = map(int, sys.stdin.readline().split())
    A = list(map(int, sys.stdin.readline().split()))
    game_over = set(A)
    A_sorted = sorted(A)

    current_intervals = [[N, N]]
    visited = set()

    while True:
        tuple_intervals = tuple(tuple(interval) for interval in current_intervals)
        if tuple_intervals in visited:
            break
        visited.add(tuple_intervals)

        new_intervals = None
        for x in range(1, 7):
            x_ranges = []
            choices = [x, 7 - x]
            for choice in choices:
                part1 = []
                lower = N - choice
                s_lower = max(lower, 1)
                s_upper = N - 1
                if s_lower <= s_upper:
                    part1 = [[s_lower, s_upper]]

                part2 = []
                for interval in current_intervals:
                    L, R = interval
                    s_start = L - choice
                    s_end = R - choice
                    if s_end < 1:
                        continue
                    s_start = max(s_start, 1)
                    if s_start > s_end:
                        continue
                    current_range = [s_start, s_end]
                    points_to_exclude = []
                    for a in A_sorted:
                        if a >= N:
                            continue
                        s_val = a - choice
                        if s_start <= s_val <= s_end:
                            points_to_exclude.append(s_val)
                    subtracted = subtract_points_from_interval(current_range, points_to_exclude)
                    part2.extend(subtracted)

                merged_part = merge_intervals(part1 + part2)
                x_ranges.extend(merged_part)

            x_possible = merge_intervals(x_ranges)
            if not x_possible:
                new_intervals = []
                break

            if new_intervals is None:
                new_intervals = x_possible
            else:
                new_intervals = interval_intersection(new_intervals, x_possible)
                if not new_intervals:
                    break

        if new_intervals is None:
            new_intervals = []

        new_intervals = merge_intervals(new_intervals)
        if not new_intervals:
            break

        new_tuple = tuple(tuple(interval) for interval in new_intervals)
        if new_tuple == tuple_intervals:
            break

        current_intervals = new_intervals
        for interval in current_intervals:
            if interval[0] <= 1 <= interval[1]:
                print("Yes")
                return

    has = any(interval[0] <= 1 <= interval[1] for interval in current_intervals)
    print("Yes" if has else "No")

if __name__ == "__main__":
    main()
0