HACK TO THE FUTURE 2022 本選 - Code Golf for Robot Vacuums 参加記録

HACK TO THE FUTURE 2022 本選に参加しました。

atcoder.jp

問題はCode Golf for Robot Vacuums。独自言語でコードゴルフする問題でした。

Code of the Rings？知らない子ですね。

結果は提出54人中19位、オープンも合わせると提出186人中29位でした。

問題

単純なコマンドを組み合わせて全セルを巡回してね。

繰り返しとかも出来るよ。

考察

これは左手法*1が強そう。

あとはAHC005に似てるかな。半端に効率の良い場所を探すより、愚直に一番近い場所に行くのを繰り返した方が強い可能性がある。

直進、左手法、右手法、と組み合わせるだけで、最短距離の最適化だけならかなり出来そう。ただ、向きの概念があるので400セル*4方向で1600状態。辺は1600*1600、ゴールをセルだけに限定しても1600*400か。ワーシャルフロイドは間に合わないな。

ということは、複数命令の組み合わせの前計算は諦めて、単純な命令の組み合わせでやるしかないか。

実装

～1:30

壁が与えられるという入力形式に慣れておらず、受け取ってデータを構築するのに難儀。

固定コマンドで400(rF)とか試してた。これくらいだと狭い場所にはまってしまうことが多い。

ん－、まずは簡単なもので完成させないと辛そうだな。

～2:30

とりあえず、左手法でいずれ大幅にコマンドを削減できるとしても吸い残しは出るはず。

スコア計算的に全マス掃除できないと低得点なので、まずは貪欲に全マス掃除を目指してみる。TSPまでやらないなら、残りを吸うのも全部吸うのも実装的には同じだしね。

とりあえず雑に、方向は考慮せず距離だけでDFSしたコストで、歩くのも1マスずつ。

9.5M点。結構出る。

～5:00

繰り返しの表現だけど、命令をCompositeパターン風に構造で持つことにした。これをすると3(5(rF)5(lF))みたいな複雑な構造にも対応できるのが良いところ。*2それから、「突き当りまで移動」のような意味のある行動を理解させれば、「R3FR2FR6F」のような命令を「3(R9F)」のように出来る。*3逆に2RFRFRFをR3(RF)にするような、構造の途中でぶった切るのは苦手そう。そういうのに対応したいならランレングス圧縮も良さそうだけど、*4ライブラリとして持っていないのでぶっつけ本番は怖かった。

連続したLRFのそれぞれを繰り返すだけで10M点。

コスト計算は、Fを繰り返す際に「Fの度に必ず1回曲がる(Uターンは考えない。*5最初の1回は別途差分計算すればよい)」「長さが2桁になる通路はそんなに無い」の2点を前提とすると「L9F」のように3文字に置き換えられる。1マス進むなら「LF」のように2文字。*6なので、優先度付きキューを使ってコストが低い順にDP*7をすればほぼ最低コストとなるものを求められた。*8

これで11M点。

～6:10

左手法と右手法を実装。

400[L3rF]のようにした。7～8文字程度の命令なので、大体4マス掃除できるなら左手法を優先するようにした。特に外周を回るのが強くて、9文字で130～180マス程度一気に掃除できる。

18M点。

～6:40

スコアが伸びず迷走。

愚直に移動するより左手法の方が短ければ左手法にしてみたり、一度直進が終わったタイミングで再考させてみたり。

貪欲スコアを[掃除可能マス/移動コスト]にするのも試してみたけど、やっぱり劣化してしまう。やはりここはAHC005方式で良いらしい。

ん－、壁をTSPするのか？いや、実装無理だろ…。

得点は微増。

～7:40

左手法が終わった後(左手法で掃除できる最後の汚れを掃除した後)、次の動作に繋がらずに愚直に動いてしまうことが多い。

繰り返し回数は0～1コストで増やせるので、上手く動作同士が繋がるようにしたいんだけど…。

うーん、汚れに隣接するまで延長すれば良さそう？汚れが無い場合は相変わらず分からないので最後の汚れの位置で。

これで19M点。あとはパラメータガチャして終了。

終了時のseed0のビジュアライズはこんな感じでした。

他の人の解法を見て

左手法は[LrrF]で良いらしい。*9コマンドの長さは一緒だけど、一応命令展開後の実行回数にも制限があり、そちらが節約できる分優秀。

全体としては、200(2(LrrF)3(RllF))のように、左手法と右手法を適当な回数で交互にやるのがとても強かったらしい。交互にやるのを更に繰り返すのは、かなり適切な値を埋め込まないと動かない気がして諦めたんだけど、割と動くんですね…。

