読者です 読者をやめる 読者になる 読者になる

simanのブログ

ゆるふわプログラマー。競技プログラミングやってます。Ruby好き

MM92 Lighting 参加録

Marathon Match 92の「Lighting」に参加していました。

問題

SxS のセル状空間に光源の強さがDのL個のライトをいい感じに設置して、なるべくたくさんの空間を照らしましょう。

すごいシンプルでした。美術館問題に似た問題だなと思いました。

方針

大きく分けて次の3つを行いました。

  • フィールドの拡大率をいい感じに決める
  • 焼きなましで照明を設置する場所を決める
  • 焼きなまし後にフィールドの拡大率をさらに上げて照明の位置を微調整する

フィールドの拡大率をいい感じに決める

最初に与えられたフィールドをそのまま使うと照明のシミュレーションの精度が粗いので、フィールドをある程度引き伸ばして精度を高めました。テスターの実装では拡大率が f = 100 で定義されていましたが、これをそのまま使うと後の焼きなましパートで試行回数が全然稼げないので、フィールドサイズが「縦 x 横 == 10000」ぐらいになるように値を修正しました。

SCALE = ceil(sqrt(10000 / (S * S))); // 端数は切り上げ

焼きなましで照明を設置する場所を決める

遷移は「照明を1つ選び任意の場所に移動させる(※ただし壁は除く)」を採用し、温度管理は「差分スコア / (任意の定数) * (残り時間)」で管理してました。

1つのセルを16分割して細かく移動出来るようにしています。

f:id:simanman:20170119163941p:plain

   ↓

f:id:simanman:20170119163947p:plain

高速化

一度照明のシミュレーションをした座標については「照らすことが出来るセルの位置情報」をキャッシュして、次回以降はそれを取り出すようにしました。

照明の位置を微調整

焼きなましパートで照明の位置を決めた後に位置を微調整を行いました。処理的には任意の照明を1つ選んでちょっとだけ動かしてスコアが改善していたら採用という感じで山登り的に行いました。シミュレーションの精度を上げるために事前にフィールドを焼きなましパートのときより少し拡大しています。

f:id:simanman:20170119013248p:plain

それぞれのパートの時間の割り振りは

  • 焼きなまし(15秒)
  • 微調整(5秒)

としました。

感想

0.1%のスコア範囲で争ったのは初めてかもしれない。みんな大体同じ戦略になってそう。

Example scores:
0) 0.9987473684210526
1) 0.8922939051918736
2) 0.7014297413793104
3) 0.382128527607362
4) 0.15465865921787708
5) 0.13367932926829268
6) 0.98818025477707
7) 0.9328539007092198
8) 0.7149500729927007
9) 0.7206551724137931

ソースコード

RubyのEnglish.rbソース読み

Rubyの標準ライブラリを読んでいく、前回は3年前に ostruct を読んだ

今回は English.rb を読んでいく。

English.rbとは何か

English.rbはRubyの特殊変数に対してわかりやすい別の名前を付与するライブラリである。Rubyの特殊変数は通常 $ + 記号 の形で与えられており大変読みにくい。そこでこの English.rb を取り込むことで読みやすい別名を使用することが出来るようになる。

require 'English'

"hogefugapiyo" =~ /fuga/

p $PREMATCH   #=> "hoge"
p $MATCH      #=> "fuga"
p $POSTMATCH  #=> "piyo"

中身を見てみる

基本的に alias を使って別名を割り当てているだけ

# The exception object passed to +raise+.
alias $ERROR_INFO              $!

# The stack backtrace generated by the last
# exception. <tt>See Kernel.caller</tt> for details. Thread local.
alias $ERROR_POSITION          $@

# The default separator pattern used by <tt>String.split</tt>.  May be
# set from the command line using the <tt>-F</tt> flag.
alias $FS                      $;

1つ気になるところ

読んでいて1個所気になったのはこの部分

module English end if false

絶対に実行されない謎のコードが入っていたので「なんだこれは」と思っていたのだがどうやらRDocのparseのために追加しているらしい。

参考URL

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つのフェーズに分けて処理を行いました。

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

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

f:id:simanman:20160706224555p:plain

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

f:id:simanman:20160706225209p:plain

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

f:id:simanman:20160706231156p:plain

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

f:id:simanman:20160706231409p:plain

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

f:id:simanman:20160706231748p:plain

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

