ABC206 F 解答

2021年6月25日 00:00

F - Interval Game 2（2221）

問題

問題文

T 個のテストケースについて、以下の問題を解いてください。
N 個の半開区間 [Li, Ri) ( 1 ≤ i ≤ N ) があり、 Alice と Bob がこの区間を使って次のようなゲームをします。
Alice から始めて、以下の操作を交互に行う。N 個の区間の中から、既に選ばれているどの区間とも共有点をもたない区間を 1 つ選ぶ。
先に操作を行えなくなった方が負けで、もう片方のプレイヤーが勝ちます。
双方のプレイヤーが勝利に対して最善を尽くした場合、どちらが勝つことになりますか？

制約

入力は全て整数
1 ≤ T ≤ 20
1 ≤ N ≤ 100
1 ≤ Li < Ri ≤ 100

考察

早速ですが、本問題では「Grundy数」というものを使用します。しかし、「Grundy数」の詳しい説明はしません。しっかりと説明しようとするとそれだけで、2記事ぐらいになってしまいます。公式放送でも詳しく説明してくれていますし、また典型90問でもテーマになっていますので、そちらにお任せします。

本問題はGrundy数の次の４つの性質がわかれば大丈夫です。

１）Grundy数は各盤面において割り当てられる0以上の整数

２）Grundy数が０の盤面は後手必勝、0以外なら先手必勝

３）Grundy数はその状態から遷移する状態のGrundy数のMex(Minimum EXcluded)で定義される

４）各Grundy数はその盤面の一部分のGrundy数のXORと一致する

４）だけちょっと補足します。例えば3つの山からおはじきを取るゲームをしているとしましょう。この時の盤面は３つの山にそれぞれ何個おはじきが残っているか、なのですが、この時のGrundy数は各山のGrundy数のXORで表すことが可能です。各山におはじきが（X,Y,Z）残っていたら、この時のGrundy数はXのGrundy数とYのGrundy数とZのGrundy数のXORで表されます。

Grundy数と何度も出てきて混乱してきましたが、必要な知識はこれだけです。

問題の解説に移ります。本問題では区間DPという考え方が登場します。が、そんなにアルゴリズム名を意識する必要はないかなと思います。問題を解いてみて、この解き方は区間DPと呼ばれるのね、ぐらいの認識で大丈夫です。

本問題はゲームをやる問題ですので、ゲームの典型に則ります。それは

後ろから考える

ということです。本問題ではAliceとBobが交互に区間を潰していくのですが、最終的にはどのような状態になるでしょうか。

与えられる区間によって異なりますが、理想的には全部のマスが選ばれた状態が最終状態になります。この状態ではどんなに頑張っても次の区間を選ぶことはできませんね。ということは、この盤面が回ってきたら負けてしまいます。先ほどのGrundy数を用いて表現するならば、Grundy数が0で後手必勝の状況です。

このように全部のマスが埋まった状態から逆向きに考えていきます。どんどん逆向きに考えていって、全部のマスが埋まっていない状態のGrundy数を見てあげるとどちらが勝つかわかります。

続きまして、とある盤面から取りうる状況を考えてみます。考える盤面は次の通りです。

選択可能区間は３つありますので、３つの状態に遷移します。この遷移を考えることで、この盤面のGrundy数がわかってしまうのです。

図の説明をしていきます。

まず、この図で何がしたいかといいますと、右上にあるこの盤面のGrundy数２を求めたいのです。遷移を考えることでこの値を求めていきます。

この盤面は１）２）３）の３通りに変化します。１）の時には[2,3)を選びました。この時、半開区間なので少し注意です。遷移後の盤面は２つに分かれてしまいましたね。一番上のGrundy数の性質にて全体のGrundy数は部分のGrundy数のXORということを述べました。ですので、分かれてしまった盤面のGrundy数は左区間の0と右区間の１のXORの１となります。ここで注意なのでが、このGrundy数は遷移前のGrundy数ではないということです。私はここの理解に時間がかかりました。遷移前は先にも言いましたがGrundy数は２ですね。これは１）の遷移をした後の盤面のGrundy数です。また、右区間のGrundy数は１となっています。これ説明が前後してしまって申し訳ないのですが、本説明と同様のことを右区間にて適用してあげると１と求めることが可能です。そのため、一旦「１」と受け入れていただいて、進んでいただきたいです。２）と３）も同様な議論によりGrundy数を求めることが可能です。

さて、遷移先のGrundy数は（１、１、０）とわかりました。ここで、再び先に述べたGrundy数の性質です。Grundy数は遷移先のGrundy数のMexで表されます。Mexは集合に含まれない非負整数の最小値ですので、この場合には２ですね。

ということで、この盤面のGrundy数が２と求まるわけです。

この過程で最も重要なのが、遷移前と遷移後の区間の長さを比較しますと、遷移前の方が長くなっているということです。区間を選択して潰していっているので、当然といえば当然なのですが、この性質のおかげで

区間の短いほうから計算することで、長い区間を考える際には必要な区間のGrundy数はすべて求まっている