感想

まず左手法を知らないと爆死するのと、*10それを上手く連結するのも天才的ひらめきが必要そうなので、天才向けコンテスト感が強かったです。

スコアにはあまり響かない部分でしたが、方向や変則的コストを考慮した最短経路の計算はやりごたえがありました。

余談ですが、今年はオープンでない本選に出場できたので、グッズや懇親会用の夕飯などをいただきました。食べながら書いています。ありがとうございました！

*1:左手を壁に付けて歩くと、いずれ同じ場所に戻ってこれるという手法。

*2:最終的にはそこまではやらなかった。

*3:最終的にはそこまではやらなかった。

*4:出来たっけ？

*5:快特の後で1駅戻るみたいなムーブは、2回曲がる必要がありコストが高い。

*6:改行コードではない。

*7:ダイクストラ？

*8:よくよく考えると2桁の長さならコスト4にすればいいだけである。

*9:一見折り返しできないんだけど、2回かければ出来るしそもそも行き止まりは存在しないらしい。

*10:意外と知ってる人が多かった。何処で知ったんだろう？

THIRD プログラミングコンテスト 2021(AHC007) - Online MST 参加記録

THIRD プログラミングコンテスト 2021 （AtCoder Heuristic Contest 007）に参加しました。

atcoder.jp

問題はOnline MST。不完全情報から最小木を作るインタラクティブ問題でした。

結果は提出632人中158位でした。ジャスト上位25%。

問題

予測値でなんとなく最小木候補を作ってあるけど、実測値で改めて作り直してね。

辺のコストを1つ受け取るたびに、その辺を採用するかを決めてね。

コストは距離(事前に分かる)の1～3倍の一様乱数だよ。

考察

候補辺の生成方法が最小木作成の抽出*5回なので、複数候補のコスト値はかなり近いものになっていそう。

とはいえとりあえず実距離で最小木を作って、受け取った実コストを見て変更をかけるのが本筋かな。

コストの他に可能性の大小という要素があって、見送っても代わりとなる辺(より低い、悪くても同程度のコストで最小木を構築できる)があるなら採用見送りしやすい。

モンテカルロも有効そうだけど、チューニングも考えると実装時間も実行時間も厳しそう。

実装

～1:00

とりあえず距離で最小木を作成。12,602,465,243点。

1位が14G強なので、1割強上がる感じか。

～1:12

一括実行のスコアを拾ったりするデバッグ環境を整える。

～1:56

実距離の最小木(0手目に1回作成)を保持して差異を判断するつもりだったけど、場合分けして差分計算って残り2時間でバグ取りまで出来るのか？そもそも拾い落としも多いよな？と考えて、厳しそうなので毎回最小木を作る方針にシフト。

～2:16

動いた。1割くらい上がっているけど1ケース10秒かかってる。(制限は2秒)

～2:46

2秒程度に速くなったけどバグって解が壊れた。苦しい。

～3:30

直った。

一番効いた高速化は、辺を予めコストの昇順にソートしておくこと。

なお、バグはここで採用を見送った枝が残って悪さをしていた。

お祈りしてsubmitすると、1秒弱でAC。13,915,411,325点。

…いや、順位低くない？

～3:50

橋でない場所を検出して、見送りすれば後で改善される確率みたいなのを求めてみる。

あの、橋でない場所が無いんですが…。

～3:59

未知の情報への期待。なんか聞き覚えあるな…。あ、AHC003か。あれは未知の道の見込みコストを期待値より下げたんだったか。0.9倍、0.85倍、0.95倍と10ケースほど試して、0.9倍が一番良かったので採用。*1

実際は序盤は改善可能性が高くて終盤は低いので、一律0.9倍でない方が良さそうなんだけど、残り90秒では調整もできない。

14,079,155,614点で終了。

…いや、順位低くない？(2回目)

やり残し

・0.9倍部分の可変化

・端数処理が雑だった(四捨五入の箇所を切り捨てにした)

他の人の解法

上位はモンテカルロで数十～数百回シミュレーションしてる人が多かった。

私は辺のコストを1つ受け取るごとにクラスカル法+UnionFindで最小木を作って1000ms前後かかっているので、2回しかシミュレート出来ない。*2何らかの高速化が出来ないと駄目そう。

writer解はDPらしい？*3

同じ解法で私よりスコアが高い人もいたけど、端数処理をしっかりした、同値でどちらを優先したかの差、辺りかな。倍率可変の人はやっぱり少し上らしい。

感想

