HACK TO THE FUTURE for Youth＋オープン 参加記録

HACK TO THE FUTURE for Youth＋オープンコンテストに参加しました。

atcoder.jp

良い感じに連結して道を作る問題でした。

このコンテストは珍しくチーム参加可能、言及OKというお楽しみコンテストで、

ゆうさん、hotpepsiさんとチーム「びっくりするほど共通点がない」で参加しました。

結果は提出339チームのうち17位(オープンだけだと117チーム中9位)でした。

A問題手動解

問題

50x50のグリッド空間があって、ポリオミノ(ブロックが連結したもの)があるよ。

指定された点全てにブロックがあるようにポリオミノを置きつつ、ブロック全てを４近傍で連結させてね。

ポリオミノごとにコストが決まっていて、総コストが低いほど高得点だよ。

やったこと・考えたこと時系列

前日夕方～夜

チームメンバーが3人決まる。

オープン側はチームだと入賞特典が一切ないのだけど、開始前にチーム登録を済ませておきたい気分だったので勝手にSlackを立ててチーム名を決めに入る。*1

メンバー同士の共通点から名前を付けられたら良いなと思い、使用言語などの自己紹介をし合った結果、共通点が、無い…！

ゆうさん「びっくりするほど共通点がない」

私「もうそれがチーム名でいいのでは」

というノリで、チーム名決定。

hotpepsiさんはcompetitiveprogramming.infoというサービスを作った方らしい。凄い。

図を書ける場所が欲しいよー、と言われたのでGoogleのスプレッドを共有。GoogleのOffice系は図はちょっと書きづらいですね。miroとかいうサービスもあるらしい。

開始直後～1時間

社会性の塊なので、全員席にいる状態で開始。*2

皆で問題を読んで考察する。

誤読したり気付かない点があったりして、皆で読み合わせ出来るのありがたいの気持ちに。

Twitterを見るとA問題が配点割合的に大きそうということで、専任を置く方針に。

A問題 私（手動で頑張る）

B問題 hotpepsiさん（直線で繋げる）

C問題 ゆうさん（貪欲で点までの距離の総和を最小化）

で作業開始。

採用しなかったアイデアとして、焼き鈍しの他、各マスを左上として各ポリオミノを置くかで全探索チックに探索するというものも。C問題なら10種で50x50なので、11^2500から枝刈りする感じ？有効パターンが多すぎて流石にきついですよね…。*3

開始1時間～2時間

A問題は1.1M点ほど取得。（当時オープン3位タイ）

BC問題が何点まで取れるか不明だったので、相談して私もBC問題に着手。*4

相談中～BC着手直前にもAの解が生えてきて、A問題1.2M。

開始2時間～3時間

hotpepsiさんとゆうさんのプログラムがそれぞれ完成。

ゆうさんのプログラムがBで1.7M、CでTLE。Cは倍速化しないと無理らしい。

一応自分のプログラムは書きつつ、ゆうさんの押し上げを優先する方針に。

実装間に合わないよー、と言っていたらゆうさんがソースを丸ごとくれた。

Pythonをそのまま使うのは無理だったけど、コードが短かったので勇気が湧いてきた。*5

hotpepsiさんもゆうさんのプログラムをC++移植する方針に。

開始3時間～4時間

いや、誰もC通せないのは不味くない？

ということで、枝刈りや打ち切りしてでもとりあえず通そうぜと提案。

hotpepsiさんのアルゴリズム提案と私のセコい技*6で、残り25分でC問題をAC。

枝刈り部分にパラメータを使っていたので、25分で出来る事と言えば…

パラメータガチャの時間だああああ！！！

ということで、C問題を1.616M→1.651Mまで伸ばして終了。

総論

結果的にはPython使いを先行させて押し上げるという動きになりました。実装難易度に対して時間が足りない問題だったのもあって、上手くはまりましたね。*7

先行して結果を出してくれたゆうさん、別角度から攻めつつ的確なアドバイスでCを通せるところまで持っていってくれたhotpepsiさんに感謝…！

おまけ

A問題の手動での解き方

以下のことを意識しました。

・1つのポリオミノで多くの目標点を踏む

・目標点を踏むついでに遠くまで伸ばす

・手動焼き鈍し(一部を破壊して作り直す)

全体的にはコスト3ポリオミノの遠くまで伸ばす能力が高く、それをどれだけ活用できるかが重要な気がしました。また、全体的に横に伸ばす能力が弱い一方で縦はTが強く、孤立した場所は縦に繋ぐ方針が強そうでした。