f:id:simanman:20160706232113p:plain

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

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

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

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

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

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

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

simanman.hatenablog.com

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

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

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

山登りで経路を修正

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

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

f:id:simanman:20160706233252p:plain

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

f:id:simanman:20160706233859p:plain

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

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

f:id:simanman:20160706235123p:plain

f:id:simanman:20160706235132p:plain

感想

まさか同じ予選で巡回セールスマン問題を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問目は不正解ということになります。

f:id:simanman:20160622062424p:plain

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

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

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

一部を抜き出して
f:id:simanman:20160622063351p:plain

解答を反転させる
f:id:simanman:20160622063427p:plain

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

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

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

f:id:simanman:20160622064122p:plain

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

分割して
f:id:simanman:20160622064350p:plain

片方を反転させて再計算
f:id:simanman:20160622064552p:plain

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

感想

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

NYC Lightning Round 参戦記録

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

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


問題文

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

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

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

戦略

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

貪欲パターン

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

f:id:simanman:20160618003525p:plain

f:id:simanman:20160618003539p:plain

不可侵領域パターン

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

f:id:simanman:20160618003815p:plain

f:id:simanman:20160618003824p:plain

この戦略が取れるのは今回の対戦する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台にしてました)


消費コストを考えると乗りにくい
f:id:simanman:20160526002654p:plain


かと言って、待ちすぎると今度は到達できる星の数が減ってしまう
f:id:simanman:20160526002852p:plain


自分の場合は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が選択されたと仮定
f:id:simanman:20160526004150p:plain

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

2番が選択される
f:id:simanman:20160526004236p:plain

3. その星に移動

1-2の経路が作成される
f:id:simanman:20160526004358p:plain

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

f:id:simanman:20160526004723p:plain

f:id:simanman:20160526004734p:plain

f:id:simanman:20160526004752p:plain

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

FI法(Farthest Insertion)

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

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

ここでは既に1-3の経路が完成しているものとします
f:id:simanman:20160526010135p:plain

現在完成している経路から一番遠い星を選択します
f:id:simanman:20160526010218p:plain

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

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

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

f:id:simanman:20160526010429p:plain

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

4を追加
f:id:simanman:20160526010708p:plain

最後に2を追加して終了
f:id:simanman:20160526010818p:plain


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

宇宙船が1つのとき

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

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

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

f:id:simanman:20160525203733p:plain

2点をランダムで選択

f:id:simanman:20160525204036p:plain

交換する

f:id:simanman:20160525204150p:plain

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

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

f:id:simanman:20160525235717p:plain

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

f:id:simanman:20160525235843p:plain

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

f:id:simanman:20160526000141p:plain

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

f:id:simanman:20160526000244p:plain

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

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

f:id:simanman:20160526000424p:plain

2が選ばれた場合
f:id:simanman:20160526000555p:plain

切り離して
f:id:simanman:20160526000815p:plain

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

f:id:simanman:20160526000929p:plain

宇宙船が2つ以上の場合

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

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


その他

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

UFOの乗り換え

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

一時離脱

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

2が到達済みならばUFOが戻ってくるまで1で待機しておく
f:id:simanman:20160526013553p:plain

離れすぎた宇宙船の回収

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

f:id:simanman:20160526011820p:plain

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

近くにUFOが来る
f:id:simanman:20160526012152p:plain

それに乗っかる(他の宇宙船が乗っていても関係なし)
f:id:simanman:20160526012201p:plain

未到達の星がある近くまで移動する
f:id:simanman:20160526012247p:plain

UFOから下りて再度停止モード
f:id:simanman:20160526012308p:plain

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


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


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

f:id:simanman:20160420235548p:plain:w400


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

f:id:simanman:20160420235828p:plain:w400

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


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

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

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

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

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

まず最初に初期状態から

f:id:simanman:20160420233828p:plain:w300

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

f:id:simanman:20160420234008p:plain:w300

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

f:id:simanman:20160420234125p:plain:w300

線を引いて切り落とす

f:id:simanman:20160420234154p:plain:w300

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

f:id:simanman:20160420234557p:plain:w300

f:id:simanman:20160420234611p:plain:w300

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

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

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

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

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

高速化

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

時間調整難しい

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

感想

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

Tシャツ欲しかったです(30位以内でもらえた年度ならワンチャンあったかも)