AtCoder World Tour Finals 2019 A - Magic (1000 点)

世界大会で注意力を問う罠枠だったのかな

問題へのリンク

問題概要

個の箱があってそのうちの一つに財宝が入っている。箱を 1 個 1 個開けて行くことで財宝を見つけたい。ただし、財宝が入っている箱を開けようとすると最大 回、財宝が他の箱に瞬間移動してしまう。

各箱について「 回までしか開けられない」という制約がついている。どのような順番で箱を開ければ財宝を見つけられるか、戦略を 1 つ求めよ。不可能な場合は -1 とせよ。

制約

• 
• 
• 

考えたこと

seica ちゃんとの議論で

• まず「箱をこの順番で開ける」というのを決めたときに、マジシャンとしてはどうするのが最適なのか

を考察するのが良さそうということになった。こういう問題ではしばしば、「箱を空ける順番の調整」と「マジシャンがどうするか」を一緒くたに考えて混乱したりしがち。。。まずは順を追ってやって行くのがよさそう。

まず、マジシャンとしては限られた移動回数で、財宝を逃がしたい。例えば として、箱をあける順序が

1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5

だった場合には、マジシャンは以下のように財宝を動かすのが最適戦略 (より少ない移動回数で、上の数列の一番先まで進めるという意味で) となる。

1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5
            o           o           o           o           o           o

最初はなるべく遠くに置くのでかまわない。上の順序に対しては、1, 2, 3, 4 に財宝を最初に置く意味はない。基本的に後ろに置いた方が後の選択肢が広がる。

そして最初に 5 に置いた後は、次に 5 には行けないので、5 に行かない範囲で 4 が最遠の箱となる。以後、4 個置きに財宝を動かす感じになる。

さて、もう少しランダムなケースとして

1, 3, 2, 4, 5, 1, 2, 1, 3, 3, 4, 5, 4, 2, 1, 3, 2, 4

であったとき、マジシャンは以下のようにするのが最適戦略になる:

1, 3, 2, 4, 5, 1, 2, 1, 3, 3, 4, 5, 4, 2, 1, 3, 2, 4
            o                 o              o

各箱を何回開けられるかにも依存するので一概には言えないが、さっきと比べると、マジシャンはより少ない移動回数で遠くまで行っているように見える。

マジシャンの基本戦略は

---

今いる箱の番号を除き、残りの番号が一通りすべて出揃った瞬間の、最後に登場した番号の箱に行く

---

となる。これがマジシャンにとって、各時点において、上の数列の最も遠くへと遷移できる方法となる。

マジシャンの戦略を踏まえて

以上のマジシャンの戦略を踏まえて、箱を空ける立場としては

---

最適戦略に則ったマジシャンに番号 i の箱を開けられた時点で、次に i を除いて「残り回数」が最も小さい番号 j を求め、i と j 以外の箱を 1 回ずつ並べて (複数回並べる意味はまったくない)、最後に j を置いて、そこにマジシャンに開かせる

---

とするのが最適戦略となる。こうすることで、j をマジシャンに開かせる手前では j を消費せず、次にマジシャンに開かせるまでの間にも j を消費せず、j を節約して使うことができる。

この戦略にしたがって、途中で a[i] が負になったら -1

面白いケース

では のようなケースがギリギリで、 では のようなケースがギリギリなのだが、 では例えば のようなケースもありになる。

最初は、数列は基本的に最大と最小との差が 1 のケースがギリギリになるものだと勘違いしたりしていた。

#include <iostream>
#include <vector>
using namespace std;

int N, K;
vector<int> a;

bool solve(vector<int> &res) {
    int prev = -1;
    for (int _ = 0; _ < K+1; ++_) {
        int ma = 10000;
        int mai = -1;
        for (int i = 0; i < N; ++i) {
            if (i == prev) continue;
            if (ma >= a[i]) ma = a[i], mai = i;
        }
        for (int i = 0; i < N; ++i) {
            if (i == prev || i == mai) continue;
            res.push_back(i + 1);
            --a[i];
            if (a[i] < 0) return false;
        }
        res.push_back(mai + 1);
        --a[mai];
        if (a[mai] < 0) return false;
        prev = mai;
    }
    return true;
}

int main() {
    cin >> N >> K;
    a.resize(N);
    for (int i = 0; i < N; ++i) cin >> a[i];

    vector<int> res;
    if (!solve(res)) cout << -1 << endl;
    else {
        cout << res.size() << endl;
        for (auto c : res) cout << c << " ";
        cout << endl;
    }
}