ARMERIA

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

AtCoder Grand Contest 043 C - Giant Graph

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

お題箱より。

C - Giant Graph

この問題は数ヶ月前に「なぜこの発想を思いつけるのか分からない」というリクエストをもらっていて、私にも分からなかったので記事を書けずにいました。でしたが、（同じ人が違う人かは分かりませんが）2つ目のリクエストをもらったので、自分なりに解説をしていこうと思います。

解法

最適解の構造を考える

頂点 (x, y, z) について、 x+y+z の値を「レベル」と呼ぶことにします。

レベルが 1 増えると重みが 10^{18} 倍になるため、「レベル k である頂点を 1 つ取るほうが、レベル k-1 以下である頂点全てを取るよりも得である」ということが成立します。さらにグラフの作り方からレベルが等しい頂点間に辺はないので、レベルの大きい方から貪欲に頂点を選んでいくことで最適解を求めることができます。

よって最適解を求める（遅い）アルゴリズムとして、以下のようなものが考えられます。

  • 全ての頂点に何も書かれていない状態から始める。全ての頂点に印が付けられるまで以下を繰り返す。
    • 今残っている頂点の中で最もレベルの高い頂点を1つ選び、それに○印を書く（選ぶ頂点として採用する）。それに接続している頂点全てに×印を書く。

※3次元の図示が大変なので2次元で描いています…

f:id:betrue12:20200702190353p:plain

ゲーム問題との類似

ここで最も重要な気づきは、この最適解を求めるアルゴリズムがゲーム問題における後退解析と同じ手順になっている、という点です。

後退解析とは、交互に手番を取るタイプの2人ゲームで

  • ゲームのルールで「この状態で手番が回ってきたら負け」と指定されている状態は負け状態とする。
  • 負け状態に遷移可能、つまり相手に負けを押し付けられる状態は勝ち状態とする。
  • 勝ち状態にしか遷移できない状態は負け状態とする。

という手順で、最終状態から遡るように各状態の勝ち負けを決めていくものです。（俗にWL-Algorithm等とも呼ばれているようです）

本問題のグラフにおいて、2人ゲームを

  • 1つの頂点に駒を置いてあって、交互に動かす。
  • 駒は、今ある頂点と辺で繋がっていて、今ある頂点よりレベルの高い頂点に動かすことができる。
  • 自分の手番に駒を動かせなくなったほうが負けである。両者最適に行動した場合にどちらが勝つか？

と考えると、このゲームの勝ち負けを後退解析で求める手順と元の問題で「どの頂点を選ぶか」を求める手順が一致します。そして負け状態に相当する頂点を選ぶことになります。

答えが一致するということは、このゲームを後退解析ではない別の手法で解いて負け状態を求めても、それがちゃんと元の問題の答えになっている、ということです。よってゲームの手法を用いてより高速な解法を考えることにします。

Grundy数の導入

ここでグラフの構造を思い出すと、駒の移動を3次元のグラフ W で考える代わりに、各次元のグラフ X, Y, Z にそれぞれ1個ずつ駒が置かれていると考えることができます。1回の移動は、

  • グラフ X, Y, Z のうち1つを選ぶ。そこに置かれている駒を、今ある頂点と辺で繋がっていて、今ある頂点よりレベルの高い頂点に動かす。

と見なすことができます。

f:id:betrue12:20200702191550p:plain

このような「独立に動作する複数の部分ゲームがあって、1ターンにはそのうち1つを選んで1手動かす」というゲームにおいて力を発揮するのがGrundy数です。 X, Y, Z それぞれのグラフにおいて各頂点のGrundy数を求めれば、状態 (x, y, z) の勝ち負けは3つのGrundy数のXORが 0 かどうかで判定することができます。負け状態、つまりこのXORが 0 であるような頂点が、元の問題で選ばれる頂点です。

答えを求める！

それでは計算をしていきましょう。まずは各次元のグラフ X, Y, Z について頂点の重みを 10^{18x}, 10^{18y}, 10^{18z} と定義します。そして「Grundy数が g であるような頂点の重み和」をそれぞれ S_{X}(g), S_{Y}(g), S_{Z}(g) としてこれを全て計算します。