感想

チームで出るマラソンなんてそうそう無いからという理由で急造チームを組んでみましたが、チームならではの戦い方が出来て楽しかったです。今度は実装でも活躍したい。

*1:終了後に、Discordで画面共有＋通話しながらもありだったかもね。うちらは言語違うからメリット無さそうだけど。という感想が出ました。ハーフマラソンなら確かにそういうのもありかも。

*2:私はお昼ご飯食べかけでしたが…。

*3:自明な枝刈りをしたり、1x1の個数を制限すれば少し希望が増すか？

*4:チャットだと何も言ってなかったけどゆうさん寄りのアプローチでやる予定でした。

*5:なお間に合いませんでした。

*6:置くポリオミノの種類を限定する、1800msで1x1しか置かなくする。

*7:そもそも3人チームを組めたこと自体が有利だった。

RECRUIT 日本橋ハーフマラソン 2021〜増刊号〜 農場王X 参加記録

RECRUIT 日本橋ハーフマラソン 2021〜増刊号〜 に参加しました。

atcoder.jp

問題は農場王X。連結成分を動かす問題でした。

暫定スコアは218M点で提出519人中80位、システスはまだです。

問題

16×16のグリッド上に野菜が生えてくるので、収穫機を置いたり動かして収穫してね。

収穫機は連結すると収穫時の収入が連結数倍になるよ。

1つの野菜は1～20ターンくらいで枯れて、全体ターンは1000だよ。

良かった、100ターンで岩になる野菜なんて無かったんだ。

考察

毎ターン平均5本生えて、平均10ターンもつので、任意の日に野菜が50個ある計算。

50/256は多いので、終盤は入れ食い状態になりそう。

となると、連結数を保ったままヘビゲームのように動くのが強いかな。

ただ頭と尻尾を固定する必要はなくて任意の場所に動かせるので多頭ヘビゲーム…ヒドラゲーム？*1

それから、空きマスを右往左往するのは弱いので、野菜に近い状態が嬉しい。

もっとしっかり言うと、多くのセルに対して近い状態が良い。

団子になるより、伸びた方が嬉しい。これはMM128っぽい。

全マスに対してM手以内にアクセスできる配置にして、そこから小さい操作を繰り返すのが強いとかありそう。

実装

現在～収穫機数(+購入1)ターン後の状態の野菜を見て、

遠隔地にジャンプするパターンとヘビ移動するパターンでそれぞれ収入を計算して貪欲。

遠隔地ジャンプは雑計算で、ヘビ移動は移動を縦横それぞれ1方向に限定したDP。

ヘビ移動は1ターンあたりの利益が高いマスに向かって動くが、利益があるマスまで移動したら一旦停止して再考する。移動元は塊を壊さない中で目的地に近く、将来の利益が低い場所とする。

ここまでやって約2億点。

あとは以下のような改良をするしかなさそう。

・読みの精度を上げる（主に移動元）

・複数手読みする

・お気持ちで良い感じに誘導する

全部それぞれ問題があって、移動元のシミュレーションは厳密に最適解を出すには処理時間がきつく、複数手読みも何をもって1手にするかが上手くはまらないと延長線上の2つを選ぶだけになり、そもそも移動元が正確でないと複数手読んだところで精度が低い。お気持ちパラメータは調整地獄。

上手く方針が定まらず、以下のようになった。

・全マスに4手でアクセスできるように固定盤面を作る

・消滅までの余裕ターンごとに0.1%ペナルティ

・将来の見込み的なものをお気持ち評価に加える

将来の見込みは移動完了後に出現する次の野菜の[価値/出現までの時間]や、将来的に固定となる場所に極小の固定値を加算。

固定盤面はこんな感じでH字に。上下端まで固定する設定にしているけど、偶然踏んだときに固定するので上下端まで固定されないことも多い。水平部分は収穫機20で固定されて、垂直部分は収穫機が増えるごとに少しずつ固定する。

没方針

・移動元の利益を逃す分も計算する

速度の都合で前計算と実移動で別ロジックを使った結果、外した方が強い状態に。悲しい。

・DP範囲を遠くまで伸ばす

遠い≒不味いで、短い動作を複数することも考慮できなくなるのであまり効果が無い？

・序盤のジャンプ移動を上手く連続動作できるようにする

色々やってみたけど誤差レベルだった。

