ハル研プロコン2020・チャレンジスコア解説

そもそもプロコンとは

あのカービィで有名なハル研究所ですが、毎年、学生とハル研の社員向けにプログラミングコンテストを開催しています。問題はスコアを競うマラソン形式で、ゲームっぽい内容です。ちゃんと賞金もあって、上位に入れば記念品も貰えます。なんならアンケートに答えるだけでも粗品が送られてきます。こんなに美味しいのになぜかTwitterではあんまり流行らないですね…　マラソン形式の宿命か、学生だけだと厳しいか、C++のみというのもありそう。

プロコン２０２０

昔むかし、かけっこでカメに負けてしまったウサギがいました。

悔しさを胸にウサギは修行の旅にでます。

次こそ勝つために、修行の地に散らばる秘伝の巻物を集めてください。

去年はカメだけでしたが、今年はウサギも来るようです。

簡単ルール解説

ジャンプ移動でマップ上の巻物スポットを回る
360°に浮動小数点精度でジャンプできる
巻物をとるとジャンプ距離が伸びる
ジャンプする場所の地形によりジャンプ可能距離が違う
少ないジャンプ回数を目指そう！

けっこうシンプル？というかかなり一般的なゲームの問題ですね。

昨日のAdventCalenderの記事と雰囲気似てないか？大丈夫？

www.hallab.co.jp

とりあえず自分がどんな感じにマラソンを進めていったか書いてみます。下手にまとめるより全部書いたほうが書きやすいのでは？と思った結果である。

触ってみる

使用可能な言語：C++14

デデドン！私が普段AtCoderで使ってるのはJavaで、ゲーム作りはUnityでC#です…　JavaScriptやPythonでも触れますが…　C++だと学校の授業のC言語レベルになります。しかもC++14はちょい古いです。

ここで朗報、問題セットにはVisualStudioのプロジェクトファイルがついてきます。MakefileもついているのでUnixでも安心。（ほんとか？）

何を書く？

毎ターンにステージを表すオブジェクトが引数に与えられるので、ジャンプ目標地点を返す関数を書きます。

おもしろビジュアライザ

マラソン形式の醍醐味です。問題セットにブラウザで動くビジュアライザのhtml,jsがついてきます。json読み込ませると白いウサギの点Pが動きます。

f:id:kametaro49:20201208025300p:plain

初期解：巻物インデックス順に直行させた（109,285ターン）

やっと考察

一見最悪な初期解でも、ターン数の上限をオーバーしたりすることなく最大20ある巻物を回収できています。とても無駄が多い順路の改善、ターンを浪費している水場・森・荒野の迂回を考える必要がありそう。逆に巻物によるパワーアップが思ったより弱いので後回しでよさそう。

順路改善その１

うさぎ自信から一番近い巻物に向かえばいいんじゃね？

f:id:kametaro49:20201208031722p:plain

（50,510ターン）

初期解の半分ほどのターンになった。しかし以下のようなステージでは行って帰ってしてしまうためこの方法では無駄が出る。

f:id:kametaro49:20201208032452p:plain

悪地形の回避

座標が整数のみで、移動も隣接マスだけであれば、50x50マスでなのでグリッド上のダイクストラ法やA*で十分に最短経路を求められる。（頂点数2500, 辺の数5000くらいなので）　しかし座標は実数値で、移動もジャンプである。

よくよく考えると、もともと360°どの方向にも行けることから、方向転換をする必要がある箇所は、巻物、地形の端の２つのみである。これらに頂点を配置し、他の全頂点と接続すればよい。まずは地形の角を抽出して最短経路を導く。

地形の角が200ほどあったとすると、辺の数はおよそ $\frac{N^2}{2}$ の20000辺となる。1ステージせいぜい3秒がリミットなので、たくさんは頂点を増やせない。巻物間の最短距離さえわかればいいので、巻物の数だけダイクストラ法を行い、計算量は $O(MN\log{N})$ となる。それぞれの辺の長さは事前シミュレーションで出している。

f:id:kametaro49:20201208142838p:plain

（31,447ターン）

チャレンジスコア達成です！おめでとう！

チャレンジスコアとは、達成した人のうち抽選5名に記念品が贈呈されるものである。

順路改善その２

結果行って帰ってしていると無駄が多いので、やはり順回路は最善である必要がありそう。この問題は巡回セールスマン問題としてよく知られている。近似解を求める方法としては、2-opt法などがある。……巻物最大２０だしワンちゃん最善解いけないかな？

蟻本さんに助けてもらう。蟻本さん：bitDPを使えば $2^NN^2$ で解けるよ！それは以下の通りだった。DPテーブルはdp[到達済み巻物集合bit][現在地]で、中身はそこからすべての巻物を巡る最短経路である。更新式は、vからuへ行くとき、

dp[S][v] = MIN( dp[S][v], dp[S (+) u][u] + edge[v][u] )

となる。イメージとしては0となっている最終状態から、逆算していく感じ。クソデカDPテーブルなのでstaticに宣言したほうがいい。（一敗）

        for (int S = 0; S < 1 << N; S++) {
            std::fill(dptable[S], dptable[S] + N, 1 << 30);
        }

        std::fill(dptable[(1 << N) - 1], dptable[(1 << N) - 1] + N, 0);
        std::fill(dprev[(1 << N) - 1], dprev[(1 << N) - 1] + N, -1);

        for (int S = (1 << N) - 2; S >= 0; S--) {
            for (int v = 0; v < N; v++) {
                for (int u = 0; u < N; u++) {
                    if (!(S >> u & 1)) {
                        float ck = dptable[S | 1 << u][u] + shortest[v][u];
                        if (ck < dptable[S][v]) {
                            dptable[S][v] = ck;
                            dprev[S][v] = u;
                        }
                    }
                }
            }
        }
        std::cerr << stage << " dp " << dptable[1][0] << std::endl;

と、実はこれはTLEします。というのも2^NがキツすぎるのでN=18が限界になります…巻物20＋初期地点1で21なので、頑張って減らします。具体的にはめちゃくちゃ近い巻物同士は一つとして扱いました。　あと、ここからSのbitCountを使ってshortestに細工すると、巻物によるパワーアップも考慮することができました（ほんとか？）

f:id:kametaro49:20201208152353p:plain