TCO 16 Round3参戦記録 - TerrainCrossing -

TCOMMの最終ラウンドが終わりました。

https://community.topcoder.com/longcontest/?module=ViewProblemStatement&rd=16704&pm=14283

問題文

縦横長さが S あるフィールドがあります。フィールド上にはN個のアイテムとN個の目的地が存在しています。あなたは全てのアイテムを各目的地に運ぶ必要があります。この時、各目的地には1つのアイテムしか届けることが出来ません。（複数のアイテムを同じ目的地に置くことは不可）

フィールドの移動についてですが、現在いるセルから隣接するセルへ移動が可能です。また、各セルにはコストが割り振られており、そのセル内での移動では「移動した距離 x セルのコスト」のコストがかかります。さらにセル間の移動については以下の計算式によって追加コストが発生します。

セル(x, y) -> セル(nx, ny) への移動
addCost = pow(fieldCost[x][y] - fieldCost[nx][ny], 2)

アイテムの回収についてですが、プレイヤーがアイテムの座標から距離0.001以内のフィールドに到達すると自動的に回収されます。アイテムの保持数については上限があり、上限を超えてアイテムを保持することは出来ません。また、アイテムの設置については回収と同様に目的に0.001以内のフィールドに到達すると自動的に配置されます。アイテムを保持していない場合は設置は行われないので注意してください。

また、経路の開始地点と終了地点についてですが、開始時は任意のマップの端から0.001以内の距離にある座標から開始し終了地点も同様にマップの端から0.001以内の距離を指定してください。なお、連続している経路の間隔は0.001より大きく、かつ座標が存在しているセルのマンハッタン距離が1以下になるようにしてください。さらに始点と終点を除いた各経路の座標はセルの端から0.001より離れた場所を指定してください。

最終的にコストの消費を少なく全てのアイテムを目的地に届けて下さい。

今回の問題、細かい制約のせいでたくさんのバグを埋め込みました。 あと参加した中で一番疲れました。

戦略

今回は「各オブジェクト間のコストを計算」「巡回セールスマン問題を解く」「山登りで経路を修正」と大きく分けて3つのフェーズに分けて処理を行いました。

各オブジェクト間のコストを計算

まず最初にフィールドに散らばっている「アイテム」と「目的地」それぞれの経路間のコストを求めます。基本的には各オブジェクトからダイクストラ法で経路を生成しました。

なるべくコストが小さくなるように移動。

今回はこのコストをどう計算するかでかなり頭を悩ませました。というのも、下の図のようなフィールドが存在し

このフィールドを次のように移動した時に、図の経路だと「1 + 1 = 2」と計算するのですが、実際には

この移動が可能なので1.41ぐらいのコストにしたい、かといってこの状態でさらに右に進んだ場合

今度は赤線の経路が最短になり、前回時点での最短を固定してしまうとロスが発生してしまう。

このロスは経路を進めれば進めるほど発生するので、このロスをいかに減らすかが難しかったです。

自分は通常のコストの計算時に追加コストを通常の2倍で計算を行いました。（これは評価値としては微妙な気がしなくもないですが

また、Sが小さい場合は、1つ進める毎に今までの経路に対して後述する山登り法を適用して経路のコストをその都度再計算していました。

巡回セールスマン問題を解く

求めたオブジェクト間のコストを元に巡回セールスマン問題を解きます。経路には以下の制限をつけました

• アイテムが0個の状態で「目的地」に到達してはいけない
• アイテムの所持数が上限の状態で「アイテム」に到達してはいけない

巡回セールスマン問題を解いた内容については前回の予選の感想ブログで書いた内容とほぼ一緒なのでそちらをどうぞ

simanman.hatenablog.com

簡単に説明すると、現在の経路に対して以下の操作のいずれかを選択します。

• 2点間のオブジェクトを入れ替える
• 2点間の交差を削除する
• 1点を取り出し任意の場所に追加する
• 連続した2点を取り出し任意の場所に追加する

また、仮に経路のコストが増加しても一定の確率でその経路を採用します（焼きなまし法

山登りで経路を修正

最終的な経路が確定したら、経路の座標をランダムに選択し、ランダムに動かしてスコアが改善されたらそれを採用する、という処理を行いました。

