2024-01-14

ALGO ARTIS プログラミングコンテスト2023 冬（AtCoder Heuristic Contest 028）参加記【最終71位】

こんにちは、notkamonohasiと申します。

ALGO ARTIS プログラミングコンテスト2023冬（AHC028）に参加しました。スコア1.077Mで最終順位71位でした。

コンテスト中の流れをぼんやり書きたいと思います。

atcoder.jp

解法概要
前提知識
コンテスト中の流れ
反省
最後に

解法概要

焼きなましで単語の順番を決める。焼きなましの遷移は「文字aで始まって文字bで終わる2つの部分文字列をswap」
キーの順番は毎回DPで最適解を計算

前提知識

DP（1000Diff程度）

コンテスト中の流れ

0:00[0.000M] ～問題を見た直後の考察～

頻出の「最適化したい対象が2種類ある」問題。前回のAA社コンもそうで、この時は選択を間違えていたので、どちらを重視するかよく考えたい。

0:36[0.950M] ～DPでキーの順番の最適化～

単語の順番を決めた時の、キーの順番の最適解はDPで出せる。単語の順番は入力と同じ順番にして、とりあえずDPだけを実装する*1。短期コンだと後で書き直すことはできないので、関数・クラスは最初から真面目に実装します。

提出すると0.950Mで15位、同じ点数の人が他に3人いて安心。

1:00[1.032M] ～しりとりで総文字数を減らす～

次は単語の順番を決める。総文字数は少ない方が有利なので、しりとりになるようにします。欲しい最初の文字を持つ単語がないときは、適当に選ぶ（←後で真面目に考える必要あり！）

提出すると1.032Mで21位

1:20[1.068M] ～山登りで単語の順番を改善～

現時点での計算時間が4msなので山登りで解を改善します。「単語の順番」と「キーの順番」の2つのどちらをメインにするか考えるが、「キーの順番」は最適解を出せるので「単語の順番」をメインに決定。

山登りの遷移のみが唯一自分の解法の非自明な箇所、遷移は「文字aで始まって文字bで終わる2つの部分文字列をswap」としました。思いついた経緯は以下の2つ

シンプルに「適当な2つの単語をswapする」だけだと、総文字数が増えてしまうので、遷移が受理される確率が低くなる。iterが十分回るならそれで良いが、DPが重いため回数を稼げない
この遷移だと、遷移に関係ない単語への影響が小さいので、遷移が受理される確率が十分高そう

（蛇足）少し考えると、単語の順番を変えるとキーの順番が大きく変わってしまうので、良くないのでは？となる。しかし、AtCoder11周年記念コンテスト（AA社とTHIRD社とFuture社の対抗戦）で似たような話があって、「文脈がある問題でも、良い解の形は保存される」（？）という議論になっていたので、「まあ良いでしょ」の気持ちで実装を始めた。

提出すると1.068M

1:51[1.070M] ～DPを高速化～

山登りのiterが5000回程度しか回っておらず、計算時間を増やして実行すると多少スコアが上がったので、遷移のボトルネックになっているDPを高速化します。

今のDPテーブルは、文字列をSとして

$DP[何文字目か:len(S)] [最後の文字の場所:N^2]$

としています。しかし、各文字が存在する場所は決まっているので、ほとんどの箇所は到達不可能となっており無駄が多いです。各文字について、存在する場所に番号を与えると、DPテーブルを約 $\frac{1}{26}$ に圧縮することができて、計算量を減らすことができます。今回はiter回数が2倍になりました*2。

圧縮と復元の実装でバグらせて、30分かかったのは反省。

提出すると1.070M、思ったより伸びず

2:12[1.075M] ～焼きなまし～

山登りを適当に焼きなましに変えます。iter回数が少ないので期待していなかったのですが、思ったより上がりました。

提出すると1.075M

4:00[1.077M] ～無～

遷移を増やしたり、初期解を複数生成したりしたが、大きなスコアアップには繋がらず。悪あがきで乱数シードガチャをしていました。。。

反省

chokudaiさんやhenoさん、公式解説がおっしゃっていた $f(A)+f(B)-f(A+B)$ をスコアとする方法が、自分の初期解に対する違和感を綺麗に定式化していて、なるほど～となりました。

適当に考えた初期解の生成方法を改善せず、安易に「山登り・焼きなましを改善すればスコアを上げられるはずだ！」と思ってしまったのが今回の敗因でした。

最後に

AtCoderの皆様、writerのterryさん、スポンサーのALGO ARTISさん、コンテストを開催してくださり、ありがとうございました！

*1:シンプルな解法だと同じ点数の人が出るので、提出デバッグができて便利

*2:元から到達不可能な場所はDPの遷移を無視する実装にしていたので、思ったより計算時間を削れませんでした

2023-12-11

HACK TO THE FUTURE 2024 （AtCoder Heuristic Contest 027）参加記

はじめまして、notkamonohasiと申します。

HTTF2024（AHC027）に参加しました。プレテス45.6Gで最終順位41位でした。

コンテスト中に考えたことや、その考えに至った経緯をぼんやり書きたいと思います。

