AHC032

 

 

 

AHC032 の考察記事です。

 

11,762 M 点で 18 位でした。

 

ざっくり方針

  • 1 マスで 1 手ずつ使う
  • 上から順に、各行を 4 マス＋ 5 マスに分けて全探索により最善手を選ぶ
  • 下 3 列は 6 マスずつ全探索
  • 最後の 9 マスは 9 手を全探索

 

お気持ち

  • 試行回数に制限があるので、試行ごとの効率を最適化したい
  • マス数と試行回数が一致しているので、基本的にはマスごとに試行 1 回を対応させたい
  • きれいな法則がないので基本的には探索ゲーになる
  • 本問では、選択肢があまり多くないことによる情報量的限界と、探索の計算時間的な限界の二つの側面がある
  • 例えば焼きなまし法のように、探索時間を潤沢に使う方法は遅い言語では不利になりがち（Python だと辛い）
  • 前者の限界以上の精度を出せる程度の探索を効率行えれば計算時間がネックになることはない
  • 実際、本問では「行ごと」「4 列＋5列」の全探索でこれを達成できる

 

 

前提

  • 1 マスあたり 1 スタンプ使うことにする
    • 2 マスで 2 スタンプなどは可とする
    • 1 マス（だけ）のために 2 スタンプ押したり、 2 マスで 1 スタンプのように節約することは取り入れなかった
      • 後者は実装できれば取り入れた方が良かった

 

詳細方針

 

左 4 マス全探索

 

各行について、左から 4 マスに影響する置き方を考えます。具体的には、画像の灰色の部分を固定したときに、ピンクの部分の置き方を最適化したいです。

白の部分はあとで考えるので浸食して OK 。

 

「1 マスあたり 1 スタンプ」ルールを考えると、許容される配置は、左上の位置のタプルで表すと (0, 0, 0, 1), (0, 0, 0, 2), (0, 0, 0, 3), (0, 0, 1, 1), (0, 0, 1, 2), (0, 0, 1, 3), (0, 0, 2, 2), (0, 0, 2, 3), (0, 1, 1, 1), (0, 1, 1, 2), (0, 1, 1, 3), (0, 1, 2, 2), (0, 1, 2, 3) の 13 パターン、どのスタンプを使うかを含めても 875,400 通りしかないので全探索できます。

なお、 (0, 0, 0, 0) や (0, 2, 2, 3) などは「1 マス 1 スタンプ」を満たさないので省きました（前者は右端のマスが覆われず、後者は最初の 2 マスを 1 スタンプしかカバーしていない）。

 

 

 

右 5 マス全探索

 

 

こちらは置く位置のパターンは 8 通り、どのスタンプを使うかを含めても 5,140,800 通りありますが、最初の 3 マスが確定した時点で弱い場合は打ち切るなどの枝刈りでもう少し減らすことができます。

先ほどの 4 マスより 1 マス増えますが、右側にはみ出せないため置き方はあまり多くなりません。

 

 

下 3 行（6 マス全探索）

こちらは置く位置のパターンは 3 通り、どのスタンプを使うかを含めても 5,081,230 通りあります。最初の 3 マスが確定した時点で打ち切ると、若干減らすことができます。

 

下 3 行（最後の 9 マスを全探索）

こちらは置く位置は 1 とおり、どのスタンプを使うかは 6,906,900 通りあります。

これは枝刈りできないので全部頑張ります。

 

 

 

スコアの概算

問題がシンプルなので、実はある程度仮定を置くと「いくつかのマスについて全探索」を繰り返すような解法を前提にスコアの理論値が概算できます。

以下 P=998244353 とします。

1 マスに 1 回までスタンプを押す場合

1 マスの場合、そこを左上とするスタンプを置く方法は「無」のスタンプを押す方法も含めて 21 通りあります。これらが一様ランダムな場合の最小コストは、 \displaystyle\frac{1}{22}P です *1 。

仮に 81 マスすべてこの誤差で置いたとすると、ケースあたりのスコアは約 77.18B になります。

 

一般の場合

より一般に d マスで c 通りを試すとき、最善パターンのペナルティを計算しましょう。

簡単のため P で割って、マスごとのコストの分布が [0, 1) の

確率変数 X が 0 以上 1 以下の一様分布に従うとします。それらの合計 S の密度関数は d 次関数が複数つながった複雑な形になりますが、 0\lt s \lt 1 （★）の範囲では f_{S}(s)=P(S\lt s)=\displaystyle\frac{1}{d!}s^{d} と表せます。

スタンプの押し方が c 通りあるとして、簡単のためこれらの置き方によるペナルティが一様ランダムに存在すると近似します。 c 通り試したときの最小値は複雑な形になりますが、簡単のため該当付近が線形だと仮定すると 1 マス 1 スタンプの場合と同様、この逆関数の c+1 分位点、すなわち \displaystyle f_{S}^{-1}(\frac{1}{c+1}) になります。

 

スタンプの押し方

1 個のマスに（そこを左上として）合計 z 個のスタンプを押す方法は _{M}H_{z} = _{M+z-1}C_{z} 通りあります。

y 個のマスに合計 z 個のスタンプを押す方法は DP を用いて計算できます。

例えば本問全体では、 49 個のマスに 81 個のスタンプを押すことができますが、その方法は約 8.4 \times 10^{122} 通りあります。

 

期待得点率

上記をもとに、 x マスを最適化するためそのうち y マスに（そこを左上として） z 個のスタンプを押すときの得点率 g(x, y, z) を計算することができます。

 

x y z 得点率 g(x,y,z)
1 1 1 95.45\%
3 1 3 94.99\%
4 4 4 98.57\%
5 3 5 97.91\%
6 2 6 96.64\%
9 1 9 92.31\%
81 49 81 98.89\%

 

 

最終解法期待値

例えば上に書いた私の解法では、理想的には、全体の得点率は 

\displaystyle\frac{1}{81}(24g(4, 4, 4) + 30g(5, 3, 5) + 18g(6, 2, 6) + 9g(9, 1, 9)) \sim 97.20\% 、すなわちケースあたり約 78.59B 、合計 11.79T のスコアが得られることが期待できると分かります。

実際の私のスコアは 11.76T とやや低くなっています。これは枝刈りによりすべて探索できていないことや、実際はすべての置き方が一様に分布していないことなどによるものと考えられます。

 

1マス - 3マス - 9マス 解法期待値

よりシンプルな解法として

  • 左上の 6×6 部分は 1 マスだけ見て貪欲に決める
  • 右 3 列は 3 マスずつ最適化する
  • 下 3 列は 3 マスずつ最適化する
  • 最後の 9 マスは 9 個のスタンプの置き方を最適化する

という方法があります。この場合の期待値は

\displaystyle\frac{1}{81}(36g(1, 1, 1) + 36 g(3, 1, 3) + 9 g(9, 1, 9)) \sim 94.90\% 、すなわちケースあたり約 76.74B 、合計約 11.51T のスコアが得られることが期待できます。実は私の 第3提出 がこれだったのですが、ほぼ理論値通りの得点が得られていることが分かります *2 。

 

全体理論値

計算量を無視したこの問題の理論上の最適解スコアは、約 81P \times g(81, 49, 81) = 79.96B 、150 ケースだと約 11.994T になることが分かります *3 。

 

 

 

 

 

End

 

 

 

*1:正確には P が有限なので少しずれます

*2:こちらでは枝刈りなどする必要がなかったので、理論値に近いスコアが得られています

*3:実際には上で書いた私の解法が理論値に比べて悪化していたのと同様に、スタンプを押した結果が一様に分布していないことにより若干悪化すると思われます

AHC031

AHC031

 

 

やったこと

  • 縦に切った盤面を構築し、日ごとには横線のみを更新する
  • 縦線の切り方は、 d 日間動かさずに耐えられる範囲でなるべく細く切る
  • 切った後の分け方は、なるべく細いところで入るだけ入れる
  • 列ごとに、翌日と全く同じ位置で切れるなら切る（列のすべての切れ目がキープできる場合のみ）
  • 縦線の集合を決めると貪欲で決める
    • 左から順に貪欲に使うマスを決める（入るやつをなるべく大きく取る）
    • その後右から順に「区切り線を前日と完全一致させられるなら一致させる」をする
  • 縦線の集合の決め方は適当に焼きなまし
    • 序盤は「区切り線を前日と完全一致させられるなら一致させる」を入れない
    • 後半はスコアそのものを評価関数

 

 

 

やりたかったこと

 

