2020-01-28

CODE FESTIVAL 2016 qual A E - LRU パズル / LRU Puzzle (橙色, 1200 点)

AtCoder AtCoder1200点パズル操作 Yes/No判定問題操作:circular_shift 数列 Greedy 集計処理 Greedy:端から順に決まっていく番兵法順列を題材とした問題操作:特定要素を先頭に持ってくる後ろから解く操作:上書き橙色diff AGC-like 操作を逆順に見る

D 問題はコーナーケースゲーかと思ったらそうでもなかった。むしろこっちの方が苦しかった。

問題へのリンク

問題概要

$M$ 要素からなる配列が $N$ 個あって、それぞれ最初は $1, 2, \dots, M$ で初期化されている。以下の操作を $Q$ 回終えた段階で、 $N$ 個の配列が等しい状態とすることが可能かどうかを判定せよ。

$q$ 回目の操作は値 $a_{q}$ で与えられる。
$N$ 個の配列のうち、好きな配列を 1 つ選ぶ。
その配列中の値 $a_{q}$ の要素を先頭にもってくる。

制約

$1 \le N, M, Q \le 10^{5}$

考えたこと

似たようなのをこどふぉでも見た！！！

drken1215.hatenablog.com

といっても操作が似てるだけで問題の内容自体は割と違うかもしれない。まず思うことは、今回の操作は基本的に上書き操作に近いということだ。つまり、最初の方の操作列がどうなっていようと、最後の方で $M$ 要素がちゃんと網羅されるなら、ほとんど最後の方の操作列だけで決まってしまう。こういう上書きな性質をもつ問題では、後ろから解くというのが定石ではある。

そして、配列の個数が 1 つだったら、配列がどうなるかを考えると、

操作列を反転して、最後尾に 1, 2, ..., M をくっつけた上で、
「初めてでてきた要素」の登場順

ということで決まっていく。2 回目以降に登場する要素については関係がない。よって元の問題は、操作列を上手に $N$ 個の要素に配分して (最後尾に 1, 2, ..., M をくっつけるのは配分後に行う)、「初登場要素の順序」が揃うようにする問題ということになる！！！

そして重要な観察として、以下のことがいえる。

操作列を後ろから見ていくと、実は各要素がどの配列に対して操作されていたべきかが (一般性を失わない程度の取り決めの下で)、ほぼ一意に決まっていく

ということだ。たとえば、 $N = 3$ 、 $M = 3$ で、操作列が 1, 3, 3, 2, 3, 1, 3 のとき、後ろから処理していって、

最後尾の 3 はどの配列でも一般性を失わないので、配列 0 とする (配列 0 の初登場要素順が {3})
次の 1 は、仮に配列 0 以外に対してやってしまうと、結果が等しくならないので配列 0 に対して行われたと思う他ない (配列 0 の初登場要素順が {3, 1})
次の 3 は、配列 0 にやっても変わらず、むしろ今のうちに配列 1 にやっておくべきなので配列 1 にやる (配列 0：{3, 1}、配列 1：{3})
次の 2 は、配列 0 に (配列 0：{3, 1, 2}、配列 1：{3})
次の 3 は、配列 2 に (配列 0：{3, 1, 2}、配列 1：{3}、配列 2：{3})
次の 3 は、もはや 3 配列すべてに行き渡ったので、どこに入れても変わらない。この 3 は将来的に上書きされることになる (配列 0：{3, 1, 2}、配列 1：{3}、配列 2：{3})
次の 1 は、配列 1 に (配列 0：{3, 1, 2}、配列 1：{3, 1}、配列 2：{3})

ここで操作列は終わりだが、ここからサドンデスで、それぞれの配列に (1, 2, ..., M) の操作を行う (元の配列が M, M-1, ..., 1 を操作してできたものとみなせるため)。

そうすると、配列 1 には「2」が補充されて、配列 2 にも「1, 2」が補充されるので、3 配列とも {3, 1, 2} の状態になる。よって Yes ということだ！！！これがもし配列 0 の最終状態が {3, 2, 1} だったならば、配列 2 の最終状態は {3, 1, 2} になるので不一致で No ということになる。

具体的な解法へ

各要素のカウンターを用意しておいて、以下のようにする。最終状態で、どの要素についてもカウンター値が $N$ になれば Yes。

まずは操作列全体を後ろから見て 1, 2, ..., M も付け加えた上で後ろからみていって、初登場順 ord を記録しておく
ふたたび操作列全体を後ろから見ていって、要素が v だったときに、もし v が ord 順で先頭だったらインクリメント、そうでなくてもインクリメントしたときに ord 順的に前の値を超えなければインクリメントする (超えるときは、その要素を新たな配列に入れることはできないため)
最後に 1, 2, ..., M について順に見ていって、v が ord 順で先頭だったらいっきに $N$ にして、そうでなければ ord 順で前の要素がすでに $N$ になっていたら、v の値も $N$ にして OK

計算量はうまくやれば $O(N + M + Q)$ になると思う。僕のは map とか使ってるから log はくっついてくる。

#include <iostream>
#include <vector>
#include <deque>
#include <map>
#include <algorithm>
using namespace std;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }

int N, M, Q;
deque<int> a;

bool solve() {
    vector<int> b(M);
    for (int i = 0; i < M; ++i) b[i] = i;
    map<int,int> id;
    int iter = 0;
    for (int i = 0; i < a.size(); ++i) {
        if (id.count(a[i])) continue;
        id[a[i]] = iter++;
    }
    for (int i = 0; i < b.size(); ++i) {
        if (id.count(b[i])) continue;
        id[b[i]] = iter++;
    }
    for (int i = 0; i < a.size(); ++i) a[i] = id[a[i]];
    for (int i = 0; i < b.size(); ++i) b[i] = id[b[i]];

    vector<int> con(id.size(), 0);
    for (int i = 0; i < a.size(); ++i) {
        if (a[i] == 0) con[a[i]]++;
        else if (con[a[i]] + 1 <= con[a[i]-1]) con[a[i]]++;
    }
    for (int i = 0; i < b.size(); ++i) {
        if (b[i] == 0) chmax(con[b[i]], N);
        else chmax(con[b[i]], con[b[i]-1]);
    }
    bool ok = true;
    for (int i = 0; i < con.size(); ++i) if (con[i] < N) ok = false;
    return ok;
}

int main() {
    while (cin >> N >> M >> Q) {
        a.resize(Q);
        for (int i = 0; i < Q; ++i) cin >> a[i], --a[i];
        reverse(a.begin(), a.end());
        if (a.empty() || solve()) cout << "Yes" << endl;
        else cout << "No" << endl;
    }
}