この様な経路が存在している時に

始点と終点とアイテムと目的地を除いた座標をランダムに1つ選び動かします

スコアが改善された場合はそちらを採用します。

セルを飛び越える移動も有効にしています

感想

まさか同じ予選で巡回セールスマン問題を2回も出題されるとは思いませんでした。点をばらまいてそれをくっつけたり切り離したり移動させたりする案もあったのですが、時間が無くて断念しました。序盤の「オブジェクト間のコストを算出」する部分が精確に出せなかったのが心残りです。

Example

Example scores:
0) 8.106127476192645
1) 85.36355804638156
2) 384.75769417466637
3) 5627.9464135616445
4) 551.6884483017363
5) 311.8191310808154
6) 313.3568643271177
7) 921.3633059194917
8) 1493.4400096579031
9) 664.7891337391771

OnlineExam 参戦記録

Codeforcesで開催されていたマラソンマッチに参加してました。

codeforces.com

問題文

オンラインの試験があります。問題は全部で5000問あり、各問題は「YES」または「NO」で解答を行います。採点については各問題ごとに正解不正解を判別し不正解の数が2000に達するまで採点が行われます。最終的な点数は採点が終了した時点の問題番号となります（正解数ではないので注意）。試験には最大100回までチャレンジできます、その間に問題の解答が変化することはありません。なるべく多くの点数を取れるように頑張ってください。

戦略

まず、大きな手がかりとして「採点したスコアの問題番号は不正解」というのがあります。例えば問題数が10で1問でも間違ったら採点終了の場合において、スコアが7だった場合は8問目は不正解ということになります。

まずこれで最大100問は不正解を正解に直すことが出来ます。

特定の範囲を指定して解答をひっくり返す

5000個の問題の中から一部を抜粋して、その部分の解答を反転させてそのスコアの増減を確認してました。

一部を抜き出して

解答を反転させる

初期の頃はこれを範囲40ぐらいで行って68000点ぐらいでした。

変化が少ない部分は分割して再調査

分割して調査していくと、特定の個所ではスコアの変動がかなり少ないところがあります。これは正解数と不正解数がその区間ではほぼ同一なことを示しているのですが、実際には図のように片方に正解が偏って、もう片方に不正解が偏っている場合があります。

その場合にはその区間を再度分割し片方の解答を反転させて再度スコアを計算します。

分割して

片方を反転させて再計算

図ではスコアが上昇したのでもう片方の領域については何も行いませんが、もし、スコアが低下した場合はもう片方の領域を反転させます。（その場合は正確なスコアの取得は行わず予測スコアを計算します

感想

シンプルな問題でしたが色々考察しがいのある問題でした。問題の環境としてtesterがもうちょっと充実していると良かったです。あと、提出間隔に制限が無いのはいいですね。

NYC Lightning Round 参戦記録

診断人さんのツイートで気づいて参戦しました

https://community.topcoder.com/longcontest/?module=ViewProblemStatement&rd=16756&pm=14282

topcoder１日マラソン開催されるのであれば、すぐ寝る。されないのであれば、プログラミングして寝る。

— nico_shindannin (@nico_shindannin) 2016年6月16日

あ、いまやってたｗ https://t.co/xtlNnrnb1b

— nico_shindannin (@nico_shindannin) 2016年6月16日

問題文

縦横長さが D のボードがあります、ボードの各ピクセルには色が割り当てられています。このゲームは2人対戦ゲームで、プレイヤー0の初期領地は左上(0,0)、プレイヤー1の初期マスは右下( D - 1, D - 1 )です。プレイヤーはなるべく多くの領地を取得することが目的です。各プレイヤーはターン毎に任意の色を指定することが出来ます。この時、現在の自分の領地の色または相手の領地の色は選択出来ません。色を指定すると以下の操作が行われます。

• 自分の領地に隣接しており、かつ誰の領地でもなく、指定した色と同じ色のマスを自分の領地にする
• 自分の領地の色を指定した色に塗り替える

この操作をプレイヤーが交互に行い、全てのマスがいずれかのプレイヤーの領地になるまでゲームを続けます。最終的なスコアは「自分が占領したマス / 全てのマス」となります。

戦略

