ARMERIA

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

AtCoder Regular Contest 099 E - Independence

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

お題箱より。

E - Independence

解説

問題文をグラフ理論の言葉で解釈します。 N 個の頂点を2つの集合 X, Y に分け、それぞれの集合内では任意の2頂点間に辺が存在している（すなわち、クリークになっている）必要があります。 X, Y の頂点数をそれぞれ x, y とすると、最小化したい値は \frac{x(x-1)}{2} + \frac{y(y-1)}{2} です。そして y=N-x なので、集合 X のサイズ x だけを考慮すれば良いことが分かります。

クリークの問題では「補グラフ」、すなわち任意の2頂点間の辺の有無を反転させたグラフを考えるとうまくいくことがあります。補グラフを取るとクリークは独立集合に、すなわち「任意の2頂点間に辺が存在している」は「どの2頂点間にも辺が存在していない」となります。頂点が2つの集合 X, Y に分けられ、それぞれの集合内ではどの2頂点間にも辺が存在していない…これはまさに二部グラフです。

f:id:betrue12:20210202201636p:plain

与えられたグラフの補グラフを取り、これが二部グラフとなるように頂点を2つの独立集合 X, Y に分けることを考えます。このとき頂点の割り振り方は連結成分ごとに決めることができて、

  1. まずその連結成分が二部グラフになっているかを確認する。そうでなければ題意を満たすことは不可能。
  2. 連結な二部グラフであれば2つの独立集合への分け方は一意なので、そのうちどちらを X に割り振るかを決める。

という手順を全ての連結成分について行うことで頂点を割り振ることができます。

冒頭で確認したように、答えを求めるには割り振った後の集合 X のサイズ x としてどの値を実現できるかが分かれば十分です。各連結成分における2つの独立集合のサイズのうちどちらか一方を x に加算していったときの総和としてあり得るものを列挙したいので、これは部分和問題と同様の動的計画法を用いて解くことができます。

ACコード

Submission #19879768 - AtCoder Regular Contest 099

AtCoder Beginner Contest 185 E - Sequence Matching

お題箱より。

E - Sequence Matching

解法

LCSとの類似性

2つの数列や文字列を操作して一致させる問題では、前から1文字ずつ扱いを決めていくという方針のDPがうまくいく場合があります。特に2つの列の長さを N, M として O(NM) が間に合う場合はなおさらです。

このような問題の代表例として最長共通部分列（LCS）を求める問題が挙げられます。LCSを求めるDPは、

dp\lbrack i \rbrack\lbrack j\rbrack = 列 A の先頭 i 文字と列 B の先頭 j 文字を見終わったときの、そこまでの共通部分列の長さの最大値

と状態を定義し、前から見ていきながら

  1. 列 A の今見ている文字を削除する
  2. 列 B の今見ている文字を削除する
  3. 列 A の今見ている文字と列 B の今見ている文字が一致しているとき、その文字を共通部分列の次の文字として採用する

の3通りの遷移で文字の扱いを決めていくものです。

共通部分列というのは結局のところ2つの列それぞれについて好きな箇所の要素を好きなだけ削除し、一致させたときの列と思うことができるので、今回の問題の前半部分と同じです。

LCSそのものの解説や具体的な遷移についてはこちらの記事などを参考にしてください。

Educational DP Contest の F ～ J 問題の解説と類題集 - Qiita

今回の問題のケースを考える

今回の問題で最小化したい値 x+y をコストと呼ぶことにします。今回の問題を少し言い換えると、

  • 1文字につきコスト 1 で A, B の文字を好きなだけ削除する。
  • その後 A, B で一致していない箇所1つにつき、 B の文字をコスト 1 で変更して一致させる。

という2段階の操作によって2つの列を一致させる問題だと考えることができます。しかしこれを2段階の操作と見なさず、2つのコストを同時に処理していったほうがDPの枠組みで考えやすくなります。

LCSを求めるDPと同じように考え、状態を以下のように定義します。

dp\lbrack i \rbrack\lbrack j\rbrack = 列 A の先頭 i 文字と列 B の先頭 j 文字を見終わったときの、そこまでの列を一致させるためのコストの最小値