・購入を連続動作の途中でも可能にする

何故か劣化した。なんで？

・出現待ちを伴う挙動は避ける

劣化した。

・複数手読み

移動元の計算を高精度でやるのが前提だったのと、確実に上がるビジョンが見えなかったので断念。順位表を見た感じ（コドゲ勢が強かったので）当たりっぽさはあったんだけど…。

他の人の解法を見て

収穫機の連結はUnionFindでチェックしていたが、グラフの関節点と橋を求めるという方法があるらしい。

あとはやはり、上位陣はビームサーチなどで複数手読む人が多かった。

感想

解法の自由度が高い分、実装は重いのに道が見えなくて苦しいところがありました。

DP+貪欲で取れる点は取った気がしますが、工夫で伸ばすフェーズがお気持ちばかりなのでもうちょっと何とかしたかったですね…。

しかし順位だけみるといつものAHCよりは順調で、やはりMMに近い問題だったなと思いました。

*1:それは別のカテゴリでは。

RECRUIT 日本橋ハーフマラソン 2021 参加記録

RECRUIT 日本橋ハーフマラソン 2021（増刊号じゃない方）に参加しました。

atcoder.jp

問題は2つあり、手順を最適化するものと、組み合わせを最適化するもの。

結果はAが提出478人中79位、Bが提出434人中148位でトータル109位でした。

問題A - 魔法使いXの戦い

300体いるモンスターの強さをバフでオーバーフローさせて弱くしてね。

バフはいずれかのモンスターの強さをいずれかのモンスターに与えて、10^8でModを取るよ。

考察

300体のモンスターに1000回のバフなので、1体あたり3.3回ほど。

バフをかけると次回以降のバフに影響が出るので、静的な評価は無理そう。

5000K、2500K、1250Kに近い値を3つ使えば全てのモンスターを1250K以下に出来そう。

ただスコア計算がLog2(強さ)で決まるので、1250K以下にするだけではスコアが25%にも満たない。

前情報だと日本橋ハーフはいつも貪欲＋ビーム（＋焼き鈍し）ということだけど…。

実装 

 とりあえずビームで20手読んでは10手動かしてみたいなものを組んでみる。

→2秒で1000手動かせるはずもなく…。（10手強しか動かない）

 最終的には5000K、2500K、1250Kを残してその他を1つずつ3手ビームで読む形に。

 複数手を復元というのはコドゲOptimizeの2048でやっていたので移植する形で持ってきたのですが、復元結果が2手だったり3手だったりでよく分からない挙動をしていました。動いてるからヨシ！

後日談

とても小さいグループととても大きいグループを作って掛け合わせる方法が強かったみたいです。150:150のグループに分かれて、一方のグループの最悪値を最高値付近まで持っていけるので0orKとの差を1/150に出来るっぽい。

そうすると貪欲というイメージが強いのですが、要は1手あたり1/150相当の改善ができればいいので、2手読みも交えることで350K強(本番1位以上)のスコアが取れました。

また1体ずつ仕上げる場合は半分全列挙という手法が使えるようで、試してみました。今回は重複選択を許す、かつ自分自身を何回も選ぶと計算が狂うので省きたいという要件だったので、元になるモンスターを固定し、全域から選んだものを1回掛け、それに対して(前半グループx2)と(後半グループx2)をそれぞれ二分探索しました。

二分探索するせいで条件などにあまり融通が利かないので、要件に合わせて都度仕様を考えないといけないタイプの手法かなぁと思いました。 

問題B - マッサージチェア2021

40x40のグリッド上にマッサージチェアがあるよ。

品質×パワーで嬉しくなるけど、音がうるさいと近くの席が使えないので良い感じに調整してね。

考察

これは焼き鈍しかなぁ。

品質にはかなり偏りがあり、実際に調べてみると品質8以上が100/1600個。品質1をガチャガチャしても実入りが少なそうなので、ある程度高い物に絞った方がよさそう。

近傍はパワーの変更だろうけど、干渉をどうするか。巻き込む場合は相手を消す、巻き込まれている場合は高確率で再考にしつつ、稀に相手を弱める感じかな。パワーの変更も、ランダムな値にするものと、可能な範囲で最大にするものがあると良さそう。

実装

まずは市松模様でパワー1を並べて提出してみる。

点が上位の半分くらい取れていて、あまり爆発的に点が伸びるタイプではないことを理解。

あとは素直に焼き鈍しして、焼き鈍し後に貪欲でパワーを拡張してフィニッシュ。