たぶんこれをやると結構伸びる（実験した感じ、列ごとの要素数が多いものだと 2 倍ぐらい良くなりそう）と思ってたけど実装がむずすぎて 5 日ぐらいかかっても実装しきれなくて泣いてた *1 。

 

 

  • 列を初日から順に、貸出先とその順列ブロックを決める
    • 左右どちらかと同じ高さになるところに「切れ目」を設けて、各切れ目間に入る貸出先の集合（「ブロック」と呼ぶ）および左右のどの切れ目と対応するかのみを保持する
    • 具体的な高さは決めない（上の情報からなるべく高さが低くなるように計算できる）
  • 各長方形の高さは自由度を持たせておく
  • 各日の中では、下から順にブロックを決める
    • 列ごとに \mathrm{DP} をしていい感じに決める
      • \mathrm{DP}_{i}：下から i 個の貸出先まで決めたときの最適状態たち
      • 最適判定は、前日との共通切れ目の個数、（同じなら）動かせる自由度の大きさ、全体で必要な高さ、の辞書式順序で
      • 遷移は \mathrm{DP}_{i} を求めるときは 0 \le j \lt i をすべて調べる。 
  • 探索の方法は
    • 前日の自由度がある部分（ブロック内の入れ替え）を自由に動かすときに、可能な切断位置の集合を決めておく
    • 今見ている列のうちまだ使っていないやつを自由に動かす
      • Combinations をすべて試せば簡単
      • ブロックごとの要素数が多い場合は最初の 100 個とかで適当に切っても良い
    • 前日の該当部分のブロックの要素数が a 個、当日分が b 個であれば 2^{a+b} ぐらいの自由度があるのでそこそこ近いものができる
    • bisect か尺取りで近いところをくっ付ける

 

感想

 

  • 短冊はすぐ思いついたけどそこからの伸びが・・・
  • DP 実装仕切りたかった。

 

 

ビジュアライザ

今回はいつもに比べて公式の機能が少なかった気がする *2 。

長期コンは考察しやすいように自作するのが良さそう。

 

 

おまけ

 

 

End

*1:誰かやってくれー

*2:何かのメッセージ？

AHC 030

 

AHC 030 参加記

 

AHC 030 おつでした。

プレテスト 7,885 M で暫定 55 位です。

（追記）システスは 528 B で 51 位でした。

 

最終提出

 

提出コード

 

  • M が小さい場合は可能なすべての状態（各油田の左上の座標の組）を持って、期待獲得情報量がなるべく大きくなるクエリを投げるのを繰り返す（☆）
  • M が大きくなるにつれて
    • 行・列ごとに☆を行い、状態数がある程度減ったらマージして再度☆を行う
    • 行 \bmod 5 と行 \bmod 4 から行を復元する
    • 左 3 列などだけを見て 2 ～ 3 個の油田の位置を確定してから上のことを行う
    • それも無理そうなら 4 セルごとに組にして、それぞれをベイズ推定する
    • それも無理そうなら 1 セルごとに聞く

 

 

情報量の計算

一般論

事前分布 P(X) に従う統計量 X を観測することで事後分布 Q(X) を得た場合に得られる情報量は

-\displaystyle\sum_{x}Q(x)\log \frac{P(x)}{Q(x)}

あるいは連続の場合は確率密度関数 p(x) および q(x) を用いて

-\displaystyle\int_{x}q(x)\log \frac{p(x)}{q(x)}dx

と表せる *1 。

 

情報量最大化への帰着

問題の言い換え

問題は「油田埋蔵量が正のマスをすべて特定すること」だが、これを「すべての油田の位置を特定すること」と言い換えたい。

実はこれは M が小さければほぼ正しい。つまり油田の配置は油田埋蔵量が正のマスとほぼ一対一に対応する。 M が大きい場合は単射にならないことが多いが、 M が大きい場合は大変なので（後述するつもり）、この言い換えをする。

 

情報量のオーダー

油田の配置は、初期情報だけからだと \displaystyle\prod_{i=1}^{M}(N-h_i+1)(N-w_i+1) 通りある。これを一意に特定するにはこの対数に相当する情報量 \displaystyle\sum_{i=1}^{M}\log(N-h_i+1)(N-w_i+1) を得る必要がある *2 。

状態数は N^{2M} で抑えられるので、 0 か 1 かを全部持つ状態数 2^{N^2} よりかなり小さくなっている。

コスト当たり約 x の情報量が得られるとすると、 \displaystyle\frac{2M\log N}{x} で正解に辿り着くことができるという計算になる。

 

貪欲法

いろいろ不確実性が高いので、「各ターン、（得られる情報量の期待値）÷（コスト）を最大にするムーブを繰り返す」という貪欲法でも十分強そうということが分かる。

 

 

 

 

 

 

正規分布で近似

（この項は結局使わないので読み飛ばしても OK）

仮定

  • X の事前分布が正規分布 X \sim \mathcal{N}(\mu, \sigma^2)
  • 観測により、実際の値に誤差  e \sim \mathcal{N}(0, \sigma_{e}^{2}) を加えた値が得られる

観測値の分布

このとき観測値 Y の分布は Y \sim \mathcal{N}(\mu, \sigma^2 + \sigma_{e}^{2})

事後分布

また観測値が Y=y であれば事後分布は正規分布 \mathcal{N}(\mu_{\mathrm{post}}, {\sigma_{\mathrm{post}}}^2) に従う

ここで

\mu_{\mathrm{post}}=\displaystyle\frac{\frac{\mu}{\sigma^2}+\frac{y}{{\sigma_{e}}^{2}}}{\frac{1}{\sigma^2}+\frac{1}{{\sigma_{e}}^{2}}}

{\sigma_{\mathrm{post}}^2}=\displaystyle\frac{1}{\frac{1}{\sigma^2}+\frac{1}{{\sigma_{e}}^{2}}}

得られる情報量

これを上の一般の場合の式に代入して、簡単のために t=\displaystyle\frac{{\sigma_e}^2}{\sigma^2} とすると、得られる情報量は

-\displaystyle\frac{1}{2}\log (1+\frac{1}{t})+\frac{1}{2t}+\frac{y^2}{2t(1+t)\sigma ^2}

 

得られる情報量の期待値

これを y について期待値を取ると得られる情報量の期待値が次だと分かる。

-\displaystyle\frac{1}{2}\log (1+\frac{1}{t})+\frac{1}{t}

 

何マス選べば良いか

kマス選んだときの平均・分散

適当に近似すると k マスを無作為に選んで占ったときに得られる情報量の期待値が分かるのでそれを最大化すれば・・・

あたりまで考えたときに、少し実験してみると \epsilon が小さいと情報量が増えすぎちゃうことに気付いた（例えば 0 か 1 しかとらない場合、情報量は最大でも 1 だけど正規分布で近似すると 5 とかが得られてしまうなど）。

 

離散

なので事前分布も誤差関数も離散でやった方が良さそう。

 

誤差と遷移確率

k, \epsilon を固定して考える。

あるサイズ k のマスの集合について、油田数の合計の分布は、それまでに聞いたクエリから理論上厳密に計算できる。

よってこの場合もその集合についてクエリを投げたときに得られる情報量の期待値が（計算量を気にしなければ）厳密に求まる。

可能なすべてのクエリに対してコスト当たり期待獲得情報量を計算するのが良いが、時間的に難しいのでいくつか候補を選んでコスト当たり期待獲得情報量が最大のものを選ぶこととしたい。

 

計算方法（離散の場合）

事前分布が P(x) および事後分布が Q(x) が分かると、得られる情報量は上述のとおり次のように表される。

-\displaystyle\sum_{x}Q(x)\log \frac{P(x)}{Q(x)}

 

あるマスの集合について質問するという観測について、観測を行う前の段階でどれぐらいの情報量を得られるか計算するには、次のように考える必要がある。

 

  1. 各観測結果について、その観測結果が得られた場合の情報量を計算する
  2. それらを事前分布の重みで加重平均する

 

1. については、観測結果から事後分布を計算する必要があるが、これはベイズで計算できる。ちゃんとやるとでかいテーブルが必要になって結構大変だが、 \epsilon はケースごとに固定なので、 k （クエリに投げるセルの個数）ごとにテーブルを前計算しておけばなんとかなる。 Python だとそれでも結構つらいので、なるべく同じ k でクエリを投げるようにした。

 

実装方法

方針

  • すべての状態について、クエリ結果をもとに確率分布を管理する。
  • トップの状態が 2 番目にある程度差を付けたら Answer クエリを投げる