遷移を次のように考えることで2つのコストを同時に処理していくことができます。

  1. 列 A の今見ている文字を削除する。コストが 1 増える。
  2. 列 B の今見ている文字を削除する。コストが 1 増える。
  3. 列 A の今見ている文字と列 B の今見ている文字が一致しているとき、その文字を共通列の次の文字として採用する。
  4. 列 A の今見ている文字と列 B の今見ている文字が異なっているとき、 B の文字を変更して一致させた上で共通列の次の文字として採用する。コストが1増える。

つまりLCSを求めるDPに4番の遷移を追加すれば良いです。これで O(NM) で解くことができます。

ACコード

実装では先ほどの遷移パターンのうち3番と4番を1行で記述しています。

Submission #18782223 - AtCoder Beginner Contest 185

AtCoder Grand Contest 047 D - Twin Binary Trees

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

お題箱より。

D - Twin Binary Trees

解法

ちょうど2本の特殊辺を持つ単純サイクルは、第1の木の異なる2つの葉の組み合わせと同じ個数だけ存在します。このサイクルは、その2つの葉の第1の木におけるLCAと、それらと接続されている第2の木の2つの葉のLCAとを2本のパスで結ぶものです。

f:id:betrue12:20201126233821p:plain

2つの葉の組み合わせを全て列挙していると間に合いません。そのため方針としては、第1の木の頂点を全探索し、その頂点を第1のLCAとするサイクルたちの積の総和をまとめて数えます。

第1の木の頂点 v をLCAとするサイクルの積の総和は、具体的には以下の手順で求めることができます。

【手順1】 まず v から左側の子孫に進み、それぞれの葉から第2の木の根までのパスを全て辿る。このとき通過する第2の木の頂点 i 全てに対して、 v から頂点 i までのパスにおける頂点番号の積を求めて配列の要素 A_{i} に足しておく。

図において各頂点の左側に書いている赤い数字が該当します。

f:id:betrue12:20201126233954p:plain

【手順2】次に v から右側の子孫に進み、それぞれの葉から第2の木の根までのパスを全て辿る。このとき通過する第2の木の頂点 i 全てに対して、 v から頂点 i までのパスにおける頂点番号の積と、先ほど求めた A_{i} との積を答えに足し合わせていく。

つまりこれは、 v から左側に降りたパスと右側に降りたパスが合流する点において、別々に求めた頂点番号の積を掛け合わせて答えに足していることになります。掛けてちょうどサイクル1周分となるためには、手順2のほうでは頂点 v とその頂点自身の値は含めずに積を計算すると良いです。図において各頂点の右側に書いている青い数字が該当します。

f:id:betrue12:20201126235319p:plain

ただしこの方法で数えると、サイクルは第2の木のほうのLCAだけでなく、さらにその祖先である頂点においても加算されてしまいます。しかも祖先においては第2のLCAからさらに余分に進んだ分の係数が掛けられた状態で加算されます。これを帳消しにするためには、第2の木を進むときに「親の頂点においては、これだけの値が余分に加算されてしまうはず」という値を伝播していって、答えから引けば良いです。

f:id:betrue12:20201126235200p:plain

【手順3】手順1において通過した第2の木の頂点を覚えておき、それらの頂点について A_{i} の値を 0 にリセットする。

これは次の v に関する計算に移る前に必要です。 A_{i} の値は手順1で通過した頂点だけしか変化していないため、それらの頂点だけについて処理することで計算量を抑えています。

これを全ての v について試して合計すると答えを求められます。

計算量について考えます。全ての葉は、動作全体で H-1 回だけ見られることになります。そして葉が1回見られるごとに、そのときの第1の木における頂点 v へのパスを1回、第2の木の根へのパスを最大2回通ります。このパスの長さは H 以下であり、葉の個数が L 個であるため、全体計算量は O(H^{2}L) となります。

ACコード

Submission #18423719 - AtCoder Grand Contest 047

やっていることは木を何回も走査しているだけですが、係数の細かな扱いを間違えずに行う必要があります。