苦手な短期マラソン(4h)にしては頑張ったというべきか。ロスも多かったとはいえ、ちょうど時間内に大きな改修をやりきったので身の丈に合わせて方針を選べるようになったというのは良い所。

高速化でバグったときにAssertを仕込んでみたらあっさりと解決したので、今後も不味そうなときは使ってみたい。あと、やる事は同じ高速化でも、コミット単位は小さくした方が良いですね。どの箇所でバグったか明確になるので…。

見えてる情報からの最善は選んだけど、可能性部分はあまり深堀り出来なかったかな。橋でない所はまず無いとかはビジュアライザを見れば気づけたので、まだ余分な動きはある。*4*5そこをやらなければ倍率可変化は出来ていたので…。

あと今回はUnionFindをとても多用する回だった。今まではUnite回数≒Root回数の用途が多かったけど、今回はひたすらRootが多かった気がする。ここのバランス次第でUnionFindの最適な実装が変わってくると思うので、実験してみたいかな。

*1:1発目のパラメータが最善になる確率、高いがち。

*2:辺が前回作った最小木に含まれず、かつ想定コストより悪かった場合は即決で非採用にして処理軽減している。大体半分刈れてる？

*3:wataさんの想定解は解法としては強いんだけど、ハズレを引いたとき何も残らない方針が多いので、本番では余程考察と実装に自信が持てていないとやりにくそう…。

*4:可能性要素を盛り込みたいばかりに釣られた。

*5:というかそもそも最小木には橋しかないのでは？

TCO21 Finals Marathon Match - CoinCollector 参加記録

TCO21 Finals Marathon Matchに参加しました。

これはTopcoderMMの2021年決勝で、リモートで監視員に見守られながらの24時間コンテストでした。*1

問題はCoinCollector。ダイスで移動して、グリッド上のコインを集める問題です。

参加者12人中、暫定テスト10位でした。

問題

本文

N*Nのグリッドがあるよ。これは上下と左右でループするトーラスだよ。

グリッドの各セルはコイン、棘、空きのいずれかだよ。

コインを取ると得点が増えるけど、棘を踏むと得点が半減するよ。*2

コインは取ると消えるけど、棘は消えずに残るよ。

方向と手持ちのサイコロを選んで、出た目の数だけ移動するよ。

サイコロは12種類あって、使ったサイコロは無くなってランダムに補充されるよ。(ケースによって2～6個持てるよ)

終了はN*Nターン、もしくは任意にいつでも。得点をたくさん取ってね。

サイコロの種類

• 1～6のいずれかが出る6面ダイス1種
• 0,1,2,3,4,5,6の1つが出る1面ダイス(?)7種
• 奇数、偶数、123、456が出る3面ダイス(?)4種

出る目の種類数が、そのままランダムに補充される確率の比となる。

0のダイスを無視すると、特定の目を含んだダイスを引く確率が約50%となる。

制約

N グリッドの1辺のサイズ 8～30

D 持てるダイスの数 2～6

ratioC コインを生成する確率 0.10～0.60

ratioS 棘を生成する確率 0.15～0.40

実行時間制限 10秒

時系列進捗

これは僅かなメモとgit履歴から復元しているので、時間の正確度は低かったり、没方針を書いていないがちです。

04:00

始まったらしい。まだ寝てる。

07:00

起きた。PC周りの環境最終調整。まだ眠い。

07:30

会場入り。

参加するためのUIが見つからないが、TCOの人に声掛けしてもらって開始。

ゲームAIっぽいので、貪欲法が書けないレベルの破滅はなさそうで一安心。

とりあえず考察だけ。

棘を踏むと得点が半減→これはMM122マインスイーパ。一度踏むとリスク許容ボーダーが変わって、踏み続けて破滅するやつだ…。

棘を回避して移動→これはボードゲームのマラケシュっぽい。複数手読みが大事そう。

あとは、この手の問題ではありがちな、早くコインを取るボーナスが存在しない。安全にじっくり行けということか。

順調でも終盤でミスると最悪0点付近まで落ちる問題なので、綺麗に終局させる処理が必要。動かすロジックと終局の判断は相互に絡むところもあるので、堅実にやるなら両方を少しずつ強化していくしかないか。

サンプルコードを投げて朝食へ。

カメラは切っていいけど画面共有はそのままにしてね、とのことだった。

8:15～9:15

朝食。

9:15

朝食前に投げていたサンプルコードがCE。

解析すると、実行環境に"csc"というコマンドが無いらしい。

csc…C Sharp Compiler？

これは環境側の問題臭い。フォーラムで報告して、修正を待ちつつ作業開始。

方針はざっくり4つ。MCTS、ビームサーチ、原始モンテカルロ、ルールベース。

