inani_waonの日記

コンテスト覚書

Topcoder MM127 - CarRacing 参加記録

Topcoder の Marathon Match 127 に出走しました。 

www.topcoder.com

問題はCarRacing。インタラクティブな、ソート手順を短縮する問題です。

事前テストは62人中3位、システス結果は2位でした。

 

レート：2039(黄)→2229(赤)

 

問題

N台の車があり、これらの速度は車ごとに別々の値で固定です。

K台ずつレースさせて、その結果を順位だけ知ることができます。

より少ないレース数で、全ての車を速い順に並べてください。

  

考察

やることはソート。

既存のソートアルゴリズムを使うなら、クイックソート（＋選択ソート）が良さそう。選択ソートは上位n個の選択、クイックソートはpivot n個によるn+1分割とすると、(基準となる車の数 n) * (基準と比べる車の数)で二重に並列化出来るので効率が良い。*1

これらのアルゴリズムではKが2→4になると基準値との比較を+2回可能(効率3倍)ということになるが、実際にはAB,AC,AD,BC,BD,CDで6組という風に、総当たりでより多くの組の大小関係を比較することが出来る。(効率6倍)

また、AがBより速い場合、[A,Aより速い車の全て]は[B,Bより遅い車の全て]より速いと言える。この点を踏まえて、どのK個を組み合わせると最も情報が増えるかという観点で出走する車を選ぶのが良さそう。下手にやると計算量が爆発するし、オーダーも安定しないので難しい。

 

最終的にやったこと

全体方針

クイックソートでざっくり振り分けた後、考察後半の方法でソート(便宜上、関係性ソートと呼ぶ)して順位を確定させた。

構造としては、木構造で分割統治。

クイックソート

選択ソートの処理コストを基準として、台数が少ない方からDPで処理コストを求め、そこからクイックソートの最適なpivot数を決定した。

選択ソートなんて使っていないので、根拠の無い値になっている…。*2

関係性ソート

これは固定のロジックがあるソートアルゴリズムではなく、確定情報による順位確定をするために出走管理を行うロジック。出走する車は貪欲で以下のルールで選んだ。

　・グループ内の既に大小関係がついている車の数ごとに1ペナルティ

　・既に大小関係がついている車と同時出走するたびに10ペナルティ

　・既に出走決定した車の平均期待順位と離れるほどペナルティ(0～グループ内の台数)

 

 やったこと時系列

・サンプル確認(0.4点)

車2台だけ使う選択ソートらしい。

クイックソート＋選択ソートを目標にして、ボトムアップで選択ソートから作るかな。

 

・K台出走する選択ソート(2点)

・上位n台を抽出する選択ソート(20点)

O(N^2)だからこんなもんかな。（震え声）

 

・pivotが1件のクイックソート(50点)

・pivotがn件のクイックソート(75点)

この辺に人が固まっていて、多分みんな同じ方針かな。

 

・既についた大小関係で分割可能ならする(80点)

・余った幅で他のグループのソートもできるように(80点)

・選択ソートを関係性ソートに差し替え(85点)

グループ（分割統治）の単位で出走させていたので、枠が余るともったいない。複数グループを同時に出走できるようにした。

また、大小関係の情報保持を、グループ内の最小や最大が運良く判明したら嬉しいな、くらいの気持ちで始める。しかしここで、基準値を使わずに要素同士で大小関係を付け合った方が効率が良いことに気づく。

ここから深い闇へ。

 

・各種調整(89点)

大小関係は連鎖的に増えていくので、より効率の良い手順を模索。

情報が少ない車同士で出走したり、(1,2) > (3,4,5) > (6, 7) のような複数台の大小確定情報も利用できるようにしたり。

しかしこの辺りは手順数が多いものを短縮できても、元々手順数の少ないものはほぼ短縮できず、絶対スコアは改善しても相対スコアがあまり変わらなかった。

 

・期待順位が近いやつ同士で出走(94点)