空いてる場所の品質が低い椅子も使えるようにできたら良かったんだけど、品質が高い椅子だけを管理する構造で作ってしまったのもあり、そこは時間が無かった。

焼き鈍しの途中経過を見守る時間も無かった。

後日談

使用する椅子だけを決めればパワーはとても簡単に最適解が求まるらしい。言われてみれば、それはそう…。

そうなると焼き鈍しじゃなくて探索が使えるんじゃない？という話はちらっと出たものの、品質8で100個あるとなると組み合わせも2^100あるわけで、なかなか大変な気がする。探索の順番を工夫する（品質もだし、なんとなく距離が近いものが探索順も近いと良い気がする）、DFS要素が入った探索を使う（chokudaiサーチやMCTS）、そもそも探索の内容を工夫する（個々のON/OFFでなく1個ずつ順番に付けていく）などなど手を尽くせば出来る余地はあるのかなぁ…。

感想

上に行くには天才の閃きが必要なタイプの問題だったと思いますが、駄目方針なりに楽しくやれたかなと思います。

4時間で2問という特徴もあり、交互に大きい改善から入れていく慌ただしさも新鮮でした。

脳死でビーム！焼き鈍し！でやりましたが、今回はそれに甘えすぎた気がするのでしっかり分析したいですね。

ColorShapeLinks AI competition 2021 参加記録

ColorShapeLinks AI competitionに参加しました。

videojogoslusofona.github.io

変則4目並べのゲームAIコンペです。

結果は10チーム中、Base track同率1位、Unknown track1位でした。

Base Trackで1位タイと1勝1敗になった以外は全勝です。*1

ルール

Base track

二人零和有限確定完全情報ゲーム。

幅7高さ6のグリッドがあり、列にブロックを落とす形で交互にブロックを配置する。自分のブロックを直線上に4つ連続で揃えると勝利。お互い揃わずにグリッドが埋まった場合は引き分け。

ここまではConnect 4というゲームと同じルールだが、Connect4との違いとしてブロックは4種類あり、それぞれ色と形状*2を持つ。色は自分の色のブロックを持つが、形状は互いの形状のブロックを半々くらいで持つ。自分の色か形状を4つ連続で揃えた側が勝つが、同時に揃った場合は形状が優先される。

Unknown track

ルール自体はBase trackと同じだが、幅、高さ、勝利に必要な連結数などが投稿締切後に決定される。*3

今回は幅37、高さ9、勝利連結数5。結構な変態設定である。*4

考察

二人零和有限確定完全情報ゲームだし、1手の選択肢が(Cols * 2)種類、終局までの手数が(Rows * Cols)しかないのでMCTSが順当に強そう。

実装

MCTSを書いて、前向き枝刈りをしました。*5

1手先と2手先の極一部を読んで、必勝の手は強制、必負の手は禁止しました。

あとはGC対策でノードを使いまわすようにしました。

コンテスト環境的な話

独自プラットフォームのコンテストでしたが、ゲームAIコンテスト慣れしていてC#が書ければやりやすい環境だったと思います。

・ドキュメントは凄くしっかりしてる。

・ゲームルールもシンプルで綺麗に纏まっているので楽しめる。*6

・言語はC#のみ。

・ゲームサーバはUnity版とコンソール版がある。*7

・タイムアウト判定がちょっと怪しい。50msくらい早めに打ち切る必要があった。*8

・ゲームサーバ側がクライアント（個々のAI）を監視していて、時間がかかると切断して終了してしまうので、デバッガで値を追うのが難しい。*9

・特定の組み合わせで1000戦するみたいな仕組みは無いので強さの評価はしにくい。

・ローカルだと既存の対戦相手が弱めのサンプルしかいないので、やっぱり強さの評価がしにくい。*10

・提出はメール添付。エントリーもメール。*11

感想

コドゲのSpringChallenge 2021でも前向き枝刈りをやりましたが改めて、プレイアウトの精度を上げるのめっちゃ強いな…となりました。またノード展開時の挙動に関して言えば、MCTS-Solverに近い働きもしてくれていると感じました。

今考えると今回のゲームは"細い短い枝の先に逆転の手がある"系統だったので、そういうゲームと前向き枝刈りは相性が良かったんだろうなと思います。

あとGUI版、おでんにしか見えない。

*1:互いに後手が勝つ状態だったらしいです。

*2:白と赤、丸と四角。

