ARC112 - C - DFS Game
https://atcoder.jp/contests/arc112/tasks/arc112_c
概要
サイズがNの根付き木が与えられる。木の根は頂点1。 AliceとBobはこの木でゲームをする。
木の各頂点には最初はすべてコインが1枚ずつ置かれている。最初に駒を用意し、頂点1(根)に置く。手番はAliceから始まり、AliceとBobが交互に行動する。 2人はともに以下の条件で動く。
- 駒が今置かれている頂点にコインがあるなら、それを取って次の人に手番を回す。
- コインがない時、子の頂点のうちのどれかにコインがある場合は、その子のどれかに駒を動かす。そして次の人に手番を回す。
- コインがなく、すべての子の頂点にもコインがない場合は、親の頂点に駒を動かす。そして次の人に手番を回す。
- 根にいるとき、子のコインがすべてなくなったらゲームは終わり。
- 自分の獲得コインを最大化するように動く。
この時、Aliceの獲得するコインは何枚?
制約:$ 1 \leq N \leq 10 ^ 5 $
考え方
- ゲーム問題なのでまず例をトレースしてみる。一本道はAliceが全部とるetc
- 木構造なので、自分の子が及ぼす影響で自分自身を計算でき、自分の親、爺、etc以外の頂点には影響を及ぼさない->木DPをいい感じに求めればOK。
- 実験やサンプル3を見ると、子を巡って、また親の頂点に戻るときに、コントロール権が移ることがある。->コントロール権のやりとりが大事そう!
- 冷静に考察して、詰めていくと子をめぐるときのコントロール権の変遷の有無で場合分けして、計算すれば$ O(n \log n) $で求められる。->AC
考察
どのよう大筋で解くべきか
この問題は問題名の通り、DFSをするかのように駒は動くとわかる。この時、明らかに親頂点での計算結果は子頂点にのみ依存することから、木DPをすることが大筋となる。
動き方
すべての葉(子を持たない頂点)を、葉から見た初めての分かれ道までの距離を見てみる。例えば、
(1) -- (2) --- (3) -- (4) -- (5) -- (6) | ------ (7) -- (8) -- (9)
の頂点(6)は、枝分かれ(2)までの距離は4であり、頂点(9)は、枝分かれまでの距離が3である。
最初に、Bob(後手)が頂点(6)の方を選択すると、頂点(6)から(2)へ戻るときは、Alice-Bob-Alice-Bobであり、分かれ道を選択した時はBobが行先を選んでいたが、この時点での選択権はAliceに渡ることになる。これは、最初の枝分かれまでの距離が偶数の場合である。
最初に、Bob(後手)が頂点(9)の方を選択すると、頂点(9)から(2)へ戻るときは、Alice-Bob-Aliceであり、分かれ道を選択した時はBobが行先を選んでいたが、この時点でも選択権は相変わらずBobにある。これは、最初の枝分かれまでの距離が奇数の場合である。
すべての枝分かれの先は個のように単純に葉につながってる構造ではないものの、ひとまずこれで葉に直結する分かれ道に関しての利得やコントロール権の変遷を計算できた。葉に直結する枝分かれで、コントロール権を持つ人は、
- できるならば相手にコントロール権を押し付けたい(自分がコインをもらえるので)
- コントロール権を押し漬けられるような子が複数個あるなら、相手が得られるコインの数(つまり枝分かれから葉までの距離)が最小になるものから選ぶ
- コントロール権が変わる枝分かれがすべてなくなったとき、コントロール権がある人が残りのコントロール権が変わらない子をめぐることになり、結果的にこの時点でコントロールできない人は残りの子のコインをすべてもらえることになる。
これは、葉に直結する分かれ道の話だったが、一般の分かれ道にもこの話を帰着させよう。同様に、子へ行くことによるコントロール権の移り変わりがあるかに着目して、先ほどの考察を広げる。
以下のようにDPテーブルを定める。
dp[i] := 頂点iを始めて訪れた時、双方適切に行動して、コントロール権を持った人の得られるコイン-持ってない人の得られるコイン
お互いにコイン数を最大化したいので、これはどの方にとっても、獲得量の差の最大化でもある。
これを使って、先ほどの葉に直結する場合例では$ dp[3] = -4, dp[7] = -3 $である。(選ぶと相手が獲得し、自分が獲得できないため)
この一般化した時のコントロール権にまつわるアルゴリズムは以下である。
- コントロール権の変化がある子$ x $の場合、$ dp[x] $が大きい順(コントロール権がある人から見て、相手より一杯とれる順)に使う。
- コントロール権の変化がない子の場合、$ dp[x] > 0 $なら最初にコントロール権がある人が全部使う。(使ってもコントロール権が向こうに行かないので、全部取るのが最適)
- コントロール権の変化がない子で、$ dp[i] \leq 0 $の場合、使っても行き損である。(相手が得するのみならず、コントロール権も押し付けられない)これは最後の最後までAliceもBobも取りたくない。
このことから、子の$ dp[x], dp[y], \cdots $がそろった時に、親の$ dp[a] $(頂点$ a $を初めて訪れた時に、コントロール権を持つ人の獲得コイン-持たない人の獲得コイン)は次のように計算すればよい。
- コントロール権が変わらない子$ x $に関して、$ dp[x] > 0 $の$ dp[x] $をすべて$ dp[a] $に加算。
- コントロール権が変わる子$ x $に関して、$ dp[x] $が小さい順に並べ、1, 3, 5, ...番目は加算(自分がとるため)、2, 4, 6, ...番目は減算(相手がとるため)する。
- 最後に、コントロール権を持つ人がコントロール権不変の$ dp[x] \leq 0 $の子をすべて取る。
これをすべての分かれ道について、再帰的に計算することでこの問題は解くことができた。
計算量についてだが、木DPなのですべての頂点を1度は見ることなり、$O(n)$である。また、分かれ道では以上のアルゴリズムを行うためにソートをする必要があるが、この部分ではたかだか$O(n \log n)$なので、解くことができた。
ACソースコード
C++ いろいろわかりやすい?コメントがついてる。ちょっと冗長。
最後に
コンテスト中に正しい考察してたのに詰め切ることができなかった。お前実装力足りてたらすぐに青上位だぞ精進しろ。
ABC191 - D - Circle Lattice Points
https://atcoder.jp/contests/abc191/tasks/abc191_d
概要
座標平面上で、$ (X, Y) $中心で半径が$ R $の円の内部や辺上に、何個の格子点(座標がすべて整数の点)がある?
制約:$ 0 \leq |X|, |Y|, R \leq 10 ^ 5 $。$ X, Y $は小数点以下4桁まで与えられる
考え方
- 円のうち、y座標で見れば最大でも$ O(Y) $通りのy座標の点しか答えの候補にならない。y座標の値さえ決まれば、円内に格子点となれる点の数は簡単に二次方程式を解くことで数えられる。
- doubleで実装。->WA doubleでは精度が足りない。これを補う工夫が必要。
- long long なら$ 10 ^ 18 $の精度で計算できる。今回はこれならギリギリいけそう。
- 入力をlong longに直して(ここ罠あり)、自前でsqrtを書く。
- AC!
考察
この問題の解法の大筋は1通りであるが、精度を解決するためには2通りのやり方がある。
- $ 10 ^ 4 $倍して、long longで計算する。
- long double で精度の問題を解決し、辺上ギリギリの点を数えるために$ R $にEPSを足すことで考える。
アルゴリズム
この問題を解くアルゴリズム自体は平易である。格子点の数を数えるやり方として、「円の内部や辺上に含まれている格子点のy座標はたかだか$ O(Y) $通りしかない。」を利用して、y座標を固定した時に、円の内部や辺上にある格子点は、円の式$ (x - X) ^ 2 + (y - Y) ^ 2 = R ^ 2 $から二次方程式を解けば求まるとわかる。
誤差の問題を考えなければ、√の計算に$ O(\log |Y|) $かかると考えられるので、全体で$ O(|Y| \log |Y|) $程度の計算量で収まる。
精度の問題
しかし、ここで考えなければいけないのはdoubleの精度で足りるか?である。 doubleは倍精度浮動小数点であり、これの計算機イプシロン(doubleで表せる1以上で最小の数と1の差)は$ 2.220 \times 10 ^ {-16} $である。
今回の場合、ルートで最大$ (10 ^ 5) ^ 2 - (10 ^ {-4} ^ 2) $の計算をすることになる。この時、要求される精度は$ 10 ^ 18 $レベルであり、明らかにdoubleの計算機イプシロンを超えている。 つまり、doubleによる計算では今回の場合精度が足りないのである(実際多くの人はここで落ちたがゆえに青上位の難易度になっている)
精度問題の回避手段(方法1)
では、どのように精度問題を回避するのか?ここで着目したいのは、doubleの分解能?は$ 2.220 \times 10 ^ {-16} $レベルであるが、long long は$ 9.0 \times 10 ^ {18} $レベルの精度の演算ができる所である。つまり、64bit整数として計算してあげれば精度面ではなんとか(ギリギリだが)なりそうということだ。
というわけで、まず入力の$ X, Y, R $をすべて$ 10 ^ 4 $倍して、整数としよう。この時、実は以下のように書くとWAになる。
long long mX = X * 10000.0;
ここでも多くの人がつまずいた。そのまま代入による切り捨てや、ceil()は、負の数ではうまく働かなかったり、$ X \times 10000.0 $の値自体を床関数で計算しても綺麗に求まらないことになる。
実際に、以下の場合でエラーが生じる。
99999.9999 * 10000.0 99999.9999は倍精度浮動小数点で表すと、1.525878904724121 * 2^{16}であり、 (Wolfram Alphaで計算すると)、999999998.999...となってしまう。
このような状況では、roundll()で四捨五入するべきである。 そもそも浮動小数点では多くの値は循環小数となり、綺麗に表せない。個の誤差は普段とても小さく、(coutで出力すれば)見た目上は綺麗に表せているものの、計算を重ねることによって誤差が蓄積して最終的な値はずれてしまう現象が起きる。この時、誤差が小さいうちに毎回roundなどの処置を考えるべきである
long long mX = round(X * 10000.00);
二乗根の計算(方法1)
STLのsqrtは、doubleなどの浮動小数点仕様である。この問題では、doubleは精度不足から、std::sqrtを用いることができない。
そこで、$ \sqrt{x} $は単調増加であることを利用して、二分探索で求めることができる。具体的には以下の通りである。
ll my_sqrt(ll x) { ll ok = 0, ng = 2 * 1e9; while (ng - ok > 1) { ll mid = (ok + ng) / 2; if (mid * mid <= x) ok = mid; else ng = mid; } return ok; }
long doubleで精度問題を対処(方法2)
long double(4倍精度浮動小数点)の計算機イプシロンは$ 1.926 \times 10 ^ {-34} $であり、今回の計算の場合ではこれで精度が事足りるとわかる。
この時、計算幾何によるあるテクニックとして、辺上にあるものの数え上げは、わずかに大きい外形の内部で考える、がある。 例えば、今回の場合は半径$ R $ではなく、ある十分小さな値$ \epsilon $を用意して、$ R + \epsilon $が半径の円の内部を代わりに考える。 この操作を施せば、辺上にあるものは安全に数え上げることができる。
今回の場合、一番精度が危ういようなケースは以下の通り。
$$ X = 0, Y = 100000, R = 100000, x = 0.0001, y = 0 $$
この場合は、ギリギリ入ってないが、$ R $の代わりに$ (R + \epsilon) $を用いて、ギリギリ入ってしまう場合は、 $ 10 ^ {10} + 10 ^ {-8} = (10 ^ 5 + \epsilon) ^ 2 $であり、解くと$ \epsilon = 5.0 \times 10 ^ -{14} $となる。これを超えるとこのようなエラーが生じるので、 $ \epsilon < 4.0 \times 10 ^ {-14} $とするのが無難である。
このように、計算幾何での$ \epsilon $はこのように最悪ケースでエラーする限界を考えて決めるとわかりやすい。
ACソースコード
解法1
C++ 自前で10000倍にceilやroundを実装した。
解法2
C++ EPSを$ 10 ^ {-14} $にした。$ 4.0 \times 10 ^ {-14} $でも落ちるみたいなので、安全を取ろう。
最後に
コンピューターアーキテクチャや開発よりの所を問われた。こういうところは実務でも生きてくるので落としちゃダメだ。
ACL Beginner Contest F - Heights and Pairs
https://atcoder.jp/contests/abl/tasks/abl_f
問題概要
$ 2N $人の人がいて、それぞれ身長が$ h[i] $である。 この人たちで、ペアを$ N $組作っていく。(任意の人は1つのペアにしか属してはいけない)
ここで、すべてのペアのうちの2人で、お互いの身長が異なるという前提で作ることにする。
この時、何通りのペアの組方があるのでしょう?$ 998244353 $で割ったあまりを答えてください。
ただし、別にカウントする条件は、すでにあるどの組方とでも、少なくとも1ペア以上で構成員が異なるである。
入力:$ 1 \leq N \leq 50000, 1 \leq h[i] \leq 100000 $
続きを読むARC059 - キャンディーとN人の子供
https://atcoder.jp/contests/arc059/tasks/arc059_c
問題概要
N人の子どもがいる。それぞれ、はしゃぎ度という整数値A[i]があるとする。 この時、それぞれの子どもが飴をB[i]個もらっているとき、全体の活発度は以下のように求められる。 $$ \Pi _ {i = 1} ^ {N} A[i] ^ {B[i]} = A[1] ^ {B[1]} \cdot A[2] ^ {B[2]} \cdot ... $$
始めに飴をC個持っているとする。この飴の全通りの配り方をしたときに、対応する{A[i]}の組での活発度の和を$ f(A[1], A[2], \cdots, A[N]) $とする。
Subtask1
{A[i]}が与えられる。この時のfをmod $ 10 ^ 9+7 $で求めよ。
制約: $ 1 \leq N \leq 400, 1 \leq C \leq 400, 1 \leq A[i] \leq 400 $
Perfect Task
{A[i]}が与えられる代わりに、{A[i]}と{B[i]}が与えられる。以下の式をmod$ 10 ^ 9 + 7 $求める。 $$ \sum _ {x _ 1 = A[1]} ^ {B[1]} \sum _ {x _ 1 = A[2]]} ^ {B[2]} \cdots f(x _ 1, x _ 2, \cdots, x _ n) $$
制約: $ 1 \leq N \leq 400, 1 \leq C \leq 400, 1 \leq A[i] \leq B[i] \leq 400 $
続きを読むNTT(数論変換)のやさしい解説
この記事は、高速フーリエ変換の1つのバリエーションである、Numeric Theory Translation(数論変換)の詳しい解説記事です。
あまりなかったので書きました。
数論変換にありがちな
- なんで$ 10 ^ 9 + 7 $じゃダメなのか
- 原始根って何?
とかについてもこれを見ればわかります。
前提知識としては、Fast Fourier Translation(高速フーリエ変換)が必要です。 kaage大先生のQiita記事とかは中高生にもわかりやすく書かれています。
下に一応自分の勉強ノートを載せます。(上の記事の行間を埋めた感じです)
では、数論変換について説明したいと思います。
高速フーリエ変換の弱点
高速フーリエ変換は正しいですが、弱点として精度が足りないというのがあります。 なぜならば、複素数の1の$ 2 ^ m $乗根は計算上ではれっきとした64bit倍精度浮動小数点のdoubleのペアなので、$ m $が増えるとdoubleではどうしても精度が足らなくなります。
一例として、$ (10x ^ 9 + 9x ^ 8 + 8x ^ 7 + 7x ^ 6 + 6x ^ 5 + 5x ^ 4 + 4x ^ 3 + 3x ^ 2 + 2x + 1) ^ 2 $の畳み込みを見てみましょう。自作のFFTの計算結果は以下です。
(1, 7.43086e-14) (4, 1.03461e-13) (10, 1.03814e-13) (20, 1.16975e-13) (35, 1.51601e-13) (56, 1.64745e-13) (84, 1.56105e-13) (120, 1.48062e-13) (165, 1.53148e-13) (220, 1.27886e-13) (264, 8.78265e-14) (296, 2.90458e-14) (315, -6.56697e-14) (320, -1.01708e-13) (310, -1.21006e-13) (284, -1.0951e-13) (241, -1.74825e-13) (180, -1.87862e-13) (100, -1.75074e-13)
実数部分は問題ありませんが、複素部分は$ 10 ^ {-13} $オーダーのエラーが出ています。倍精度浮動小数点の計算機イプシロン(double型で表す1より大きい最小の数)が$ 2.220 \times 10 ^ {-16} $ であることを考えると、なかなかに無視できない誤差ではないかとわかります。
実際、畳み込みの結果が$ 10 ^ {8} $オーダーになると、倍精度浮動小数点では精度が足りなくなります。そして、畳み込みなどを使う数え上げではこの限界をいとも簡単に突破する問題が多いです。
FFTのアルゴリズム自体は正しいのですが、計算機の精度保持の限界の問題で大きな値は正しく計算できないのです。
FFTのn乗根
FFTのn乗根は、複素数$ \zeta _ n = (\cos \frac{2 \pi}{n} + i \sin \frac{2 \pi}{n}) $が採用されていました。この値は、以下の性質を持っていました。
- $ \zeta _ n ^ 0, \zeta _ n ^ 1, \cdots , \zeta _ n ^ {n - 1} $の値はみんな違う。
- $ \zeta _ n ^ n = 1 $(n乗すると単位ユニット(=単位元)になる)
- $ \sum _ {i = 0} ^ {n - 1} (\zeta _ n ^ k) ^ i $は$ 0(k \neq 0) $か$ n(k = 0) $
逆に言うとこれを満たすものであれば、離散フーリエ変換に代入する値としてOKです。(FFTをするために$ n = 2 ^ m $の形としないといけないけど)
複素数の世界では、候補はこれしかありませんでした。しかし、世界を変えてみるとどうなるでしょう?
mod pの世界
整数を$ p $で割ったあまりの世界(剰余環)を考えます。この世界での四則演算について考えると、割り算以外なんでもできそうな気がします。 そして、$ p $が素数の場合、割り算も定義できます。(けんちょん大先生の記事を参考)
そして、この世界で、$ n $乗したら1になるものも$ n $乗根といいます。
mod pの世界の原始根
ここで、mod $ p $($ p $は素数)の世界の原始根という考え方を説明します。
mod $ p $の世界で、ある要素$ g $があって、$ g ^ 0, g ^ 1, g ^ 2, \cdots , g ^ {p - 2} $がみんな違う値を取るような$ g $を原始根といいます。
詳しいのはけんちょんさんと同じ研究室の人が書いた高校数学の美しい物語の記事をご覧ください。
mod pの世界での離散フーリエ変換
mod $ p $(素数)の世界でも、$ n=2 ^ m $乗根にあたるものを考えてみます。これは$ g ^ n = 1 $を満たす必要があります。ところで、mod $ p $の世界で有名なフェルマーの小定理があり、 $$ g ^ {p - 1} \equiv 1 (mod p) $$
が成り立ちます。このことから、$ p = 2 ^ m \times a + 1 $($ a $は2と互いに素)と書ける場合、 $$ g ^ {2 ^ m \times a} \equiv 1 (mod p), (g ^ {a}) ^ {2 ^ m} \equiv 1 (mod p) $$
となります。つまり、 $ 2 ^ m $乗根は$ g ^ {a} $ となります。(一方で、$ 2 ^ {n + 1} $乗根は存在しません)
これで、複素数の上で定義していた$ 2 ^ m $乗根を定めることができました。 これを2乗することで、$ 2 ^ {m - 1} $乗根も複素と同様に定めることができますので、mod $ p $の上の1乗根、2乗根、4乗根、...、$ 2 ^ {m} $乗根と全て求められます。
mod $ p $の上での割り算も定義されているので、FFTをmod $ p $の世界で考えることができました。
$ 10 ^ 9+7 $と$ 998244353 $の違い
NTT有名素数modとして、$ 998244353 $が挙げられます。この値は、 $$ 998244353 = 2 ^ {23} \times 119 + 1 $$ となります。
これは、mod $ 998244353 $では$ 2 ^ {23} $乗根まで存在する($ 2 ^ {24} $乗根はない)ということです。 $ 2 ^ {23} $乗根まで存在するので、mod $ 998244353 $の世界で$ 2 ^ {23} = 8300608 $から、$ 8388607 $次までの畳み込みを、FTTと同じように分割統治で計算することができます。
このことから、競プロでは一般的に実用的な畳み込みの余りは$ 998244353 $となっています。
一方、$ 10 ^ 9 + 7 $の場合 $$ 10 ^ 9 + 7 = 2 ^ 1 \times 50000003 + 1 $$ であります。
これは、mod $ 10 ^ 9 + 7 $ の世界では、2乗根までしかなく、4乗根すらないということです。 つまり1次式までしか畳み込みできません。 さすがにこれは使えないです。
$ 10 ^ 9+7 $で無理やり畳み込みをするには?
mod $ 10 ^ 9+7 $は1の4乗根が存在しないことから、畳み込みはかなり困難になります。一応頑張ればできるらしいのですが、計算量的にも実装量的にも手法的にも全く実用的ではありません。しかし、任意modでの畳み込みをしたいというのならば、複数回のNTTとGarnerのアルゴリズムというもので復元できます。
やり方の詳細はここにあります。
実装例
//mintはModintである。 //畳み込みをする前にsetup()を実行する。 typedef std::vector<mint> vectorM;//NTT用のmintのベクター型 const int DIVIDE_LIMIT = 23;//99...の有名素数は23回分割統治できる。 mint ROOT[DIVIDE_LIMIT + 1];//[i]は2^i乗根 99...の有名素数の原始根は3で、そこから2^22乗根, 2^21...などをsetup()で計算する。 mint inv_ROOT[DIVIDE_LIMIT + 1];//[i]は2^i乗根の逆数 setup()で計算する。 mint PRIMITIVE_ROOT = 3; void setup() { ROOT[DIVIDE_LIMIT] = modpow(PRIMITIVE_ROOT, (MOD - 1) / modpow(2, 23).val);//99..なら119乗 inv_ROOT[DIVIDE_LIMIT] = 1 / ROOT[DIVIDE_LIMIT]; for (int i = DIVIDE_LIMIT - 1; i >= 0; i--) { ROOT[i] = ROOT[i + 1] * ROOT[i + 1]; inv_ROOT[i] = inv_ROOT[i + 1] * inv_ROOT[i + 1]; } } vectorM ntt(const vectorM& f, const int inverse, const int log2_f, const int divide_cnt = DIVIDE_LIMIT) { vectorM ret; if (f.size() == 1 || divide_cnt == 0) { ret.resize(f.size()); mint zeta = 1; for (int i = 0; i < ret.size(); i++) { mint now = zeta; for (int j = 0; j < f.size(); j++) { ret[i] += f[j] * now; now *= zeta; } zeta *= ((inverse == 1) ? ROOT[0] : inv_ROOT[0]); } return ret; } vectorM f1(f.size() / 2), f2(f.size() / 2); //f1とf2を作る。 for (int i = 0; i < f.size() / 2; i++) { f1[i] = f[i * 2]; f2[i] = f[i * 2 + 1]; } vectorM f1_dft = ntt(f1, inverse, log2_f - 1, divide_cnt -1), f2_dft = ntt(f2, inverse, log2_f - 1, divide_cnt - 1); ret.resize(f.size()); mint now = 1; for (int i = 0; i < f.size(); i++) { ret[i] = f1_dft[i % f1_dft.size()] + now * f2_dft[i % f2_dft.size()]; now *= ((inverse == 1) ? ROOT[log2_f] : inv_ROOT[log2_f]); } return ret; } //eraseHigh0は高次項が係数ゼロ、vectorから排除するかどうか vectorM mulp(const vectorM& _f, const vectorM& _g) { vectorM f = _f, g = _g; //fとgの次数の和以上の最小の2冪-1を次数とする。 int max_dim = 1, log2_max_dim = 0; while (f.size() + g.size() > max_dim) max_dim <<= 1, log2_max_dim++; f.resize(max_dim), g.resize(max_dim); //多項式fとgのDFT結果を求める。 O(n log n) vectorM f_dft = ntt(f, 1, log2_max_dim), g_dft = ntt(g, 1, log2_max_dim); //f*gのDFT結果は各f_dftとg_ftの係数の積。O(n) vectorM fg_dft(max_dim); for (int i = 0; i < max_dim; i++) { fg_dft[i] = f_dft[i] * g_dft[i]; } //fg_dftをDFT vectorM fg = ntt(fg_dft, -1, log2_max_dim); //最後にmax_dimで割る for (int i = 0; i < fg.size(); i++) { fg[i] = fg[i] / max_dim; } return fg; }
最後に
NTTについてかなり一杯学べました。これがみんなの役に立てれば幸いです。
参考文献
- FFT(高速フーリエ変換)を完全理解する話, kaage, 2020/2/6
- 競技プログラミング だれでもわかる FFT/NTT 入門, monkukui, HCPC, 2020/7/13
- FFTとNTTとFMTと, Peria Peria, 2020/12/31
- 「1000000007 で割ったあまり」の求め方を総特集! 〜 逆元から離散対数まで 〜, drken, 2021/1/31
- 原始根の定義と具体例(高校生向け), Masuo, 2016/5/22
AGC045 - A - Xor Battle
概要
以下の問題がTケース与えられるので、それについてT回回答すること。
長さNの配列{A_i}が与えられる。そして、もう1つ長さNの文字列Sが与えられ、それは0と1のみに構成される。0さんと1さんの2人はこの数列を使って、次のようなルールでゲームを行う。
- という変数を用意し、で初期化する。
- S[i]が0だったら0さんの手番、1だったら1さんの手番
- 自分の手番では、を行うか、何もしない。
各々最善を尽くした時に誰が勝者になるのでしょう?
制約:
1 <= T <= 100, 1 <= N <= 200, 1 <= A[i] <= 10^18, |S| = Nで0か1で構成されている。
解法
以下は全部1-indexで解説する。
このようなゲーム問題では、詰んだ局面から逆算するのが常であるので、詰む=勝ち確定の局面をいくつか考察していく。
S="*1"(最後が1のような文字列)の場合
この場合は、明らかに1さんが勝つ。なぜならば、最後の手番が回ってきたとき
- ならXORをする。この時より必ず
- ならXORをしない。何もしなくても勝てるからである。
S="*10"(最後が10のような文字列の場合)
この場合は、1さんがN-1手目でかを作ってしまった or 作らざるを得なかった場合、0さんはXORをしない or することで必ずにすることができる。
逆に、1さんがN-1手目でを満たせれば1さんの勝ちが確定するのだ。
しかし、これだけではまだ難しい。なぜならばN-1手目にたどり着くまでには1さん以外にも0さんの手番が存在しているので、1さんが一意にの値を決められるとは限らないので、考えるのが難しいと思えるからだ。
では、逆に今手目を見ているとして、に関係がなくいくつかの局面での勝ち負けを断定する方法はあるのだろうか。これについて掘り下げると、どうやらの値が重要らしい(情報量0の発言)。
ここで、の時、の時を考える。この時、最後の2手についてだけ言うのであれば、お互いに打ち消せる手であると認識できる。(XORは2回すると元に戻る。1さんがやる->0さんがやる or 1さんがやらない->0さんがやらない)
逆に、の場合ではどうだろうか。実はこの時は1さんの勝利が確定するのである。をでは打ち消せないことを解釈すると以下のようになる。
- にはどこかの桁などでと違っていて、その結果お互いに打ち消すことが不可能。その違う桁の位の集合をXとする。
- 手までに、Xに入っている桁の位たちが、ですべて立っていなかったら、1さんはをXORすることで立てることができる。
- 手までに、Xに入っている桁の位たちが、で1つでも立っていたら、1さんは手番をパスすれば、0さんは必ず手目でそれを消すことができない。
よって、の場合、1さんが勝利確定である。
逆に、の時は、まだ勝負はわからない。これは最後の2手を削って再び考えることができる。
S="*100"、(最後が...100で終わる)の場合
この場合に先ほどの考えを適用させて考えてみる。この時、先ほどのであるか?という条件は、少し考えると、「とを自由にXORして、を作れるか?」というのにかわるとわかる。
つまり、とをそれぞれ1回までXORに使用可能なときに、を作れるか?という問題に対して、
- 作れる=まだ勝負はわからないとして、もう1つ前を見ていく。
- 作れない=を1さんがXORすれば勝ち確定。
と先ほどのS="*10"から拡張できる。
これをさらに拡張すると、以下のような事実が得られる。
について、1が手目だとして、をまで各々最大1回まで使ってXORして、
- 作れる=勝敗決定できないので、手目を見ることになる。(手目が0さんの手番なら、これより前の1さんの動作に対して使えるかもしれない切り札が1つ増えるだけである)
- 作れない=1さんがこれをXORすればいいので、1さんの勝ちである。
これで勝敗決定問題をかなり一般化できた。
ところで、理系大学生などの方は、これが線形代数の線形空間、基底という概念とこれは非常に似ていることに気づかないだろうか?
実は、XORという演算は各桁に分解すると、「mod 2の上で行われている演算」であると言い換えることができ、今回の場合であることから、とのXORは、60次元のmod 2上でのフィールドそのものであるとみなせる。
そして、いくつかのベクトルを好きな個数だけ、自由に足し引き出来るとき、指定したベクトルが作れるか?は明らかに線形空間に含まれるベクトル、ひいては基底で求められるベクトルが作れるか?と全く同じことである。
というわけで、後は線形代数の問題を解決できれば、この問題は解けたと言えるだろう。
線形空間と基底については以下の解説サイトなどで参考してください。
線形空間(ベクトル空間)を画像と具体例で解説 | 大学1年生もバッチリ分かる線形代数入門
【線形空間編】基底と次元と成分 | 大学1年生もバッチリ分かる線形代数入門
つまり、
のを毎回たかだか1本まで足すことができるmod 2の60次元の線形空間で、を作れるか?という問題と全く同じである。
まず、を基底にまとめ直そう。(があるのならば、は不要。)これは、すべての基底候補のベクトルを縦or横に並べた行列を作って、行列の基本変換を施すことで変形できる。
ちなみに、行列の基本変換といったが、これはmod 2の上なので数倍にする必要性はなく、結局のところある行 or 列を別のに足すことを繰り返すことである。(XORによる行列の特徴でもあり、これを利用して実装はスマートに書ける)
行列の基本変換を施すことで、逆三角行列という形に持っていくことができる。これは以下のような形で、
対角線上にはすべて1が乗っており、それ以外は0であるという性質を持つ。(右端の対角線が切れている部分は無視する)この性質から、「でその桁に+1(mod 2)をしたいときには、決まった基底を選ぶとできる」という重要な性質が導ける。
今まででは、いくつかの候補のうちから総当たりで2の累乗回最悪見る必要があったが、基底に整理して逆三角行列の形で見れば、基底を上から見て、採用or不採用を一意に選べるので、計算量は大きく改善したことになる。
これで掃き出し法を行った結果、新しく加えたいベクトルの行 or 列が行列の基本変換によってとなっていたら、それは既存の基底で作れることを表していて、逆にならなかったら、既存のでは作れないということになる。(これが1さんの手番の時ならば1さんの勝利が確定し、0さんならばこれを基底として線形空間に加えればよい)
ところで、もう1つ考慮するべき点がある。一般的には、行列の基本変換を施して、基底を1組作ったときには、「変換前で作れたすべてのベクトルと、各基底の任意の実数倍の和で作れるベクトルは全く同じ線形空間をなす」ということであるが、任意の実数倍というところと、今回の問題の各はたかだか1回までしか使えないというところで少し違うのだ。
しかし、今回に関してはそれは安全である。なぜならば、mod 2の世界であるので、係数自体は整数である上に、0か1しか係数にありえないとわかる。これは、同じ数に対して、XORが2回したら0になることに起因する性質である。
なお、mod 2の上での線形代数は普通の線形代数と違って多くの便利な性質があり、計算もbit演算を用いて簡便と高速化ができるので、普通の線形代数計算ライブラリとは別個な実装がされていることが多い。
解法のまとめ
ここまでの話を整理すると以下のようになる。
実装
掃き出し法によって規定を作る部分はこのように実装した。
vector<ll> V;//この線形空間に新た加わるベクトルが含まれているか?を計算するために行列の基本変形で対角線の片側だけに並ぶあの形に掃き出し法を使う。 //掃き出し法自体はXORなのでmod2の上でできるbit演算を行う。 auto get_MSB = [](ll x) {return x & (-x); }; auto contain_in_V = [&](ll new_v) { for (int i = 0; i < V.size(); i++) { if ((get_MSB(V[i]) & new_v)) new_v ^= V[i]; } //0になったら、既存の基底で作れちゃうということなので追加する必要なし。 return new_v; }; auto insert_to_V = [&](ll new_v) { ll ret = contain_in_V(new_v); if(ret == 0)return; V.push_back(ret); };
ここでは先ほど解説では逆三角行列としたが、左右を反転した変則的な逆三角行列で考えている。
この変則的な逆三角行列にMSB()という一番下の桁だけを立てるbit演算を駆使すると、一番右端のつまり対角線上に乗っている1のみが立つ値が得られる。新しく加えるnew_vのi桁目が1であるのならば、必ずこの基底を加えてi桁目を0にしないといけない。(^での演算部分)
contain_in_V()で得られた値が0であるのならば、加えたいnew_vはその線形空間に含まれるということであり、0でなければnew_vから抽出した基底が得られる。
insert_to_V()はその値に応じて線形空間に既定に挿入をする操作を行っているだけである。
参考文献
敬称略
公式解説
Editorial - AtCoder Grand Contest 045
maspyさん
[AtCoder 参加感想] 2020/06/07:AGC045 | maspyのHP
kappaさん
AGC 045 A Xor Battle 解説 - 情報の坩堝的な
deoxyさん
AtCoder Grand Contest 045 - A. Xor Battle 解法ログ - deoxy’s diary
その他多数の方に感謝。