これがかなり大きかった。何故これが効くかというと、どちらが勝ってもその上位/下位にいる車の情報を与えることができるため。期待順位が離れていると、高確率で1対1の分しか情報が増えないということもある。

実装方法がなかなか浮かばなかったが、自分より速い車の数、遅い車の数から上位何%くらいにいるかあたりを付けて、出走する車がこの全台平均から離れるとペナルティを付けるようにした。

ここでコンテスト終了。

 

ビジュアライザ関連

MM127はビジュアライザが無かったので、開催中または終了後にビジュアライザを作る人がいたようです。

 

もおあきさん

総当たり

 

yowaさん

クイックソート、マージソート、総当たり

 

私

クイックソート、総当たり

 感想

コンセプトはソートというシンプルな題材なものの、複数の車同士に大小関係が付いたり、並列化のような処理を書いたりとなかなかにハードで面白かったです。複数のソートアルゴリズムを操るということでinterfaceも使ってみたけど、マラソンでinterfaceを使ったのは初めてじゃないかな…。*3

ビジュアライザが無いのに加えて、車の数が多く情報が複雑なので、考察＆デバッグは大変でした。結構ゴリゴリの実装コンテストだったのでは？

終盤の見通しを立てて上手く設計するというのも時には必要になりそうですね。

*1:nはKやソート対象の台数によって決定する。

*2:なので再帰的に下位の計算コストを0.8倍すると改善した。

*3:なお綺麗に書けたとは言いません。

AHC003 - Shortest Path Queries 参加記録

AHC003に参加しました。

問題名はShortest Path Queries。

インタラクティブ問題で、最短路探索＋コスト推定です。

 

atcoder.jp

暫定テストは90.7Gで、提出1000/AC875 人のうち、316位でした。

→システス308位。→リジャッジ309位。

 

問題

経路を送ると経路全体のコストが返されるので、

1000経路のコストを全体的に低くしてね。

 

最初読んだ雑感

・1クエリあたり2ms。大したことは出来なさそう。

・それって結局O(1)あたりの性能が問われるのでは。

・どう見ても数学問題なんですが、数学問題が苦手な方にお勧めとは…？

 

 

考察

M=1とM=2があって、M=1は行や列ごとにコストがほぼ一定、M=2は行や列ごとに分割点があり、そこでほぼ2種類のコストに分かれるという感じ。

スコアの重み(0.998辺り)は前半717回≒後半283回になるっぽい。とはいえ700回かけて調査は長すぎるかな。300回くらい？→実際は200回前後になった

辺は1740個あり、1回に探索する経路長は最短経路なら10～60。*1経路長35として全部の辺を2回ずつ通るには最低100回くらいの探索が必要、端の辺は通る機会が少ないので実際はもっと必要といったところか。

経路を重ねると差分を取る戦略が取れそう。[A→B→C→D=10]で[A→B→C=8]なら[C→D=2]みたいな。

 

やったこと

 今回はモチベーションが出なかったのでM=1だけ想定して行・列の推定だけ雑に行った。

お気持ち計算で以下の感じに。

 コスト={全体コスト/経路長}

 確度={特定の列(行)の経路長 / 全体の経路長 * 0.9}

探索時の経路は[横→縦]か[縦→横]の2通りで確度が低い側。*2

スコア稼ぎ時の経路はダイクストラ法。何気に競プロだと初めて実装したらしい。

ダイクストラ時の辺の重みは{コスト * 確度 + 5000 * (1 - 確度)}。

 

やらなかったこと

M=2の想定や、Dによる分散への対応。

1740辺を全部持つのは本格的に統計でコストと確度を導かないと厳しいかな。行内で2箇所が分かれば間は大体同じコストという推定はできそう。適当にやったらスコアが下がった。

行や列ごとに2分割で持つ方法は雑計算とは相性良さそうだけど、それでも実装すると1日以上飛びそうだったので断念。