3次元のグラフ W の頂点 (x, y, z) について、 x, y 座標のGrundy数の組 (g_{X}, g_{Y}) を全探索します。そうすると g_{Z} = g_{X} \oplus g_{Y} であるような頂点を選べば良いということになります（ \oplus はXOR演算を表します）。このような頂点の重み和は、因数分解によって S_{X}(g_{X})\times S_{Y}(g_{Y})\times S_{Z}(g_{Z}) と計算することができます。

これを全て合計していくことで答えが求められます。

計算量は？

先ほどの解法は (g_{X}, g_{Y}) を全探索しています。これは間に合うのでしょうか？それを評価するために、Grundy数が最大でどれだけの値になるかを確認します。

Grundy数は「そこから遷移可能な頂点のGrundy数として登場しない最小の非負整数」です。つまりGrundy数が G である頂点は、Grundy数が 0, 1, ..., G-1 である頂点全てに遷移可能でなければいけません。そしてGrundy数 G-1 の頂点も 0, 1, ..., G-2 の頂点に遷移可能で…と考えると、Grundy数 G を実現するためには少なくとも \frac{G(G+1)}{2} 本の辺が必要であることが分かります。

そのためグラフ X, Y の辺の本数 M_{1}, M_{2} を用いて、 g_{X}, g_{Y} の最大値をそれぞれ O(\sqrt{M_{1}}), O(\sqrt{M_{2}}) と評価することができます。これなら (g_{X}, g_{Y}) を全探索しても大丈夫です。

ACコード

Submission #11159114 - AtCoder Grand Contest 043

Introduction to Heuristics Contest 参加記録

AtCoder プログラミング マラソンコンテスト 競技プログラミング

Introduction to Heuristics Contest - AtCoder

f:id:betrue12:20200629193803p:plain

33位でした。

戦略

焼きなまし法を選択しました。

理由は、問題の性質として解の局所改善がやりやすく、スコアの差分計算を高速化して大量に回せそうだと考えたからです。対して、1手の変更がその後の展開を大きく変えるような問題（落ち物パズルとか）であればビームサーチ等の手法を取る、貪欲やDPなどで近似解や確率的に良い解が得られそうな問題であればそれらの直接的な実装を頑張る、という印象です。

初期解

何通りか試したけど焼きなましたら結局同じくらいになったので適当です。最終提出ではペナルティを無視して各日ごとに s_{d, i} が最も大きいコンテストを選んだものを初期解としています。

近傍の取り方

まずは「日をランダムに1日選び、ランダムなコンテストに変更する」という1点変更を試しました。次に「コンテスト種類が異なっているような隣り合う2日を選び、コンテストを交換する」という隣接スワップと混ぜるようにしました。

もう少し近傍のバリエーションを増やしたかったなという感想です。コンテスト後に試しましたが、隣接スワップに限らず、例えば w = 1, ..., 15 をランダムに選んで w 日離れている2つの日のコンテストを交換するようにするとスコアが伸びました。

差分更新

まず各コンテスト j と日数 d について、「コンテスト j を開く間隔が d 日空いた時のペナルティ総和」を前計算しておきます。

差分を取る前の解における、各コンテスト j についての「コンテスト j を開く日を昇順に並べた配列（vector）」を管理しておきます。解を1点変更してこの配列に要素を挿入/削除しようとする場合、その前後にある要素は二分探索で求められるので、それらとの間隔を求めることでペナルティの変動量を計算できます。

最初は set でやっていましたが定数倍が重そうなので vector にしました。vector だと実際に変更を採用する時 の insert/erase で線形時間掛かりますが、これらの操作は定数倍が軽い（らしい）のと、変更を採用する回数よりもスコアを差分計算する回数のほうが多いので、トータルで見ると vector のほうが反復回数が多くなりました。

一応「日 d より前/後ろにある、一番近いコンテスト j の開催日」を 365\times 26 の配列で常に管理しておけば差分計算が O(1) なんですが、大して速くなりませんでした。

温度調整

何個か試して適当に初期温度 4000 にしました。私の実装だとこの辺が良さそうですが、近傍の取り方や時間経過による温度減少のさせ方等によって良い値は変わると思います。