最初は一直線にフィールドの中心を目指します。（むしろ中心から敵の初期位置寄り）、このゲームでは「相手の陣地は取れない」のでなるべく大きく自分の陣地を囲みに行きたいからです。そして、到達後は相手の伸びしろを消すためにボードの端っこを目指して不可侵領域を作りに行きます。最初は貪欲にマスを取っていましたが、最終的には不可侵領域を多く作るほうが効率が良かったです。

貪欲パターン

貪欲にマスを取ると領地が図のような感じで増えますが、同時に相手の領地も増えやすい形になってしまいます。

不可侵領域パターン

最初に相手に近づいて不可侵領域を作ります

この戦略が取れるのは今回の対戦するAIがランダムに色を選択するタイプだったので、比較的、敵の領地の広がり方が遅いのでこの戦略が使えました。

1日マラソン参加しましたけど集中力が全然持たないですね、もっとゆっくり参加したかったです。あと1日マラソンでtesterにバグ生えてるのは勘弁して下さい

Examples

Example scores:
0) 0.62
1) 0.7975
2) 0.7822222222222223
3) 0.9122
4) 0.8722601248366961

TCO 16 Round2参加記録 - StarTraveller -

TCO 16 Round2 が終了しました。

https://community.topcoder.com/longcontest/?module=ViewProblemStatement&rd=16703&pm=14268

問題文

ある宇宙空間にN個の星とM個の宇宙船とK個のUFOが存在しています。宇宙船は星と星の間を移動する際にその星と星の間の距離の長さ分の燃料を消費します。
宇宙船は移動する際に、UFOと一緒に移動した場合は消費燃料が0.001倍になります。（UFOが複数ある場合は効果が重複されます）あなたは「全ての星を1回訪れるような宇宙船の移動計画を立てる」のが目的となります。使用する燃料が最小となるように計画を立ててください。

TSP問題（巡回セールスマン問題）がベースとなっている問題でした。（宇宙船 1でUFO 0の場合とか完全にTSPです）

戦略

自分の今回の戦略についてです。

1ターン目

1ターン目は全宇宙船に対して停止命令を出します。というのも1ターン目は星の到達判定が発生しないので、宇宙船の初期位置が訪問済みと認定されないためです

追跡するUFOを決める

今回の問題では通常移動とUFOと一緒に行動する時の燃料の消費差が1000倍あるので、基本的にはUFOと一緒に行動します。ただUFOに乗り込むタイミングが結講難しくて、その辺り苦労しました（最後もここでずっと悩んでました）。というのも UFOに乗り込むのに通常コストで燃料を消費 しないといけないので「なるべく早く乗り込みたい。。。でも距離が遠い。。。」みたいなところでトレードオフをうまく調整する必要があったからです。（あとは1つのUFOに乗る宇宙船は1台にしてました）

消費コストを考えると乗りにくい

かと言って、待ちすぎると今度は到達できる星の数が減ってしまう

自分の場合はUFOと宇宙船の遭遇率を考えてその辺りは調整しました。（例えば宇宙船1つでUFO1つのケースなら遭遇率は低いので、乗り込む閾値を高く設定、一方、宇宙船10個のUFO20個のケースであれば遭遇率は高いはずなので乗り込む閾値を低くする）

この辺りは若干、過学習させた感はあるので本番スコア下がるかも。。。

UFOを追跡する

追跡するUFOを決めたら「残り時間 - 未到達星 > 0」の間ずっとUFOを追跡します。

経路を作成する

最後に残った星を訪問する経路を作成します、自分の場合は宇宙船が1つの時と2つ以上ある場合で経路の作成方法を分けています。経路の作成には「初期解の構成」+ 「山登り法 or 焼きなまし法」を使用しました

初期経路の構成

まずは初期経路を生成します。初期経路の生成には「NN法 (Nearest Neighbor)」と「FI法 (Farthest Insertion)」の2つを使用しました（今回は制限時間が長かったので両方試してスコアが良いほうを選択しています）。個人的にNN法のほうが後半の焼きなましの時に改善しやすく、FI法は初期の精度は良いが焼きなましで改善しにくい印象を受けました。

NN法 (Nearest Neighbor)

NN法では以下の手順で経路が作成されます