AtCoder Grand Contest 046 D - Secret Passage

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

お題箱より。

D - Secret Passage

解法

操作の特徴をつかむ

与えられる文字列 S の長さを N とします。また S の i 文字目を S_{i} と表記します（ 先頭は S_{0} です）。

操作列によって文字列がどのようになるかを、まずは大雑把に理解しましょう。前から順に操作されるため、元の文字列 S は操作された前側の領域と操作されなかった後ろ側の領域に分かれます。そして操作された文字のうちいくつかが後ろ側に挿入されることによって文字列が完成します。

f:id:betrue12:20201126095848p:plain

削除されなかった文字がどこに挿入されるかは自由です。また、挿入された文字が再び操作の対象となる場合もあり得ます。

このように考えると、操作列の結果としてある状態が作れるかどうかは、その操作列において操作される領域の長さ、後ろに挿入する 0 の個数、後ろに挿入する 1 の個数という3パラメータから判断できることが分かります。例えば上の図の操作であれば (6, 2, 1) です。

これを踏まえて、次のDPを考えましょう。

  • E\lbrack i\rbrack\lbrack j\rbrack\lbrack k\rbrack = 文字列 S のうち先頭 i 文字を操作することで、0 を j 文字、1 を k 文字後ろ側に挿入することはできるか？（true/false）

初期条件は E\lbrack 0\rbrack\lbrack 0\rbrack\lbrack 0\rbrack がtrueであることです。遷移を考えましょう。 E\lbrack i\rbrack\lbrack j\rbrack\lbrack k\rbrack がtrueであるとき、その状態からの操作を考えることで次に列挙する遷移先をtrueにすることができます。

  1. 先頭2文字を操作し、後ろ側の文字をそのままの位置に戻す。実質的に先頭1文字を削った形になり、 E\lbrack i+1\rbrack\lbrack j\rbrack\lbrack k\rbrack がtrueである。
  2. 先頭2文字を操作し、そのうちの1文字を後ろに挿入する。 S_{i} と S_{i+1} のうちいずれかが 0 であれば E\lbrack i+2\rbrack\lbrack j+1\rbrack\lbrack k\rbrack がtrueであり、いずれかが 1 であれば E\lbrack i+2\rbrack\lbrack j\rbrack\lbrack k+1\rbrack がtrueである。
  3. これまでの操作で「後ろに挿入する」ということにした文字のうち、 S_{i} と異なる文字を1つ S_{i} の直前に挿入してから、その文字と S_{i} を操作し、 S_{i} を後ろに挿入する。 S_{i} が 0 であれば E\lbrack i+1\rbrack\lbrack j+1\rbrack\lbrack k-1\rbrack がtrueであり、1 であれば E\lbrack i+1\rbrack\lbrack j-1\rbrack\lbrack k+1\rbrack がtrueである。

※遷移1については、厳密には操作されているのは i+1 文字目までではなく i+2 文字目までなのですが…後の説明の都合上、「残っている文字が2文字以上のとき、先頭の文字を1つ削除する」という操作として扱ってしまうことにします。

後で使う性質として、このDPテーブルには単調性が成り立ちます。 E\lbrack i\rbrack\lbrack j\rbrack\lbrack k\rbrack がtrueならば、 j_{1} \le j かつ k_{1} \le k である (j_{1}, k_{1}) に対して E\lbrack i\rbrack\lbrack j_{1}\rbrack\lbrack k_{1}\rbrack もtrueです。これは E\lbrack i\rbrack\lbrack j\rbrack\lbrack k\rbrack を実現する遷移列において、遷移2と遷移3を適切に遷移1に置き換えていくことで j, k の値を自由に減らせることから示せます。

このDPテーブルにおいて値がtrueであるような (i, j, k) の組全てについて、

  • S の後ろ側 N-i 文字に、0 を j 個、1 を k 個挿入してできる文字列が何通りあるか？

を計算して合計すれば答えが求められそうな気がします。しかし、残念ながらこれでは正しい答えになりません。異なる (i, j, k) の組から同じ文字列ができてしまう可能性があるからです。