テスター・ビジュアライザ

テスターはスコア計算（特に差分計算）があっているかを確認するのに重宝しました。実際結構バグらせたのでなかったら大変でした。

ビジュアライザは（そもそも視覚的に何か分かるような問題じゃないので）よく分かりませんでしたが、なんとなく「ペナルティの係数が大きいコンテストをまんべんなく開催している」「ある程度、各日で利得が大きいコンテストを開くことができている」という確認をすることができました。なんとなく。

振り返り

コンテスト中の成績は 12071 万点でした。上にも書きましたが、本番中に書いていた近傍を少し発展させるだけで 12567 万点、本番の2位相当の点を出すことができました。とはいえコンテスト中にこの「少し発展させるだけ」を思いつき、他の思いつきよりも優先して実装する、ということが難しいのも事実です。

「今のものと実装差分が少なければ、ちょっと変えすぎじゃないかと思うくらい遠い近傍も試してみる」というのは過去のコンテストでも試して、このときは成功しているので、ちゃんと意識していきたいです。

提出コード

本番での最大スコアコード（ 12071 万点）：Submission #14821684 - Introduction to Heuristics Contest

コンテスト後のコード（ 12567 万点）：Submission #14839906 - Introduction to Heuristics Contest

Codeforces Round #653 (Div. 3) E2. Reading Books (hard version)

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

Problem - E2 - Codeforces

問題概要

n 冊の本があり、本 i は読むための所要時間 t_{i}、アリスがその本を好きかどうか a_{i}、ボブがその本を好きかどうか b_{i} で特徴付けられる。

n 冊の本からちょうど m 冊の本を以下の条件を満たすように選ぶとき、その合計所要時間の最小値と、それを実現する選び方の一例を求めよ。ただし条件を満たす選び方が存在しないときは -1 を出力せよ。

  • 選んだ本の中にアリスの好きな本が k 冊以上含まれ、かつボブが好きな本が k 冊以上含まれる。

制約

  • 1 \le k \le m \le n \le 2\times 10^{5}
  • 1 \le t_{i} \le 10^{4}

解法

まず本を (a_{i}, b_{i}) で分類し、 A_{0, 0}, A_{0, 1}, A_{1, 0}, A_{1, 1} の4つの配列を作ります。それぞれ t_{i} の値でソートしておきます。

「 A_{1, 1} に属する本から少なくとも x 冊選び、 A_{0, 1}, A_{1, 0} に属する本から少なくとも (k-x) 冊ずつ選ぶ」という値 x を決め、これを 0 \le x \le k の範囲で全通り試します。そうすると最適な本の選び方は

  • A_{1, 1} から、 t_{i} が小さい順に x 冊選ぶ。
  • A_{0, 1}, A_{1, 0} から、 t_{i} が小さい順にそれぞれ (k-x) 冊選ぶ。
  • r = (m-x-2(k-x)) とする。余った本を全て混ぜ、 t_{i} が小さい順に r 冊選ぶ。

となります。ここで本が足りなかったり r が負になるような x は飛ばします。

余った本を選ぶところ以外は累積和などで計算できます。 A_{1, 1}, A_{0, 1}, A_{1, 0} の中でどの本が余っているかは、 x を順にループしながら追加/除外されるものを差分更新することができます。あとは余った本の t_{i} を小さい方から r 個選んだときの和を効率的に求められれば良いです。

これは以下のようにすればBITやセグメント木で実現できます。所要時間 t をインデックスとして、以下の値を管理するBITを作ります。

  • num\lbrack t \rbrack = 所要時間が t である余り本の冊数。
  • sum\lbrack t \rbrack = num\lbrack t \rbrack \times t

小さい方から r 個の和を求める時には、まず num\lbrack t \rbrack の区間和を用いて二分探索することで小さい方から r 番目の値を求め、 sum\lbrack t \rbrack の区間和を用いてそこまでの合計を求め、取りすぎていればそのぶんを調整すれば良いです。