という非常にありがたい状況が生まれているわけです。この性質を用いて計算をしていくためにこのアルゴリズムは区間DPと呼ばれるわけです。

短いほうから計算していくので探索順序は次の図のようになります

図の補足します。

まず、開始は一番上ですね。区間の長さ0として調べていきましょう。なのですが、区間0はどんな状況でも区間を選ぶことはできませんね。Grundy数は0となります。

次に区間長を1つ伸ばして１とします。左から順に調べていって、選択可能区間がこの区間にすっぽり収まっていればその区間が選択可能となります。現在考えている区間を選択可能区間で分けてあげましょう。現在の区間を[l,r)として、選択可能区間を[L[i],R[i])としましたら、区間は

[ l , L[i] ) と [R[i] , r )

に分かれます。これとっても重要です。

この時に、遷移先のGrundyをメモしておきましょう。全ての選択可能区間を調べたのちにメモに載っていない非負整数の最小値がそのGrundy数となります。

この辺はソースコードを見ながらの方が理解しやすいと思います。

これを続けていって、一番最後の最長区間のGrundy数を調べれば勝敗がわかります。本問題では、1 ≤ Li < Ri ≤ 100ですので、99マス目が最も左のマスになります。1から99マス目が指定区間になったときのGrundy数を求めればOKです。

考察はこれでおしまいです。あとは実装に関して少し補足します。今回は各区間のGrundy数を順番に求めていくので、次のようなデータを使います。

dp[ l ][ r ]:
[ l , r )の区間におけるGrundy数

最終的にdp[ 1 ][ 100 ]の値を見ることになります（実装は0-indexedですので、dp[0][99]の値を見ています。）あまり大きな声では言えませんが、少し長めに計算しても答えは変わりませんので、105ぐらいまでみても大丈夫です。範囲外参照だけ気を付けましょう。

実装

 #include <bits/stdc++.h> #define  rep(i,n) for(int i=0;i<n;++i) #define  reps(i,s,n) for(int i=s;i<n;++i)
using namespace std;
using ll = long long;
using P = pair<int, int>;
using T = tuple<int, int, int>;

const int M = 100;

int main()
{
   int t;
   cin >> t;
   while (t--)
   {
       int n;
       cin >> n;
       vector<vector<int>> dp(M + 5, vector<int>(M + 5));

       vector<int> L(n), R(n);
       rep(i, n) cin >> L[i] >> R[i];
       rep(i, n) --L[i];
       rep(i, n) --R[i];
       //区間の短いほうから計算する
       for (int w = 1; w <= M; ++w)
       {
           //区間の左端
           for (int l = 0; l < M; ++l)
           {
               //区間の右端（開く区間）
               int r = l + w;
               if (r > M) break;
               vector<int> s(M + 5);
               rep(i, n)
               {
                   //l,rの区間に選択可能区間が含まれていたら計算する
                   if (l <= L[i] && R[i] <= r)
                   {
                       //区間は[l,L[i]),と[R[i],r)にわかれる
                       //こことっても重要です

                       //出現したGrundy数に１を立てる
                       s[dp[l][L[i]] ^ dp[R[i]][r]] = 1;
                   }
               }
               //Mexを計算する
               rep(g, M + 5)
               {
                   if (s[g] == 1) continue;
                   dp[l][r] = g;
                   break;
               }
           }

       }

       if (dp[0][M-1] == 0) cout << "Bob" << endl;
       else cout << "Alice" << endl;

   }

   return 0;
}

あとがき

ゲーム問題＋Grundy数＋区間DPという問題でした。ゲーム問題とGrundy数が＋なのかはちょっと諸説ありそうですが、、

こうやってみると典型といえば典型要素の組み合わせなのかなと思います。でも、本問題を見てこの方針はなかなか思いつかないですね。難しいです。

本記事ではGrundy数の説明を飛ばしてしまいましたので、私が理解するのに大変役に立った記事を紹介します。また、典型90問でも取り上げられていたのでそちらも併せてご覧いただけると、さらに理解が深まると思います。典型の方が簡単（必要な要素が少ない）ので、こちらから解いてみても良いと思います。と思いましたが、こちらも十分難しいです。やっぱり、Grundy数自体が難しい概念なんでしょう。

031 - VS AtCoder（★6）

これで、ABC206の解説はおしまいです。久しぶりにF問題まで解説を書いたような気がします。時間が全くないといえば嘘になりますが、まあぼちぼち忙しさを感じるようになってきました。自分の勉強にもなるので可能な限り書きたないなあ、と思っていますが、そのあたりは私のやる気との相談でもありますので、まったりとやりたいと思います。

もし、あの回のあの問題の解説を書け！という方がいらっしゃいましたら、遠慮なくおっしゃってください、やる気があれば対応します。なければどうなるかわかりません。

とりあえず、ABC206を完走できたことを喜びつつ、この辺りで締めとさせていただきます。もし、記事内で分からない点、誤ってる点などありましたら、お知らせいただけると助かります。

ここまでお付き合いいただきありがとうございました。また、ABC207でお会いいたしましょう。

この記事が気に入ったらサポートをしてみませんか？