*3:海外の宝くじの結果を見て決めるらしい。こういうの面白くて好き。

*4:22超えは想定していなかった…。

*5:展開とプレイアウトの両方です。

*6:Base trackは狭く感じるかも。

*7:私はコンソール版だけ使った。

*8:ローカルでコンソール版だと1ターン目に計測されない時間を含んでいる様子があり、提出サーバでは50ms弱のスパイクが割とあった

*9:無理矢理押し切ったけど、別のエントリーポイントを作るか単体テストを使うと良さそう。

*10:過去の自分と戦わせるか提出するしかなさそう。

*11:英語だけど短文のやり取りだったのでGoogle翻訳で快適にできた。

AHC005 - Patrolling 参加記録

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

MM128の疲れが取れていないんですが…。

atcoder.jp

問題はPatrolling。低コストな巡回ルートを作る問題でした。

結果は12,224,847点で、提出561人中、192位でした。

考察

まず事前のメタ読みとして、高校生のマラソン大会と同じ問題なので、高校生程度の知識で解けるある程度素直な問題が出ると予想。

全ての道を視界に入れるには、全ての交差点を通れば良さそう。あとは全ての交差点を通る最短ルートを構築すればよさげ。全ての点を通る最短ルート…あ、これTSP(巡回セールスマン問題)か。そうなると2-optのライブラリは事前に作ってあったので、あとは問題固有の場所を実装すれば良いっぽい。

通るべき交差点は上手く組み合わせれば削減出来そうだけど、まずは最低限のコードで取れる点を取るところからやろう。

グラフがちょっと複雑かな。移動コストがちょっと特殊で有向グラフになりそうだけど、各交差点を1回ずつ通るという前提を付けることで交差点間の経路のみのコストを取って、無向グラフに置き換えることができた。

実装

まずは交差点の列挙、交差点間の移動コストの計算、交差点→交差点の移動ルートの計算と出力、といったところをやる。多対多を求めるせいか、頭がバグって冗長な計算をしていた…。（普通にグリッドベースのダイクストラで良かったんだけど、前処理してから交差点間でワーシャルフロイドしてた）で、まあまあ時間ロス。(90/240分)

次に2-optライブラリを貼る。…んだけど、座標間のマンハッタン距離を見る形のライブラリになっていたので、計算済みのコストを与える形に改造。こういうのは何度か実戦投入してみないとどういう形がいいのか分からないことも多い。動かしてみると初期解から全然変わらない…であれこれデバッグしてみると、ライブラリ自体は問題なくて処理結果を見ないコードになっているだけだった。で、滅茶苦茶時間ロス。(200/240分)

ここでもうほとんど時間が無くて、雑に交差点を削減するところを書いたら交差点間のコストを取得するところと干渉して動かなくて、あと5分あれば動くのに～というところで終了。

感想

writer解は見つからなかったけど、やはり使用する交差点の選定と、使用する交差点でのTSPが肝の問題だったっぽい。あとは2-optじゃなくて2点swapが強かったとか？ただ交差点の選定の方がより重要だったらしい。

重要パートまで行けなかったので、はい。実装も凡打でもとりあえず打てたのは良かったですかね…。いや、これは良くない。ライブラリ無ければ破滅してましたよね？*1

4時間コンともなると1箇所詰まるだけで破滅するので大変だと思いました（小学生）

ワーシャルフロイドを初めて書いて理解したのと、2-optライブラリを初めて実戦投入出来たのは良かったです。

*1:ライブラリのせいで破滅してた気もする

Topcoder MM128(TCO21 Regional) - BallSwaps 参加記録

TopcoderのMarathonMatch128に参加しました。

www.topcoder.com

問題はBallSwaps。良い感じに連結成分を作る問題でした。

事前テストは70人中7位。

地域毎の順位で賞金が出る大会なんですが、これで日本4位って魔境すぎませんか？

MM128 Seed2

問題

N*Nのグリッドがあり、各セル内に1つボールがある。ボールはC色ある。

隣接するボール同士を交換して、色毎に1つの連結成分になるようにせよ。

 （その手数を少なくせよ）

考察

中間状態の評価が難しそう。

●●●●

●●●●

●●●●

●●●●

こういう状態とか。反復横跳びが怖い。となると、青写真を作ってからそれを完成させる感じか。なんかMM123っぽい。

