実はとても単純な解法に落とし込めるのだけど、発想がちょっと難しい

問題へのリンク

問題概要

AtCoder 王国の 1 週間は $A+B$ 日あり、最初の $A$ 日が休日、後半の $B$ 日が平日である。

高橋君は $N$ 日分の予定があり、それぞれ $D_{1}, D_{2}, \dots, D_{N}$ 日目に予定がある。

これらの予定日がすべて休日であることがあり得るかどうかを判定せよ。

制約

$1 \le N \le 2 \times 10^{5}$
$1 \le A, B \le 10^{9}$
$1 \le D_{1} \lt D_{2} \lt \dots \lt D_{N} \le 10^{9}$

考えたこと

まず、各 $i$ に対して、 $D_{i}$ に $A+B$ を足し引きしても状況が変わらないことに注意しよう。よって、最初に $D_{i}$ を $A + B$ で割った余りに置き換えて考えることにした。さらに、その状態で $D$ を小さい順にソートしておくことにする。

このとき、 $D$ は、円環上に並んだ $A+B$ 個のマスのうちの特別な $N$ 個のマスだと考えるとわかりやすい。たとえば下図は $A+B = 12, N = 4, D = (1, 3, 6, 10)$ であるような場合を表している。

このように整理したとき、今回の問題は次のように言い換えられる。なお、0-indexed で表現している。

$A + B$ 個のマスが円環状に並んでいる。

今、この円環のうちの連続する $A$ マスを塗りつぶす。このとき、マス $D_{0}, D_{1}, \dots, D_{N-1}$ がすべて塗られている状態にすることは可能か？

たとえば、上の図の設定の場合、もし $A = 9, B = 3$ であれば、下図のように塗りつぶせば可能である。

このような問題に落とし込めば、もう判定は簡単だ。マス $D_{0}, D_{1}, \dots, D_{N-1}$ のうちの隣接するマスの組であって、その差が $B+1$ 以上離れている組が存在すれば "Yes"、そうでなければ "No" だ。

以上の解法の計算量は $O(N \log N)$ となる（ $D$ のソートがボトルネック）。

コード

#include <bits/stdc++.h>
using namespace std;

int main() {
    long long N, A, B;
    cin >> N >> A >> B;
    vector<long long> D(N);
    for (int i = 0; i < N; i++) {
        cin >> D[i];
        D[i] %= A + B;
    }
    sort(D.begin(), D.end());
    D.push_back(D[0] + A + B);  // D[N-1] と D[0] の間隔を調べるためのもの

    bool res = false;
    for (int i = 0; i < N; i++) {
        if (D[i+1] - D[i] >= B + 1) res = true;
    }
    cout << (res ? "Yes" : "No") << endl;
}

けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

AtCoder ABC 347 C - Ideal Holidays (1Q, 緑色, 350 点)

問題概要

制約

考えたこと

コード