AtCoder Grand Contest 047 D - Twin Binary Trees
お題箱より。
解法
ちょうど2本の特殊辺を持つ単純サイクルは、第1の木の異なる2つの葉の組み合わせと同じ個数だけ存在します。このサイクルは、その2つの葉の第1の木におけるLCAと、それらと接続されている第2の木の2つの葉のLCAとを2本のパスで結ぶものです。
2つの葉の組み合わせを全て列挙していると間に合いません。そのため方針としては、第1の木の頂点を全探索し、その頂点を第1のLCAとするサイクルたちの積の総和をまとめて数えます。
第1の木の頂点 をLCAとするサイクルの積の総和は、具体的には以下の手順で求めることができます。
【手順1】 まず から左側の子孫に進み、それぞれの葉から第2の木の根までのパスを全て辿る。このとき通過する第2の木の頂点 全てに対して、 から頂点 までのパスにおける頂点番号の積を求めて配列の要素 に足しておく。
図において各頂点の左側に書いている赤い数字が該当します。
【手順2】次に から右側の子孫に進み、それぞれの葉から第2の木の根までのパスを全て辿る。このとき通過する第2の木の頂点 全てに対して、 から頂点 までのパスにおける頂点番号の積と、先ほど求めた との積を答えに足し合わせていく。
つまりこれは、 から左側に降りたパスと右側に降りたパスが合流する点において、別々に求めた頂点番号の積を掛け合わせて答えに足していることになります。掛けてちょうどサイクル1周分となるためには、手順2のほうでは頂点 とその頂点自身の値は含めずに積を計算すると良いです。図において各頂点の右側に書いている青い数字が該当します。
ただしこの方法で数えると、サイクルは第2の木のほうのLCAだけでなく、さらにその祖先である頂点においても加算されてしまいます。しかも祖先においては第2のLCAからさらに余分に進んだ分の係数が掛けられた状態で加算されます。これを帳消しにするためには、第2の木を進むときに「親の頂点においては、これだけの値が余分に加算されてしまうはず」という値を伝播していって、答えから引けば良いです。
【手順3】手順1において通過した第2の木の頂点を覚えておき、それらの頂点について の値を にリセットする。
これは次の に関する計算に移る前に必要です。 の値は手順1で通過した頂点だけしか変化していないため、それらの頂点だけについて処理することで計算量を抑えています。
これを全ての について試して合計すると答えを求められます。
計算量について考えます。全ての葉は、動作全体で 回だけ見られることになります。そして葉が1回見られるごとに、そのときの第1の木における頂点 へのパスを1回、第2の木の根へのパスを最大2回通ります。このパスの長さは 以下であり、葉の個数が 個であるため、全体計算量は となります。
ACコード
Submission #18423719 - AtCoder Grand Contest 047
やっていることは木を何回も走査しているだけですが、係数の細かな扱いを間違えずに行う必要があります。
AtCoder Grand Contest 046 D - Secret Passage
お題箱より。
解法
操作の特徴をつかむ
与えられる文字列 の長さを とします。また の 文字目を と表記します( 先頭は です)。
操作列によって文字列がどのようになるかを、まずは大雑把に理解しましょう。前から順に操作されるため、元の文字列 は操作された前側の領域と操作されなかった後ろ側の領域に分かれます。そして操作された文字のうちいくつかが後ろ側に挿入されることによって文字列が完成します。
削除されなかった文字がどこに挿入されるかは自由です。また、挿入された文字が再び操作の対象となる場合もあり得ます。
このように考えると、操作列の結果としてある状態が作れるかどうかは、その操作列において操作される領域の長さ、後ろに挿入する 0
の個数、後ろに挿入する 1
の個数という3パラメータから判断できることが分かります。例えば上の図の操作であれば です。
これを踏まえて、次のDPを考えましょう。
- 文字列 のうち先頭 文字を操作することで、
0
を 文字、1
を 文字後ろ側に挿入することはできるか?(true/false)
初期条件は がtrueであることです。遷移を考えましょう。 がtrueであるとき、その状態からの操作を考えることで次に列挙する遷移先をtrueにすることができます。
- 先頭2文字を操作し、後ろ側の文字をそのままの位置に戻す。実質的に先頭1文字を削った形になり、 がtrueである。
- 先頭2文字を操作し、そのうちの1文字を後ろに挿入する。 と のうちいずれかが
0
であれば がtrueであり、いずれかが1
であれば がtrueである。 - これまでの操作で「後ろに挿入する」ということにした文字のうち、 と異なる文字を1つ の直前に挿入してから、その文字と を操作し、 を後ろに挿入する。 が
0
であれば がtrueであり、1
であれば がtrueである。
※遷移1については、厳密には操作されているのは 文字目までではなく 文字目までなのですが…後の説明の都合上、「残っている文字が2文字以上のとき、先頭の文字を1つ削除する」という操作として扱ってしまうことにします。
後で使う性質として、このDPテーブルには単調性が成り立ちます。 がtrueならば、 かつ である に対して もtrueです。これは を実現する遷移列において、遷移2と遷移3を適切に遷移1に置き換えていくことで の値を自由に減らせることから示せます。
このDPテーブルにおいて値がtrueであるような の組全てについて、
- の後ろ側 文字に、
0
を 個、1
を 個挿入してできる文字列が何通りあるか?
を計算して合計すれば答えが求められそうな気がします。しかし、残念ながらこれでは正しい答えになりません。異なる の組から同じ文字列ができてしまう可能性があるからです。
重複を排除する
操作列によって作ることができる全ての文字列を、それぞれちょうど1回だけ答えに加算する方法を考えます。ある文字列 が作れるとして、 を作る時に操作する領域の長さ をちょうど1通りだけ考えることができれば、操作されない領域に不足している 0
と 1
の個数である は一意に定まります。
ここで、次の性質が成り立つことが証明できます。
- ある操作列によって文字列 を作ることが可能であるならば、「 の接尾辞であって、 の部分列として取れるもののうち最も長いものの長さ」を として、 の末尾 文字を操作することなく を作るような操作列が存在する。
この性質を利用して、 を作る時に操作する領域の長さを に限定することで、文字列 をちょうど1回だけ数えることができます。
この性質を証明します。以下の図のように、操作されない領域の長さが よりも短い操作列Aで が作れると仮定します。このとき、操作されない領域が1つ長くなるような操作列Bが存在して が作れることが証明できればよいです。
直感的には、操作する領域の文字のうち最大で半分しか後ろ側に挿入できないことを考えると、操作する領域の長さが1つ減る代わりに挿入すべき文字が1つ減るのは条件として易しくなってそうな気がします。ちゃんと証明するために冒頭のDPを用います。
操作列Aにおいて操作した領域の長さ、挿入した0の個数、挿入した1の個数を とします。図のように が 1
である場合を考えます( が 0
である場合も同様に考えられます)。すると操作列Bは で特徴づけられるため、「 がtrueであるならば、 もtrueである」ことが証明できれば良いです。
がtrueであるならば、その遷移元としてあり得る状態のうち少なくとも1つがtrueであるはずです。冒頭の遷移一覧に基づいてこの遷移元を列挙します。
- ( が
0
である場合)
第1添字が のものについては、そこから遷移可能な先に置き換えます。すると次のうち少なくとも1つがtrueであることが分かります。
これらは全て、第2添字、第3添字がともに示したい の添字以上になっています。よってDPテーブルの単調性から、これらのうちどれがtrueであっても がtrueであることが言えます。以上で証明が完了します。
答えを数える
ようやく答えを数えるパートです。これまでの考察から、 の組全てについて次の値を計算すれば良いです。
- : の後ろ側 文字に、
0
を 個、1
を 個挿入してできる文字列であって、「 の接尾辞であって、 の部分列として取れるもののうち最も長いものの長さ」が であるものが何通りあるか?
これは文字列 を後ろから作っていくDPで求めることができます。 からの遷移としては、もし が 0
であれば
- 文字列の先頭に
0
を付ける:部分列として取れる接尾辞の長さが増えるので、 に遷移 - 文字列の先頭に
1
を付ける:部分列として取れる接尾辞の長さが増えず、挿入した文字の扱いになるので、 に遷移
という2通りの遷移があり得ます。 が 1
であれば逆です。
がtrueである 全てについて を合計すれば答えになります。実装によっては空文字列を含んでしまう( を算入してしまう)ことがあるので、その場合は を引きましょう。
ACコード
CodinGame Fall Challenge 2020 参加記
ゲームAIコンテスト「CodinGame Fall Challenge 2020」に参加して、Legendリーグ63位でした!
どんなゲーム?
アニメーション:Game Replay - CodinGame
素材からポーションを作ってお金を稼ぐゲームです。各プレイヤーはターンごとに「注文リスト内のポーションを調合して報酬を得る」「呪文を使って素材を獲得したり変化させる」「新しい呪文を覚える」「休憩して既に使った呪文を回復させる」のいずれかの行動を取ることができます。最後に稼いだお金が多いほうが勝ちです。
効率よく呪文を使って、短いターンで報酬の多いポーションを作れる手順を組み立てることが何よりも重要です。一方で、覚えられる呪文とポーションの注文は2人のプレイヤーに共通で、どちらかが先に取るとなくなってしまいます。相手が持っている素材と呪文のリストも見えるので、相手の行動を予測したり、相手が欲しそうなものを先回りして取ることで妨害したりする戦術も可能です。
以降の戦略説明ではルール内の言葉が多く登場しますので、ツカモさんのルール和訳も合わせてご覧ください。
codingame:Fall Challenge 2020 ルール要約&内部パターン紹介 - tsukammoの収穫記
戦略
大まかな行動方針は以下の通りです。
- 最初の6ターン:必ず呪文を習得する
- それ以降:ビームサーチを用いて行動を決定する
ビームサーチでも呪文習得は行動の選択肢として考慮するので、全部ビームサーチで行動決定するという案もありました。しかし序盤は相手も呪文を多く取ってくるので、未来のターンで取れる呪文に不確実性が高いと考え、先を読まずターンごとに判断する方法にしました。
序盤の呪文習得
このゲームでは、repeatableな呪文を用いて大量の素材を一気にグレードアップさせていくことが非常に重要です。そのためrepeat回数を考慮した呪文の価値付けをしました。習得可能な呪文を以下のように価値付けして、最も価値が大きいものを習得しました。
- 呪文1回分の価値 :素材の価値を順に としたときの、呪文前後での価値合計の増分
- repeatableな呪文の最大回数 :1回で消費する素材個数 、獲得する素材個数 とすると、
- 呪文の価値:
ポーションの報酬額は素材の価値を として設定されているため、私も長くこの値を使ってきましたが、差し引きで素材個数が増える呪文を優遇するためにLegend昇格直前で に変更しました。これは呪文がキレイに回るパターンである
個数が増える呪文で個数を増やす→tierを上げる呪文で全体のtierを上げる→ポーションを作って個数が減る→個数が増える呪文で個数を増やす→…
という流れができやすいようにしたいという意図です。
係数 は、呪文の効果と先読み税の得失のうちどちらを重視するかを決めるものです。当初この係数は でしたが、先読み税が高い呪文を取りすぎて序盤の所持素材に差が付き、そのまま追いつけない試合が多くありました。そのため何度か調整して結果的に に落ち着きました。
補正値では「tier-0の素材を消費する呪文(まだ持っていない場合)」と「消費無しで3個以上の素材が貰える呪文」の価値を しています。逆に「既に持っているrepeatableな呪文と消費色・獲得色が全く同じ呪文」は機能が被ってしまうので、価値を しています。
ビームサーチ
行動と状態管理
ビームサーチで考慮する行動の候補は以下の通りです。
- 現時点で見えているポーションの作成
- 現時点で見えている呪文の習得
- 呪文の使用(repeatableの場合、可能な全回数を試す)
- 休息
ポーションの緊急ボーナスや呪文習得の先読み税などは未来のターンでは変動する可能性がありますが、現時点で見えている情報のままとして扱います。また、現時点で出現していない習得呪文やポーションは考慮しません。
状態を表す構造体は以下の情報を管理しています。
- 自分のインベントリにある素材の個数
- 自分の累積ポーション作成個数
- 使用可能な呪文のID配列
- 使用済みの(休息で回復する)呪文のID配列
- 習得可能な呪文のID配列
- 作成可能なポーションのID配列
- 最初の行動
- 評価値
IDから各アクションの中身を取り出すための配列を別途作っておくことで、状態が持つべき情報をIDだけにしています。ビームサーチでは状態をコピーすることが多いのでなるべくスリムにしました。
ビーム幅は色々試した結果60になりました。時間で探索を切っているので見ているターン数は決まっていませんが、実測では10ターンくらい先まで見ていました。
状態の評価値の計算
状態の評価値の計算に用いるのは、それまでの行動で作成したポーションの価格と作成したターン、そしてインベントリの素材です。
ポーションは相手に取られる可能性があり、なるべく早く取ったほうが有利です。そのためポーションの報酬は、現時点からポーション作成までの経過ターン数に応じた減衰率を掛けて評価値に加算していきます。具体的にはターン数を として を掛けています。
さらに「現時点で相手が作成可能なポーション」である場合、次のターン以降には無くなっている可能性が高いので、次ターン以降に作る場合はさらに の減衰率を掛けています。
インベントリの素材の価値はそれぞれ として計算して合計し、こちらにも を掛けています。インベントリの素材は「将来的にポーションの報酬に変わる可能性があるもの」なので、本来はポーションの報酬の係数 よりも低い割合にするのが自然だと思いますが、低くするとポーションを作った直後にインベントリが空になって次の動きが悪くなることが多かったので高めに評価しています。
ただし高いtierの素材がインベントリを圧迫して消費できない状態になってしまうと詰むので、tier-2とtier-3の素材はそれぞれ5個分までしか評価値に算入しません。
例外として、累積6個のポーションを作った状態は特別に扱います。自分が6個のポーションを作った状態でゲームを終わらせるのは有利なので、経過ターン数が少ないほど大きくなるボーナス値を足しました。またインベントリの価値は計算せずに、最終得点計算の基準(つまりtier-1以上の素材1個につき1点)で6個目のポーションの報酬と同じように加算しています。
ゲーム終了条件の考慮
現ターンでゲームが終わる可能性がある状況では、ビームサーチを行わずに行動を判断することがあります。
もし自分の累積作成ポーションが5個で、ポーションを作成することで勝利が確定する場合、ビームサーチを行わずにポーションを作成して終了します。「勝利が確定する」かどうかの判定では、相手がポーションを作るだけでなく呪文で素材ボーナスを目一杯伸ばすことも考慮しています。Gold上位だと、勝ちを読んだと思ったら素材ボーナスを伸ばされて負けることが意外とありました。
また逆に相手の累積作成ポーションが5個で、相手がポーションを作成することで自分が負ける場合、自分はポーション作成または呪文によって可能な限り最終スコアを高めます。これで勝てている試合も意外とありました。
やっていないこと
以下の2つは検討しましたが、効果が期待できるほどしっかり実装に組み込める気がしなかったので見送りました。
- まだ見えていない呪文やポーションの注文を予測して未来の行動を評価すること。
- 相手の未来の行動を予測すること。
何となく良さそうだなと思っていた戦略は、「ある1手目の行動について、相手の行動に応じて分岐するいくつかの展開を考えて、それらの展開の評価値の重み付き平均をその1手目の行動とする」という考え方です。例えば狙っていたポーションが先に取られて非常に苦しい局面になることがあったので、取られた場合の展開も考慮しながら行動を評価すると良さそうだと考えました。
考え方としてはモンテカルロ木探索に近いのかな。ただ実装経験がなく、ビームサーチからの移行も難しそうだったので採用しませんでした。
その他、雑多な感想
前回のパックマンがとても面白かったので、半年間密かに楽しみにしていました。今回もLegendリーグに行けて良かったです。
駆け引きや読み合いも重要かもしれませんが、まずシンプルに効率を上げないと太刀打ちできません。Silverリーグにいた頃、上位勢が自分の想像をはるかに超える速度で呪文を回しているのを見て衝撃を受けました。こんなの無理だろと思っていましたが、ビームサーチをしっかり組んで自分のプログラムが同じような動きをしてくれた時は嬉しかったです。その時のツイート↓
おばあちゃん、覚醒 pic.twitter.com/iVPuekXnWb
— アルメリア (@armeria_betrue) 2020年11月17日
あと、この記事の戦略説明はコンテスト中に下書き状態で書いています。書くことによって自分の現状が整理され、ロジックの不自然な所や新しい改善案が見えてきました。終わったらそのまま参加記として公開できるので一石二鳥です。オススメ。
Waseda University Programming Contest 2020 E: LCM Count (AOJ 3155)
お題箱より。
解法
最小公倍数や最大公約数は、素因数ごとに「重複度の最大値/最小値」を取るという観点で捉えると考えやすくなることがあります。
- の最小公倍数(LCM)は、全ての素数 について各要素における の重複度の最大値 を求め、 を全て掛け合わせたものである。
- の最大公約数(GCD)は、全ての素数 について各要素における の重複度の最小値 を求め、 を全て掛け合わせたものである。
この観点で問題を捉えるために、まず を素因数分解します。 の相異なる素因数を とし、それぞれの重複度を とします。
整数列 の要素のLCMが になる必要十分条件は、以下の条件を全て満たすことです。
- の全ての要素は の約数である。すなわち の全ての要素について以下が成り立つ。
- 素因数として 以外の素数が登場しない。
- 全ての の素因数 について、その重複度が 以下である。
- 全ての の素因数 について以下が成り立つ。
- の少なくとも1つの要素について、素因数 の重複度がちょうど である。
この条件を満たす数列を数える上で、「 の全ての要素は の約数である」という点は前提とします。その上で「 の少なくとも1つの要素について、素因数 の重複度がちょうど である」という条件は扱いにくいので、包除原理を適用します。
の部分集合 について、 を以下の条件を満たす数列の個数と定義します。包除原理から答えは と計算できます。
- 相異なる の約数からなる、空でない数列である。
- に属するインデックス について、素因数 の重複度が である要素が存在しない。
この を求めましょう。まず数列の要素として使える整数が何種類あるのかを計算します。これはそれぞれの素因数 について、取り得る重複度が何通りあるのかを以下のように求めて、全て掛け合わせたものです。
- が に属している場合、取り得る重複度は の 通り。
- が に属していない場合、取り得る重複度は の 通り。
この値を とすると、 は 種類の整数から 種類以上を選んで並べた数列の個数です。これは数列の長さごとに分けて考えると、
- 長さ : 通り
- 長さ : 通り
- 長さ : 通り
と計算することができて、この総和は とまとめられます。これは階乗と階乗の逆元の累積和を前計算しておけば で計算できます。
これで が計算できるので、包除原理の式に従って答えを求めることができます。
計算量は素因数分解パートと階乗前計算パートが 、包除原理パートが の相異なる素因数の個数 に対して です。 のとき なので十分間に合います。
ACコード
第11回日本情報オリンピック 予選 E - イルミネーション
お題箱より。
解法
座標の表記について、(縦の座標, 横の座標)という順番で表記することにします。こちらのほうが配列の添字順と合うので都合が良いです。
公式解説と同じく、与えられる領域の外周にもう1つ分の六角形が存在するとして考えると扱いやすいです。入力を1-indexedのまま扱い、 から までの座標が存在すると思えば良いです。
全ての六角形について「外から建物の中を通らずに到達できる場所」かどうかを判定することを目指します。求めたい答えは、外から到達できる六角形と到達できない六角形が隣接している壁の枚数です。
外周から到達可能な六角形は、例えば以下のような方法で求めることができます。
- 外周にある六角形から、互いに通行可能な六角形を辿っていく幅優先探索を行う。
- 外周にある六角形から、互いに通行可能な六角形を辿っていく深さ優先探索を行う。
- UnionFindを用いて、互いに通行可能な六角形同士を連結し、外周と同じ連結成分に属するか判定する。
どの方法でも構いません。今回は幅優先探索することにしましょう。
ここで少し問題となるのが、ある六角形に隣り合う六角形の座標の求め方です。今回の問題のような座標の付け方では、座標 と隣り合う六角形の座標は縦の座標値 の偶奇に応じて変わります。具体的には以下のようになります(問題文中の図と座標の表記順が逆なので注意)。
- が奇数の場合、隣り合う座標は 。
- が偶数の場合、隣り合う座標は 。
これらの隣接する座標のうち通行可能な場所を辿っていくように幅優先探索を行えば良いです。
これで全ての六角形について「外から建物の中を通らずに到達できる場所」かどうかを判定できました。答えを求める際には、外から到達できる六角形全てについて、隣接している外から到達できない六角形の個数を数えて合計すれば良いです。
隣接している六角形の座標を求める処理は、幅優先探索パートと答えを求めるパートの2通りの用途で使います。実装の際には関数化しておくのが良いでしょう。
ACコード
AtCoder Regular Contest 106 D - Powers
解法
- である全てのペア について、【 と について対称な式】の値を合計せよ。
という問題設定はよく登場します。このような問題では、 という条件を外して
- かつ である全てのペア について、【 と について対称な式】の値を合計せよ。
と考えると見通しが良くなることが非常に多いです。この値を求めてから、 の場合を引き、対称性を利用して で割ると元々の答えが求められることになります。
ということで、 を かつ である全てのペア について合計することを考えます。
ここで が
と二項係数を用いて分解できることに注目します。これを全てのペア について合計したものが、今求めたい値です。
ここで和を取る順番を逆にします。ある を1つ固定し、全てのペア について、 それぞれの次数が となる項だけを取り出してみましょう。そうするとそれらの合計は、次の形に因数分解できます。
実際にこの式を展開すると、全てのペア に対する が全て足された形になっていることが確認できます。
この値を について合計すれば良いので、今求めたい値は
となります。これは の 乗和を全て前計算しておくことで、 で求めることができます。
ここから の場合を引き、対称性を利用して で割ると答えになります。 の場合の総和も、 の 乗和を用いて と計算できます。
計算量は前計算パートが 、全ての に対して答えを求めるパートが となります。
ACコード
AtCoder Grand Contest 048 B - Bracket Score
解法
正しい括弧列の必要十分条件
いわゆる「正しい括弧列」の問題です。よく使われるアプローチとして累積和がありますが、今回は括弧が2種類あるので2つの累積和を管理する必要があり厳しそうです。
今回は別の性質を使うことにします。1種類の括弧 (
)
からなる括弧列が正しい括弧列であることの必要十分条件として、
- 文字列から連続する
()
を取り除く操作を繰り返すことで、空文字列にできるような操作列が存在する
ことが挙げられます。今回のように2種類の括弧列がある場合も、同様に
- 文字列から連続する
()
または[]
を取り除く操作を繰り返すことで、空文字列にできるような操作列が存在する
ことが「良い括弧列」であることの必要十分条件になります。
AB文字列に置き換える
括弧列をそのまま考えるのは面倒なので、文字を2種類だけにします。括弧列 に対して、(
と )
を A
に、[
と ]
を B
に置き換えた文字列 を考えます。括弧列のスコアはこの から計算することができます。
もし が良い括弧列であるならば、先ほど確認した事実から、 は「文字列から連続する AA
または BB
を取り除く操作を繰り返すことで、空文字列にできるような操作列が存在する」という条件を必ず満たすはずです。逆に A
または B
からなる文字列 がそのような条件を満たすならば、操作列において取り除かれる AA
を ()
に、BB
を []
に置き換えることで必ず良い括弧列 を作ることができます。
このことから、括弧列ではなく A
または B
からなる文字列を最初から考え、「文字列から連続する AA
または BB
を取り除く操作を繰り返すことで、空文字列にできるような操作列が存在する」という条件のもとでスコアを最大化すれば良いことが分かります。
偶奇いずれかのインデックスを反転
ここまでの考察でも解けますが、もう1ステップ進んでみます。「連続する2文字を取り除く」という操作において、残された各文字が位置するインデックスの偶奇は変わりません。このことを利用して、初期状態で奇数インデックスに位置する文字だけ A
と B
を反転してみます。「連続する AA
または BB
を取り除く」という操作は、この反転によって「連続する AB
または BA
を取り除く」という操作に変わります。
そして連続する AB
または BA
を取り除く操作によって空文字列にできる必要十分条件は、A
と B
がちょうど同数存在することです。必要性は明らかで、十分性は「初期状態でA
と B
がちょうど同数であれば、操作の過程で A
と B
は常に同数であり、空文字列になるまで A
と B
が隣り合う箇所が常に存在する」ことから言えます。
ここまで考察できれば解法は非常にシンプルです。以下の手順で答えを求めることができます。
- 与えられた入力に対して、奇数であるインデックス の と を入れ替える。
- 全てのインデックスを の値でソートし、小さい方から半分の と大きい方から半分の を採用し、合計値を求める。
ACコード
Submission #17509364 - AtCoder Grand Contest 048
最後の考察は少し前のAGCでも出題されていたため、コンテスト本番ではこれを思い出して解くことができました。