あとは経路の差分取りもMM122のマインスイーパに近いので頑張れば出来たのかもしれないけど、こちらは時間が短いし実装すると時間がかかりそうだったので以下同文。

 

感想

今回は周囲の空気感も掴めていないので感想も無しで…。

*1:意図的に伸ばそうと思えば89まで伸ばせる。

*2:[横→縦→横]みたいに間の長辺を探索するパターンも書いたけどあまり芳しくなかった。

CodinGame Spring Challenge 2021 参加記録

CodinGame Spring Challenge 2021に参加しました。

リアルタイムのコンテストでは初Legendです。とても嬉しい。

 

ルール

下記記事参照。

inaniwa.hatenablog.com

 

考察

手法

ルールベースや評価関数系を作るにはゲームパラメータが多く複雑で、MCTS系を作るには有効手が多すぎ探索も深くなる。

→何も分からん。

→センスが無くてもなんとかなるMCTS系で行くか…。

栄養素

戦略性がある。同じ回数ずつCOMPLETEするとして、先にCOMPLETEすると[相手の残りCOMPLETE数]分のアドバンテージを稼げるっぽい。序盤に纏めて行うと乗算で効いてくるけど、相手もCOMPLETEを挟んでくると効果が薄くなる。自分のSUN収入源である木を失うので、攻めるのにもリスクがある。

影

3日後には反対方向から日が当たるので、相手を妨害できるパターン≒自分が妨害されるパターンとなる。そのため盤面を木だけで評価することは難しく、翌日や以後何通りかの日当たりから評価する必要がありそう。具体的には翌日に相手の木が影に入るようにしたり、影になる位置のSize3は枯死させてしまう等。

戦略

木を成長させるとSUN収入が増えて更に木を成長させられるので、とにかく序盤ゲー。土俵に立てるか否かでそのまま勝負が決まることも多い。探索するとしても、序盤はルールベース埋め込みにする手はあり。

 

最終的にやったこと

DUCTのみ。

プレイアウト数は最初のターンに900msで6000プレイアウトくらいで、高速言語勢と比べると少なめ？またMCTS系の問題点として、プレイアウトに全ての有効手を一様乱数で選ばせると、現実味の無いプレイばかり行い結果が信用できないというものがあった。今回のゲームはSEEDコマンドの使用頻度が低い割に列挙した場合のコマンド数がとても多く、特にプレイアウトの精度が低くなりがち。

そのため工夫点として、プレイに現実感を持たせるため、一定条件で特定コマンドを強制、または禁止した。前向き枝刈りというらしい。*1

 

プレイルールは以下のようなものを用意した。以降、日付は0日目～23日目という表記。

 

・0日目はWait

・4日目まではSize0,Size1の木がどちらも存在しない場合のみSEED可能

・4日目まで、木同士を隣接させない

・7日目まで、SEEDは桂馬飛びで行う

・12日目まで、長さ4の直線上に自分の木を3つ並べない

これらは初動の良い動きはほぼ固定となるため。

 

・木(種を含む)は9本まで

・Size毎の木は、小さい順に{2, 3, 4, 6}本まで

同じサイズの木を持ちすぎるとGROWコストが苦しくなるため。

また、木は多すぎても影のせいでパフォーマンスが伸びないため。

 

・SUNが15以上ならSEEDは使わない

これはGROWの後にSEEDすることでが目的で、

種を減らしてSEEDコストを下げるのと、SEEDの考慮回数を減らすため。

 

・Size1の木はSEEDを使わない

これはLegend勢のリプレイを見たらそうなっていたのでSEED考慮抑止に。

 

・16日目まで、SUN収入(理論値)18未満の場合COMPLETEしない 

これは中盤までに無理にCOMPLETEして後が続かないのを避けるため。

 

・Size3の木が6本かつSUN16以上あれば必ずCOMPLETEする

・木が9本かつSize3の木が3本かつSUN16以上あれば必ずCOMPLETEする

