Codeforces Round #641 Orac and Mediansの解説

約1年ぶりにCodeforcesに出場しました。Div. 2の4問目、Orac and Medians が解けそうで解けませんでした。終了後、解説を読みながら考えをまとめました。

問題概要

数列が与えられる。この数列の任意区間を選び、その区間のすべての値を、その区間の中央値で置換することを好きな回数だけ行う。数列すべての値を値にすることはできるか？ できる場合は"yes", できない場合は"no"を出力。

ここで、数列sの中央値は、要素を小さい順に並べたときの ⌊|s|+1/2⌋ 番目の要素と定義。例えば数列{1, 7, 5, 8, 4}の中央値は、3番目に小さい5。数列{1, 7, 5, 8}の中央値は、2番めに小さい5。

考察

Kより小さい値、K、Kより大きい値の3カテゴリのみ考えればよい。以下では、Kより小さい値を0, Kを1, Kを2と置換した数列を考える。

以下のケースはすぐに分かる。

• 数列に1個も1が存在しない場合は明らかに"no"。
• 数列の長さが1の場合、が1の場合のみ"yes"。

今後、数列の長さは2以上、かつ少なくとも1個は1が存在するものとする。

以下のケースも少し考えると分かる。

• 1と1が隣り合う箇所がある場合は"yes"。
  • "? 1 1" または "1 1 ?" どちらのパターンでも中央値は1なので、"1 1 1" と1が増殖する。これを続けると数列はすべて1になる。
• 1と2が隣り合う箇所がある場合は"yes"。
  • "1 2" または "2 1" どちらのパターンでも中央値は1なので、"1 1"となる。あとは↑のパターンに帰着。
• 2と2が隣り合う箇所がある場合は"yes"。
  • "2 2"の前後にある"0"をすべて"2"に変えていくと、いつかは"1"に接触する。
  • すると"1 2"または"2 1"のパターンが発生するので、"yes"になる。

さらに考えると、以下のパターンも成り立つことがわかる。

• "1 0 1"がある場合は"yes"。
  • "1 0 1" の中央値は1なので、"1 1 1"を作れる。"1 1"のパターンを作れたので"yes"。
• "1 0 2" または "2 0 1" がある場合は"yes"。
  • "1 0 2" または "2 0 1" どちらのパターンでも中央値は1なので、"1 1 1"を作れる。"1 1"のパターンを作れたので"yes"。
• "2 0 2" がある場合は"yes"。
  • "2 0 2"の中央値は2なので、"2 2 2"を作れる。
  • "2 2"のパターンを作れたので"yes"。

解説によると"yes"のパターンとなるのは実は上記までで、上に書いたパターンのどれも持たない数列はすべて"no"になる。これを直感的に感じ取るのは私には難しかった。

上に書いたパターンにどれにも当てはまらないということは、数列の1や2の間には、少なくとも2つの0があるということ。例えば以下。

• "0 1 0 0 1 0 0 2"
• "2 0 0 2 0 0 1 0 0 2"

0の影響力は強くて、0を1や2に変えるには、1や2で挟む必要がある。しかし上記のようなパターンだと、1や2で挟めない。よって"no"となる。

回答例 (C++)

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
#define REP(i,n) for(int i = 0; i < (int)(n); ++i)
#define FOR(i,a,b) for(int i = (a); i < (int)(b); ++i)
#define ALL(c) (c).begin(), (c).end()
#define SIZE(v) ((int)v.size())
#define pb push_back
#define mp make_pair
#define mt make_tuple

string solve(int N, int K, vector<int>& As) {
    // Kが1個もなければno
    if (find(ALL(As), K) == As.end()) {
        return "no";
    }

    // 以下では少なくとも1個のKがあるとしてよい

    // 配列の長さ1
    if (N == 1) {
        return "yes";
    }

    // 以下では配列の長さが2以上としてよい

    // 隣り合う数同士にK以上があるならyes
    REP(i, N - 1) {
        if (As[i] >= K && As[i + 1] >= K) {
            return "yes";
        }
    }
    // 1個離れた位置にK以上があるならyes
    REP(i, N - 2) {
        if (As[i] >= K && As[i + 2] >= K) {
            return "yes";
        }
    }

    return "no";
}

int main(void)
{
    cin.sync_with_stdio(false);
    int T; cin >> T;
    REP(t, T) {
        int N; int K;
        cin >> N >> K;
        vector<int> As(N);
        REP(n, N) cin >> As[n];
        cout << solve(N, K, As) << endl;
    }

    return 0;
}