1. 未到達の星の中からランダムで1つを選択

1が選択されたと仮定

2. 選択された星から一番近い星を求める

2番が選択される

3. その星に移動

1-2の経路が作成される

4. 未到達の星がなくなるまで2-3を繰り返す

こんな感じで経路を作成していきます。NN法では終盤にかなり効率の悪い経路を作成する傾向があります

FI法(Farthest Insertion)

FI法では以下の手順で経路を作成していきます

1. 既に作成している経路から一番遠い未到達の星を選択

ここでは既に1-3の経路が完成しているものとします

現在完成している経路から一番遠い星を選択します

ちなみにここで逆に一番近い星を選択するとNI法（Nearest Insertion）になります。

2. コストが最小となるように星を挿入

星を選択後、経路「A -> B」に挿入するとして「A -> C -> B」、この時のコスト「AC + CB - AB」が一番最小となる場所に挿入を行います

3. 未到達の星がなくなるまで1-2を繰り返します

4を追加

最後に2を追加して終了

FI法ではNN法に比べ、精度の高い経路が生成されます。（特に星の数が1000を超えてくると顕著です）

宇宙船が1つのとき

初期の経路の生成後、以下の操作を近傍と定義し焼きなましを行いました。

1. ある2点間の星の訪問順番を交換する

ランダムで経路から2点を選び交換します

2点をランダムで選択

交換する

2. 交差している経路が存在する場合に、交差部分を取り除く

下のような経路が存在している場合に

以下の2点を選択したとします（実際にはランダムで選択しています）

選択した星からスタートして、交換処理ができなくなるまで交換し続けます

処理が完了すると交差していた部分が解消されます

3. 経路から任意の場所を抜き出して、任意の場所に入れなおす

経路の中からランダムから1つ選択します

2が選ばれた場合

切り離して

ランダムで選択された場所に挿入します（図は4-5の間が選択された場合）

宇宙船が2つ以上の場合

初期経路の生成後、以下の操作を行った後にコストが減少した場合に経路の更新を行いました（山登り）

1. 任意の宇宙船の経路が交差していた場合にこれを取り除く
2. 任意の宇宙船の訪問経路から2点を選び、これを入れ替える
3. 任意の宇宙船の経路を反転する
4. ある宇宙船の経路の一部を切り取り、それを別の宇宙船の経路の最後に追加する
5. ある宇宙船の経路の一部を切り取り、それを別の宇宙船の経理の先頭に追加する

その他

他にも細かく調整したポイントについて

UFOの乗り換え

UFO追跡中に時折、他のUFOと重なるタイミングがあります。この時に重なったUFOが無人でかつ平均移動距離が今のUFOより長い場合はそこで乗り換えを行いました。（平均移動距離が長いと星の到達率が高くなる傾向があるので）、特に宇宙船が1つのケースではスコアの上昇が顕著でした。

一時離脱

UFOの行動は2ターン先まで与えられているのですが、たまにUFOが行って戻ってくる時があります。この時は次の訪問地が到達済みの場合にUFOから下りてました。（0.001倍になっていてもチリも積もればなんとやら）

2が到達済みならばUFOが戻ってくるまで1で待機しておく

離れすぎた宇宙船の回収

自分は1つのUFOに対して1つの宇宙船を乗せていましたが、宇宙船の数 > UFOの数のケースにおいて、UFOに乗れない宇宙船が出てきました。このケースだと、一定ターン経つと 周りに未到達の星が全く無い 状態が発生します。

この状態は後で星を探索する際に不利なので 、近くにUFOが来たらそれに乗っかり未到達星の近くまで移動します。

近くにUFOが来る

それに乗っかる（他の宇宙船が乗っていても関係なし）

未到達の星がある近くまで移動する

UFOから下りて再度停止モード

Examples

Example scores:
0) 2063.911340486327
1) 7700.186086852073
2) 4577.47499473865
3) 2367.5522684008797
4) 8787.464703717615
5) 5524.8693553478615
6) 8296.651085271313
7) 4765.360580919411
8) 6927.3815665480315
9) 12032.230311687837

TCO 16 Round1参加記録 - CutTheRoots -

久々の日記です、今年もTCOの季節になりました。

