ARMERIA

Rubyと競技プログラミングの話　AtCoderやCodeforcesの問題解説記事が多め。

CADDi 2018　参加記録＆解説（C～E）

AtCoder プログラミング 競技プログラミング

2問速解きでレート微増。悪くはないけど良くもない。

f:id:betrue12:20181223010458p:plain

C - Product and GCD

C - Product and GCD

解法

各素因数ごとに考えてみます。

ある素数 p について、各 a_{i} ごとに「 a_{i} には素因数としていくつ p が含まれているか？」を考えます。その個数の最小値を m_{p} とすると、 \gcd(a_{1}, ..., a_{N}) には p が m_{p} 個含まれます。

a_{i} の積 P が与えられているので、素数 P に素数 p がいくつ含まれているかは素因数分解で計算できます。この個数を n_{p} 個として N 個の要素に分配するとき、なるべく最小個数が大きくなるようにするには均等に分配するとよいです。結果として、最適に分配したときには m_{p} = \lfloor\frac{n_{p}}{N}\rfloor となります。

そのため P を素因数分解して、各素因数 p ごとに \gcd(a_{1}, ..., a_{N}) に含まれる個数 m_{p} を求め、全て掛け算すると答えが求められます。

ACコード

D - Harlequin

D - Harlequin

解法

結論は公式解説にある通りなので、ちょっと別のことを書きます。

ゲームの問題の解き方は「Grundy数を計算する」「遷移を考えてDP」「実験してエスパー」など色々タイプがありますが、

  • まず初手で「必勝状態」に持っていって、それ以降は相手の行動の真似をしたり打ち消したりするような操作を取り続けることで必ず勝てる

という視点で考えると解ける問題がけっこうあります。

ちょっと抽象的なので、今回の問題よりも簡単な具体例を出してみます。

（例）石取りゲーム

  • 全部で n 個の石がある。各プレイヤーは交互に、 1, 2, 3個 のいずれかの個数で石を取る。最後に石を取った人が勝ち。

というゲームを考えます。

このゲームには必勝法があり、

  1. まず、自分のターンの終了時に石が4の倍数である状態にする。これが「必勝状態」である。
  2. 相手が石を k 個取った場合、自分は石を 4- k 個取る。
    • 取れる石の個数が1, 2, 3個なので、これは必ず可能。
    • このように立ち回ると、必ず自分のターンの終了時には石が4の倍数になっている。
  3. これを繰り返すと、自分のターンの終了時に石が0個になるので、勝ち！

というのが必勝法です。このときの勝敗は

  • n が4の倍数でないときは、先手が初手で4の倍数にできるので勝ち
  • n が4の倍数でないときは、先手が初手で4の倍数にできないので、後手に必勝法を取られて負け

となります。「相手が何をしても、必勝状態に戻せる」というふうに、必勝状態と戦略を選ぶのが一番のポイントです。

今回の問題の場合

この考え方にあてはめて今回の問題を考えてみると、

  • リンゴの数が全部偶数である状態が「必勝状態」。
  • 必勝状態から相手がリンゴを食べた直後は奇数のリンゴが必ずあるので、奇数のリンゴを全部1個ずつ食べることで必勝状態に戻せる。

という発想をすることができます。

もちろん最初に小さい数で実験をしてみることはとても効果的です。実験で思いついた仮説を証明するときに、この「必勝状態を保つ」という考え方のパターンを知っておくとちゃんと証明できることがあります。

蟻本に詳しく解説がありますが、Grundy数も理論としてはこの考え方の発展です。ただGrundy数を扱うような問題は、その性質は単に知識として使ってしまうことが多いですね。

ACコード

E - Negative Doubling

E - Negative Doubling

解法

負と正の区切り位置に注目する

A_{1} \le A_{2} \le \cdots \le A_{N} となっている数列は、左側に負の数が、右側に正の数が集まっていて、それぞれ外側に行くほど絶対値が大きくなっています。この区切り位置を全探索することにします。