これらは中盤でCOMPLETEさせ、栄養素の争奪を表現するため。

 

・最終日は栄養素が2以上あれば必ずCOMPLETEする

・Seedは19日目まで、Grow(0→1)は20日目まで、…

　(最終日COMPLETEが間に合うように)

これらはサイズ3の木を持ったままゲームが終わることを避け、

プレイアウトの精度を上げるため。

 

これらのルールは自分で考えたものや自明なもの、上位のリプレイの特徴を目視で分析したもの。まだまだ改善の余地はありそうだけど、コンテスト期間中にやれることは頑張ったかな。

 

リーグ別やったこと

Wood2, Wood1

貪欲っぽいルールベースをしました。各木の違いは生えている場所の土壌品質だけなので、土壌品質が高い順に（GROW→）COMPLETEすると最大の得点を得られます。実は中央ほどCellIndexが小さいので、土壌品質の降順でなくCellIndexの昇順に処理することができます。

Bronze

自分の点だけを考慮するMCTSを書きました。

5日目までは桂馬飛びとか、簡単な枝抑止は入れました。

Silver開放と同時に昇格。

Silver

序盤の土俵入りが弱かったので、4日目までの動きをルールベースにしました。

（この辺でプレイルールを整備しないと先が無いことに気付く）

あとはTimeoutが多すぎたので、探索時間を90ms→80msに短縮しました。

リーグ開放から1日くらい遅れて昇格。

Gold

MCTSをDUCTに変更しました。

式はよく分からなかったので、互いにUCB1-Tunedで手を選ぶようにしました。

Legend勢のリプレイを見て、プレイルールをゴリゴリ埋め込みました。

まだTimeoutが多かったので、最初に5000個作ったノードを使いまわすようにしました。

最終日に昇格。

Legend

残り時間がほぼ無かったので新しいことは何もしていないです。

後日談

Seedを2個までにしていたのを、1個までに変更したところ100位上がりました。

もっと思い切って調整すれば良かった…。

 

感想

取っ付きやすくはないけど、それが故に解法が自由で面白い問題だったなと思います。

DUCTやノードの全使いまわしを新しく覚えたり、

MCTSのプレイ矯正をやりこんだりと得られるものも多かったです。

今回はTwitterでの技法の情報交換も活発でしたね。

今後も楽しみながらスキルアップ出来るコンテストとして推していきたいです。

*1:有効手を列挙する関数内にif文がいっぱいあります。

CodinGame Spring Challenge 2021 日本語訳ルール

2021/05/06より、CodinGameにてSpling Challenge 2021が開催されています。

www.codingame.com

この記事は、同コンテストのルールを日本語に訳して紹介するものです。*1個人が作成したものなので、間違いがあっても責任は負えません。ルール原文を読む補助に使うことを推奨します。

また、攻略情報は掲載しません。CodinGameではソースコード公開以外の情報共有は許可されているので、情報が欲しい方はCodinGame内のチャットやTwitter等で探してみてください。

 

1. ゲーム概要

2人同時着手ゲームで、HEX(6角形)フィールド上で木を育てて枯死させるゲームです。最終的にポイントを多く稼いだ方が勝利です。*2

リーグ制になっていて、Wood1,Bronzeになると段階的にルールが開放されます。

f:id:inani_waon:20210507023025p:plain

ちなみに、ボードゲームのPhotosynthesisがモチーフのようです。

 

2. 用語

2.1 森

37個の小さなセル(HEX)を繋げて大きな6角形を作ったものが森です。

ゲーム盤といったところでしょうか。

2.2 土壌

セル毎に土壌の品質があり、0～3の値が設定されています。Woodリーグは1～3のみです。

これはゲーム中は常に同じ値で、ゲーム開始時に1回だけ入力を受け取ります。

ゲーム盤の上に置くタイルといったところでしょうか。

品質1～3は得られる枯死ボーナス値(後述)が違うだけですが、品質0は種を植える(後述)ことができません。 