・MCTS

　MCTSに落とせれば強いんだろうけど、確定ゲームでないことと、実スコア以外を評価にどう盛り込むかがネック。遠くのコインは2,3手では取れないだろうし。

・ビームサーチ

　上に同じく。ただMCTSよりは作りやすいかな。

・原始モンテカルロ

　頭を使わなくていいのが強み。ただシミュレーション結果が偏って悪手を打つと、1ミスで悲惨なことになるからなぁ…。平均パフォーマンスが高くても、安定していないのは不安が残る。

・ルールベース

　1行ずつ順番に取っていけば1次元の問題に落とせる。天才か？

　→ratioS=0.40の地雷原を見て絶望。4マス連続の棘とか越せるわけないじゃん。

没ったルールベースはともかく、他3つは全てダイス目をランダムとしたシミュレータが必要そうか。*3

一番簡単そうな原始モンテカルロから始めてみる。1手読み、シミュレーションは各動作100回くらいで、評価関数は手持ちのダイスでコインや棘に到達できる確率(その結果の得点)のbestと、直線上にコインや棘があるかをメインにする。あとは手持ちダイスの多様性と、択が少ないダイスを持っている方が嬉しそう。*4

0のダイスは全く使い道が分からなくて、ここはルールベースで棘の上にいないなら即使うようにする。棘の上で使うと更にスコア半減するのか調べたかったけど、結局最後まで調べなかった。

13:05

原始モンテカルロを書き終えて動作確認。バグで横にしか動かない…。

＞＞反復横跳び＜＜

13:20

ちょうどC#の提出バグを直してもらえたので、提出。CE。

MMのC#ばーじょんでは たぷるは つかえないぞ！（本日1回目）

13:35

サンプル以外で初AC。26.93点。

得点はすこぶる悪いが、終局処理を丁寧にやればある程度上がるのは見えているので気にしない。

今は1手読み*5だけど、制限時間的に軽い2手読みが限度かな。モンテカルロ法でやってたけど、確率で期待値を計算すれば別にランダムにダイス値を決めることはしなくていいですね…。ということで貪欲法に変更。多分最終的にはビームサーチかな。

基本的には、ここからずっと最下位。途中で11位になったけど、12位の人は潜伏してそうだった。

14:10～15:30

お昼休憩。徹夜コースなので、食事は少し遅めにずらしていく。

16:00

何も分からん。ビームサーチを書きかけるが、下手な貪欲を複数手読みにしたところで挙動が分かりにくくなって効率が落ちるだけ。ぐっとこらえて、貪欲を鍛える。

17:00

終局処理に着手。

「これくらい点を取った後に無茶すると破滅しがちだからやめておけ」というお気持ち表明を入れる。*6testerから取った得点をExcelで散布図にして、にらめっこして人の温かみがあるボーダーを設定。

18:40

自明な改善として、高速化やバグの修正。

正常動作するけど結果が悪くなる系のバグがいくつもあってひどい。

19:45

終局処理を追加。「1回棘踏んだらもう回復できないから期待値下がるぞ」という自明なパターンに対応。落とさなくても良い点を落とさなくなっただけで、普段の動きが良くなったわけではない。本質は何処…。

20:30

どう頑張っても手持ちが6面ダイスばかりになる。

なんとなく原因は見えてきて、貴重なダイスを使ってでもコインと軸合わせしたり、安全な場所に逃げ込みたいと思っているようだ。

そこで6面ダイスを使うことに特大ボーナスを付けてみる。

これで大きく動きが改善されたうえ、棘もそこまで踏まないようで得点大幅アップ。視界が開ける。（実装方法は美しくないんだけど…）

提出60.88点。そろそろ貪欲の改良は終わりかな。

21:00

打ち切り基準を再度手調整。

俺、この調整が終わったらビームサーチ撃つんだ…。

23:00～24:00

夕食。28:00まであるので、遅めに調整。

戻ってくると、TCO監視員とのやり取りに使うプラットフォームにエラーが出て、やり取りが出来なくなる。*7

どうせ皆続行してるんだろうから、カメラと画面共有はそのまま付けて作業再開。

向こうからは見えてはいたらしい。

27:00

ビームサーチライブラリを貼って2手読みに。*8

1手目の結果がダイス値や受け取るダイス毎に分かれていて、それぞれに対して2手目を読むので書き方が難しい。

提出。CE。

MMのC#ばーじょんでは たぷるは つかえないぞ！（本日2回目）*9

27:10

2手読みしようとすると恐ろしく重くて、すぐに時間が危険ラインになり結局貪欲モードに戻ってしまう。*10ビーム幅を削ってみるものの、根本的な計算量削減が必要そう。