Round 1の問題は「CutTheRoots 」で、簡単に説明すると植木鉢の中にある植物を根っこをなるべく切り取らないように切り分けるかの問題でした。

TopCoder

図としては下のような感じです。

最初は複数の植物がのびのび成長しています。

これを直線を引いて各自バラバラになるように切り分けます。

この時、下の赤、紫の部分で黒くなった部分がありますが、これは直線で切り分けた際に根っこを切り落としたことを示しています（今回のスコアではこの切落しの長さをいかに少なくするかが争われました）

今回、自分の方針としては貪欲法で

• ランダムに線を大量に引く
• 一番良さそうな線を残す

この2つを植物同士が完全に切り分けられるまで、ひたすら繰り返していました。

1. 与えられた植物同士で完全グラフを作る

今回、終了判定がなかなか難しくて最終的に「完全グラフの辺を全て切断したら終了」というプログラムにしました。最初はドロネー三角分割で生成した線を全部切断したら終了ってやっていたのですが、これだと全て切断しても完全に分けきれていない状態があったので諦めました。

まず最初に初期状態から

完全グラフを作ります（と言っても長すぎる辺は無視してたりしてます）

あとはバッサバッサ辺を切り落としていきます

線を引いて切り落とす

全部切り落としたら終了です

これで切り分け完了です。この直線を選ぶときの評価値としては

• 直線を引いた際に切り落とした根っこの長さの合計 / 切り落としたグラフの辺の数

みたいな評価にしてました（あと、直線上に植物があると切り分け判定でバグったので、その直線は除外とかしてました）

終了後に無駄な直線の排除

切り分け後に、引いた直線を調べて「この直線を取り除いても、全ての辺が削除された状態を維持出来る」場合にその直線を排除する処理をいれました。

高速化

枝が多いと直線と枝の交差判定だけでめちゃめちゃ時間とられたので、その辺りの高速化と、あとは現在の評価値の一番いいやつより良いスコアを出せなくなったら交差判定を即終了とかやってました。

時間調整難しい

やたら自分の提出数が多いのは、今回ちょっと時間管理が難しくてその辺りの調整で迷走した結果です。

感想

本当は焼きなましを使いたいなと思っていましたが実装できませんでした。

Tシャツ欲しかったです（30位以内でもらえた年度ならﾜﾝﾁｬﾝあったかも）

現在開催中 or 今後開催予定のマラソンマッチ系コンテストについて

これは 「Competitive Programming （その2） Advent Calendar 2015 」の12日目の記事です。
www.adventar.org

マラソンマッチとは、2週間から長いもので1ヶ月以上の期間をかけて行われるコンテストです。有名なところではTopcoderのMarathon Matchがあります。なぜかマラソンマッチ系のコンテストは冬に集中するので、今後のリマインダー的なものとしてご活用下さい。

ハル研究所 プログラミングコンテスト 2015

www.hallab.co.jp

コンテスト期間

• 「2015 12/15（木） - 2016 01/07（木）」

説明

「スマブラ」、「カービィ」 等の開発元で有名なHAL研究所主催のコンテストです。今年は学生が対象の「学生部門」とHAL研社員対象の「HAL研部門」の２つに分かれています。

SamurAI Coding 2015 - 16

samuraicoding.info

コンテスト期間

• 1次予選 2016年1月8日迄

• 2次予選 2016年2月8日迄

説明

情報処理学会が主催しているAIコンテストです。今年のお題は某Splat○○nを彷彿とさせるお題となっています。

Kaggle Santa

www.kaggle.com

期間

• 2016 1/8迄

説明

賞金総額20,000$というビックなコンテストです。

Marathon Match 90

期間

• 12/15/2015 3:00:00 - 12/29/2015 3:00:00」

説明

TopCoder社が定期的に出題しているコンテストです。ある問題に対しての最適化を行うお題を出されることが多いです。

TENTATIVE Secret Santa Marathon Match

期間

• 12/16/2015 3:00:00 - 12/30/2015 3:00:00

説明

こちらもTopcoderからの出題予定です。

Prostate Cancer Foundation Stupski Prize Challenge - Computational Oncology

期間

• 12/16/2015 3:00:00 - 12/30/2015 3:00:00

