マラソン勉強するぞ！~過去問演習編3~
はじめに
こんにちは、tardigradeです。本ブログでは主に競技プログラミングのマラソンコンテスト(ヒューリスティックコンテスト)についての記事を書いていく予定です。そんなに固い記事を書くつもりはないので、のんびり気楽に読んでいただければ幸いです。
chokudaiコン003を解く！
AHC001も終わって、次のコンテストまでまだ時間がありそうなので、のんびり過去問演習したいと思います。今回は「Chokudai Contest 003」です。
問題把握
- N×Nの正方形ブロックが与えられる
- ブロックは「○」「×」「.」の三種類
- しばらくすると「.」が消されて上にあるブロックが自由落下する
- 「.」は、消滅しない「+」か消滅せず自由落下もしない「-」に置き換えられる
- ブロック消滅後の、残ったブロックについて、連結成分の大きさの最大値を足す
最初に考えたこと
- スコアを計算する関数書くの大変そう
- 連結はUnionFindで管理するのかな？
- 与えられた入力をそのまま出力するのが一番簡単に正の点数を得られる
- 「.」が多くなるように入力が作られるので基本的にはたくさん消したほうがよさそう
1回目のAC
入力を受け取って、それをそのまま出力。スコア関数の計算はとりあえず放置。
1759点。このコンテストはあまり高いスコアがでなさそうですね。
スコアを計算する
貪欲があまり見えないので乱択をしたくなったのですが、その前にまずスコアを計算する関数を書かなければなりません。関数の設計をしてみます(C++で書くことを想定しています)。
- 出力形式に合わせたvector<string>を引数に参照渡し
- 最初に「.」を消す
- 必要なブロックを下に落とす
- 残ったブロックについて、順番にBFSをして連結しているグループを作り、それをUnionFindで管理
- 各UnionFindでもっともグループ内の要素数が多いものを足し合わせ、それをreturn
2,3,4辺りでバグを生むのが非常に怖いです。どのように実装するかもう少しじっくり考えてみます。
最初に「.」を消す
「.」が消えるということは、もともと正方形だったブロックが歪な形に変わるということです。
この歪な形をした図形をそのまま配列で管理しようとすると結構大変そうです。そこで、ブロックが何もない空間を何らかの文字で表すことを考えてみます。こうすることで、配列や文字列の長さを変えることなくブロック消滅後の図形を管理できます。
必要なブロックを下に落とす
これに関しては、よくよく考えるとブロックの落下操作自体は列ごとに独立しているので、そこまで難しくなさそうです。計算を軽くするための工夫はいくつかあるとは思いますが、どれも愚直の域を出ない気がします。
残ったブロックについて、順番にBFSをして連結しているグループを作り、それをUnionFindで管理
ABCのD問題くらいで出そうな難易度。番兵を置いておくと場合分けがシンプルになりそう。UnionFindは無向グラフに対して作るものなので、[i][j]で得られるブロックの頂点番号をi*50+jと定義しておくと実装がスムーズになるでしょうか。
方針が固まったので実装してみます。………できました。多分バグはないと思いますが、手元にジャッジ環境が無いのでほんとに正しいかはわかりません(;・∀・)
2回目のAC
さて、スコアを計算する関数が用意できたので、まずは普通に乱択してみます。より具体的には
- ランダムで一カ所選択
- 選んだ場所が「.」なら「+」と「-」の両パターン試す
- 「変えない」「+に変える」「-に変える」の中で一番良いものを選ぶ
という感じです。
5228点。意外と伸びました。本番だと52位の点数ですが、Unratedのコンテストの順位は全然参考にならないとAHC001で学んだばかりなので何とも言えません。
高速化した先に未来はあるのか
愚直乱択でも意外と点数が伸びることがわかりました。スコア計算の部分の計算量を改善できそうな気はしているのですが、まず実行時間制限の10倍の時間手元で回してみて、高速化がどれほどスコアに影響するのか確かめてみます。
………変わらない！！！テストケース2で試してみたのですが、1点も向上しませんでした。局所解に陥ってしまっているようです。本質的な部分の改善が必要みたいですね。
3・4・5回目のAC
わりと早い段階で収束しているしている感があったので、シンプルに多点スタートにしてみて提出してみます。状態の数は多すぎても少なすぎてもスコアが伸びないので、ちょっと調整。
atcoder.jp↑は10個ver.で5637点。35位相当でした。
6・７・８・9回目のAC
最初からなんとなく感じていたことですが、下のブロックと上のブロックの価値(重み？)ってだいぶ異なる気がします。上ばっか使って改善していると下のブロックを変化させるのが改悪になりやすくなって、すべてのブロックを十分に使えない…みたいな。
下から上へ乱択していく感じに書き直してみて提出します。パラ調整を少々。
5860点。ギリギリ順位表1枚目に乗りましたね。ちなみに時間10倍にして手元で回してみましたが、ほとんどスコアが変わらなかったので、上を目指すにはまだまだ本質的な改善が必要そうです。
その後考えたこと
- 高速化
- 下からビームサーチみたいなことする(ちょくだいさーちでも可)
- 素直に焼き鈍しをする
- スコアの持ち方を変えてみる
- 列ごとで見てみる
1は大して伸びしろがないことを確認済み。2は結局遷移を乱択頼りにするなら今と変わらなそう。3は「焼き鈍しをする」=「DPする」くらいの重みしかないので、結局どうやるかみたいな話になってわからん。4は、今連結成分の最大値だけ見ているけど、平均値も加味して更新したら面白いそうという話。5は列単位で端から貪欲なりDPなりしてみたらどうなるかなっていう。DP苦手なので書ける気がしないけど。
10・11回目のAC
とりあえず、上の考察の4を実装してみます。
- 最大値が更新されたら確定更新
- 最大値が更新されない場合は連結成分の大きさの平均値が上がっていれば更新
- 最大値が下がっていたら更新はしない(焼き鈍し寄りの話になりそうなので安易に触れたくないというお気持ち)
という感じで書いてみました。
5927点。順位表1位とまだ1500点以上差がある…。
そろそろ終わり
今日の深夜からtopcoderのMMがあるので、過去問演習はそろそろ切り上げたいと思います。twwiterで共有されている解法を覗いてみると
- 焼き鈍し
- 列ごとの更新
- ビームサーチ
等の単語が拾えました。
chokudaiさんが言及されていた「追加するのはおじゃまブロック」という話は気づいていたはずなんですが、それが問題に与える影響まで正しく考えられなかったのは普通にミスですね。
下から改善していくという発想は割と初期の方からあったんですが、ビームサーチまで持っていけなかったのは悔しい。「下から改善した方が悪くなっちゃうパターンも考えられるから~」みたいなことを思ってたんですが、これはアルゴの弊害ですかね…。平均で俯瞰してみるという意識を忘れないようにしたいです。
個人的に気になっていたのは得点計算の部分なんですが、提出されたコードを見ていると大体BFSかDFSで、たまにUnionFindを使っている方も観測できました。変な道突っ走ってなくてよかったです…(*´▽｀*)
それでは、そろそろMMに備えたいので、この辺で切り上げさせていただきます。MMの解法も終わったら共有するつもりです。最後まで読んでいただきありがとうございました！
マラソン参加記~AHC001~
はじめに
こんにちは、tardigradeです。本ブログでは主に競技プログラミングのマラソンコンテスト(ヒューリスティックコンテスト)についての記事を書いていく予定です。そんなに固い記事を書くつもりはないので、のんびり気楽に読んでいただければ幸いです。
自己紹介
名前は「tardigrade(たーでぃぐれいど)」です。「くまむし」の英訳から来ているので、「くまむし」とか「くま」と呼ばれることもあります。競技プログラミング歴はおよそ1年、2021/03/14時点でAtCoder緑です。
AHC001に参加しました
およそ一週間にわたるコンテストでしたが、あっという間に終わってしまったように感じます。
よかった点も反省点もいろいろあるので、本記事でそれを共有できればと思います。何か感想やアドバイス等あれば、気軽にコメントお願いします！
AHC001を振り返る
とりあえず思考の流れを最初から順に追ってみたいと思います。
問題把握
ざっくりまとめると
- 要求された座標を通るように長方形を配置出来れば正の点がもらえる
- 要求された面積に近いほど得られる点は高い
といった感じでしょうか。
最初に考えたことは、「やべぇ、方針が何も見えねぇ」です。ほんとに、冗談抜きで、なんも思い浮かばなくてめちゃくちゃ焦りました。
1回目のAC
なにも思い浮かばなかったのでとりあえず問題を眺めていると、
- 要求されている座標を通るように1マス分だけ確保する
という方法で最低点は取れることに気づきます。焦って一度しょうもないWAを吐きますが、無事正の点は確保します(確か80万点くらい)。
後々使うかもしれないと思い、スコア計算の関数もこの時書きました。
2回目のAC
1回目のACから考えて、
- 要求されている座標を通るように1マス分だけ確保する
- 辺を拡張していく
という方針をまず思いつきました。
重複判定
しかし、辺を拡張すると「他の長方形と重なる」可能性が出てくるので、「長方形が他の長方形と重なっているか」を判定する関数が必要になります。実装が重くてめちゃくちゃバグらせましたが、何とか実装します。
拡張の仕方
将来的には乱択が見えますが、とりあえず初期解がほしいです。
山登り等への発展を考えると、あんまり偏った解になっても困る気がします。
そこで、まずは正方形の形を保ったまま拡張することを考えました。「正方形」と決め打ちしてしまえば、大体どれくらいまで辺を伸ばすべきかを考えるのも簡単ですし、重複判定も若干楽になります(これがとても嬉しい)。
拡張する順番
スコアは「長方形の面積の大きさ」ではなく、「どれだけ要求された面積に近いか」に対して与えられます。要求された面積の小さい物から拡張していくのが効率がよさそうだと考えました。
これで確か2.7*10^10点くらい。
3,4回目のAC
2回目のACの時点で「初期解は正方形で…」ということを決めたのに、なぜか長方形を許すことで初期解を改善できないか考え始めます。この辺の思考の過程はあまり覚えていません…。長方形の重複判定などはどのみち必要になるので、無駄足ではないのですが。
要求されている面積との差が小さくなるように正方形の辺を拡張(伸縮は面倒だったので考えない)するような処理を書き加え、提出しました。それなりに改善されたのでこちらを初期解にすることに決めます(3.1*10^10点くらい)。
ちなみにこの時の拡張処理は、「重複しないようにできる限り拡張する」といった器用なことはできておらず、「決まった値だけ拡張」or「拡張しない」のどちらかが選択されるようになっていました。結構雑な作りです。
5,6,7回目のAC
拡張処理の精度をあげるか、乱択を実装するか悩み、乱択を選択します。いろいろなパラメーターを試して、よさげなものを投げました(大体4.1*10^10点)。
もう少し具体的に言うと、四隅の座標を0~10000の間でランダムにいじって、スコアが改善されれば採用、みたいな感じです。
8~20(?)回目のAC
拡張処理の精度を上げたり、パラメーターを調整したりしていると、実装ミスに気づきます。エラーがでる類のものではなく、やりたかったことができていなかった感じ。
これを修正すると、4.5*10^5点に乗ります。
以降のAC
完全な乱択だと効率が悪いことに気づき、近傍の値で乱択できるようにしました。時間が経つごとに座標の変化量が少なくなるようにすると、4.7*10^10点に乗ります。
あとはパラメーター調整で時間を溶かしました。
反省
良かった点
- 最初何も思いつかなかったけど、しっかり考察を続けられた
- 山登り法までは実装できた
悪かった点
- 実装の本質的な改善ができなかった
- 見やすい実装にしようと思って逆に冗長に書いてしまう部分が多かった
疑問点
- 焼き鈍しでスコアが良くならない…パラメーターの設定の仕方がよくわからん
- inlineってとりあえずつけておけば速くなるのか？
- 手元で、複数のテストケースをいっぺんに回せる方法があれば便利だな～と思った
めっちゃ楽しかったです！！！
マラソン勉強するぞ！~過去問演習編2~
はじめに
こんにちは、tardigradeです。本ブログでは主に競技プログラミングのマラソンコンテスト(ヒューリスティックコンテスト)についての記事を書いていく予定です。そんなに固い記事を書くつもりはないので、のんびり気楽に読んでいただければ幸いです。
前回の記事の続き
↓前回に続いてchokudaiコン004の問題を解いていきたいと思います。
chokudaiコン004を解く！
前回の考察の続き
前回は、確か焼き鈍し法で点数上げられそう、みたいなところまで書いたと思います。とりあえず、そこから温めてきた考察と実装方法について、述べていきます。
正しいかどうかはわかりませんが、僕はこの問題の評価関数は↓このような形をしていると考えています。
お椀型ではなく、つんつんしている山が乱立しているイメージです。
たくさんある山の中で、最も標高が高いところを目指したいわけですが、普通の山登りでやろうとするとすぐに局所解に陥ってしまいます。焼き鈍しでやろうにも、何回も登ったり下ったりというのはなかなか大変ですし、それで良い解が得られるとも考えにくいです。
そこでやってみたいのが、計算点を増やしてみる、いわゆる多点スタート焼き鈍しです。一人で登るのが大変なら人数を増やしてしまえば、誰かしら最も高い場所にいってくれるのではないでしょうか。
手順としては、まず乱択でいろんな場所について考えてみて、そのうち点数がよかった状態を上から適当な数保持しておきます。そして、各状態に焼き鈍し法を適用して、頂点を探させます。
いきなり焼き鈍しをしようとすると実装がめちゃめちゃ大変になりそうなので、とりあえず多点スタート山登りを実装していきたいと思います。山登りでは、時間に応じて値を変化させるマス目の数を減らしていくような形で実装してみます。
実装終わりました。山登りの辺りの実装これでいいのかとても不安ですが、とりあえず出してみます。1164836点。なんか時間ミスってるっぽいのでもう一度。
うーん、乱択貪欲を超えられず、1165492点。値をいじりながらもう少し粘ってみます。
いろいろいじってみましたが、1168961点が最高で、順位は146位です。
点数が伸び悩んでいる原因について考える
現状、乱択貪欲で出したスタート地点がほぼそのまま解になってしまっています。すなわち、山登りでの改善がほとんどできていないということです。その原因について考えてみたいと思います。
ぱっと思いつくのは、乱択貪欲で作成した盤面の性質です。貪欲というのは、あるルールに則ったときの最適解なので、そのルールから外れる(マス目の値を変える)ことは、点数を悪化させやすいのでしょう。今回の場合の貪欲はほぼ局所解に等しいのかもしれません。
他には、山が想定より高くない可能性です。高い点数を出せる山の数が全体の山に対してかなり少ないという可能性もあります。この場合、なんとかして乱択の回数を増やして、アタリの山にたどり着かなければなりません。
このまま焼き鈍しに移ったとしても、きちんとした関数定義ができず、大してスコアが伸びないような予感がします。
貪欲を改善してみる
一旦初心に帰って貪欲を整理してみたいと思います。今まで横オンリーで考えていましたが、縦の情報も加えたいです。前回の記事で、「実装重そう」とか言いましたが、よくよく考えたら全然そんなことはなかったので、ぱっぱと実装します。
まだ実装途中ですが、最初に書いた貪欲の部分でミスを見つけたので修正して投げます。なんとびっくり1184980点！139位です。最初のミス痛すぎる…。
そして縦方向の実装も終わりました。手元だとなかなかいい記録が出ているので楽しみです。はい！1362148点！！！順位は64位！！！貪欲実装し直してよかったです(´▽｀)
点数計算の高速化
今までの感じを見てみると、あんまり多くの値をいっぺんに変化させるのは良くないようです(1~10個くらいが良さげ)。また、今回縦も考慮して実装したことで、貪欲がより局所解に近づいたような気がします。そこで、値を変化させる場所を一点に絞り、点数計算を高速化して、試行回数を増やすことを試すことにしました。
変化させるマス目が1個であれば、その行と列だけ見れば差分計算ができるので、点数計算にかかる計算量がO(N^2)からO(N)に改善されます。
提出しました。1378183点！59位まで浮上しました！
焼き鈍しを行う
自分的にはそこそこ納得のいく形で山登りが書けたので、これをなましていきたいと思います。どれくらいの悪化をどれくらいの割合で許容すればいいのかあまり見当がつかなかったので、実験してみます。具体的には、ランダムで値を一つ変更したときの、全体の点数の上下を見てみます。
赤丸がexample1、青丸がexample2、黄丸がexample3です。縦軸が点数の変化量、横軸に変化させた回数を示しています。
マイナスになるような変化が圧倒的に多いことから、最初から既に局所解に近い位置にいることが想像できます。
結局どうすべきかよくわからなかったので、
- 点数がより良くなった場合は常に遷移
- 点数が悪くなった場合でもある確率で遷移(確率は以下のように定める)
- 序盤(時刻t=0に近いとき)ほど高確率で、終盤(t=3000に近いとき)ほど低確率
- スコアが悪くなった量が大きければ大きいほど、低確率
という感じで実装してみます。ずっと言っていますが、この問題の評価関数は、山の麓が広く、頂点のほうが急激にとんがっているようなグラフになる予感がするので、指数関数っぽい感じで遷移を絞ってみたいです。
実装しましたが、手元では全然いい結果が出ないです。
提出しましたが微妙ですね…。1374506点です。
まとめ
焼き鈍しの関数何入れていいのかわからないです。いろいろ考えてみましたが、さすがに疲れてきたので、今までの流れをまとめて「マラソン勉強するぞ！~過去問演習編~」を終わりにします。
書いてきたプログラムとその順番は、早い方から
- 貪欲
- 乱択貪欲
- 多点スタート山登り
- 多点スタート山登り(貪欲改)
- 多点スタート山登り(貪欲改・点数計算コスト減)
- 多点スタート焼き鈍し(貪欲改・点数計算コスト減)
です。ベストスコアは5つ目で、1378183点でした。
初めてまともに取り組んだ割には、いい点数を残すことができたかなと思います(好きなだけ時間をかけれたので当然かも)。このコンテストは公式解説が無いので、twwiterで他の方の解法を見て、気づいたことや改善案が見つかれば、そちらを~復習編~と題してまとめるかもしれません。個人的には、焼き鈍しの温度関数・遷移確率関数の設定の仕方が全然わかっていないので、もっと勉強したいです。
AHC001のマイ解法も、コンテストが終わり次第記事を通して共有したいと思っているので、そちらも読んでいただけると嬉しいです。最後まで読んでいただきありがとうございました。
マラソン勉強するぞ！~過去問演習編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時を回っております…。マラソンの沼を現在進行形で実感していますが、そろそろ寝ないとまずいので、一旦温めさせてください<(_ _)>もう記事もだいぶ長くなっているので、続きは次回に回します。
夜遅くに考察を入れながら書いていた記事ですので、読みにくかったところも多々あるかと思いますが、最後まで読んでいただきありがとうございます。
マラソン勉強するぞ！~アルゴリズム編~
はじめに
こんにちは、tardigradeです。本ブログでは主に競技プログラミングのマラソンコンテスト(ヒューリスティックコンテスト)についての記事を書いていく予定です。そんなに固い記事を書くつもりはないので、のんびり気楽に読んでいただければ幸いです。
本記事が初投稿になります。
自己紹介
名前は「tardigrade(たーでぃぐれいど)」です。「くまむし」の英訳から来ているので、「くまむし」とか「くま」と呼ばれることもあります。競技プログラミング歴はおよそ1年、2021/03/02時点でAtCoder緑です。
AHC001が開催されるぞ～！！！
今週の土曜日、3/6から3/14まで、「AtCoder Heuristic Contest 001」が開催されます。マラソン用の新しいレーティングも整備されるということで、とても楽しみです(*ﾟ▽ﾟ*)
ところで、僕はあまりマラソンの経験がありません。ずっと面白そうだなとは思っていたのですが、AtCoderではあまりマラソンコンテストが開催されてこなかったので、本格的にやる機会がありませんでした。
そこで、AHC001を楽しむためにもある程度勉強をすることにしました。本記事は、その過程の記録です。僕と同じように、ほとんど初めてマラソンをするという方の参考になればいいなと思っています。
tardigradeの対マラソン戦績
大した数は出ていませんが、一応書いておきます。
2020/06/28 Introduction to Heuristics Contest 1654位(1点)
2020/09/27 Chokudai Contest 005 291位(49654250点)
2020/11/07 HACK TO THE FUTURE 2021 予選 463位(144006点)
2020/12/17 Hitachi Hokudai Lab. & Hokkaido University Contest 2020 67位(435756208236756点)
ちなみに、一番最後のコンテストはサンプルコードを投げただけなので、誰でも取れる点数です。これまでのマラソンコンテストは参加者が少なく、順位が高くなりがちなので、どのコンテストも見た目ほどいい成績を残しているわけではありません。
マラソンの勉強をする
どんな勉強をすればいいのかわからなかったので、とりあえず競プロを始めたときにしたことと同じことをします。具体的には
- 頻出のアルゴリズムを勉強する
- 過去問を解いてみる
- 知らない知識がでてきたらそのたびに勉強する
といった感じです。他になにかいい方法を知っている方がいたら教えてください。
頻出のアルゴリズム
まずはアルゴリズムです。ビームサーチや山登り法といったものが存在することは知っているので、その辺を重点的に調べてみます。
貪欲法
これはABCなどでも頻出ですので、あまり説明はいらないかと思います。その時その時で最善の手を選び続ける方法です。マラソンでも、最初は貪欲法で組んでそこから改善出来るところを探す、ということをよく行うみたいです。
ビームサーチ
ビームサーチは、貪欲法の考え方を発展させたアルゴリズムのようです。貪欲法が最善を選び続けるのに対し、ビームサーチは上からk番目までの手を選んだときの遷移を考えます。図にするとわかりやすいです。
黄色い部分(選んでいる手)がビームに見えるのでビームサーチと呼ばれるみたいです。また、kのことをビームの幅と言います。ビーム幅を広げると、遷移に多様性が生まれますが、その分計算量やメモリは食うので注意です。
chokudaiサーチ
個人的に一番気になっていたアルゴリズムです。詳しい説明はchokudaiさん本人がブログで書いていらっしゃったので、そちらをどうぞ。
個人的な感想としては、BFSとDFSの関係に近いかなぁと思いました。ビームサーチがBFSでchokudaiサーチがDFSです。もちろん得られる遷移もその多様性も違うので、全然正しい表現ではないんですけどね。
山登り法
調べてみると、イメージ通りというか言葉通りというか、結構シンプルな方法でした。
山登り法ではとりあえず何でもいいので一個解とそれに対するスコアを算出しておきます。そして、「解を少し変えたとき、スコアが良くなるのであればそちらを採用する」ということを延々と繰り返します。これだけです。
山登り法のメリットは、実装が単純であること。対してデメリットは、局所解に陥りやすいということです。
デメリットの部分を少し補足します。前述した山登り法の説明を「登山」に置き換えてみると、「解を変えること」と「場所を移動すること」、「スコア」と「標高」がそれぞれ対応します。山が一個しかない場合、登山をしていればいずれ一番標高の高い場所に移動できます。一方で山が複数ある場合は、登り切った山の標高が存在する山の中で一番高いとは限りません。そして、「登山」は下ることを考えないので、その場所から移動できなくなってしまうのです。この状態を、山登り法では「局所解に陥る」と表現します。
焼き鈍し法
これは、山登り法を調べていく中で知ったアルゴリズムです。山登り法のデメリットとして局所解に陥ってしまうことを挙げましたが、ここではそれを回避することについて考えてみましょう。
山登り法で局所解から抜け出せない原因は、「スコアを上げる方向にしか移動できない」という点にあります。もともとはより良い解を出すために課した制限のはずなのに、今度はそれがあだとなってしまっているわけです。
それなら、ある程度スコアが悪化することを許容しちゃえばいいんじゃね？というのが焼き鈍し法の考え方です。より具体的には、
- スコアが低いうちは改悪をがんがん許容
- スコアが良くなってきたらちょっとずつ許容しなくなる
- 最終的には山登りとおんなじことをして解を求める
ということを行います。山登り法では単純にスコアが良くなる方に遷移していけばよかったのですが、焼き鈍し法では「どの程度の改悪を許容するのか」や「どの程度の確率で新しい遷移をするのか」といったことも決定する必要があります。実装は少し複雑になりそうですが、この辺のパラメーターの調整作業ってとても楽しそうですね(*´▽｀*)
少し発展的な話になりますが、山登り法や焼き鈍し法は、多点スタートにしたり、複数の状態を保持(状態プール)したりすることもできるようです。オプションまでたくさんつけられるなんてめっちゃ面白そう！
粒子群最適化
英語名の頭文字をとってPSOとも呼ばれます。これ、僕は初耳だったのですが、焼き鈍し法を調べているときに見つけて面白そうと思ったので共有します。
粒子群最適化は、その名の通りたくさんの粒子(スコアを計算する解、標高を調べる場所)が必要になります。粒子群最適化は鳥の群れが餌を探す様子に着想を得た手法であるようなので、ここではその粒子を鳥に、スコアを餌の多さに例えて説明します。
まず重要なポイントとして、各鳥は速度を持っています。飛んでいるから当然と言えば当然かもしれません。そして、各鳥は今まで自分が通った場所の中でもっとも餌の多かった場所と、群れに属する鳥のいずれかが通った場所の中で最も餌の多かった場所の情報を常に保持しています。それらをもとに鳥の位置を修正する作業を繰り返していくと、最終的にすべて鳥の位置が一点に収束するようです(最適解が複数ある場合は収束しないっぽい)。
具体的な式だったり初速度の与え方だったりとかは、ぱっと調べた感じ難しくてよくわからなかったので、ここでは省略させてください<(_ _)>
感想
当初思ってたよりいろんな方法がありました。調べている最中に、「焼き鈍し法とビームサーチは二項対立の構図は適切でない」という記事を見かけて、とても興味深かったので共有させていただきます。
次回予告
本当は過去問演習までで一つの記事にしたかったのですが、思ったより長くなってしまったので二つに分けたいと思います。
次回の記事では、実際に過去問を解きながら、着眼点とか考え方とか発想の様子とかを共有できたらと思います。