重複を排除する

操作列によって作ることができる全ての文字列を、それぞれちょうど1回だけ答えに加算する方法を考えます。ある文字列 T が作れるとして、 T を作る時に操作する領域の長さ i をちょうど1通りだけ考えることができれば、操作されない領域に不足している 0 と 1 の個数である (j, k) は一意に定まります。

ここで、次の性質が成り立つことが証明できます。

  • ある操作列によって文字列 T を作ることが可能であるならば、「 S の接尾辞であって、 T の部分列として取れるもののうち最も長いものの長さ」を L として、 S の末尾 L 文字を操作することなく T を作るような操作列が存在する。

この性質を利用して、 T を作る時に操作する領域の長さを N-L に限定することで、文字列 T をちょうど1回だけ数えることができます。

この性質を証明します。以下の図のように、操作されない領域の長さが L よりも短い操作列Aで T が作れると仮定します。このとき、操作されない領域が1つ長くなるような操作列Bが存在して T が作れることが証明できればよいです。

f:id:betrue12:20201126104925p:plain

直感的には、操作する領域の文字のうち最大で半分しか後ろ側に挿入できないことを考えると、操作する領域の長さが1つ減る代わりに挿入すべき文字が1つ減るのは条件として易しくなってそうな気がします。ちゃんと証明するために冒頭のDPを用います。

操作列Aにおいて操作した領域の長さ、挿入した0の個数、挿入した1の個数を (i, j, k) とします。図のように S_{i-1} が 1 である場合を考えます（ S_{i-1} が 0 である場合も同様に考えられます）。すると操作列Bは (i-1, j, k-1) で特徴づけられるため、「 E\lbrack i\rbrack\lbrack j\rbrack\lbrack k\rbrack がtrueであるならば、 E\lbrack i-1\rbrack\lbrack j\rbrack\lbrack k-1\rbrack もtrueである」ことが証明できれば良いです。

E\lbrack i\rbrack\lbrack j\rbrack\lbrack k\rbrack がtrueであるならば、その遷移元としてあり得る状態のうち少なくとも1つがtrueであるはずです。冒頭の遷移一覧に基づいてこの遷移元を列挙します。

  • E\lbrack i-1\rbrack\lbrack j\rbrack\lbrack k\rbrack
  • E\lbrack i-2\rbrack\lbrack j-1\rbrack\lbrack k\rbrack（ S_{i-2} が 0 である場合）
  • E\lbrack i-2\rbrack\lbrack j\rbrack\lbrack k-1\rbrack
  • E\lbrack i-1\rbrack\lbrack j+1\rbrack\lbrack k-1\rbrack

第1添字が i-2 のものについては、そこから遷移可能な先に置き換えます。すると次のうち少なくとも1つがtrueであることが分かります。

  • E\lbrack i-1\rbrack\lbrack j\rbrack\lbrack k\rbrack
  • E\lbrack i-1\rbrack\lbrack j\rbrack\lbrack k-1\rbrack
  • E\lbrack i-1\rbrack\lbrack j+1\rbrack\lbrack k-1\rbrack

これらは全て、第2添字、第3添字がともに示したい E\lbrack i-1\rbrack\lbrack j\rbrack\lbrack k-1\rbrack の添字以上になっています。よってDPテーブルの単調性から、これらのうちどれがtrueであっても E\lbrack i-1\rbrack\lbrack j\rbrack\lbrack k-1\rbrack がtrueであることが言えます。以上で証明が完了します。

答えを数える

ようやく答えを数えるパートです。これまでの考察から、 (i, j, k) の組全てについて次の値を計算すれば良いです。

  • dp\lbrack i\rbrack\lbrack j\rbrack\lbrack k\rbrack： S の後ろ側 N-i 文字に、0 を j 個、1 を k 個挿入してできる文字列であって、「 S の接尾辞であって、 T の部分列として取れるもののうち最も長いものの長さ」が N-i であるものが何通りあるか？