これで最適値を求めることができます。この問題では具体的にどの本を選ぶかも要求されているので、最適値を実現する x の値を記憶しておいて、改めて最適な本の選び方をなぞって選ぶ本の番号を求めれば良いです。

ACコード

Submission #85337458 - Codeforces

yukicoder No.1100 Boxes

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

No.1100 Boxes - yukicoder

解法

まずボールが1つも入っていない箱の数を固定します。これを a とすると、その選び方は _{K}C_{a} 通りです。

その上で、残りの K-a 個の箱全てにボールが入るような場合の数を求めます。これは包除原理を用いて

\displaystyle\sum_{b=0}^{K-a}(-1)^{b} {}_{K-a}C_{b}(K-a-b)^{N}

と求めることができます。

先ほどの _{K}C_{a} と合わせて、二項係数を階乗の形にすると、これは結局

\displaystyle_{K}C_{a}(-1)^{b} {}_{K-a}C_{b}(K-a-b)^{N} = \frac{K!}{a!b!(K-a-b)!}(-1)^{b}(K-a-b)^{N}

を、 a=1, 3, 5, ... かつ b=0, 1, ... かつ a+b \le K の範囲で全て足し合わせれば良いことになります。

これは2重ループですが、NTTを用いた畳み込みで計算できる形になっています。具体的には先ほどの式を

\displaystyle f(a) = \frac{1}{a!}

\displaystyle g(b) = \frac{(-1)^{b}}{b!}

\displaystyle h(s) = \frac{K!}{(K-s)!}(K-s)^{N} （ s = a+b とする）

の積として分解できるので、 f(a) と g(b) を畳み込んだ後に h(s) を掛け、 s \le K の範囲で全て合計すれば良いです。

ACコード

#504097 (C++17(1z)) No.1100 Boxes - yukicoder

AtCoder Beginner Contest 171 F - Strivore

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

F - Strivore

解法

文字列 S の長さを N とします。また最終的に出来上がる文字列を T と表記します。

T の長さは N+K になります。そのうち元々あった文字と追加した文字の場所の割り当て方が _{N+K}C_{K} 通りで、追加した文字の種類が 26^{K} 通りで…とやりたくなりますが、これでは最終的に同じ文字列になるものを重複して数えてしまいます。例えば S を abc、 K=2 として、文字を追加した場所を * で示したときに

  • 場所の割り当て方を a*b*c として、追加する文字を順に b c とする
  • 場所の割り当て方を ab*c* として、追加する文字を順に b c とする

という選び方はともに abbcc という文字列になります。

このような重複を防ぐためには、最終的に出来上がる文字列に対して、その作り方が1通りに決まるようなルールを決めてしまえば良いです。ここでは「 T のなるべく左側の文字が、元々あった S の各文字と対応するようにマッチさせる」というルールにしましょう。例えば S が abc 、 T が abbcc であるような場合には、ab*c* という場所の割り当て方だけを考えることになります。

f:id:betrue12:20200621223911p:plain

では逆に、このルールに基づいた時に場所の割り当て方が ab*c* となるような文字列 T はいくつあるでしょうか？

3文字目の * に入る文字は c 以外の 25 種類があり得ます。なぜなら3文字目がもし c だった場合、「なるべく左側にマッチ」ルールに基づくと abc** という割り当て方になっているはずだからです。一方、5文字目の * は何でも良いので 26 種類です。

これをより一般の場合で考えると、割り当て方に含まれる * のうち末尾に並んでいるものは 26 通り、そうでないものは 25 通りの選択肢があります。つまり

  • 場所の割り当て方を決めた時に、その末尾に並ぶ * が t 個、そうでない * が K-t 個あった場合、その割り当て方に対応する文字列は 26^{t} \times 25^{K-t} 通りである

ということになります。これで計算ができます。

末尾に並ぶ * の個数 t を全通り試しましょう。そうすると割り当て方のうち末尾は「 S の末尾1文字＋ * t 個」だと決まるので、残りの文字と * の並べ方は _{N-1+K-t}C_{K-t} 通りです。これに先ほど計算した文字列の個数を掛けて、全て合計すれば良いです。

制約が大きめなので、 25, 26 の冪乗は前計算しておくのが安心です。与えられる S のうち、文字数以外の情報は使う必要がありません。