まず区切り位置より右側だけを考えます。この範囲の数は正である必要があるので、「-2倍」という操作をする回数は必ず偶数です。そのため、「4倍する」という操作に置き換えてしまい、後で回数を×2することにします。

区切り位置が A_{i-1}, A_{i} の間にある場合、右側で成り立って欲しい条件は A_{i} \le A_{i+1}\le \cdots \le A_{N} です。これを満たす操作回数を求めたいですが…区切り位置は全部試すので、全ての i についてこれを求める必要があります。

DPを考える

A_{i} \le A_{i+1}\le \cdots \le A_{N} が成り立つための最小操作回数を dp\lbrack i \rbrack として後ろからDP、つまり dp\lbrack i+1 \rbrack から dp\lbrack i \rbrack を更新するDPができそうな気がします…が、これだけでは情報として不十分です。

f:id:betrue12:20181224024851p:plain

この図に2つ例示したように、 A_{i+1} を増やしたときに、さらに右側の要素を「道連れ」で増やさなければいけないかもしれません。この情報が得られないと、何回追加で操作をしなければいけないかが求められません。

ではどうすればいいかというと、DPの情報を増やします。「 A_{i} に j 回操作をした上で、 A_{i} \le A_{i+1}\le \cdots \le A_{N} が成り立つための最小回数」を dp\lbrack i \rbrack\lbrack j \rbrack とします。このように情報を持ち、 dp\lbrack i \rbrack\lbrack j \rbrack を求めるときには A_{i+1} 以降の追加操作は行わないと決めてしまえば、先ほどのような理由で情報が不足することはありません。

具体的に dp\lbrack i \rbrack\lbrack j \rbrack を求めるときには、 A_{i} \times 4^{j} \le A_{i+1} \times 4^{k} を満たすような全ての k について dp\lbrack i+1 \rbrack\lbrack k \rbrack からの遷移を計算し、その中で一番良いものを採用すればよいです。

これで操作回数の計算は正しくできますが… j の値は実際にはとても多くなってしまう可能性があり、これだと間に合いません。もうひと工夫考える必要があります。

操作回数の多いところをサボる

先ほどの「道連れ」で操作回数が増えるかどうか分からないという問題は、その時点で A_{i+1} と A_{i+2} がどれだけ離れているか分からない、ということが原因です。 A_{i+2} が A_{i+1} \times 4 以上であれば、 A_{i+1} を4倍しても道連れは必要ありません。

ただし、既に A_{i+1} がとても大きい場合はどうでしょうか。 A_{i+1} が全要素の初期値より大きくなってしまっている場合、感覚的に言うと A_{i+1} 以降の要素は「だいたい同じ高さに均されてしまっている」と思うことができます。その状態で A_{i+1} にさらに1回の操作を加えると、それ以降の全要素も1回ずつ必ず道連れされることになります。

そう考えると、操作回数 j がある一定以上を超えてしまった場合

  • dp\lbrack i+1 \rbrack\lbrack j+1 \rbrack = dp\lbrack i+1 \rbrack\lbrack j \rbrack + (i+1番目以降の要素数)

という性質が成り立ちます。これを用いると、実際のDPテーブルは j が小さいところだけ計算しておいて、大きいところはこの式で求めることができます。

具体的には \frac{A_{i+1}}{A_{i+2}} \le 10^{9} \lt 4^{15} なので、15回より上は先ほどの性質が成り立ちます。ここまで絞れば計算量がかなり落ち、現実的に間に合うくらいになってきます。

逆向きも計算して答えを求める

元々やりたいことは「負と正の区切り位置を全探索して、負と正それぞれの操作回数を考える」ことでした。

正のほうはこれまで見てきたようにDPで計算できます。そして負のほうは、負の範囲の要素全てにまず-2を掛けてから、絶対値が左側ほど大きくなるように左からDPをしていくことができます。この実装は、reverseなどで数列を反転させて正のときと同じコードを通すのが断然オススメです。

両方の計算が終わったら、区切り位置を全部見て操作回数を求め、その一番良いものを出力すればよいです。

ACコード