2.3 木

成長段階に応じてsize0～3の値を持ちます。

Wood2リーグは3のみ、Wood1リーグは1～3のみです。

毎ターン状態が変わる可能性があるので、毎ターン入力を受け取ります。

ゲーム盤の上に置く駒といったところでしょうか。 

2.4 SUN(太陽)ポイント

一言で言うと行動力で、行動するときに消費します。

 

3. ゲーム進行

3.1 ゲーム全体の流れ

1日を24回繰り返します。

ただしWood1リーグは6回、Wood2リーグは1回です。

それが終わるとゲーム終了です。

3.2 1日の流れ

1. 毎日の初めに、各プレイヤーはSUNポイント(行動力)を受け取ります。

2. 各プレイヤーは同時に行動を行います。SUNポイントが続く限り何回でも行動でき、両プレイヤーが行動終了するまで繰り返します。

3.3 SUNポイントの受け取り

木ごとにsizeと同じ量のSUNポイントを受け取れます。

ただし、Bronzeリーグ以上では、影の影響を受けた木はSUNポイントを発生させません。

影は日光が木に当たるとその木のsize分の長さだけ発生し、その木"以下"のsizeの木に影響を与えます。影になっている場所の木も影を発生させます。

日光は最初の日は左から当たっていて、毎日反時計回りに60度ずつ回転します。

3.4 行動の内容

GROW、SEED、COMPLETE、WAITの4つのコマンドがあります。

WAIT以外のコマンドは対象を指定しますが、同じ木を1日に2度以上対象にすることはできません。(ゲームルール上では休眠状態と表現)

WAIT

何もしません。両者がこれをすると1日が終了します。

COMPLETE

size=3の木(大きい木)を枯死させます。SUNポイントを4消費します。

得点を得て、対象の木は消滅します。

得られる得点は森の栄養価 + (土壌の品質-1) * 2ポイントです。

森の栄養価は最初20ポイントで、いずれかのプレイヤーがCOMPLETEコマンドを使うたびに1ポイント減少します。両者が同時使用した場合は2減少します。栄養価が0未満になることはありません。

COMPLETEを行った後の空き地は休眠状態ではないので、同一日に後述のSEEDコマンドの対象にできます。

GROW

指定した木のsizeを1上昇させます。消費するSUNポイントは、サイズと既存の木の数により異なります。

0→1 : 1 + 既存のsize1の木の数(自分の木のみ)

1→2 : 3 + 既存のsize2の木の数(自分の木のみ)

2→3 : 7 + 既存のsize3の木の数(自分の木のみ)

SEED

size=0の木(種)を発生させます。

既に持っている種の数と同じだけのSUNポイントを消費します。

種の発生源として既存の木を指定する必要があり、種とその木は次の日まで休眠状態になります。

種を発生させることができるセルは、発生源の木からそのsizeの距離までです。この距離は直線である必要はありません。また、土壌の品質が0のセルには種を発生させることができません。

このコマンドのみ対戦相手と衝突することがあり、その場合種は置かれずにSUNポイントは返還されますが、各発生源の木は休眠状態になります。

3.5 ゲーム終了

ゲーム全体の流れが全て完了するとゲーム終了で、より勝利点を持っているプレイヤーが勝利します。勝利点はCOMPLETEで得た得点に、ゲーム終了時に余ったSUNポイント3ポイントごとに1点を足したものです。勝利点が同点の場合は木が多い方が勝利で、それも同じなら引き分けになります。

ただし、ゲーム中に無効なコマンドを出力したり制限時間をオーバーした場合はその場で負けとなります。

 

4. その他情報

公式

コンテストのルール（規約）

サンプル的なもの

サーバソースコード

コドゲフォーラム：バグ報告、質問スレッド 解説動画(英語)もあり

非公式

CodinGameデバッグ補助手法

 

5. 終わりに

間違いや補足すべき事項があればTwitterかコドゲ内チャットでお知らせください。可能な限り修正します。

 