N>=12では2手目は1面ダイスを入手できないことにして計算量を半減させると、絶対スコアの伸びは地味だが相対スコアが大きく上がった。最下位脱出で、10位くらい。

27:30

評価関数で手持ちダイス射程を覗いている部分が重いので、使いまわせるようにしたいところ。手持ちダイスがちょっと違うだけの状態を何パターンも見ているのだし…。

しかし、ここで違法建築のツケが来てしまい、上手に該当箇所を切り出せない。切り出せるんだけど挙動が変わってしまい、スコアが下がる。

ここの速度が数倍になれば、相対スコアではがっつりスコア上がりそうなんだけどなぁというところで時間切れ。

やり残しメモ

ビジュアライザでは、一度でも到達したセルは色が変わる。

色々な場所を巡回してみろというヒントか？

チャンスは増えるけど、ピンチも増えそう。

感想

ダイス部分の元ネタはDicast: Rules of Chaosらしいです。

不確定ゲームを分岐させる形でシミュレートしたのは初めてで、ぶっつけ本番でしたが最低限なんとかなりました。

多分私は得意なタイプの問題で、本質を大きく見誤っていたわけではないと思うけど、実装速度で負けたかなぁという感じです。評価関数も違法建築の連続で酷いことになっていました。短期（？）マラソンは綺麗な設計と実験/本実装速度とのバランスが難しい…。

そもそも4時からやれば良かったのでは？というのはありますが、その分を同じ覚醒度で長く起きていられたかというと怪しいところ。*11

完敗でしたが、俺だけ出られる隠しマラソン感があり面白かったです。*12

でも監視まで付いちゃうと机に縛り付けられている感が強くて思考力も落ちちゃうし、気軽にやってるいつものマラソンの方が好きかな。

*1:問題以外の部分については、余力があれば別途書いてみたいと思います。

*2:その時点で持っている得点のみ半減。

*3:※必要ではない。

*4:評価関数はこれが最終方針で、方向性は最後まで変わらずでした。

*5:評価関数が1手読みに近いので、実質2手読み。

*6:これは改修するたびに上がっていく値だが、低い値を設定する分には困らない。

*7:実はリロードすれば直ったっぽい。

*8:評価関数が1手読みの性質を持っているので実質3手読み。

*9:MM125のコードで思いっきりタプル書いてるんだけど、これは大丈夫だったのか…？（手元にあるコードを提出してたのかは未確認）

*10:終盤で棘を踏むことを一番避けたいので、終盤に2手読み出来なければ意味が薄い。

*11:そもそも24時間起きている前提のコンテストってなんかおかしくないですか。開始3時間前に開会式があるので3時間しか寝れなくなるし。

*12:だけではない。

HACK TO THE FUTURE 2022 予選 - Project Leader 参加記録

HACK TO THE FUTURE 2022 予選に参加しました。

atcoder.jp

問題はProject Leader。推定とスケジューリングの合体問題です。

提出823人中、暫定テスト14位、システス12位でした。

問題

メンバー20人にタスクを振り分けて、プロジェクトを最速で完了させてね。

タスクに必要な能力値は分かるけど、メンバーの能力値は分からないから完了日数から推測してね。

能力の種類は10～20種類あって、その不足分の総和±3日が完了日数になるよ。

あと、前提タスクを終わらせないと着手できないタスクもあるよ。

考察

やたらたくさんの要素が絡み合っている感。

推測部

複数の値と、確率で出てくる結果から元の値を推測する…これはMM121 SoccerTournamentじゃな？　可能性を絞り込むという観点では、人狼知能にも通じるものがありそう。

日数の求め方的に、メンバの能力を上回る難易度のタスクをぶつけないと正確な能力値は出せない。簡単なタスクしか与えないと、過小評価している状態が続く。過小評価して簡単なタスクしか与えないと、挽回の機会が与えられない。*1序盤は現評価より難しいものを与えるか、過大評価にする必要がありそう。

SATソルバみたいなものがあればかなり正確な値が出る可能性があるけど、自分の能力的に不可なのと、振れ幅の状態も扱ってみたいので、焼き鈍しかな…。

スケジュール部

クリティカルパスは1つの重要ポイントになりそう。

ただPERT図を書こうにも、能力が分からないと実日数が分からないし、そもそも誰が担当するかで日数も変わるので一筋縄では行かない。

上手く出来るなら、クリティカルパスは優秀なメンバに割り当てて最速で終わらせて、脇で他のメンバがクリティカルじゃないタスクを終わらせる感じかなぁ…。