ACコード

Submission #14551392 - AtCoder Beginner Contest 171

AtCoder Grand Contest 046 C - Shift

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

C - Shift

解法

S に含まれる 0 の個数を N_{0}、1 の個数を N_{1} と書くことにします。 S を、0 で区切られた N_{0}+1 個のエリアに分割します。

f:id:betrue12:20200621170809p:plain

図に示すように、エリア i に含まれる 1 の個数を one\lbrack i \rbrack とし、エリア i を含むそれ以前に含まれる 1 の個数を sum\lbrack i \rbrack とします。

本問題の操作は、1 を1つ選んで元々あったエリアより左のエリアに移動させる操作だと思うことができます。つまり操作後の状態において、以下の条件が満たされている必要があります。

  • 1 の個数の合計は初期状態と同じである。
  • 初期状態よりも 1 が増加しているエリアについてその増加量を合計した値は K 以下である。
  • エリア i 以前（エリア i を含む）に存在する 1 の個数は sum\lbrack i \rbrack 個以上である。

逆にこれらの条件を満たすような操作後の状態は常に作ることが可能です。これらの条件を満たしているならば、1 の増加箇所と減少箇所を左から順番にマッチングさせていくことで実際に操作列を構成することができるからです。

以上の考察から、エリアで区切って各エリアに存在する 1 の個数を決めていく以下のDPを組みます。

dp\lbrack i \rbrack\lbrack j \rbrack\lbrack k \rbrack = エリア i-1 までの 1 の個数を決め終わって、操作回数が j で、これまで 1 を合計 k 個使っているような状態の数

このDPの遷移は、エリア i に置く 1 の個数が one\lbrack i \rbrack 個未満かどうかで2通りに分けられます。それぞれの遷移で

  • 最小操作回数で実現するパターンだけを考える。つまりあるエリア i に右側から 1 を借りてきて、さらに左側にも貸すような無駄な操作を考えない。
  • どこから借りた/どこから貸したということは考慮せずに、個数の増減だけを考える。

という2点を守ることで、操作列が違っても結果が同じ文字列になるものは1通りとなるように数えることができます。

エリア i に置く 1 の個数が one\lbrack i \rbrack 個未満

このときは元々あった one\lbrack i \rbrack 個の 1 のうち一部をエリア i で使い、残りの 1 を左側に貸しているという扱いになります。

使う 1 の個数は複数通り考えられるので、 dp\lbrack i \rbrack\lbrack j \rbrack\lbrack k \rbrack からの遷移先の候補は

  • dp\lbrack i+1 \rbrack\lbrack j \rbrack\lbrack k \rbrack
  • dp\lbrack i+1 \rbrack\lbrack j \rbrack\lbrack k+1 \rbrack
  • …
  • dp\lbrack i+1 \rbrack\lbrack j \rbrack\lbrack k+one\lbrack i \rbrack -1 \rbrack

となります。これを全部試していると全体で4乗になってしまうので、貰うDPにして累積和を使います。

dp\lbrack i+1 \rbrack\lbrack j \rbrack\lbrack k \rbrack に遷移する値を累積和で計算できたとします。ここで先ほどの「エリア i 以前（エリア i を含む）に存在する 1 の個数は sum\lbrack i \rbrack 個以上である」という条件に従い、 k \ge sum\lbrack i \rbrack の時だけ実際に遷移すれば良いです。

エリア i に置く 1 の個数が one\lbrack i \rbrack 個以上

このときは、元々あった one\lbrack i \rbrack 個の 1 は必ず全てエリア i で使い、さらに右側から0個以上の 1 を借りてくるという扱いになります。

借りてくる 1 の個数が複数通り考えられるので、 dp\lbrack i \rbrack\lbrack j \rbrack\lbrack k \rbrack からの遷移先の候補は

  • dp\lbrack i+1 \rbrack\lbrack j \rbrack\lbrack k+ one\lbrack i \rbrack \rbrack
  • dp\lbrack i+1 \rbrack\lbrack j+1 \rbrack\lbrack k+ one\lbrack i \rbrack + 1 \rbrack
  • …