データの持ち方

  • \displaystyle\prod_{i=1}^{M}(N-h_i+1)(N-w_i+1) 通りの状態をすべて管理する。
    • 初期状態では事前分布は互いに等確率なので、すべて同じ重みとする
  • クエリを行うごとに、結果に対して整合的になる確率を掛ける
    • 実装上は対数確率を加算する
    • 管理する量が膨大になるのを防ぐため、十分小さい確率になったら管理対象から外す

どのクエリを選ぶか

  • なるべく結果の分散が大きくなるようなクエリを聞くのが良い
  • マス同士の共分散が高い（≒近くにある）マス同士を一緒に選ぶのが効率的であることが多い
  • ただし一度クエリを投げると、次回からはそのクエリの結果は既知となるので、同じ（あるいは似ている）クエリをたくさん投げても得られる情報量の期待値は少なくなりがち

 

 

計算量削減の工夫

 

 

独立空間への分解

 

O(N^{2M}) 個の状態を管理・更新するのは、 Python では M=2 かせいぜい M=3 ぐらいしか対応できない *3 。

 

行だけ見て、すべての油田の行の位置を決定する

→列だけ見て、すべての油田の列の位置を決定する

 

みたいな方針だと管理する状態数を O(N^{M}) まで減らせるので M=4 ぐらいまで対応できる。