説明

こちらもTopcoder社からの出題となります。同時に3つとはスゴイですね

CODERS STRIKE BACK

www.codingame.com

期間

• 2016 2/21から8日間

説明

CodinGameというフランスにあるプログラミング学習サイトが開催しているコンテストです。大体の傾向としてはゲームAIを参加者同士で対戦させる形式が多いです。

恐らく開催（個人の感想

CODE VS

codevs.jp

期間 (追記 2015/12/14)

• 風の噂で来年の3月にやるとかやらないとか。（公式で発表があったらリンクはります）

説明

日本最大級のAI対戦型コンテストです。恐らく今月中には何かしらのアナウンスがあるんじゃないかなーと勝手に想像してます。

以上、駆け足でしたが自分が把握している中でのマラソン系のコンテスト一覧です。他にも「こんなコンテストがあるぜ！」という方はコメントかリプライで教えてください！

「Code Festival A If you cannot solve this」参加記録

CodeFestivalの短縮王の事前公開問題があったのでそれをやっていました。

anarchy golf - Code Festival A If you cannot solve this

問題としては

クラスメイトのテストの点が与えられる。
クラスの平均点の半分以下である点数を赤点と定義する。
s1が赤点ならFail 、赤点でなければ Passを出力する（s1とはクラスの1人目の人） 

というものでした。そして、今回書いたコードはこれです。

#!ruby -apl
$_=eval$F*'+~'+">-2*%d*%d?:Pass:'Fail'"%$F

ちょっとだけ解説します。

#!ruby -apl

この謎の記述ですが、これは「Rubyを実行オプション-a -p -lを有効にして実行するぞ！」という宣言です。

pオプションが有効になっている場合はプログラム全体が

while gets
    .
    .
    .
  print $_
end

のように動作します。ここで$_はgetsしたときの値が入っています。

aオプションはpオプションが有効になっている状態で各whileループで

$F = $_.split

を実行してくれます。

lオプションはpオプションが指定されているときに、各行に対してchop!を実行し、また$_の出力時に改行をつけてくれます。

他のオプションについては Rubyの起動 (Ruby 1.9.3) に詳しく書かれています。

今回は入力形式として以下のように与えられていました。

# クラスの人数 1人目の点数 2人目の点数 3人目の点数 4人目の点数
4 42 1 90 77

そのまま書くとこんな感じになるのですが

# クラスの人数と点数リストを分ける
n,*a=$F.map(&:to_f)
# 平均点の半分より大きければPass
a[0]>a.inject(:+)/n/2?:Pass:'Fail'

これをベースにどんどん変化させます。まず

a[0]>a.inject(:+)/n/2

この部分ですが、to_fに依存しない形に変形します。（後々evalを使った式に変形するため）

2*n*a[0]>a.inject(:+)

次に数値化していた部分のコードをevalを使って省きます。

eval"2*#{$F[0]}*#{$F[1]}>#{$F[1..-1]*'+'}?:Pass:'Fail'"

このままだと長過ぎるので、String#%を使って左側の値は%dに置き換えます。

eval"2*%d*%d>#{$F[1..-1]*'+'}?:Pass:'Fail'"%$F

ここまで来ると「$F[1..-1]*'+'」の部分も消し去りたくなります。今はクラスの合計値を出すために

$F[1..-1]*'+' #=> 42+1+90+77

になっていますがこれを

$F*'+~' #=> 4+~42+~1+~90+~77

に置き換えます。この状態は、クラスの人数をn、合計点数をSとすると

n+(-S-n) => -S

とクラスの合計点数にマイナスをかけた値が出ます。これは「~n」が「~n == -n-1」を表すため、

n + ~s1 + ~s2 + ~s3 + ~s4
n + (-s1-1) + (-s2-1) + (-s3-1) + (-s4-1)
n - (s1 + s2 + s3 + s4) - 4
-S

となり、ちょうどいい感じにnを消し去ることができます。

あとは、これを条件が崩れないように変形してあげると最後の

#!ruby -apl
$_=eval$F*'+~'+">-2*%d*%d?:Pass:'Fail'"%$F

になります。「$F*'+~'」の記述をみつけるのに10hぐらい使った気がします。