マラソン勉強するぞ！~過去問演習編1~
はじめに
こんにちは、tardigradeです。本ブログでは主に競技プログラミングのマラソンコンテスト(ヒューリスティックコンテスト)についての記事を書いていく予定です。そんなに固い記事を書くつもりはないので、のんびり気楽に読んでいただければ幸いです。
前回の記事の続き
前回の記事↓の続きとして過去問演習をやります。
あんまり重たいコンテストをやってる時間もないので、Chokudai Contest 004をセレクトしました(005は出場していたので)。
chokudaiコン004を解く！
思ったこと、考えたことを記事に残しながら解こうと思っているのでバチャはしません。勉強したことを生かせるようにじっくり解いていこうかと思います。
問題把握
点数を計算する式があって、その点数がなるべく大きくなるように盤面を構築しろ、って問題ですね。第1感、貪欲より先はあんまり見えないです。
入力の受け取り・答えの出力・スコア計算
とりあえず入力の受け取りと答えの出力、点数計算をする関数を作成します。ビームサーチにしろ山登りにしろ、点数計算をする関数が無いと話にならないので、早いうちから作っておいて損はない気がします。今回の場合は、入出力検証プログラムがダウンロードできるようになっていたので、ダウンロードして必要な部分をコピペしました。
今週開催されるAHCもそうですが、マラソンコンテストは割と長期にわたって開催されますし、コードも長くなりがちです。変数や関数の名前はわかりやすくしておくのがおすすめです。自分はこんな↓感じにしてます。
貪欲法を実装してみる
下準備は終わったので本格的に解法を考えてみます。いきなり山登りとか書くのは怖すぎるので、まずは無難に貪欲を実装しに行くことにします。
貪欲と一口に言っても、「何をもって最善とするか」ということは自分で決めなくてはなりません。考察ノートみたいになってしまいますが、考えたことを逐次ここにまとめていきます。
安直なのは角から値を入れてくことでしょうか。あるマスに対して縦横両方を同時に考えるのは、一発目の実装としては重すぎる(主観)ので、横だけ見て貪欲に値を入れたいです。いろいろ考えてみて、下のような「貪欲ルール」を作りました。
- 縦無視
- そのマスに入れたときに、一番ポイントが増加するような値を選ぶ
- 何を入れても点数が増えない場合は、一番小さい値を入れる
実験的な意味が強いので、あんまり深くは考えていません。早く提出したい一心です(*‘ω‘ *)
はい、書き終えたので提出します。1092316点です。
順位表を見ると174位ですね。まずまずという感じです。
手軽に改善できるところはないか
次は最適解を探索するようなアルゴリズムを書きたいところですが、その前に貪欲でもう少し粘れないか考えてみます。というか、山登りのイメージがまだ思い浮かばないので粘らせてください( ;∀;)
ぱっと見直して気になるのは貪欲ルールの3つ目、一番小さい値を入れるのがいいのか否か、という話です。ここを最大値にして手元で回してみます。
はい、場合によっては良くなる(そりゃそう)ということがわかったので、min,maxにパターンやって大きい方を出力するようにプログラムを書き換え、再提出。1099571点で順位は2つ上がって172位です。
山登りを考える
さてさて、詰めれば貪欲でももう少し上がる気はしますが、そろそろ山登りもしたいので、山登りの方を考えます。先ほどのmin,maxで分かったことですが、やはり点数が増加しないときの値の入れ方で、最終的なだいぶ点数が変化します。ここをどうにかしていい値を選べるようにできないか考えます。
しばらく考えてみて、ある直感を得たので話します。僕は最初、貪欲で得られた盤面のうち、何カ所かのマス目の値を乱択で変化させて点数が伸びればそれを採用、みたいなことを繰り返すイメージをしていたのですが、それだとうまくいかない気がしました。もともとの盤面は、貪欲ルール3でminかmaxを入れ続けて、それに適するように構築されたものなので、そのルールから逸脱した値を入れた際に点数が増加するというのはイメージしづらいからです。この直感が正しいならば、マス目の値を乱択で変化させる場合は、それに応じて盤面も作り変えたほうが良いという話になります。
この理論が正しいかどうかはわかりませんが、このコンテストは幸い練習用なので、気になったことは試してみたいです。
乱択を考える
貪欲と掛け合わせて、次のような乱択×貪欲ルールを作成しました。
- 縦無視
- そのマスに入れたときに、一番ポイントが増加するような値を選ぶ
- 何を入れても点数が増えない場合は、範囲内で乱択
これの優れている点(主観)は、山登りや焼き鈍しへの発展が見えやすいという点にあります。先ほどは、統一ルールで縛っていたせいで、最初からある程度局地解に落ち着いているような感覚がありました。しかし、今回は乱択にしたので、ある程度道が開けている気がします。気分的には一つ階段を昇れたようで満足です。とりあえず、実装してみます。
書けました。本当はこれを何度も回すべきだとは思うんですが、乱択なんて初めて書いたので、テンションぶち上げワクワクが止まりません(＊≧▽≦)bb
提出してしまいました。1089985点でした。サンプルでの勝率は高かったですが、やはり乱択は渋いということですね(;・∀・)
とりあえずひたすら回してみる
↓こういう感じで時間いっぱい回してみます。
提出しました。なんと1166331点！！！148位までジャンプアップです！！！
本格的な焼き鈍しが書きたい
今はただ乱択しているだけなので、これをもっとちゃんとした感じに書き直せないか考えたいところ。スコアの低いうちは改変や乱択をたくさんして、上がってきたらそれらを少しずつ減らすというのが典型だったと思います。しかし、ここで、この評価関数はお山型になるのかということについて考えてみたいです。言い換えると、近傍により良い値があるのかということです。なんかこう、スパイクノイズみたいなのがピッ、ピッ、っと独立している感じだと、最適値が求まりにくそうなので、その辺何も考えずに書くのは怖いなぁと…(この感覚が間違ってたらただの時間の無駄なんですが)。
逆から考えてみます。最適解から値を少し変えたとき、どれだけ点数が落ちえるのかということです。あるマスが重複しえる、総和がB1になる区間というのは、縦横それぞれ2つずつで計4つ、B2,B3についても同様に言えるので、最大で減少するのは350点くらいだと概算できます。マラソンのケースは意地悪をしてこないので、実際は高々100くらいだと思っていいでしょう。そして最適解から近い場所では、急激に点数が変化し、最適解から遠い場所では緩やかに変化しそうということもわかります。よって、評価関数の形をざっくり考えると、
↑こんな感じの鋭利な山が乱立している形になりそうです。以後、これが正しいと仮定をして考察を進めていきます(間違っていたら笑ってください)。
スパイクノイズみたいなほぼ棒のような形にならないということは、普通に焼き鈍しができそうです。なんとなくの設計ですが、状態プールを持っておいて、はじめのうちは乱択でたくさん改変を行いながら、点数のいいものを上からk番目まで状態プールに保存。時間がしばらくたったら、状態プールの中のものを部分的に変化させて近傍に最適解がないか探索していくのが良さげに感じます。今書いたのはビームサーチに近いですが、はじめのうちはchokudaiサーチを実装した方がいいかもしれませんね。ビームサーチは多様性の保持が難しいので、焼き鈍しに必要な「どれだけ改悪や新しい遷移を許すか」という関数がしっかりするまでは、いい点数を出すのが難しそうです。
一旦温めさせてください
現在時刻が朝4時を回っております…。マラソンの沼を現在進行形で実感していますが、そろそろ寝ないとまずいので、一旦温めさせてください<(_ _)>もう記事もだいぶ長くなっているので、続きは次回に回します。
夜遅くに考察を入れながら書いていた記事ですので、読みにくかったところも多々あるかと思いますが、最後まで読んでいただきありがとうございます。