これは文字列 T を後ろから作っていくDPで求めることができます。 dp\lbrack i\rbrack\lbrack j\rbrack\lbrack k\rbrack からの遷移としては、もし S_{i-1} が 0 であれば

  • 文字列の先頭に 0 を付ける：部分列として取れる接尾辞の長さが増えるので、 dp\lbrack i-1\rbrack\lbrack j\rbrack\lbrack k\rbrack に遷移
  • 文字列の先頭に 1 を付ける：部分列として取れる接尾辞の長さが増えず、挿入した文字の扱いになるので、 dp\lbrack i\rbrack\lbrack j\rbrack\lbrack k+1\rbrack に遷移

という2通りの遷移があり得ます。 S_{i-1} が 1 であれば逆です。

E\lbrack i\rbrack\lbrack j\rbrack\lbrack k\rbrack がtrueである (i, j, k) 全てについて dp\lbrack i\rbrack\lbrack j\rbrack\lbrack k\rbrack を合計すれば答えになります。実装によっては空文字列を含んでしまう（ dp\lbrack N\rbrack\lbrack 0\rbrack\lbrack 0\rbrack を算入してしまう）ことがあるので、その場合は 1 を引きましょう。

ACコード

Submission #14615785 - AtCoder Grand Contest 046

CodinGame Fall Challenge 2020 参加記

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

ゲームAIコンテスト「CodinGame Fall Challenge 2020」に参加して、Legendリーグ63位でした！

f:id:betrue12:20201123205107p:plain

f:id:betrue12:20201123205022p:plain

どんなゲーム？

f:id:betrue12:20201121205452p:plain

アニメーション：Game Replay - CodinGame

素材からポーションを作ってお金を稼ぐゲームです。各プレイヤーはターンごとに「注文リスト内のポーションを調合して報酬を得る」「呪文を使って素材を獲得したり変化させる」「新しい呪文を覚える」「休憩して既に使った呪文を回復させる」のいずれかの行動を取ることができます。最後に稼いだお金が多いほうが勝ちです。

効率よく呪文を使って、短いターンで報酬の多いポーションを作れる手順を組み立てることが何よりも重要です。一方で、覚えられる呪文とポーションの注文は2人のプレイヤーに共通で、どちらかが先に取るとなくなってしまいます。相手が持っている素材と呪文のリストも見えるので、相手の行動を予測したり、相手が欲しそうなものを先回りして取ることで妨害したりする戦術も可能です。

以降の戦略説明ではルール内の言葉が多く登場しますので、ツカモさんのルール和訳も合わせてご覧ください。

codingame:Fall Challenge 2020 ルール要約&内部パターン紹介 - tsukammoの収穫記

戦略

大まかな行動方針は以下の通りです。

  • 最初の6ターン：必ず呪文を習得する
  • それ以降：ビームサーチを用いて行動を決定する

ビームサーチでも呪文習得は行動の選択肢として考慮するので、全部ビームサーチで行動決定するという案もありました。しかし序盤は相手も呪文を多く取ってくるので、未来のターンで取れる呪文に不確実性が高いと考え、先を読まずターンごとに判断する方法にしました。

序盤の呪文習得

このゲームでは、repeatableな呪文を用いて大量の素材を一気にグレードアップさせていくことが非常に重要です。そのためrepeat回数を考慮した呪文の価値付けをしました。習得可能な呪文を以下のように価値付けして、最も価値が大きいものを習得しました。

  • 呪文1回分の価値 v ：素材の価値を順に 1.25, 2.25, 3.25, 4.25 としたときの、呪文前後での価値合計の増分
  • repeatableな呪文の最大回数 m：1回で消費する素材個数 x、獲得する素材個数 y とすると、 m=\lfloor\frac{10}{\max(x, y)}\rfloor
  • 呪文の価値： 0.75v\frac{1+m}{2} - (消費する先読み税) + (得られる先読み税) + (補正値)

ポーションの報酬額は素材の価値を 1, 2, 3, 4 として設定されているため、私も長くこの値を使ってきましたが、差し引きで素材個数が増える呪文を優遇するためにLegend昇格直前で 1.25, 2.25, 3.25, 4.25 に変更しました。これは呪文がキレイに回るパターンである

