inani_waonの日記

コンテスト覚書

AHC004 - Alien's Genome Assembly 参加記録

AtCoder Heuristic Contest 004に参加しました。

atcoder.jp

問題はAlien's Genome Assembly。

大量の部分情報から、全体の情報を推定する問題です。

提出者622人中104位でした。

問題

20x20のトーラス(縦横それぞれの端同士で循環する構造)があり、各セルにA~H(8種類)のいずれかが設定されています。縦横いずれかの連続したセルから2~12文字を測定したデータ(本記事上ではヒントと呼びます)が400~800件あります。辻褄が合うようにトーラス全体のデータを作成してください。*1測定データと合致する件数が多いほど高得点です。

考察

400セルに対してヒントが400~800件*長さ2~12あるので、同じセルに対する情報が多い。完全に部分文字列になっているものもありそうというところから始まり、重複文字が多いヒントは同じ場所から切り取った可能性が高そう、という考えに至る。登場する特定の長さのパターン数は最大400セル*縦横2方向で800パターンに対して、8^3が512、8^4が4096ということで、一致長が4~5あれば大体同じ場所から切り取ったと言えそう。*2

これで長さ20のヒントを2N本作れたら完全復元も可能だけど、運良く正確に準備できたとき専用の処理になりそうなので、それを頑張りすぎて他の実装が間に合わないと破滅しそう。

あとは縦横で組み合わせて上手く敷き詰めたい。完全回答の場合は空きスペースが多いほど高得点らしいけど、何処まで点が取れるか直感的に全く分からない。とりあえず完全回答は出来ない前提で進める。

貪欲を頑張るか、山登り系統か。スコア計算速度が絡むので両立は厳しそう。初期解が悪いと変形を頑張ってもスコア伸びなさそうな気がするし、貪欲かなー。

やったこと

前処理

ヒントのうち、完全に部分列になっているものを統合する。

それとは別に、2つの先頭と末尾で8文字以上一致するものを結合する。本来は5文字一致で良いのだけど、下記の理由により8文字となった。

・考察ミスでチキった

再帰的に動くので、更に短いものから始めるとタイムオーバーするケースがあった

・長い文字列を作ったはいいけど、配置が隙間だらけになって点が落ちるケースがあった

この辺りは愚直にやったうえ、後者は1つ結合する度に最初から再判定したのでとても重い。seed78のような重いケースだとこれで時間オーバーしてしまうので、本番ケースにタイムオーバーが無かったのは運が良いとしか言えない。それでもヒント情報が長いケースだと、貪欲を1周回しきれずに途中で出力しているものがあるかも…。

これの対策は、文字列を結合すると長くなるという性質を使って、短いものから順番に処理すれば最初から再判定するコストはかなり削れそうな気がする。本番中にそれを実装すると嫌な時間切れの仕方をしそうだったので断念。

貪欲

最初に一番長いヒントを左上に横向きに配置する。

その後はヒント同士で重なる文字数が多いように貪欲に配置。タイブレークでヒントが長い順にした。ヒントが長いものは隙間に入れにくいうえ、複数のヒントが結合されているので価値が高い。それでも同着ならランダム。

終わったら、時間がある限り最初から貪欲を繰り返して、一番いいものを採用。大根005とMM126で貪欲を1回だけして時間を余らせて悔しい思いをしたので、ここはもう失敗しないよう意識した。

やらなかったこと

検索を高速化するためのKMP法とかビット演算とか。

あとは、実はスペースとして使われている'.'は正規表現の任意1文字マッチの文字で、トーラスから切り取った文字列でヒント側に対して検索することも可能そうだった。*3

いずれも縦横それぞれ考えると重実装になりそうだった。

感想

今回は貪欲・焼き鈍し・ビームサーチという基本解法のみの人が多く、知識や発想の方針コンテストというより、実装力コンテストだったように思います。実装力にしても、WAで殺しにくるというよりは、高速化出来れば点に繋がるよという感じ。ただ実行時間制限がきつくて、愚直解法だと本番ケースは通るけどMと部分文字列長が最大のケースは通らないとか、はまりそうなポイントはありました。言語差もあるだろうけど、愚直解は最悪ケースでも通るようにしてほしかったかな。

文字列の連結や敷き詰めパートを高速に処理したいというと、高速なアルゴリズムを短時間で正確に実装する能力が問われるので、6時間という微妙…絶妙?な時間もあって、個人的にはアルゴコンテスト感も強く感じました。

何をするにも実装時間が微妙で逆に手持ち無沙汰になってしまったところがありますが、 はまりポイントだけ乗り越えれば解きやすくて楽しかったです。

*1:それは特定や推定というより捏造では。

*2:後に迷走して6まで厳しくしたけど、あまり影響は無さそうだった?結局貪欲で同じ並びになりやすかったのかもしれない。

*3:別に最終出力が'.'じゃないと出来ないわけではないが。

Topcoder MM127 - CarRacing 参加記録

TopcoderMarathon 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では無さそう。詰む場所をチェックしてそこをゴールから外すくらいが現実的かな。