しかし、そもそも愚直解が強すぎる。ID順に処理すれば、なんとなく深さがある場所から処理できるのでなんとなくクリティカルパスをカバーできるし、優秀なメンバは回転率が高く、多くのタスクを請け負うので、なんとなくクリティカルパスを担当する確率が高い。その特徴を増幅させる方向かな。

実装

推測部

焼き鈍し。

近傍は[skill+1、skill-1]を1～2回変形。

スコアはペナルティとして、日数破綻の合計値。

ただ状態1つだけで持つと、確度が高い状態なのか振れ幅がある状態なのか分からない。

スコアに[過去の必要能力の最高値+3]をターゲットにする補正をかけてみるも、局所解にはまるのかあまり芳しくなく、さらに低能力部分の推測精度が低かった。

そこで初期スキルの異なる4つの能力値候補を用意し、それぞれ焼き鈍して平均値を取った。各能力の上限値はMin(15, 過去の必要能力の最高値+6)として、日数破綻のみを評価値とした。

初期能力値候補の例

これで振れ幅部分は破綻しない範囲で自由に上下するので、実能力より多少高く見積もれるようにしつつ、それが破綻する場合は実能力に合わせるという挙動ができた。

また、スキルを測定するためのタスク割り当てを行った。4つの能力値候補でそれぞれ日数計算を行い、日数差が大きいものはより多くの可能性を否定できるもの（＝多くの情報を得られるもの）として優先度を上げた。上の画像の例で言うと、CとC++の必要技能値だけが高いタスクを与えれば、Type3＞Type1・2＞Type4の順で適正が高く日数が短くなる。結果の日数によって各TypeのC,C++の部分だけ推定が進み実際の値に近づき、他の能力はばらついた状態を保てる。*2

1点問題があるとすると、4パラメータをそれぞれ焼きなますので、焼く回数は1/4になる。問題点が出ないよう上手く管理できるなら4つに分ける必要はなく、弱者の戦略という感じ。

スケジュール部

何も分からん。

Rが小さいケースでは前提タスクはあまり気にしなくていいのだが、Rが大きいケースでは気にしないと多数の手が空いてもったいない状態になる。なるべく全員の作業日数を揃えたいが、前提タスクも含めて計算するのは大変。

焼き鈍しなど色々試してみたが最終的には、全タスクを能力値ALL9として子を含めた作業時間を計算し、原則それが多い順に作業することにした。*3

メンバへの割り当ては、タスクを上記の優先順に貪欲に割り当てる。評価値はペナルティで、各メンバの[割り当て済み作業日数^2]の合計とした。*4

割り当て時にタスクの並列化や前提タスクについては一切考慮していない。のだが、実はこの方針もなかなかに強力と考えている。並列にすべきタスクというのは同時に終わらせたいタスクで、何が該当するかといえば、同じ子タスクを持つか、プロジェクト終了間際の2パターンしかない。*5このどちらも並列したいタスク同士で[子を含めた作業時間]が近くなる傾向があり、割り当て順序も近い。なのでその1つを割り当てられたメンバは割り当て済みの作業日数が長くなり、並列したいタスクが割り当てられる確率は減るという寸法。

前提タスクのせいで空きが出るのはもう仕方ないものとして、手が空いた時は、着手できるタスクのうち計画が乱れないもの（自分の次のタスクが遅れない、本来の担当者より早く終わらせる）だけ隙間で行うようにした。

実は一番何も分からないのは序盤～中盤の能力推定と絡めたタスクの決め方で、何回か学習専用に割り当て無視で行うのがいいのか、非効率でもクリティカルパスを崩しながら能力推定するべきなのか、軽いタスクで刻んでいくべきなのか、重めのタスクで振れ幅を確認しに行くのがいいのか…。一切分からなかった。とりあえず試した中では6タスクを割り当てせずに全タスクから選ぶのが良さそうだった。バタフライエフェクト的に終盤まで響くので、本当に何が良いのやら。

感想

愚直解が『上手く行く性質』を持っていて、それを壊さないように新しい指針を入れたり改良する必要がある問題だったと思います。下手をすると既存の性質を壊してスコアが落ちるので、「ぼくのかんがえたさいきょうのほうしん」で気軽にスコアを伸ばして楽しむというタイプではなく、自分含めて苦しんでいる人が多く感じました。

制御するためのパラメータの多さからゲームAIに例えている人もいましたが、個人的には何故それが上手く行くのかを理解しないと前に進めない問題で、謎解きっぽいなーと思いました。

あとビジュアライザが過去HTTF比でもAHC比でも超速で進化してる感があって凄かったです。