atcoder.jp

解法概要
前提知識
解法詳細
- 初期解
  - 次どこに行くか
  - どの道を通るか
- 山登り
コンテスト中に考えたこと
感想
最後に
おまけ

解法概要

貪欲＋ダイクストラ法で初期解を生成。評価関数の設計を頑張る
長さが3～6のパスを破壊・再構築。差分更新を頑張る

前提知識

ダイクストラ法
山登り・焼きなまし

解法詳細

厳密性はなく、お気持ちが多めとなっています。

初期解

初期解構築パートは以下の2つに分かれています。

次どこに行くか
どの道を通るか

この2つを全てのセルが訪問済みとなるまで繰り返します。計算時間は0.3秒前後でした。

次どこに行くか

以下の三要素がバランスされているセルを目標とするのがベストだと考えました。

汚れがたまっているセルに行ってほしい
未訪問のセルに行ってほしい
今いる場所から遠すぎない場所に行ってほしい

色々調整した結果、評価関数は以下のようにすると貪欲だけで良い感じになりました。

${f_{target}(x,y)=\frac{Sv}{\sqrt{d}}}$

$S：セル(x,y)の現在の汚れ$

$v=\left\{ \begin{array}{ll} 10\quad (未訪問) \\ 1\quad (訪問済) \end{array} \right.$

$d：現在位置からセル(x,y)への距離$

特に $\sqrt{d}$ がスコアに効き、目標地点が近すぎず遠すぎないセルになってくれました。

どの道を通るか

考えたいのは以下の三要素です。

汚れがたまっているセルを通ってほしい
未訪問のセルに通ってほしい
遠回りしすぎないでほしい

前節のお気持ちとは3のみ異なっています。具体的な評価関数は以下で、この評価関数をダイクストラ法の辺の重みとします。

$f_{route}(x,y)=(D-S)*v$

$D：汚れ増加の総和\sum d_{i, j}$

$S：セル(x,y)の現在の汚れ$

$v=\left\{ \begin{array}{ll} 2\quad (未訪問) \\ 1\quad (訪問済) \end{array} \right.$

注意点として $f_{route}$ は負の値を取り得ます。ダイクストラ法は辺の重みが非負である必要があるので、厳密解を出すことはできません。しかし、厳密解を出すのは計算時間的に厳しいですし、大体良い感じであれば良いのでこれで妥協します。

山登り

初期解は細部が非常に適当なので、改善の余地があります。残った計算時間を使って山登りで解を更新します。

山登りの遷移の流れは以下です。

長さ3～6のパスを削除
削除したスタート地点とゴール地点を繋ぐパスのうち、規定長さ以下を全探索
一番スコアが良かったパスを採用・状態を更新

愚直に実装するとスコアの計算には $O(L)$ 必要なので、遷移回数を稼ぐために差分計算で高速化します。

総経路長が変わらないときの差分計算は簡単な一方、総経路長が変わった時の正確な差分計算は分かりませんでした。そのため、総経路長が変わった時は以下の様にスコアを推定しました。

$f_{score}=totalScore+\alpha\times \bar{S} \times \Delta t$

$\alpha：不確実さを考慮した係数$

$\bar{S}：平均汚れ$

$\Delta t：総経路長の符号付増減$

要は「総経路長が増えると罰則を与え、減ると報酬を与える」をしています。

不正確なスコアなので、更新時に正しいスコアを計算して、元のスコアを下回った場合更新しないことにしています。

1回の遷移にかかる計算時間は長く、seed=0でも遷移は20000回程度しか回っていません。特に $N$ が大きいケースでは試行回数が足りず、計算時間を短くできれば更にスコアを上げられる状態です。

コンテスト中に考えたこと

今回のコンテストでは、初期解の構築に結構リソースを割きました。理由は以下の2つです。

スコアを維持したまま解の形を大きく変化させるのが不可能に見えた。そのため、山登りパートを頑張っても、初期解が悪いと良いスコアにならないと思った。
開始4時間でitigoさんが出したスコアが中盤まで2ページ目に残っていた。このことから、難しいことをしなくても最終38Gを出せる解法が存在することに確信を持てた。

短期コンはともかく、長期コンでは最近の傾向・難易度を考えると、中盤までは貪欲をじっくり考える（＝問題固有の性質に向き合う）のが良い進め方だと思っています。

感想

問題設定の簡単さに対して、初期解を頑張る必要がある点と、計算時間が全く足りない点が特に難しかった。

ビジュアライザーの機能が充実していて、ビジュアライザーを眺めながら局所的な改善ポイントを見出せたのが良かった。

最後に

AtCoderの皆様、そしてtsukammoさんをはじめとするフューチャー社の皆様、コンテストを開催してくださり、ありがとうございました！

次回HACK TO THE FUTUREも楽しみにしています！

おまけ

就活＆研究ヤバい

2023-08-22

RECRUIT 日本橋ハーフマラソン 2023夏（AtCoder Heuristic Contest 022）解説

はじめまして、notkamonohasiと申します。

AHC022お疲れさまでした。システス後46位でした。

Twitterを見る限りでは、自分の解法がかなりレアだったため、人生で初めてブログを書いてみようと思った次第です。

軽実装かつ難解な統計知識なしで高順位を取れるというのが自分の解法のメリットです。

紹介した手法の強さを計測するために、各手法毎にPythonの実装例と延長戦順位表を掲載しています。

解法概要
前提知識
解法詳細
自分の解法の評価
更に点数を上げるには？
最後に
おまけ

解法概要

1点だけ温度を超高温とし、他の点を0とします。各ワームホールについて、出口セルからどの位置に超高温セルがあるかを特定することで、どの出口セルにつながっているかを特定することができます。

結果としてはσ=900, N=75程度までの難易度ならノーミスを実現できます。

前提知識

正規分布が何か分かっていれば十分だと思います。

数式ないです。アルゴリズム使いません。

解法詳細

1. そのセルが0か超高温かの判定方法

一点高温解法の肝であり、判定精度が悪いと何もできないので、ここを詰めるのは非常に重要です。

あるセルの温度を適当な回数測定したときに、そのセルが0度なのか超高温（以下分かりにくいので1000度と言ってしまいます）なのかを知りたいです。

直感的には測定結果の平均値が閾値を超えていればokだと思います。しかし、この閾値が小さすぎると上振れ・下振れに弱くなってしまいますし、逆に大きすぎると同じ場所を無駄に何度も測定する必要が出てきてしまいます。また、この閾値はσによって変える必要があり、各σについて適切な閾値を求めるのは面倒です。

そこで自分は1回の測定に対する評価値xに対する評価値を「実際の温度が1000度の時に測定値がx度になる確率」÷「実際の温度が0度の時に測定値がx度になる確率」としました。この評価値は数学的には「測定値がx度の時に、そのセルの実際の温度が1000度である確率は0度である確率の何倍か」ということを意味しています。例えば、この評価値が1万倍であれば1000度で一発で確定だし、10倍程度であれば「不安だからもう一度計測しておこう」という気持ちになります。

この評価を各ワームホールについて、全ての出口に対して行っていけば、各ワームホールに対応する出口を見つけることができます。しかし、「全ての出口に対して3回ずつ計測する」などの方法は非常に無駄が多いです。計測しているうちに、明らかに温度が高い点・低い点が見つかるからです。そこで、Dijkstra法の様に「今最も評価値が高いセル」を見ていき、この評価値が閾値を超えたら終わりにすれば良いです。

一点高温解法で点数が出なかったとおっしゃっていた方達との差は恐らく、上記2つの評価値の計算方法と、計測の順番だと思います。

評価値の実装方法については、Pythonであればscipyを使うことで楽に実装できます。C++には多分ないので、累積和を使って確率累積分布を前計算して、高速に計算できるようにしておきます。

ここまでのアイデアを実装すると、最終68位相当の点数が取れました。実装量は大量のコメントアウトを含めて200行弱です。この実装量で長期コンテストの68位を取れるのはヤバいですね...

atcoder.jp

2. 計測コストを下げる工夫①

更に順位を上げるためには設置コストか計測コストを減らすことが必要です。ここでは、計測コストを下げることを考えます。

1.の段階だと、出力は下図のようになっています。

見て分かる通り、出口から離れた場所を何度も計測してしまっています。計測コストは出口から離れるごとに大きくなるので、なるべく出口から近い場所を探索したいです。

評価値が同じ場合は、1.の段階ではindexが小さい順に計測していますが、出口から近い順に測定すれば良いです。このアイデアを実装すると出力は下図のようになります。

測定コストを小さくできました！

提出すると最終58位相当の点数が取れました。実装量は200行です。

atcoder.jp

3. 計測コストを下げる工夫②

（かなり細かいので、初心者の方は見なくて良いです！）

2.ができていれば十分ですが、実はまだ計測コストを下げることができます。

σが大きい場合、測定結果が下振れてしまうことにより、1周目の測定で正しい出口を見つけられないことが少なくないです。その場合は、1週目の測定で比較的マシだった出口を順にみていくことになりますが、出力は下図のようになります。

(5, 9, -10)までが1周目の測定で(5, 1, -2)以降が2周目の測定です。2周目で出口から離れたセルを何度も計測しているため、計測コストが跳ね上がっていることが分かります。1周目で正解を見つけられなかった場合でも、計測コストを小さくしたい気持ちになります。

これを実現させるためには「入口を固定して出口を見つける」のではなく、「出口を固定して入口を見つける」という発想の逆転が必要です。例えば、1000度のセルから(-2, -2)の位置にある出口に対応する入口を見つけたい場合は、(0, 2, 2)→(1, 2, 2)→(2, 2, 2)→...を出力することになります。具体例から分かる通り、何度計測しても計測コストは変わらないので計測コストが増加するのを防ぐことができます。

入口を特定する出口の順番は、2.と同じように計測コストが小さい順とします。

上記のアイデアを実装して最終51位相当の点数が取れました。実装量は相変わらずです。

atcoder.jp