*1:いつもはhttps://twitter.com/tsukammoさんが書いてくださるのですが、体調不良とのことで代わりに書かせていただきました。

*2:枯死で点を得るという表現が直感的でないなら、ドングリの木を育てて木ごと収穫するという認識でも良いと思います。

Topcoder MM126 Slider 参加記録

TopcoderのMarathonMatch 126に参加しました。

問題はSlider。ブロックをスライド移動して穴に落とすパズルです。

 

www.topcoder.com

結果は登録157人、提出67人中(システスはまだ。provisional15位)でした。

 

問題

ブロックと穴がある。

ブロックは4方向に移動でき、移動数は[1]か[落ちるかぶつかるまで]。

ブロックを穴に落とすと[残ターン * ブロックの価値]の点を得られる。

 

考察

得点が高いものを早く落とすほど良さそう。しかしそのために無駄な手を打つとスコア倍率が減衰してしまい、その後得点が稼げなくなってしまう。そこのバランスが難しいということか。言い換えを使うと、「手数を最小に保つために高得点ブロックを後回しにした場合」「高得点ブロックを優先的に落とすために手数を増やした場合」はそれぞれ次のように表現できそう。

・8点のブロックを落とすのが100ターン遅れると800点の損失

・合計500点のブロックを落とすのが1ターンずつ遅れると500点の損失

seed=2などはブロックの合計点がとても高く、高得点ブロックを優先するよりも全体の手数ロスを避ける方が重要と言えそう。

 

評価関数をある程度リアルに作るなら、ブロック毎に何手で落とせるかを計算してブロック数[点][手数]みたいな配列に纏めた後に、評価が高いものから順に取る前提で何点になるか決める感じ？評価関数内でBFSするの、間に合わない気がする…。 

ルールベースかなぁ。

 

実装

まず最初に、プロトタイプの貪欲法を作った。各ブロックを4方向にMoveもしくはSlideして、全ブロックを最も近い穴との距離関係で以下のように評価。

-[ブロックの点数] * ([穴とのX差 ^ 0.5] +[穴とのY差 ^ 0.5])

seed=2で7.7秒かかり、動きもロスが多くて微妙な感じ。

これは使えそうにない。ルールベースへの移行を決意。

提出してないけど、Score84くらい？

 

次に、1手で落とせるブロックを高いものから落としていくようにした。高得点ブロックが奥に埋もれていることもあるので、直線上のブロックは纏めて落とす平均値も計算できるようにした。ルールベースというか、これは貪欲法では？　出来ることが無くなったらプロトタイプ貪欲をした。

この時点でScoreは95.7。

 

その次に、1回曲がった2手落としも出来るようにした。この時点では1手落としが終わった後に2手落としを行い、混在はできない。

この時点でScore97.1。

 

2手落としが終わった後のことを考えるが、1ブロック毎に何手も使うような手を探索するのはスコア的にも実装的にも美味しくない気がする。穴の向こう1段を全部壁に出来たら全部2手で落とせるけど、壁を構築するのは流石に実装難易度高いなー。あれ、壁は1枚あればスライドさせて使えるのでは？

で、ルールベースでシーケンス動作するようにしてこうなった。（動画は最終提出版）

 水平分割しかできないし、何処に何点があるとか全然考えてないしで、トップを狙えるような効率は出せないのだが、とりあえず全ブロックを2手+αで落とせるようにはなった。

これでScore97.3。

実装の重さの割に伸びないのは、これをやるのは既に終盤だからスコア上の重みはほとんど無いってことですかね…。

 

その後は微調整的なものが多かった。1手落としと2手落としを混在可能にしたり、シーケンス動作の効率化をしたり。2手落としの前倒しは、考察にもある損失で[前倒したことにより回避した損失]と[前倒したことにより発生した損失]を比較すれば実行すべきかが分かる。

Scoreに大きく効いたのは以下2つで、