*1:この辺のジレンマが凄く"リアル"に感じた。

*2:そういう難しいことは考慮しない焼き鈍しなので、必ず保てる保証はなく運でばらつく。

*3:公式放送ではALL0という話が出ていたが、ALL9の方がより現実に近い値が出ると考えている。

*4:いつもの、最大値を最小化する手法。

*5:しかないは言い過ぎかもしれない。

CodinGame Fall Challenge 2021 参加記録

CodinGame Fall Challenge 2021 から脱出しました。

www.codingame.com

ゲームAIコンテスト…ではなく、脱出ゲームです。

ソロ参加して、仮眠・ペナルティ(ヒント・誤答)込み7時間強で脱出成功でした。

プレイ記録

墓地

CodinEscapeの仕組みが分からず…に加えて、サーバ負荷で挙動が不安定になり、何が起きているかも把握できなかった。

コードタブに入出力をたくさん接続できるようだけど、多対1で接続できて、かつ出力を繋ぐ場所もたくさんあるのでいまいち整理しにくい。出力を繋いでしまうと標準エラー出力を吐くこと(printデバッグ)も出来ないし、よくある標準入力から受け取る形ではないので、とにかく組みにくい。あと、グリッドデータを改行込みで1つの文字列にするのはやめて…。

問題そのものは脱出ゲームでよくありそうな暗号解読。

城内

出力を接続しなければ任意の内容を文字列で出力できることに気付き、効率が10000倍になる。

ここから、大量のデータから条件に合うものを探して出力しろという問題がメインになってくる。脱出ゲーム×コーディングのコンテストとして、相性が良い問題だと思った。4分割した領域が添字の0123とどう対応するかはデータを見て察するしかなく、リバースエンジニアリングみがあった。

ここは楽しめた。

儀式の間

ここも家系図から条件に合う人を探す。正直クエリが書きにくい…。*1一人っ子の孫の従兄とか言われても。クエリを書きたくないなら、グラフとして出力して目視で見るのが良さそうか。でも、上手く家系図として見やすいように高さを合わせて可視化するのきつくないですか？
私はPlantUMLに喰わせたらこんな図が出てきて泣いてしまいました。*2

あとは絵を見ないといけないのに絵が小さくて見にくいところがあり、大画面でやりたかったなと思いました。

個々の要素についての感想

実装難易度

パズルのEasyくらいと予想していたんですが、真面目にプログラムで解こうとすると全人類が解ける難易度ではなさそう。

全問題で入力をそのまま吐き出して手で解くことは出来るので完全に詰むことはないと思いますが、その入力をそのまま吐き出す操作に一癖あって苦労しました…。

協力要素

全員何かで手を動かしている状態が良いと思うのですが、複数人で参加した場合はコーディング待ちが発生しやすそうな構成に見えました。

特に非コーダーがいる場合は強制待機になるので、この感じだと今後も非コーダーは誘いにくいなと思いました。常にコーディングと非コーディングが並行で出題されると非コーダーに優しいかも？

全体的な感想

脱出ゲーム好きかつプログラマの人が数人でやるにはありかなと思いましたが、それならBotProgrammingでも楽しめますし、やっぱりそっちをやりたいですね。

コドゲは最近買収されたようで、転職支援サービスであることを考えると非プログラマにプログラマの価値を示すためにこういうものが出てきたのかなと妄想しています。でもそこで示すのが「大量のデータから目的のものを検索できます」なのは…良いのか？謎の技術でゲームをプレイするAIの方が凄くありません？*3

*1:というか頭を使う気にならない。

*2:真面目に解く気になれなくてヒントを見ました。

*3:目的のデータは検索できましたか？

Topcoder MM130 - GraphLabeling 参加記録

TopCoder の MarathonMatch 130 に参加しました。

www.topcoder.com

問題はGraphLabeling。同名の既存問題です。

事前テストは66人中31位でした。

問題

グラフの各ノード（頂点）にUniqueな値を割り振って、

ついでに辺で繋がったノード同士の差もUniqueにしてね。

頂点に割り振る値の最大値を最小化してね。

最終的にやったこと

貪欲で一番小さい値を置き続ける以外に現実的な実装が思いつかない。あとは順番をどうするかしか無さそう。
大きい値と大きい値に大きい差が付くと値が跳ね上がる。後で置く場所≒大きい値を置く場所なので、後で置く場所同士の隣接を減らせると良い？

→1秒間焼きなましで順番の積の総和を最小化。

やったけど没にした方針

全連結されたグループを探して最初に埋める。全連結の組合せ最適を得るのが難しい。速度を出すのも難しい。