「行だけ見る」というのは、 (i, j) を i に移す関数 f((i, j)=iにより「圧縮」操作をしたと考えることができる。

これでうまくいくのは、「行だけ見る」が加群の商群になっていることが効いている。

 

より一般化すると加群 f:\mathbb Z ^{2} の部分加群 X を固定すると、その商群で考えることができる。

 

一部のマスだけで判定する

例えば左 3 列だけを見て、ここにかぶっている油田が 3 個以下であると仮定すると、調べるパターンは {}_{M}C_{3} \times (3N)^{3} になる。さらに行をまとめたり列 \bmod 5 などを考えることで探索パターンを減らし現実的な計算量で順次特定していくことができる。

私の実装では、これを一度行って 2 ～ 3 この油田の位置を固定して、上の独立空間に分解する方法になった。

 

その他やったこと・考えたこと

  • 今回はローカルで実行せず、すべてコードテストでデバッグした
    • 提出コードと同じコードでコードテストデバッグできるようにした 
    • せっかくビジュアライザ練習してたので使えば良かった
    • 途中まで導入してないと心理的に途中から作るのがめんどくなってしまって良くない
    • コードテストで困ったこと
      • クエリ回数が多いと、クエリ部分だけに絞っても全部出力できないのでデバッグできない
  • 序盤は M=2 以外は打ち切るとかでやっていて、後半に徐々に M を増やしていこうと思っていたが増えきらなかった
  • Web 版ビジュアライザの罠：
    • N と M の上限・下限が設定されている雰囲気があるが、あり得ないパターンが含まれている
      • N=10 かつ M=20 とかを表示して、特定むずそうだなーとか言ってたけど存在しないケースだった

 

できなかったこと

  • 全部の状態を持たなくても、クエリの結果に矛盾しない配置を焼きなましとかギブスサンプリングとかで得るのでも当てられるか
    • 焼きなましは、全部当てないと使いづらそうだし、自分の実力だとだめそうなので棄却
    • ギブスサンプリングだと、最初例えばランダムに 10000 状態持っておいて、クエリごとに尤度を更新して、ある閾値を下回ったらダメな部分を付け替えるみたいなイメージを考えていた（けどこれも自分の実力だと無理そうなので棄却）
  • 「一部のマスだけで判定」を逐次的に実行することで M が大きい場合も計算量を爆発させずに探索ができるはず
    • 実装しきれなかった。
    • PyPy では 1 回やるだけで 1 秒程度かかってしまうので、高速化しないとむり

 

今後やりたいこと

  • 焼きなまし（無限回言ってる）
  • Rust に乗り換える（無限回言ってる）
    • 今回ちょっとだけ chat GPT くんに翻訳してもらおうとしたけど無理だった

 

関連ツイート

 

 

 

（追記） M ごとのシステス順位

6 以上ほぼ 1000 位付近ですね・・・

（これで全体 51 位取れてるので力の入れどころは合っていたということで・・・）

 

 

M \mathrm{Rank} \mathrm{Score} \mathrm{Case} \mathrm{Average}
2 36 146,610,872,823 369 397,319,438
3 27 144,668,767,503 354 408,668,834
4 22 137,882,178,018 358 385,145,748
5 348 23,766,708,507 398 59,715,348
6 1002 7,026,140,456 288 24,396,321
7 703 7,877,432,650 241 32,686,442
8 998 5,235,875,353 190 27,557,238
9 975 6,288,036,010 156 40,307,923
10 981 4,758,143,130 109 43,652,689
11 672 7,383,989,361 140 52,742,781
12 972 5,054,494,368 84 60,172,552
13 979 4,430,272,358 71 62,398,202
14 968 4,682,556,825 60 78,042,613
15 659 5,073,713,315 51 99,484,574
16 955 4,973,223,557 43 115,656,361
17 970 3,373,058,320 28 120,466,368
18 972 6,253,621,561 36 173,711,710
19 952 1,569,309,822 12 130,775,818
20 979 1,215,604,211 12 101,300,350

 

ソース： 

https://siman-man.github.io/ahc_statistics/030/index_m.html

 

 

 

End

*1:カルバック・ライブラー情報量。これがいわゆる情報量の獲得量と一致するのかは未確認

*2:情報量の対数の底はなんでも良いが、実装の都合で私は e のつもりでやった。

*3:状態ごとにシミュレーションをする必要があるので、計算量オーダーとしてはもっと大きい

AHC で出てくる分布

 

 

AHC でよく出てくる分布について書きます。

（書きかけ。あとで追記する。）

 

確率分布と確率変数

あとで書く。

 

期待値と分散

確率変数 X の期待値を E(X) 、分散を V(X) と書きます *1 。

 

 

正規分布

こんな やつ。

確率変数 X が平均 \mu 、分散 \sigma ^{2} の正規分布に従うとき X \sim N(\mu, \sigma^{2}) *2 と書きます。

 

特徴

あとで書く

 

 

対数正規分布

 

X \sim N(\mu, \sigma^{2}) のとき、 Y=e^X が従う分布を対数正規分布と言い、 Y \sim \Lambda(\mu, \sigma ^{2}) と書きます。

 

特徴

このとき E(Y)=e^{\mu+\frac{\sigma ^{2}}{2}} が成立します。

 

お気持ち

X の平均が \mu なんだから Y=2^{X} の平均は e^{\mu} なんじゃないかと思いがちですが、それよりは分散がある分だけ若干大きくなります。

例えば X が -1 、 0 、 1 の値を等確率で取る確率変数だとすると、 2^{X} は \displaystyle\frac{1}{2} 、 1 、 2 となり、平均は \displaystyle\frac{7}{6} なので 1 を若干超えますね。

 

例

 

AHC029 では、プロジェクトの残務量および価値や、方針カードの労働力およびコストが対数正規分布 *3 になっていました。

 

プロジェクトの生成

このように生成されます。

 

何やらややこしい数式が書かれているように見えますが、 round と clamp を無視すれば *4 、大したことはないですね。

このとき、プロジェクトの価値を残務量で割った比率の期待値がどれぐらいになるか気になりませんか？ほぼ同水準に近いように作られているように見えますが、平均は 1 ではありません。

round 関数と clamp 関数を無視すれば、 \displaystyle\frac{v}{h} は \displaystyle\frac{2^{\mathrm{gauss}(b,\ 0.5)}}{2^{b}} の部分、つまり上の記法で \Lambda (0, 0.5^{2}) の対数正規分布になっています。底が 2 であることに注意すると、これは \Lambda(0, (0.5 \log 2)^{2}) に従います。よってこの期待値は \displaystyle\frac{(\log 2)^2}{8} \fallingdotseq 1.061896 \cdots であると分かり、価値の期待値は初期残務量より 6.2\% 程度大きくなることが分かります *5 。

 

方針カードの生成

このように生成されます。

（なお各ターンで 0 枚目に与えられるコストゼロのカードはこの分布に従いませんが、ここでは使わない前提で考えています。）

 

こちらは指数がかかっていない普通の正規分布なので、攻撃力 1 に対するコストの期待値はほぼ 1 です。

 

最初の記載が間違っていたので修正しました（12/27 18:00）

 

プロジェクト完了までに得られる利益の期待値

プロジェクトの初期残務量を基準とすると、価値はそれより約 6.2\% 高く、必要なカードのコストの期待値は残務量と等しいので、すべてのプロジェクトをキャンセルせず無駄なく完了すると期待値としておおよそ 6.2\% の利益が得られることが分かります *6 。

 

 

 

 

End

*1:アクチュアリー試験でもよく使われる記法。

*2:後者の引数は 2 乗を付けることで標準偏差ではなく分散になっています。

*3:正確には clamp 関数や round 関数で丸められていましたが、本質的には対数正規分布と思って良いです。

*4:いずれも影響があまり大きくないことが分かります

*5:正確には round 関数、 clamp 関数の影響で少しずれます

*6:前述のとおりコストゼロのカードは使わない前提です。また実際には「キャンセル」もかなり重要な戦略になるので、この期待値自体が直接使える訳ではないです。

AHC 029

 

 

AHC 029 参加記

 

AHC 029 でやったことと参加記です。

プレテストは 6.4B で暫定26位です。

 

 

やったこと

最終提出 の説明です。バグなどもありますがそのまま説明しています。細かいところは一部省略しています。

 

概要

評価関数による貪欲です。将来ターンのシミュレーションは行っていません。

 

 

カードを引く場面での選択

 

引くカードの評価をだいたい次の表のとおりとして、「（カードの評価）－（コスト）」が最大のものを選択する。

引くカードの種類 評価
通常労働カード 現在持っているプロジェクトに使ったときの評価の変動量の最大値
全力労働カード 現在持っているプロジェクトに使ったときの評価の変動量の合計
キャンセルカード 現在持っているプロジェクトのうち評価が最低のものの -1 倍
業務転換カード 現在持っているプロジェクトの評価の合計の -1 倍
増資カード 600 \times 2^{L}

 

ただし、プロジェクトの評価はだいたい次のとおりとした。

状態 プロジェクトの評価
未完了 0.83v - 0.85h + 0.1(h-h^{0.995})
完了 v

また増資カードは \displaystyle t \times (1 + \frac{p}{m - p + 1} \cdot \frac{1}{L + 5}) \le 999 のときに限り引くこととした。

ここで、 t はその時点のターン数、 m はその時点での所持金、 p はカードの価格、 L はそれまでの増資回数。

 

カードを使う（実行する）場面での選択

増資カードがあれば必ず使用する

そうでなければ「（お金の変動）＋（プロジェクトの評価の変動）－（カード評価）」が最大のものを使用した。

プロジェクトの評価は上と同じものを使用した。カードの評価はだいたい次のとおりとした。

 

カードの種類 評価
通常労働カード 0.7w
全力労働カード 0.6Mw
キャンセルカード 2^{L}
業務転換カード 2^{L}

 

 

最終提出には使わなかったけど試したこと

  • 増資カードの評価を、増資カードの出やすさによって変える（実はやってるつもりだったけどバグっていた）
  • 「カードを引く」→「カードを使用する」の一連の流れをまとめて最適化する
  • 最後の方で実現可能性が低くなったプロジェクトは評価を下げるべきだった（一応何かは入れたけどあまりいい感じにならず・・）
  • プロジェクトごとに評価を作っていたので、特に M が大きいときは余りがちだった
  • Optunaでパラメタ調整をいろいろ試した（けど変動が大きすぎてよく分からなかったので結局手で決めたもの（上に書いたもの）に戻した）

 

できなかった・うまくいかなかったこと

  • N が大きいときも、選んだ直後のカードをそのまま使っていることが多かった（将来使う予定のカードをもう少し効率よくストックできると良かった）
  • 増資カードは 2 枚以上連続で買うと 2 枚目以降のコストが下げられることに気付いたが、うまく使えなかった
  • 高い買い物をしたときに、所持金不足で一定期間（ほぼ）ゼロコストのカードしか取れないみたいな状況に陥ることがあった。うまく指標化して避けるようにしたかったができなかった
  • 適当にシミュレーションすると上がりそうな気がしたけど、それ以前にいろいろバグってできなかった

 

 

参加記

 

序盤

最初の 1～2 日ぐらいはいい感じだったな（遠い昔の思い出）。

 

 

中盤

帰省

 

終盤

いろいろ改造したかったが試してみるとうまくいかず。。

 

 

 

 

End

AHC 027 （HTTF 2024）

AHC 027 （HTTF 2024）参加記

問題は こちら

 

この記事に書いてあること

 

  • 最終提出（プレテスト 189 位）は、汚れやすいマスを TSP で回るのをベースとして、それを倍々に複製しながら、残りのマスを最も良い位置に入れる貪欲
  • マスをグループ分けしたとき、グループ i のマス数を c_i 、汚れやすさの和を x_i とすると、理想的には（頻度を自由に選べるなら）各グループは \displaystyle\sqrt{\frac{x_i}{c_i}} に比例する頻度で訪れるのが最適
  • 二重頂点連結成分分解を用いることで、あるマスの集合とそのうち 2 マス（入口と出口）を与えると、重複なく一度ずつ回って入口から出口まで行けるかどうかの擬似判定がマス数の線形時間でできる（稀に不可能な場合に可能を返すが、ほとんどのケースで大丈夫なはず）
  • グループ分けは汚れやすさが 11 以上のマスからなる連結成分をもとに作成する方法を試した
  • 同じ連結成分内でも比率が 10 を超えるものは別グループにする方法も試した
  • pygame をビジュアライザに使うと便利
  • その他いろいろ考えたけど使えるところまでいけなかった

 

1 日目 - 12 月 1 日（金）

 

考えたこと

  • 汚れがひどいマスを高頻度で掃除するのが最適
  • 最も汚れがひどいエリアを基地として、そこから遠征するイメージか
  • 遠征先は汚れやすさによって数値化して、汚れやすさに比例する頻度で遠征するのが良いか？（理論値の計算は後述）
  • A → B → A → C → A → B → A → D → A → のように、高頻度のものの合間に低頻度のものを挟むイメージ

 

実装してみるがこれムズくない？

この日は提出までいけず。

 

 

おまけ

最初にビジュアライザを見て、カラーモード "d" にしてみたところ、ぱっと見汚れやすさがどれぐらいか分からなかったので、カラーリストを作って、色を見たらすぐに汚れやすさ（ d_{ij} ）がだいたいわかるように練習した。

 

下から 1～10 （ 1 刻み）、 11～20 （ 1 刻み）、 10～100 （ 10 刻み）、 110～200 （ 10 刻み）、 100～1000 （ 100 刻み）。「ある色を見たときにその数値を 1.5 倍までの精度で当てる」（絶対色感）「2 色を見たときにどちらが大きいかを当てる」（相対色感）、ぐらいができれば実用上問題なさそう。

 

 

 

2 日目 - 12 月 2 日（土）

 

1 日目の方針をそれっぽく（雑に）実装

  1. まずは汚れやすいマスたちだけを使って基本のループを作る
  2. 1. の部分は焼きなまし法でやった
  3. 次に全体を 2 倍して、次のレベルのものを最適位置ひとつずつ付ける
  4. 3. での付ける位置は汚れやすさの順に貪欲にした
  5. 3. と 4. をあと 2 回ずつ繰り返す（つまりレベルの段階は全部で 4 つ）

 

この日瞬間最大で 9 位。絶対スコア 839 M 。

 

 

汚れやすさと最適訪問頻度の（簡略化）理論値計算

いろいろ煮詰まったので、基地からいくつかのループがあるときの（簡素化）理論値を計算してみました。簡単のために次の仮定を置きます。

 

  • 基地（例えば最も汚れやすいマスなど）からのループがいくつかあるとする
  • ループは全部で m 個あり、 i 番目（ 1 \le i \le m ）のループはマスが c_i 個、汚れやすさの合計が x_i であるとする
  • 各ループは互いに重ならず、ループ内でも複数回通るマスはないとする（厳密には基地は複数回通るがそこも無視）とする
  • i 番目のループは k_i 回行うこととし、 k=\displaystyle\sum_{i=1}^{m} k_i とする
  • i 番目のループの k_i 回は理想的に（つまり等間隔で）登場するとする
  • このとき、コストを最小にする k_i を求めたい

 

なお、問題の条件および上の仮定によって、 k_i は（絶対数ではなく）比率のみを決めることと考えられます。

移動回数の和 \mathrm{MOVE} は \mathrm{MOVE}=\displaystyle\sum_{i=1}^{m} c_{i} k_{i} 

i 番目のループに含まれるマスは \displaystyle \frac{\mathrm{MOVE}}{k_i} 回ごとに通るので、このグループからの寄与は一次近似で \displaystyle \frac{1}{2} \left(\frac{\mathrm{MOVE}}{k_i}\right)^{2} になります。よって、問題文で定義される「平均汚れ」は、

\displaystyle \sum_{i=1}^{m}x_i \cdot \frac{1}{2} \left(\frac{\mathrm{MOVE}}{k_i}\right)^{2} \cdot k_i \cdot \frac{1}{\mathrm{MOVE}} = \frac{1}{2} \sum_{i=1}^{m}\frac{x_i\ \mathrm{MOVE}}{k_i} = \frac{1}{2} \sum_{i=1}^{m}\frac{x_i}{k_i} \sum_{j=1}^{m}c_{j} \ k_{j}

と計算できます。ここで q_i = c_i\cdot k_i とおき、さらに \displaystyle \sum_{i=1}^{m}q_i = 1 を仮定します（先述のとおり、比率だけを考えれば良いのでこれで一般性を失いません）。

すると平均汚れは \displaystyle \sum_{i=1}^{m}\frac{c_i \ x_i}{q_i} となります。ちょっと実験すると、これは q_i が \displaystyle\sqrt{c_i\ x_i} に比例するとき、すなわち k_i が \displaystyle\sqrt{\frac{x_i}{c_i}} に比例するときに最小値を取ることが分かり、このときの最小値は \displaystyle \frac{1}{2}\left( \sum_{i=1}^{m}\sqrt{c_i \ x_i} \right) ^{2} となります。

当初は汚れやすさに比例する頻度で訪問するのが良いかと思ってましたが、マスの数が同じなら汚れやすさの平方根に比例するという結果になりました。

また式をよく見ると、複数のループに分ける際、平均汚れやすさ \displaystyle\frac{x_i}{c_i} が均等になるように分けても意味はなく、なるべく偏りが大きいように分けると効率が良くなることが分かります。

 

なお、この仮定では各ループが基地を始点・終点としているとしましたが、元のループに対して「寄り道」をすることで追加的に到達できる部分についても同様の結果が得られます。

メインループを 1 つ決めて、そこからの「寄り道」をいくつか作り、上の理論値を参考に頻度を割り振るという方法もありそうです。

 

例えば次のような方法が考えられます。

  • 汚れやすさがなるべく高いものを使ってメインループを作る
  • 全体を網羅するようにメインループから分岐する「寄り道」をいくつか作る
  • その際、なるべく寄り道部分のセルの汚れやすさに偏りが出るようにする
  • 上で計算した理論値をもとに、寄り道のタイミングを決定する

 

3 日目 - 12 月 3 日（日）

ビジュアライザを見るとコース取りがいまいちすぎる。同じマスを複数回ることが多く、同じところを行ったり来たりすることもある。

悪いところは分かるけど何をすればよいのか分からんぐぬぬーー。

 

無駄な往復をする理由を調べるために TSP 部分の挙動も調べられるようにしてみた。ついでに RGB 目利きにも限界があったので、そのへんも見れるようにした。

 

 

TSP で汚れやすいマスを結んでいるところ（Turn を動かすことで焼きなましの様子が分かる）

 



ビジュアライザはこの前の yukicoder score contest 8 で使われてた pygame を使ってやってました。

 

 

キーで進めたり戻したり、表示する内容（道筋・ TSP の焼きなまし状況・後述のグループ分けや部屋割りなど）を変えたり、マスに表示する数を変えたりする機能を付けた。

手元で実装するとそのままグラフ表示できるのでとても便利。

 

4 日目 - 12 月 4 日（月）

うーん、あまり進捗がない。

貪欲に頂点を追加していくという方法だとどうしても無駄な道ができてしまう。頂点集合を決めてから、そこを重複なく通る方法を考える方が効率が良さそうな気がしてきた。

Line Racing のときに使った二重頂点連結成分分解が使えるのか。

 

二重頂点連結成分分解による簡易判定と道順検索

判定

ある頂点からスタートしてある区画（頂点集合）が一筆書きできるかどうかの判定をしたいが、これは二重頂点連結成分分解を使うと概ね判定できるはず。稀に例外があるけど、ほぼ出くわさなかった気がする。二重頂点連結成分分解は頂点数に対して線形時間でできるので時間効率も悪くない。

 

  • 区画全体を二重頂点連結分解する
  • 各連結成分は木になる
  • 木が直線でなければ一筆書きはできない *1 
  • 直線であれば、各連結成分の要素をすべて選びながら順に進んでいくしかない
  • 各連結成分では入口と出口が一意に決まるので、連結成分ごとの判定に帰着できる（最後に到達する連結成分は出口に自由度がある可能性があるが、何パターンか試すことにする）
  • 各連結成分の判定は次のようにする 
    • 入口と出口を除く頂点集合について考える
    • 入口の隣接点のうち複数が葉（次数が 1 ）であれば失敗
    • 出口についても同様
    • 入口と出口の偶奇（市松模様にしたときの色）が異なる場合、残りの頂点集合は偶奇がちょうど半数に分かれる必要がある
    • 入口と出口の偶奇が一致する場合、残りの頂点集合の偶奇は、入口・出口の偶奇ではない方がちょうど 1 だけ大きい必要がある
    • ここまでではじかれなかったものは成功と判定する

 

これでだいたいの場合にうまくいく。稀に反例もあって、図のようなとき、緑から赤マスをすべてちょうど一回ずつ通って逆の緑に行くことはできないが、上の判定法だと可能と判定されてしまう。

 


道順検索

例外を無視して判定が正しいとすると、一マス進んでも条件が満たされるかどうかを判定しながら、 OK になる方向に進めば良い。

（この実装では、一マス進むごとにマス数に対して線形時間かかるので、全体ではマス数の 2 乗オーダーになる。）

 

5 日目 - 12 月 5 日（火）

 

昨日考えてたのもなんかいまいちな気がして、部屋割りをいろいろやってみる。

通常マス（「汚れやすいゾーン」に入ってない）場合の汚れやすさは 10 以下なので、 11 以上のものは必ずゾーンに入っていることが分かるが、逆は言えない *2 。

11 以上のマスだけを見て連結成分をいい感じに分解すれば汚れやすいゾーンをまとめることができそう。同じ連結成分でも汚れやすさの比率が 10 倍を超えている *3 ペアがあれば、複数のゾーンが重なっていることが分かる。ふたつ重なっているとして、どちらのグループに属するかを判定するのはちょっと厄介。

適当に分けてみたけどいろんなパターンがあってむずい。

 

あとこれきれいにゾーン分けできたとして、そこからどうすれば・・・（ゾーンごとの順序焼きなましか？）

 

Seed 4

 

 

6 日目 - 12 月 6 日（水）

 

ゾーン方式だと形がいびつになって回収のときに困りそうだったので、部屋割り（長方形っぽいバージョン）も試してみた（けどここからどうすれば・・・）

 

 

7 日目 - 12 月 7 日（木）

上で書いた部屋内を重複なく回るロジックを入れてみた。 Seed 4 の上部の黄緑部屋を回る様子（ちゃんと重複なく進めてそう）。

 

 

 

進むロジック：

以降としている区間が二重頂点連結かつ一筆書きできる場合は、その条件を崩さないように動く

二重頂点連結でなければ、各二重頂点連結成分に分解して、成分ごとに最適ムーブをする

具体的には、各成分を頂点とする木ができるので、スタートからゴールまで進む

 

例えば、二重頂点連結成分を頂点とする木が次の図のようになっている場合で、①から⑤に行きたい場合は、①→③→①→②→④→⑤→⑥→⑤→⑦のように進む。複数回入る成分があるが、各成分の最初の入口から最終出口までの最適路を作っておいて、横道にそれるときはその部分を置き換えれば無駄なく回ることができる。

例えば②では①からの入口（関節点）から⑤への出口に向かう最短路を作っておいて、④につながる関節点を通ったときに寄り道して行って帰って来る感じで。

 

（左：①→②→⑤と動く場合の②内の動き、右：①→②→④→②→⑤にする場合の②内の動き）

 

あとは部屋の順番を焼きなませばそれっぽくなる。

近傍は①部屋の追加、②部屋の削除（複数ある場合のみ）、③部屋の順番の入れ替え（2-opt）の 3 種類。下記の前提で最終コストが部屋の順番から直接計算できるのでこれを評価関数とする。

  • 部屋のマス数および汚れやすさの合計を前計算
  • 部屋の中は必ずマス数で通れる前提
  • 部屋内の順番の違いは無視

 

連結成分内で重複なく取り切るのが不可能な場合などは、単純に「今いるマスに隣接する訪問予定マスのうち、出口から最も遠いマス」に進むことにした。その結果非連結になる場合は今いるマスを訪問予定のまま残した。

 

 

 

実際に Submission してみると、二重連結判定と最適経路計算が重くて 14 ケース TLE 。。

Submission

 

速度改善方法はいろいろあるのでなんとでもなるんだけど、ここまで実装つらくて萎えてしまった。

 

スコア改善の余地もまだだいぶあるはず

  • 最初の方針では汚れやすさがひどいマスを中心に基本ループを作っていたが、この方針だと部屋内の汚れやすさの違いを考慮できていない
  • 広い部屋や、部屋内部での汚れやすさにムラがある場合に部屋を分割する方法が考えられる
  • 行き止まりの部屋（特に隣接部屋が 1 つだけの部屋）は必ずその前の部屋を二度通ることになるので、ふたつを合体したベースで最適化をするのが良い
  • もともとの仕切りが少ない盤面では、部屋が少なすぎる（ Seed 0 では 2 部屋になるのでこの場合も適宜分割する必要がある
  • 部屋間を繋ぐマスは適当に 1 つ固定したが、偶奇問題があるので少なくとも 2 つは試した方が良い

 

 

 

8 日目 - 12 月 8 日（金）

結局 2 日目（ 9 位のとき）の Submission に戻した方が（TLE でケースが減ってるのを考慮しても）良くなったので一旦こちらに戻しておいた。

 

 

結局その後もアイデア止まりで実装まで行けず、これが最終提出。

 

 

ぐぬぬー

最初の方針と二重頂点連結成分分解をうまく融合させたかったけど、結局独立になっちゃったし後者は TLE しちゃったしで方針ミス感が否めないところ。一週間あるからいろいろ試してみるかーと思ってたけど二重頂点連結成分分解は結構つらいというのを思い出した。 Line Racing のときは（常設でやってたので）制限時間がないので無限時間かけて良かったけど、一週間ぐらいだと自分の実装力だとリスクが大きい。

探索アルゴリズムを使わずに CodinGame の Line Racing をやって Legend になった話 - Kiri8128の日記

 

 

 

End

 

*1:Line Racing のときはどの子に行くのが最善かを木 DP の要領で計算した

*2:ちなみにゾーンに入っていない場合の汚れやすさの平均は約 3.9 で、ゾーンに入っている場合の平均は 84 程度

*3:厳密には、小さい方を a として大きい方が 10a+5 以上

焼きなまし法が使えなくても AHC 橙になれたよ

 

 

AHC レーティング橙になりました！

AtCoder のヒューリスティックレーティングが橙（2400+）になりました。

 

 

 

（参考：アルゴ橙記事）

kiri8128.hatenablog.com

 

AHC で橙になるまでにやったこと

  • AHC に出る

 

言語

基本 Python（PyPy）でやってました。 1 回だけ Rust で書き換えたことがあります（AHC 014）。

 

 

得意問題・苦手問題

 

同じレート帯の中では、基本的に高速化や探索ゲーは苦手で、評価関数や貪欲系が得意だと思っています。AHC と言えば焼きなまし法やビームサーチ等の最適化アルゴリズムを使う印象がある人が多いかもしれませんが、私は AHC でこれらをうまく使えたことはほとんどありません。逆に言えば、焼きなまし法が使えなくても橙ぐらいまでは十分狙えるということが示せたと思います。

 

【得意】

  • 評価関数ゲー
  • 貪欲ゲー
  • 戦略ゲー

 

【中間】

  • 盤面構築ゲー
  • 推定系

 

【苦手】

  • 焼きなまし
  • ビームサーチ

 

 

問題形式としてはインタラクティブのものに得意意識がありました。ただ入橙したときの AHC 026 が短期かつ非インタラクティブで大当たりを引いた影響が大きく、プロットしてみるとむしろ非インタラクティブ寄りにいるみたいです。

 

 

 

 

プロット方法について

なおプロットに用いた計算方式の概要は次のとおりです。

  • コンテスタント（参加者） c およびコンテストいくつかからなる集合 S について f_c(S) を、過去に S に含まれるコンテストのみに出ていたとした場合の  c の Rating とする
  • 長期コンテストの集合を S_{long} などする
  • x = f_c(S_{long}) - f_c(S_{short}) 、 y = f_c(S_{int}) - f_c(S_{non int}) をベースにして、次の 2 つの調整をした位置に c の ID をプロットする
    • レートが高いほど影響を強くする（一色で 1.08 倍）
    • プロットが一部分に集中しすぎないように単調増加な奇関数で調整
  • 文字の大きさはレート依存（1600 以上は一色で 1.5 倍、 1600 以下は 3 色で 1.5 倍）
  • ただし文字数による調整あり

 

使ったコンテストはこれまでの Rated コンテストです。カテゴリは下記のとおり設定しています *1 。

 

コンテスト 問題 長期 or 短期 回答形式
AHC001 AtCoder Ad 長期 非インタラクティブ
AHC002 Walking on Tiles 短期 非インタラクティブ
AHC003 Shortest Path Queries 長期 インタラクティブ
AHC004 Alien's Genome Assembly 短期 非インタラクティブ
AHC005 Patrolling 短期 非インタラクティブ
RECRUIT 日本橋ハーフマラソン 2021〜増刊号〜 農場王X 長期 非インタラクティブ
HACK TO THE FUTURE 2022 予選 Project Leader 長期 インタラクティブ
AHC006（京セラプログラミングコンテスト） Food Delivery 短期 非インタラクティブ
AHC007（THIRD プログラミングコンテスト 2021） Online MST 短期 インタラクティブ
AHC008 Territory 長期 インタラクティブ
AHC009（モノグサ プログラミングコンテスト2022） Robust Memory of Commuting Routes 短期 非インタラクティブ
AHC010（ALGO ARTIS プログラミングコンテスト2022） Loop Lines 短期 非インタラクティブ
AHC011 Sliding Tree Puzzle 長期 非インタラクティブ
AHC012 AtCoder 10th Anniversary 短期 非インタラクティブ
AHC013（RECRUIT 日本橋ハーフマラソン 2022夏） Server Room 長期 非インタラクティブ
AHC014（estie プログラミングコンテスト2022） RectJoin 長期 非インタラクティブ
AHC015（トヨタ自動車 プログラミングコンテスト2022） Halloween Candy 短期 インタラクティブ
AHC016（HACK TO THE FUTURE 2023 予選） Graphorean 長期 インタラクティブ
AHC017（THIRD プログラミングコンテスト 2022） Road Repair 長期 非インタラクティブ
AHC018（RECRUIT 日本橋ハーフマラソン 2023冬） Excavation 長期 インタラクティブ
AHC019（MC Digital プログラミングコンテスト2023） Silhouette Block Puzzle Creation 長期 非インタラクティブ
AHC020（ALGO ARTIS プログラミングコンテスト2023） Broadcasting 短期 非インタラクティブ
AHC021（TOYOTA Programming Contest 2023 Summer） Pyramid Sorting 短期 非インタラクティブ
AHC022（RECRUIT 日本橋ハーフマラソン 2023夏） Exploring Another Space 長期 インタラクティブ
TOYOTA Programming Contest 2023 Summer final Transit Warehouse 短期 インタラクティブ
AHC023（第10回 Asprova プログラミングコンテスト） Crops on Grid 長期 非インタラクティブ
AHC024（丸紅プログラミングコンテスト2023） Topological Map 短期 非インタラクティブ
AHC025 Balancing by Balance 長期 インタラクティブ
AHC026（トヨタ自動車プログラミングコンテスト2023#6） Stack of Boxes 短期 非インタラクティブ
AHC027（HACK TO THE FUTURE 2024） Recurring Cleaning Route 長期 非インタラクティブ
AHC029（RECRUIT 日本橋ハーフマラソン 2024冬） Business Simulation Game 長期 インタラクティブ
AHC028（ALGO ARTIS プログラミングコンテスト2023 冬） Lucky Words 短期 非インタラクティブ
AHC030（THIRD プログラミングコンテスト2023） Polyomino Mining 長期 インタラクティブ

 

成功回の傾向と戦略

これまでの参加で順位が良かった回（Rated 50 位以内）の戦略です。表を見ると、評価関数や貪欲で稼いでいることが分かります。

 

順位 コンテスト 問題 解法概要 解法リンク
【番外編】Unrated 2 位 新ジャッジテストコンテスト -Heuristic- AtCoder Contest Scheduling (Online Version) 謎の評価関数に基づく貪欲 リンク
4 位 AHC 026 （トヨタ自動車プログラミングコンテスト2023#6） Stack of Boxes 貪欲 リンク
13 位 AHC 018（RECRUIT 日本橋ハーフマラソン 2023冬） Excavation 評価関数と戦略 リンク
26 位 AHC 025 Balancing by Balance 戦略 リンク
27 位 AHC 021（TOYOTA Programming Contest 2023 Summer） Pyramid Sorting 評価関数に基づく貪欲 リンク
36 位 RECRUIT 日本橋ハーフマラソン 2021〜増刊号〜 農場王X 評価関数と戦略 リンク
38 位 AHC 008（MC Digital プログラミングコンテスト2022） Territory 盤面構築＋戦略 リンク

 

 

評価関数・貪欲の考え方

 

評価関数・貪欲ゲーのときに高順位になることがあり、評価関数をどうやって作っているかなど聞かれることがあります。

 

「天才貪欲」「天才評価関数」のような呼ばれ方をすることもありますが、天から降って来る訳ではなく、また何も考えずに作ったらたまたま当たるという訳でもなく、ある程度根拠のある（数値化できる）指標や簡素化した状況での理論値をもとにアレンジして作るというのが基本だと思っています。

以下で自分なりの考え方や普段考えていることを書きます。なお、今後のコンテストでも広く使えるようにしたいので、なるべく汎用的・抽象的な記載にしています *2 。

具体的な使用例があるものは後述します。

 

  • 問題を簡素化する
    • AHC の問題は厳密解が計算できないように適度に複雑になっていますが、なんらかの簡素化を行うことで状況をつかみやすくします
    • 簡素化というのは、問題の本質を失わない範囲で情報を捨てるなどにより簡単にすることです。例えば「取得・計算できうる情報のうち、『ある部分』について計算コストがとても大きいが、そこを無視しても結果に 10% 程度しか影響しない」などが分かれば、その部分を捨てることで、考察を簡単にしたり計算の実行時間の節約につなげたりすることことができます
    • なんでも切り捨てればよい訳ではなく、考察・計算のコストが高い割に最終結果にほとんど影響しない部分を捨てるのが大事です
  • 寄与の概算
    • いくつかの簡素化前提をおくことで、その前提の下での理論値を計算できたり、各種指標に対する寄与を直接計算できるようになったりことがあります
    • 仮に最終スコアに対する寄与が計算できれば、それが最大になるものを選ぶとそれっぽい貪欲になります
  • どうなると嬉しいかを理解する
    • 嬉しさを数値化をしておくと便利です
    • この嬉しさは、直接何らかの寄与になっていなくても、大小比較のための順序を決めるためだけの情報でも OK です
    • 複数の嬉しさを合算する場合は、係数を吟味する必要があります
    • 例えば A も B も大きい方が良いなら単純に A+B を指標にする手もあるかもしれませんが、 A が 1 増えることが B が 10 増えるぐらいの効果がありそうなら 10A+B を指標にするのが良いですね。
  • 評価関数の設定
    • 行動を決定するタイプの問題では、各行動に評価を定めることで評価関数ゲーに落とし込むことができます
    • 最終スコアに対する寄与でなくても、「嬉しさ」を基準とした評価関数でも OK です
    • 複数の指標がある場合もすべて評価関数に合計すれば良いですが、優先度の高いものの影響が大きくなるように調整します（嬉しさの項と同様）
    • 不確実性による評価の補正が有効な場合も多いです（すぐに実現できるものは確実性が高いが、将来実現できる予定のものは状況によって変わる可能性があるので適当に割り引くなど調整する）
    • ターゲットを定めることも有効です（1 ターンで○点ぐらいは欲しい、最適解だと△点ぐらい取っているはずだ、など）
  • ステップを分解する戦略
    • 特にターン制の問題では、まず序盤で○○という状況にする→その後△△を行う、という複数ステップでの攻略が有効になることがあります
    • 「○○なら△△が計算できるのに・・」「□□という状況ならあとは貪欲でできるのに・・」のような願望があるときに、現実的なコストをかけることで実現できるなら試してみるのもありかもしれません
  • 解法選択時の概算
    • 解法・アイデアが浮かんだとしても、結果的に外れ方針になることもあります
    • 実装に走る前にその方法でどれぐらいのスコア・順位が見込めるかを概算することで、外れ方針に突っ走ってしまうリスクを減らせます *3
    • あるいは逆に、上位陣のスコアや目標スコアをもとに、どれぐらいの改善が求められるのかを想定しながら解法を考えることが有効になることもあります
    • 例えば 1 ターンのコストを平均 10 に抑えたい場合、ターンごとに 8 のコストを掛ける処理は相当なベネフィットがないと使えないが、平均 0.5 程度のコストであればガンガン使って良さそう、など。コストとリターンの両方が数値化できるとなお良いです。
  • パラメータの設定
    • 上位陣では、手元でたくさん回すことでチューニングしているのを見かけますが、私はあまりやっていません（できていません）
    • 基本的に、パラメータは最初はなんらかの概算を行って最適そうなものを選びます
    • コンテスト終盤になったらいくつかのパターンを比較することも検討しますが、当初の予定と大きくずれることはあまりないです
    • 序盤でチューニングしすぎるとメタ局所最適に陥る可能性があります。
  • 平均と分散
    • たくさんの入力変数や乱数がある場合、個々の平均と分散（および独立でない場合は共分散）が分かればそれらの合計の分布の平均と分散が分かります
    • 変数の推定の際、平均と分散が分かれば十分なことも多いので、分布が複雑な場合などでもまずは平均・分散を調べるのは有効です
    • 理論値が計算できなくても、入力データを乱数から作成することで、平均・分散の予測をすることもできます
  • 入力の分布
    • AHC では、入力の制約だけでなく、入力の生成方法（確率分布）が与えられます *4 。
    • 回によっては「必ずしも理解しなくても良い」のような文言があることもありますが、これはワナです。必ず熟読して理解しましょう。
    • 各パラメータがどのような値を取り得るかを理解することで、その後の各種概算が可能になります。
    • 場合によっては、いろいろな指標の理論値（平均・分散など）が計算により求まることもあります。

 

イメージが付きづらいものもあるかもしれないので、次節でうまくいった例を挙げてみます。

 

うまくいった例

寄与と嬉しさ、ターゲット

寄与と嬉しさを考えてうまくいった例としては、（上でもでてきた）新ジャッジテストコンテスト Heuristic があります。こんな感じで考えてました。

「上振れ」は上述の「ターゲットを定める」に近い考え方です。

 

 

 

複数ターンで達成できる効果

複数ターン等を使ってある状況を得るような場合は、 1 ターンあたりなどのコストに置き換えると公平に評価できます。例えば 農場王X では、連結を保っているマスの集合から k マス離れたところに評価が s であるマスがあれば、 \displaystyle\frac{s}{k} などと評価できます。ただしあまり遠い場合は不確実性が増える（そこまで行くまでに他の有力候補が出てくるなど）ので、適宜割り引く方法もあります。もし厳密解を求めたいなら他のすべての選択肢を考慮して今やろうとしている方法に勝つのがあるかを計算する必要がありますが、それだと計算量が爆発しますよね。ヒューリスティックではあまりに複雑なところは確率処理することで簡素化できます。

 

 

解法の概算

解法の概算が役に立った例としては、 AHC 026 があります。本問の戦略としては、

  1. 各列をソートする
  2. 列ごとに近い数を集める（例えば 0～19 は左端の列に置くなど）

などが考えられます。 1. では、ひとつずつ出す・戻すをすると一回のコストは 2 なので、列ごとに 40 、合計 800 のコストがかかりスコア 9200 点ぐらいが狙えそうです。複数同時移動も許すと、確率 \displaystyle\frac{1}{2} でくっ付けられると考えると一回のコストは 1.5 程度に抑えられるので、特に工夫しなくてもスコア 9400 は出せそうと予測することができます。

一方、 2. の方法では、例えば

  • 一旦すべて右端の列に集める（コスト 21\times 9=189 ）
  • 上から見て列 1～9 に分解する（コスト約 2 \times 200=400 ）
  • 小さいやつの列から見て順に回収する（コスト 2\times 200=400 弱ぐらい）

という方法がありますが、これだとスコア 9100 も達成が難しそうです。

 

実はコンテストの序盤（30 分～ 1 時間ぐらい？）で、一瞬 2. の方法を検討していたんですが、順位表を見たら既に 9300 程度の人がいたのですぐに棄却して再考したところ 1. を思い付くことができました。

 

 

 

 

影響による優先度付け

概算ではなく実験によって効果が小さそうだったから無視した例もあります。下記は ハーフマラソン2021 のコメントです。

 

 

 

ステップに分解する戦略

「ステップ分解」は AHC 026 （ソートしてから出す）、 AHC 025 （グループソートしてからチャレンジする）、 AHC 008 （まず犬トラップをして、その後は壁を配置してから仕留めに行く）などで使えました

 

簡素化前提による理論値計算

AHC 018 解法 の最後のところで一段階の攻撃力を \sqrt{\displaystyle\frac{2hC}{k}} にするところなどでは、問題を簡単にして相加平均・相乗平均の関係から（簡素化前提での）理論値を求めて使いました。

 

 

 

その他工夫など

その他、 AHC コンテスト中に考えていることや工夫などを列挙しています。

 

  • 盤面の設定
    • テストケースによらず強い盤面が存在するときは、事前に盤面を決めて固定する（AHC 008 など）
  • 拡張性の高いコード
    • 最初のアイデアだけでなく、将来的に使うであろうアイデアを考えて拡張しやすい設計にしておく
    • 最初は使わない機能でも枠だけ作っておいて自明設定にしておく（あとで必要があれば書き換える）など
    • 終盤に局所的に良いアイデアを思いついたとき、設計が窮屈だと実装が大変すぎて断念してしまうことになるともったいない
  • 戦略の工夫
    • 自由度と扱いやすさのトレードオフ
      • AHC 018 では、ルートを必ず 10 マス刻みの格子を通るという制約を付けることで、自由度を犠牲にしながら実装・考察を簡素化する選択をした
    • コンピュータに任せる探索と簡素化前提に基づく理論値計算の最適化の併用

      • AHC 016 では、ある前提に基づく理論値を計算することで計算量を改善した。ただし 記事 にも書いたように結果的にはうまくいかなかった点もある

  • 実行速度と実装速度のトレードオフ
    • まずは動くことが大事なので、実行速度は遅くても実装しきるのが大事
    • ただし後から部分的に改善できるように、どの部分でサボっているかを理解しておくのと、後から修正しやすい設計にしておくとよい
  • デバッグの工夫
    • 提出コード、手元実行コード（1 ケースのみ）、手元実行コード（複数ケースで得点確認）、コードテスト、などを同じコードで実行できるようにしておく
    • 手元実行コード（1 ケースのみ）では、デバッグ用の出力を無限に吐き出して、意図通り動いているかをチェックする
    • 実行時間が大事な場合は、実行時間を処理ごとに計測して何がボトルネックになっているか検証できるようにする
  • 設計と実装の役割分担
    • 特に長期だと設計をちゃんと作らず実装を始めると混乱してやっぱりやめるみたいなことになりがち
    • 設計を作る人と実装を作る人を分けるとお互いに自分の役割に専念できて良い
    • ただし AHC では複数人参加が認められていないので、長期コンなら例えば「昼の自分が設計書を書いて夜の自分に実装を依頼する」→「夜の自分は依頼を見て、期日（翌朝）までに納品する」みたいにやるとよい
  • 手元の実行速度とジャッジの実行速度の差
    • 手元では PyPy 環境を構築していないので、ジャッジに比べて 5～10 倍ぐらいの時間がかかることが多い
    • コードテストでループ数を計測して、何倍の時間回せば同じ条件になるか調べておく
  • 得点・改善量の見積もり
    • 実装しようとしている解法で何点取れるのかを事前に見積もる
    • 局所的な改善では、改善量があまりに小さいと実装時間をかけたくないことがある
    • 改善量をある程度見積って効率（≒予測改善量÷実装時間）の良いものを優先する

 

 

 

  • ビジュアライザの活用
    • ある程度のものが作れたら、そこからの改善はアイデアや微調整が多くなる
    • そうなるとビジュアライザが有効。具体的には次のような感じ。
      • ビジュアライザをステップごとに実行して、「このターンではこっちの方が良いのでは？」というのを見つける
      • 単にビジュアライザの動きを見ているだけではなぜそう判断したのか分からないので、適宜コメントや手元実行のデバッグコメントを見てなぜそう行動したかを確認する
      • ロジックに改善点できるがあれば、それを抽象化して設計に落とし込み実装する
      • 修正前に比べて良くなったか検証する
    • ビジュアライザは自動実行ではなく、 1 ステップごとに見るのが良い（必ずしも全ステップ見る必要はなく、大きな動きをするところだけでも良いかも）
  • 入力パラメータによる場合分け
    • 特に長期コンでは、入力パラメータごとに最適な戦略が異なる場合が多い
    • 極端な例でのスコアを確認したり、ビジュアライザを回してみたりしてどういうケースで弱いのかを把握する

 

 

FAQ

Q: 焼きなましを使わないのはなんで？

A: 敢えて使ってないんじゃなくて、使おうとしたこともあるけど結果的に順位に反映されていない感じです。例えば AHC 024 も焼きなましを実装する予定だったけど本番中間に合わなかった感じ。

 

 

 

Q: ヒューリスティックでも Python しか使わないのなんで？

A: まだ環境構築などの準備と言語の習得が整っていないので使えていないです。幸い、私が得意な貪欲ゲーや評価関数ゲーのときは Python の実行速度面の弱点があまり効かないので、結果的にそこまで不利になっていない感じです。

焼きなまし法などを本格的に使うようになると高速化が本質になってくるので、そうすると Rust などの速い言語を使うのも有効だと思っています。

 

Q: 並列処理の環境構築するって言ってなかった？

A: まだできてませんごめんなさい。

 

Q: アクチュアリーをやってるって聞いたけど、業務でプログラミングしてる？

A: 今のところ、業務でプログラミングをすることはないです。

 

Q: アクチュアリー業務をしていて AHC に有利になることはある？

A: アクチュアリー業務で扱う決算数値や経営成績などの指標は、市場環境や顧客行動などさまざまな要因に影響されます。それを分析や経営判断に生かすため、（専門家ではない）経営陣等にも因果を含めて説明する必要があります。このため、どの事象がどの指標に影響しているかなどのメカニズムを理解し、簡易的に分かりやすくモデル化して説明するという必要性が多くあります。このように問題の本質を崩さない範囲でシンプルに体系化するという作業は、 AHC の評価関数を作る場面などでまさに必要とされることだと思っています。

 

Q: 新ジャッジコン（ヒュ）の 1.8 乗解法が意味不明なんだけど・・？「(d - last_i) を 2 乗したい」とか「それはやりすぎなので 1.8 乗」について詳しく教えて

A: [tex:(d - last_i)] はこれまでコンテスト i が開催されなかった期間です。コンテストの種類によってコストの係数 c_i が異なるので開催頻度は変わりそうですが、対称性からだいたいこれまでに経過した期間と同じぐらいの期間後に開催されると想定するのが自然ですよね。そこで c_i * (d - last_i)^{2} を使うのが一案になり、これでも十分強いです。

ただこれだと c_i * (d - last_i)^{2} が一致しているものは同等に扱うことになります。実際はこれらの中では c_i が少ない方（ (d - last_i)^2 が大きい方）は回収までの日数の期待値が長く上振れを引きやすいことから、将来の大上振れに期待するのが（ c_i が大きい方に比べると）良いことになります。この影響を含めると最適な指数は 2 乗より少し小さくなるはずですね。 1 乗や 1.5 乗にするほど大きな影響とは思えないので、 1.8 乗ぐらいに最適解がありそうと分かります。

 

Q: ほかに質問があったらどうしたら良い？

A: リプ等で教えてもらえればなるべく回答します。

 

 

 

 

 

 

*1:記事執筆以降も追加しています

*2:普段から考えている人にとっては当たり前と思うかもしれませんし、逆に慣れていない人にとってはイメージが付きづらいかもしれません。

*3:特に短期コンだと方針の修正が難しいので、早い段階で概算できるのが望ましいかもしれません

*4:保証されているかどうかは確認できていないですが、少なくともこれまではすべて与えられていたはずですし、競技性を考えると今後も与えられるべきだと思います