・1手落としと2手落としを混在

・2手落としで0点ブロックは2手使って落とさずに1手で投げ捨てる

それぞれ0.5くらい効き、最終的にScore98.5でフィニッシュ。

やっぱり序盤～中盤の動きの改善の方が効くらしい。

 

やれなかったこと

・2手落としでストッパーになるブロックの扱い

高得点でも残すべきか、残すならいつまで残すのか

・2手落としで邪魔になる0点ブロックの扱い

落とす必要は無いので邪魔にならないような場所に寄せても良かったんだけど、その判定をお気持ちで行っていた

・2手落としが出来ない位置を落とすためにストッパーを作る

これを判断しなくても万能で動くのがシーケンス動作なんだけど、より効率を上げるために1～2手落としと混在させるのはきつかった。

・何らかの探索

実行時間が余りまくったので。多少ランダム要素を入れて10回回すとかでもやれば良かったかな。

 

皆の方針を見て

 この問題、ぼくのかんがえたさいきょうの方針が結構外れがちでしたね。

 

 ビームサーチ多様性の御株、完全に奪われました…。

 

よくばりセット、 お腹いっぱいになりそう。

 

こういうの出来たら強そうだけど、実装が地獄になりそう。

全体の操作が無効になる入れ替え処理もすべきか？とか考えると…。

 

TopCoderフォーラム:方針投稿スレッド

 

全体的には2手落としの(合計点/手数)による計算が鉄板で、

＋αの精度を高める何かをそれぞれやっていた感じでしょうか。

 

感想

いや、そのサイズの穴にブロックは落ちないだろ。

 

本当の感想

現実感のある評価関数を書けば応えてくれる、教養問題感がありました。ただ、それだけで到達できるのは98点(20位)くらいで、それ以上は各々の工夫が効いていたのかなと思います。私はそこで詰まってしまいましたが…。

今回は貪欲法(1手)と貪欲法(2手)を混在させて、終わったらルールベースのシーケンス作成と、手法の混在が酷かったですが、やはり終盤にメンテナンスで苦労しました。強い1つの方針で殴れるようになりたいですね…！　好き嫌いで言えばよくばりセットみたいなのも大好きなんですが。

 

 

AtCoder Heuristic Contest 002 Walking on Tiles 参加記録

AHC002に参加しました。

 

atcoder.jp

問題はWalking on Tilesで、最長路問題でした。

順位は参加2685人、提出1076人のうち1018位でした。

空文字を出力しただけです…。

 

問題

得点付きタイルの上を移動する。

ただし1x2や2x1のタイルもあって、その両方を移動することはできない。

移動済タイルを複数回移動することもできない。

 

考察

最長路問題はNP困難らしい。

 

ビームサーチ → 得点と移動可能タイルを両方評価するの大変そうだな。どちらかというとDFS系の方が強そう？

MCTS → メモリ制限がきつそう。

延長ルートを探す焼き鈍し → これはあり。

10x10の区画を25個に分ける → これもあり。区間内は愚直DFS？時間大丈夫かな…。開始位置によっては1つの区画を利用できない。かと言って区画を16個にしてしまうと時間が間に合わない。区画36個は…なんかロス多そう。

方針

10x10の25区画に分けるのをやって、区間を跨ぐ改善は追加で焼き鈍しかな。

 

結果

上手く行くケースは下のように上手く行く。

f:id:inani_waon:20210426002244p:plain

上手く行った例

だけど別の区画に入った瞬間に次の移動が不可能になることがあり、25区間完走はあまり出来ない。区画を移る際に、最後の移動位置で分けて複数持っておけば改善しそうではある。*1あとは完全に詰まった場合は区画を無視して貪欲するとか。

その辺はまだやりようはあったのだけど、実装時間が足りないのとWAが取れずに結局空文字を出力するものしか提出できず。

 

感想

かなりもやっと。

AHC001もだけど、低確率で発生するバグに殺されすぎですね…。