順番をDFS風にしたりBFS風にしたり。最初に作ったお気持ち評価が強すぎて改善できない。

大グループと小グループに分けて、双方向に伸ばしたり、双方向から間に向かって伸ばしたり。前者は両グループに隣接するノードがあると上手く行かない。後者は上手く隙間が埋まれば良さそうに感じるけど、実際のところ埋まらない。

他の人の解法

最小値を貪欲に置く方針は大体皆一緒らしい。
差が出たのは連結密度が高くて値が跳ね上がるケース。ゴロム定規という既存の解（？）があり、検索→解を生成して貼り付けるのでseed2で100倍差が付くらしい。

感想

既存の解法を参考に何かを作ろうとか、自分で考えたものを埋め込むならまだマラソンらしさがあるのだけど、既存のものを丸々埋め込むだけはちょっと楽しめない。
マラソンの形は色々あるし、好みじゃないものも認めていきたいけど、うーむ。

あとはローカルPC上だとseed=2は余裕だったけど、提出上だと全然通る気配が無かった。時間が厳しくて枝刈りも出来ない系の問題だとどうしようもなく…。*1

あらゆる楽しめない要素がこれでもかと詰め込まれていたので、一旦全てを忘れたいです…。

*1:アルゴ部分を最速にするなりC++を使うなり、公開されている情報を使って自前ジャッジ環境を作ればいいと言えばそうなのですが…。

過去マラソンコンテスト概要一覧

過去のコンテストでどういう問題が出たかを見たくて自分用の覚書を書いたものです。

抜けや間違いが無いことや、このページが10年後に残っていることは保証しません。

ソロプレイヤー問題

AtCoder

AtCoder Marathon Contests(competitiveprogramming.info)

RECRUIT 日本橋ハーフマラソン 2021(A問題)　2グループに分けて逐次改善。

RECRUIT 日本橋ハーフマラソン 2021(B問題)　グリッド上での組み合わせ最適化。

RECRUIT 日本橋ハーフマラソン 2021〜増刊号〜　ヘビゲーム亜種

HTTF2020予選　TSP＋スタック管理。

HTTF2021本選　外から内に向かって採掘。

HACK TO THE FUTURE for Youth＋(2021)　ポリオミノ連結。

AHC001　矩形パッキング。

AHC002　条件付き最長路。

AHC003　和のコストから部分のコストを推定。インタラクティブ。

AHC004　部分文字列連結＋矩形に敷き詰めるパズル。

AHC005　視界でTSP。

Topcoder

Topcoder Marathon Matches(competitiveprogramming.info)

MM5　　マッチ5パズル。インタラクティブ。

MM122　マインスイーパ。インタラクティブ。

MM123　マッチ3パズル。インタラクティブ。

MM124　視界が悪い迷路グラフを探索。インタラクティブ。

MM125　マッチ5パズル。インタラクティブ。

MM126　スライドして穴に落とすパズル。

MM127　複数の値を比較できるソート。インタラクティブ。

MM128　ボールを隣接するボールと入れ替えて同色を連結させる。

MM129　群れで群れを追い込み漁。インタラクティブ。

MM130　GraphLabeling。

CodinGame

Valさんによる紹介

2048　　　　同名パズル。

SameGame　同名パズル。

Bulls and Cows 2　同名パズル。

MarsLander　宇宙船着陸シミュレータ。インタラクティブ。

Code of the Rings　brainf**kで動的にコードゴルフ。

A*Craft　　　群体＋方向転換ブロック＋最長路。

SearchRace　慣性＋相対方向指定レース。インタラクティブ。

Code vs Zombies　座標ゲー。インタラクティブ。

Number Shifting　加算か減算を選んで数字同士をマージ。

Bender - Episode 4　難しい手続き。

CGFungePrime　独自言語で素数判定。

CodinGame Sponsored Contest　入出力からリバースエンジニアリング。

マルチプレイヤー問題（全てインタラクティブ問題）

CodinGame

専用記事参照。

企業系

広報や採用の一環として開催されているもの。性質上、想定解があるものが多い？

天下一 Game Battle Contest 2021 Spring　部分文字列連結＋ルート巡回。リアルタイム。

天下一 Game Battle Contest 2021 Autumn　資源の山分け争奪。リアルタイム。

学術系

JSAI、CoGなど。性質上、想定解がないものが多い？

人狼知能(プロトコル)　人狼ゲームで勝ちを競う。2021現状メタ読みゲーム。

人狼知能(自然言語)　人狼ゲームで人間っぽさを競う。

ColorShapeLinks 　属性が2つある4目並べ。