個数が増える呪文で個数を増やす→tierを上げる呪文で全体のtierを上げる→ポーションを作って個数が減る→個数が増える呪文で個数を増やす→…

という流れができやすいようにしたいという意図です。

係数 0.75 は、呪文の効果と先読み税の得失のうちどちらを重視するかを決めるものです。当初この係数は 2 でしたが、先読み税が高い呪文を取りすぎて序盤の所持素材に差が付き、そのまま追いつけない試合が多くありました。そのため何度か調整して結果的に 0.75 に落ち着きました。

補正値では「tier-0の素材を消費する呪文（まだ持っていない場合）」と「消費無しで3個以上の素材が貰える呪文」の価値を +2 しています。逆に「既に持っているrepeatableな呪文と消費色・獲得色が全く同じ呪文」は機能が被ってしまうので、価値を -2 しています。

ビームサーチ

行動と状態管理

ビームサーチで考慮する行動の候補は以下の通りです。

  • 現時点で見えているポーションの作成
  • 現時点で見えている呪文の習得
  • 呪文の使用（repeatableの場合、可能な全回数を試す）
  • 休息

ポーションの緊急ボーナスや呪文習得の先読み税などは未来のターンでは変動する可能性がありますが、現時点で見えている情報のままとして扱います。また、現時点で出現していない習得呪文やポーションは考慮しません。

状態を表す構造体は以下の情報を管理しています。

  • 自分のインベントリにある素材の個数
  • 自分の累積ポーション作成個数
  • 使用可能な呪文のID配列
  • 使用済みの（休息で回復する）呪文のID配列
  • 習得可能な呪文のID配列
  • 作成可能なポーションのID配列
  • 最初の行動
  • 評価値

IDから各アクションの中身を取り出すための配列を別途作っておくことで、状態が持つべき情報をIDだけにしています。ビームサーチでは状態をコピーすることが多いのでなるべくスリムにしました。

ビーム幅は色々試した結果60になりました。時間で探索を切っているので見ているターン数は決まっていませんが、実測では10ターンくらい先まで見ていました。

状態の評価値の計算

状態の評価値の計算に用いるのは、それまでの行動で作成したポーションの価格と作成したターン、そしてインベントリの素材です。

ポーションは相手に取られる可能性があり、なるべく早く取ったほうが有利です。そのためポーションの報酬は、現時点からポーション作成までの経過ターン数に応じた減衰率を掛けて評価値に加算していきます。具体的にはターン数を t として 0.9^{t} を掛けています。

さらに「現時点で相手が作成可能なポーション」である場合、次のターン以降には無くなっている可能性が高いので、次ターン以降に作る場合はさらに 0.8 の減衰率を掛けています。

インベントリの素材の価値はそれぞれ 1, 2, 3, 4 として計算して合計し、こちらにも 0.9^{t} を掛けています。インベントリの素材は「将来的にポーションの報酬に変わる可能性があるもの」なので、本来はポーションの報酬の係数 0.9^{t} よりも低い割合にするのが自然だと思いますが、低くするとポーションを作った直後にインベントリが空になって次の動きが悪くなることが多かったので高めに評価しています。

ただし高いtierの素材がインベントリを圧迫して消費できない状態になってしまうと詰むので、tier-2とtier-3の素材はそれぞれ5個分までしか評価値に算入しません。

例外として、累積6個のポーションを作った状態は特別に扱います。自分が6個のポーションを作った状態でゲームを終わらせるのは有利なので、経過ターン数が少ないほど大きくなるボーナス値を足しました。またインベントリの価値は計算せずに、最終得点計算の基準（つまりtier-1以上の素材1個につき1点）で6個目のポーションの報酬と同じように加算しています。

ゲーム終了条件の考慮

現ターンでゲームが終わる可能性がある状況では、ビームサーチを行わずに行動を判断することがあります。

もし自分の累積作成ポーションが5個で、ポーションを作成することで勝利が確定する場合、ビームサーチを行わずにポーションを作成して終了します。「勝利が確定する」かどうかの判定では、相手がポーションを作るだけでなく呪文で素材ボーナスを目一杯伸ばすことも考慮しています。Gold上位だと、勝ちを読んだと思ったら素材ボーナスを伸ばされて負けることが意外とありました。