どんな青写真が良いか考える。移動数を最小化するためには、初期配置に近い青写真を作りたい。初期配置は各色のボールが多少の偏りはありつつ満遍なく散っている状態なので、そのような配置を取りつつ上手く連結できる図形にしたい。

蛇腹ボーダー

●●●●

●●●●

●●●●

●●●●

これは上下に0～N手必要で、1ボールあたりN/2手かな。

単層渦巻

●●●●

●●●●

●●●●

●●●●

計算しづらいけど、これも上下に各0～N/4手でN/2手くらいか？蛇腹ボーダーよりちょっと良い気がする？（実際は蛇腹ボーダーより有意に優位っぽい）

ブロック

●●●●

●●●●

●●●●

●●●●

なんか良くない気がする。上下に各0～N/2手でN手？実測すればもうちょっと良い気がするけど…。

多層渦巻

●●●●●●

●●●●●●

●●●●●●

●●●●●●

●●●●●●

●●●●●●

ド本命。部分的に見ればC個のブロック内で色交換するだけなのでC/2手。Nが大きくCが小さいケースほどこれが強くなる。ただ、NがCの倍は必要かな。NがCの倍数じゃないケースとか、生成ロジックが難しそう…。

江戸でペンキ塗りのアルバイトをした経験が生きた。

初期版は単層渦巻で決定。完成次第多層渦巻を作ったり、左右上下反転や回転、別パターンから最良を選ぶ感じかな。あとは色の順番によって違いが出そうだから、ハンガリアン法で二部マッチかな。ますますMM123っぽい。

実装

単層渦巻で57点。端から渦巻状に、一番近いものを持っていく。意外と良いスコア。

どのボールを目標地点に持っていくかをハンガリアン法で決めて、コストの目安にする。移動中に他のボールを巻き込んで盤面が変わるので、贅沢に1個ボールを動かす度にチェックする。また、コストの目安が出来たので、色の順番を全列挙する。Nが大きいと全て回らないので時間制限付き。移動経路のボールが移動するので厳密なスコアは出せないんだけど、大体上手く行くっぽい。これで77点。勝ったな（確信）

残り2色くらいになったとき明らかに無駄だなーという動きをしているんだけど、汚い解決策しか思いつかない。そういうので変なコーナーケースで沼にはまりたくないんだよね…。

多重渦巻は†Excel†でテンプレートを作って良い感じに加工することにした。82点。強くはなったんだけど、周囲の伸びが強くて追い付けない…。

最終日に晩御飯を食べながら10000件耐久テストを回すと、失敗しているケースを4件ほど発見。テンプレート加工時に孤立ボールが出てしまうらしい。UnionFindでチェックを入れて対応。せっかくなので、終盤に「実は完成してるけど青写真が完成するまで続けるぜ！」みたいなのを検出できるようにした。logだしハンガリアン法のN^3に比べたら全然重くない。

移動経路を踏み荒らすやつの改善が出来るか試行。既に青写真と同じ色のボールが乗っているところは避けるようにしてみる。微改善。移動により青写真と同じ色のボールを乗せられるなら優先通過するようにしてみる。悪化。なんで？ → これDFSだけでやってるのでキューの順番が狂ってる気がする。DPやダイクストラにすると多少違ったかも？

ついつい大きいケースを見てしまうんだけど、小さいケースも大切。時間余ってるしね。単層渦巻は左右・上下反転も試行するようにした。これでseed=1が10→8stepに。

あとはテンプレートを調整する感じで、81点で終了。やりたいことは大体やりきったかな。これで勝てなかった人には完敗。

他の人の解法を見て

渦巻や多層渦巻をベースに変形操作して、初期配置に近い謎のうねうねした形を作るのが強かったっぽい。

ついつい避けてしまう変形解法、もっと鍛えないとなぁ…。

感想

MM123[中の人パズルゲー]の再来という感じも少しありましたが、そこからの変形解法が強かったり、コストを厳密には計算できないけどなんとなくで進めていくところなど、とても面白かったです。サンプルコードがAC不可コードだったので初動は結構大変でしたね。

TCO Finalの練習のつもりでやりましたが、最後にFinal参加者の人達に抜かれて惜しかった…。今回分かったのは短期間マラソンではやれる事しか出来ないということ。Finalは8時間(かも)なので、調査無し(というかライブラリ貼るだけ)でも出来る事を増やさないといけないですね。

あと日本強すぎ。次からEast JapanとWest Japanで分けませんか？

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:別に最終出力が'.'じゃないと出来ないわけではないが。