【AtCoder】ABC 347 C - Ideal Holidays | 茶コーダーが解くAtCoder

実行時間制限: 2 sec / メモリ制限: 1024 MB / Difficulty: 926

問題概要

「1週間」を1日目から $A$ 日目までを休日、 $A + 1$ 日目から $B$ 日目までを平日とした、 $A + B$ 日間で定義する。また、 $N$ 個の予定があり、 $i$ 番目の予定は今日から $D_i$ 日後である。ただし、今日が1週間のうち何日目なのかは分からない。 $N$ 個の予定が全て休日になる可能性があるかを判定せよ。

制約

$1 \leq N \leq 2 \times 10^5$
$1 \leq A, B \leq 10^9$
$1 \leq D_1 < D_2 < ... < D_N \leq 10^9$

考察

この問題は、コンテスト終了時に自分を含め多くの人が「WA が1個出てしまい解けなかった...」という事態に陥ったことと思う。そのため、 WAx1 が出てしまう解法とその原因、そして正しい解法について書くことにする。

誤解法

まず、簡単な例で考えてみよう。入力が

2 2 5
2 3

の場合について考える。「今日」が1週間のうち何日目なのかを考えると、予定の日の配置は全部で $A + B$ 通りある。☆を「今日」、oを予定の日とすると、この例では以下の7通りの配置が考えられる。

ex1

これより、「今日」が1週間のうちの6日目であれば条件を満たすことになり、このケースの判定はYesとなる。

ここで、予定がある曜日 (1週間のうちの何日目にあるのか) に注目して考えるために、各 $D_i$ を $A + B$ で割った余りを考えることにする。このケースなら、図は以下のようになる。

ex1-2

この図をじっと見ていると、判定すべき問題は次のように言い換えられることに気付く。

「☆をずらしていって、赤の範囲に全てのoを収めることができるか？」

つまり、

「左端のoと右端のoを同時に赤の範囲に収めることができるか？」

この問題を判定するプログラムをこんな感じに実装してみた。

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

#define all(x) (x).begin(), (x).end()
#define rep(i, start, end) for (ll i = (start); i < (ll)(end); i++)

using ll = long long;

// ======================================== //

int main()
{
    ll N, A, B;
    cin >> N >> A >> B;
    vector<ll> D(N);
    rep(i, 0, N)
    {
        cin >> D[i];
        D[i] %= A + B;
    }

    sort(all(D));

    if (D[D.size() - 1] - D[0] + 1 <= A)
        cout << "Yes" << endl;
    else
        cout << "No" << endl;
}

Dに予定がある日の曜日を格納し、昇順にソート。その最大値と最小値の差+1が休日の区間 $A$ 以下であればよい、としている。

これを提出すると、こんな結果になる。

atcoder.jp

orz

誤判定の原因と正しい解法

先ほどの解法、一見正しそうに思えるが、実はこんなコーナーケースで落ちる。

2 2 5
6 7

図示すると、こんな感じ。

ex2

☆をずらしていけば確かに2つのoが休日の範囲に収まるのだが、与えられた数値は6, 7。これらを $\mod 7$ すると $6 \to 6, 7 \to 0$ となり、2つの予定の日数差は $6$ となって $A (= 2)$ より大きくなるので、先ほどのプログラムではこのケースはNoとなってしまい、正しく判定されない。

では、どうすればよいのだろうか。実は一番最初の図がヒントになっている。

要件としては、上の例で言う $7 \to 0$ を $7 \to 7$ としてあげたいので、 $\mathrm{mod}$ を取った後の各D[i]に $A+B$ を加えたものをDに追加して、 $\min(D_{i+N-1} - D_i + 1) \: (1 \leq i \leq N)$ を求め、それが $A$ 以下であるかを判定しよう。 $i$ をずらしていく操作が、前述した☆を図らしていく操作に対応している。

なお、コードでは 0-indexed になっていることに注意。

コード

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

#define all(x) (x).begin(), (x).end()
#define rep(i, start, end) for (ll i = (start); i < (ll)(end); i++)

using ll = long long;

// ======================================== //

int main()
{
    ll N, A, B;
    cin >> N >> A >> B;
    vector<ll> D(N);
    rep(i, 0, N)
    {
        cin >> D[i];
        D[i] %= A + B;
    }

    sort(all(D));
    rep(i, 0, N) D.push_back(D[i] + A + B);

    ll diff = INF;
    rep(i, 0, N) diff = min(diff, D[i + N - 1] - D[i] + 1);

    if (diff <= A)
        cout << "Yes" << endl;
    else
        cout << "No" << endl;