また逆に相手の累積作成ポーションが5個で、相手がポーションを作成することで自分が負ける場合、自分はポーション作成または呪文によって可能な限り最終スコアを高めます。これで勝てている試合も意外とありました。

やっていないこと

以下の2つは検討しましたが、効果が期待できるほどしっかり実装に組み込める気がしなかったので見送りました。

  • まだ見えていない呪文やポーションの注文を予測して未来の行動を評価すること。
  • 相手の未来の行動を予測すること。

何となく良さそうだなと思っていた戦略は、「ある1手目の行動について、相手の行動に応じて分岐するいくつかの展開を考えて、それらの展開の評価値の重み付き平均をその1手目の行動とする」という考え方です。例えば狙っていたポーションが先に取られて非常に苦しい局面になることがあったので、取られた場合の展開も考慮しながら行動を評価すると良さそうだと考えました。

考え方としてはモンテカルロ木探索に近いのかな。ただ実装経験がなく、ビームサーチからの移行も難しそうだったので採用しませんでした。

その他、雑多な感想

前回のパックマンがとても面白かったので、半年間密かに楽しみにしていました。今回もLegendリーグに行けて良かったです。

駆け引きや読み合いも重要かもしれませんが、まずシンプルに効率を上げないと太刀打ちできません。Silverリーグにいた頃、上位勢が自分の想像をはるかに超える速度で呪文を回しているのを見て衝撃を受けました。こんなの無理だろと思っていましたが、ビームサーチをしっかり組んで自分のプログラムが同じような動きをしてくれた時は嬉しかったです。その時のツイート↓

あと、この記事の戦略説明はコンテスト中に下書き状態で書いています。書くことによって自分の現状が整理され、ロジックの不自然な所や新しい改善案が見えてきました。終わったらそのまま参加記として公開できるので一石二鳥です。オススメ。

Waseda University Programming Contest 2020 E: LCM Count (AOJ 3155)

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

お題箱より。

Aizu Online Judge

解法

最小公倍数や最大公約数は、素因数ごとに「重複度の最大値/最小値」を取るという観点で捉えると考えやすくなることがあります。

  • A_{0}, ..., A_{k-1} の最小公倍数（LCM）は、全ての素数 p_{i} について各要素における p_{i} の重複度の最大値 c_{i} を求め、 p_{i}^{c_{i}} を全て掛け合わせたものである。
  • A_{0}, ..., A_{k-1} の最大公約数（GCD）は、全ての素数 p_{i} について各要素における p_{i} の重複度の最小値 c_{i} を求め、 p_{i}^{c_{i}} を全て掛け合わせたものである。

この観点で問題を捉えるために、まず N を素因数分解します。 N の相異なる素因数を p_{1}, ..., p_{n} とし、それぞれの重複度を c_{1}, ..., c_{n} とします。

整数列 A の要素のLCMが N になる必要十分条件は、以下の条件を全て満たすことです。

  1. A の全ての要素は N の約数である。すなわち A の全ての要素について以下が成り立つ。
    • 素因数として p_{1}, ..., p_{n} 以外の素数が登場しない。
    • 全ての N の素因数 p_{i} について、その重複度が c_{i} 以下である。
  2. 全ての N の素因数 p_{i} について以下が成り立つ。
    • A の少なくとも1つの要素について、素因数 p_{i} の重複度がちょうど c_{i} である。

この条件を満たす数列を数える上で、「 A の全ての要素は N の約数である」という点は前提とします。その上で「 A の少なくとも1つの要素について、素因数 p_{i} の重複度がちょうど c_{i} である」という条件は扱いにくいので、包除原理を適用します。

\lbrace 1, ..., n\rbrace の部分集合 s について、 C(s) を以下の条件を満たす数列の個数と定義します。包除原理から答えは \sum_{s} (-1)^{|s|}C(s) と計算できます。

  • 相異なる N の約数からなる、空でない数列である。
  • s に属するインデックス i について、素因数 p_{i} の重複度が c_{i} である要素が存在しない。

