AtCoder Beginner Contest 347 C問題 解説

ArCoderの問題の解き方を自分用に記録する。
難しいなあ...。

問題

考え方

今日を0日目として何日目に予定があるのか週ごとでまとめる。
理由は休みが1日目であった場合、8日目、15日目も同じく休みとなる規則性があるため。平日であっても同じ。
例えば以下は予定Dが1日目、2日目、8日目にあると仮定した場合を表にしたもの。

0	1	2	3	4	5	6
-	☆	☆	-	-	-	-
7	8	9	10	11	12	13
-	☆	-	-	-	-	-

この週の予定が問題に記載されている休みと平日の規則にあてはまっているかを確認してあげれば良い。
1日目が休みであるか平日であるかという規則は8日目にも適用されるため、7日目以降を0〜6日目にそろえる。

0	1	2	3	4	5	6
-	☆	☆	-	-	-	-
0	1	2	3	4	5	6
-	☆	-	-	-	-	-

サンプルコード

• setで重複削除しようとすると実行時エラーになる原因は不明
• 二分探索を使うと良いみたい
• 以下のコードではD[0]もD[i]として使いたいので2週目の最初の予定D[0]+A+Bを追加している

N, A, B = map(int, input().split())
D = list(map(int, input().split()))
D = [i%(A+B) for i in D]
D.sort()
D.append(D[0]+A+B)
for i in range(1, N+1):
    if D[i]-D[i-1] > B:
        print("Yes")
        exit()
print("No")