ハル研プロコン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

（28,770ターン）

3万切れましたね！上のと一見同じですが、よく見ると行き帰りが減っています。

ここらで上位層が強すぎたため、30位挑戦にはリタイアです。

雑記

C++14とかいう古代言語のせいで、popcount()など存在しなかった。なんか他にも詰まったところあった気がする。

VisualStudioのデバッガが付いてると実行が死ぬほど遅くなりました。気づくまで時間を浪費していた。

2次元配列で添字ミスをし、配列がぶっ壊れるのにその場ではエラーが出ないで異常値になるやつもあった。（困る）

コード長480行！意外とコンパクトでは。記事長3000文字なのでどっこいどっこい（何が？）

initial commit

これは大見出し　概要

とりえあず最初はブログを書くことについてブログに書くメタ戦法にしました。

目標はこの記事をうまく着地させることにします。ちなみにではないですが、ブログ書くのは初めてです。

 

これも大見出し　開設

なぜはてなぶろぐにしたか？これ書いとけば記事の半分埋まる気がする。

まずステークホルダーと要件の定義から…（ソフトウェア工学的に）

・ステークホルダー（これは中見出し）

  • Me　（いわゆる筆者）
  • 閲覧者　（Advent Calenderの人のみならず）
  • サイト運営者　（これもステークホルダー）

・要件

  1. 最初の記事がAdventCalenderに間に合うこと
  2. 初めてブログをかく初心者でも大丈夫であること
  3. 技術寄りのことを書ける
  4. 無料
  5. 筆者が満足するデザイン

これくらいかな？

要件と、自宅サーバは持っていないことからして、ブログの構築にはクラウドサービスの利用が考えられる。SaaS、PaaS、IaaSのどれがよいか考えてみよう…（露骨な文字稼ぎ）ーーー　　　あれ、表がない（現在「編集：見たまま」を選択している）

 脱線　（小見出し）

 まさかbb9より編集機能が貧弱なのか？流石にそんなことはないだろうとドキュメント（ヘルプとも言う）を見に行く。どうやら「見たままモード」、「はてな記法モード」、「Markdownモード」と有料の「HTMLモード」があるらしい。いや、HTML編集触れるんだが？（もちろん何も払っていない）

検索してもHTMLモード無料化とかヒットしない。　ドキュメントが古いのか、バグか…　見た感じはてな記法モードはMarkdown形式がちょっと変わった程度だった。

　形式　 正式名称
SaaS Software as a Service
PaaS Platform as a Service
IaaS Infrastructure as a Service

 HTML編集で無理やり追加。

考えるまでもなく今回使うのはSaaS。

\begin{array}{|c|c|}形式 &amp; 正式名称\\ \hline SaaS &amp; Software as a Service\\PaaS&amp;Platform as a Service\\IaaS&amp;Infrastructure as a Service\end{array}

texのarrayはなんか崩れまくった。

サービス選定　（もう1000文字書いたらしい）　

候補に上げたのは以下のサービス

結局、見ての通りHatenaBlogを選んだわけだ。

最初はQiitaが良さそうだと思ってたのだが、この記事も含めて要件ではプログラミングではないことも書こうとしている。Blenderはプログラミングか？Unityは？ちょっと面倒なので却下された。編集機能は良さそうではある。 次、NoteはどうやらSNSチックらしい、そういうつもりではなかったので…　次、Wordpress、なんか難しそう…　やたら絶賛されてるイメージがあるが初心者向けではないはず。PaaSに近いのでは？　消去法でHatenaBlog！

ferret-plus.com

ちゃんとこういう比較サイト見ると良いと思う。（手遅れ）

ちなみに楽天やらLINEやらAmebaで技術寄りのを書く気にはならなかった。

 

コンクルージョン

 わりとちゃんと書けた気がする（自画自賛）

 

以下落書き

HTMLコピペが効くのでVSCodeからコピペするとこうなる。

    Main() {
        Scanner sc = new Scanner(System.in);
        long ans = 0;
        int N = sc.nextInt();
        System.out.println(N);
    }

kametaro49's blog の左のロゴマークの変え方わからん。