この C(s) を求めましょう。まず数列の要素として使える整数が何種類あるのかを計算します。これはそれぞれの素因数 p_{i} について、取り得る重複度が何通りあるのかを以下のように求めて、全て掛け合わせたものです。

  • i が s に属している場合、取り得る重複度は 0, ..., c_{i}-1 の c_{i} 通り。
  • i が s に属していない場合、取り得る重複度は 0, ..., c_{i} の c_{i}+1 通り。

この値を M とすると、 C(s) は M 種類の整数から 1 種類以上を選んで並べた数列の個数です。これは数列の長さごとに分けて考えると、

  • 長さ 1： _{M}P_{1} = \frac{M!}{(M-1)!} 通り
  • 長さ 2： _{M}P_{2} = \frac{M!}{(M-2)!} 通り
  • \cdots
  • 長さ M： _{M}P_{M} = \frac{M!}{0!} 通り

と計算することができて、この総和は M!\times(\frac{1}{0!} + \frac{1}{1!} + \cdots + \frac{1}{(M-1)!}) とまとめられます。これは階乗と階乗の逆元の累積和を前計算しておけば O(1) で計算できます。

これで C(s) が計算できるので、包除原理の式に従って答えを求めることができます。

計算量は素因数分解パートと階乗前計算パートが O(\sqrt{N})、包除原理パートが N の相異なる素因数の個数 n に対して O(n2^{n}) です。 1 \le N \le 10^{12} のとき 0 \le n \le 11 なので十分間に合います。

ACコード

Aizu Online Judge

第１１回日本情報オリンピック 予選 E - イルミネーション

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

お題箱より。

E - イルミネーション (Illumination)

解法

座標の表記について、（縦の座標, 横の座標）という順番で表記することにします。こちらのほうが配列の添字順と合うので都合が良いです。

公式解説と同じく、与えられる領域の外周にもう1つ分の六角形が存在するとして考えると扱いやすいです。入力を1-indexedのまま扱い、 (0, 0) から (H+1, W+1) までの座標が存在すると思えば良いです。

全ての六角形について「外から建物の中を通らずに到達できる場所」かどうかを判定することを目指します。求めたい答えは、外から到達できる六角形と到達できない六角形が隣接している壁の枚数です。

外周から到達可能な六角形は、例えば以下のような方法で求めることができます。

  • 外周にある六角形から、互いに通行可能な六角形を辿っていく幅優先探索を行う。
  • 外周にある六角形から、互いに通行可能な六角形を辿っていく深さ優先探索を行う。
  • UnionFindを用いて、互いに通行可能な六角形同士を連結し、外周と同じ連結成分に属するか判定する。

どの方法でも構いません。今回は幅優先探索することにしましょう。

ここで少し問題となるのが、ある六角形に隣り合う六角形の座標の求め方です。今回の問題のような座標の付け方では、座標 (x, y) と隣り合う六角形の座標は縦の座標値 x の偶奇に応じて変わります。具体的には以下のようになります（問題文中の図と座標の表記順が逆なので注意）。

  • x が奇数の場合、隣り合う座標は (x-1, y), (x-1, y+1), (x, y-1), (x, y+1), (x+1, y), (x+1, y+1)。
  • x が偶数の場合、隣り合う座標は (x-1, y-1), (x-1, y), (x, y-1), (x, y+1), (x+1, y-1), (x+1, y)。

これらの隣接する座標のうち通行可能な場所を辿っていくように幅優先探索を行えば良いです。

これで全ての六角形について「外から建物の中を通らずに到達できる場所」かどうかを判定できました。答えを求める際には、外から到達できる六角形全てについて、隣接している外から到達できない六角形の個数を数えて合計すれば良いです。

隣接している六角形の座標を求める処理は、幅優先探索パートと答えを求めるパートの2通りの用途で使います。実装の際には関数化しておくのが良いでしょう。

ACコード

Submission #17836742 - 第１１回日本情報オリンピック 予選（オンライン）