入力ファイルは改行コードが違ってそのままでは動かない、テスター兼ビジュアライザはバッチ実行できない、バグの再現率は低いのでWAが出るケースを大量に1個1個探さないといけない、とデバッグが苦痛すぎるので、これを改善できない限りはAHC（特にハーフマラソン）は手を付けないのもありかなぁ…。自前テスター作成は流石にハーフマラソンで作ると時間が大変なことになりそうだし。

終了後にまたバグが出るケースを探したけど全然見つからないので苦痛になってきて、これは一旦放置することにしました。良い感じに効率化できる方法が出てきたらまた考え直すことにします。

一応の反省点としては、どうせ焼き鈍しを入れる前提なら別ロジックまで重実装するのは冗長だったというのと、期待点が出るまでがあまりに長すぎて間に合わなかったので軽実装でバグりにくいシンプルなものから始めるという辺りですかね…。

一旦切り替えて、次のマラソンに臨もうと思います。コドゲに出たいのでMM126

はお休みかなぁ…。

*1:ただ、それをやる時間は愚直DFSでは無さそう。詰む場所をチェックしてそこをゴールから外すくらいが現実的かな。

天下一 Game Battle Contest 2021 Spring 参加記録

天下一 Game Battle Contest 2021 Springに参加しました。

 

github.com

問題は、天下一でよくある利益を他のプレイヤーと分配するタイプのものでした。

結果は参加者数不明のうち35位。

 

問題

タスクをこなすと得点が得られる。

タスクとはグリッド上の指定ルートを巡回すること。

具体的に言うとタスクは文字列として与えられ、文字に対応する座標を巡回する。

ただし、得点はゲーム完了時にタスク完了数に応じて他の参加者と山分けする。

タスクは10分ごとに追加される。60分以降は追加されるタスクの点が100倍。

 

考察

文字列は頭の方にあるサンプル以外はランダムっぽい？

文字数の多い物は移動コストが高い、文字間の距離が遠いものは移動コストが高いということで、美味しいタスクはかなり限定される。LUCK→KLABのように連鎖することで移動コストを抑えられるが、*1ランダムであれば有用なものは少なそう。

10分毎にタスクが追加されることを考えると、細かい調整はあるにせよ追加されたタスクで一番良い物を回しているとその間に新しいタスクが来るので以下ループという感じ？

 

やったこと

最序盤は美味しそうなやつを手で探して固定で回させてみたり。

序盤のタスクは不味いし後に繋がらないのでやめた方がいいですね…。

60分経過後は高いタスクだけ回すようにした。

移動コスト計算して時間コスパを調べるの面倒だなーと思いながら、もっさり実装。

同時に移動履歴を見て連結時の文字被りをチェックしたんだけど、何故か動かない。

この原因を探りながら、短いタスク同士で連結できないか目視確認したけどダメそう。

履歴が見れないの、サンプルのバグじゃん…と気づいた辺りで終了。

 

コンテスト終了時のタスク完了数の見積もりは、

現ペースの1/10のペースで増えるみたいな雑見積もり。

この辺は全然分かりませんでした。

 

終わってみて

・実はサンプルコードに必要以上のスリープが仕込まれていた

・同様に、同じ文字を繰り返す際に何故か画面中央に行って戻るようになっていた

・実はタスク文字列はランダムではなく、途中からタスク同士が完全に内包関係にあるようなものが出てきていた

・ルール説明上出てこない、重み（得点）1のタスクがあった

・C#のサンプルがバグっていて、そのままでは取得出来ないデータがあった

 

割と罠がたくさんあって、罠を避けるコンテストという面も大きかったなと思います。

体系化されたコンテストにばかり出るとこういうのへの対応力が落ちてくるのでそこは引き締めないとなーというポイント。

 

ビジュアライザのサイバー感がすごくかっこよかった。

 スクリーンショット取っておけばよかった。

*1:ガンパレードマーチ感。