とこちらもそのままでは4乗になります。これの対処は斜めに累積和を取っても良いですし、 dp\lbrack i \rbrack\lbrack j \rbrack\lbrack k \rbrack から

  • dp\lbrack i \rbrack\lbrack j+1 \rbrack\lbrack k+1 \rbrack に遷移（1 を1個借りてきて同じ i に遷移し、後で↓の遷移をしてもらう）
  • dp\lbrack i+1 \rbrack\lbrack j \rbrack\lbrack k+ one\lbrack i \rbrack \rbrack に遷移（元々あった one\lbrack i \rbrack 個の 1 を追加して i+1 に遷移）

という遷移をしても良いです。個数制限なしナップサック問題などで使うテクニックですね。

こちらも i+1 に遷移する際には k + one\lbrack i \rbrack \ge sum\lbrack i \rbrack の条件をチェックしましょう。

ACコード

Submission #14520186 - AtCoder Grand Contest 046

AtCoder Grand Contest 046 B - Extension

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

B - Extension

解法

まず以下のようなDPを考えてみましょう。

dp\lbrack i \rbrack\lbrack j \rbrack = 本問題の操作によって、縦 i 行、横 j 列になるまで操作してできる盤面の数

このDPで「上側に行を足し、その1つを黒く塗る」遷移と「右側に列を足し、その1つを黒く塗る」遷移をすれば良さそうですが、数えるものは最終的な盤面の数なので、途中の操作列が違っても盤面として同じものは重複しないように気をつける必要があります。

操作列が異なるのに結果が同じになるような操作は、具体的には以下のようなものです。

f:id:betrue12:20200621003842p:plain

このように、 i \times j の盤面で

  • 右上隅が黒くない
  • 最上行、最右列ともに黒マスが1つ
  • 初期状態から行、列がともに1つ以上追加されている

の全ての条件を満たすものは、 (i-1) \times (j-1) の盤面から2通りの操作で到達します。

より一般的には、黒マスがちょうど1つの行が上から x 個・列が右から y 個あり、それらが交差する場所に黒マスが存在しない場合、 (i-x) \times (j-y) の盤面から行・列を追加する順番が _{x+y}C_{x} 通りあります。

※逆に重複パターンがこのようなものしかないことは、これ以外の盤面に対しては逆操作（黒マスがちょうど1つある最上行または最右列を取り除く）を考えた時に、操作できてかつ次も詰まないような操作が高々1通りしかないことから分かります。

よって、このような操作列のうち特定の1つしか遷移として採用しないというルールでDPをします。例えば「上に行を全て足した後、右に列を全て足す」ものしか採用しないことにしましょう。このときは右に列を追加する遷移のときに

  • その列の上端（右上隅）以外を塗る
  • 遷移前の最上行の黒マスが1つ
  • 初期状態から行が1つ以上追加されている

の全てを満たす場合、それは別の操作列で数えている盤面なので遷移をキャンセルするようにすれば良いです。

これを判定できるようにするためには、DPテーブルを拡張して

dp\lbrack i \rbrack\lbrack j \rbrack\lbrack a \rbrack\lbrack b \rbrack = 本問題の操作によって、縦 i 行、横 j 列になるまで操作してできる盤面で、最上行の黒マスが a 個、最右列の黒マスが b 個であるようなものの数

とすれば良いです（実際には a, b のどちらかで良いです）。ここで判定に使うのは「黒マスがちょうど1つかどうか」なので、 a, b としては「0」「1」「2以上」の3通りを区別しておけば良いです。

遷移を「上側に行を足し、その右端/右端以外を黒く塗る」遷移と「右側に列を足し、その上端/上端以外を黒く塗る」遷移の計4通りに分けることで、遷移先の a, b の計算とキャンセルすべきかどうかの判定をすることができます。右端以外/上端以外の遷移には、それぞれ候補となるマス数を係数として掛ける必要があります。

dp\lbrack C \rbrack\lbrack D \rbrack\lbrack a \rbrack\lbrack b \rbrack を a, b について合計したものが答えです。

ACコード

Submission #14500984 - AtCoder Grand Contest 046