simanのブログ

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

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位以内でもらえた年度ならワンチャンあったかも)

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

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


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

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

www.hallab.co.jp

コンテスト期間

  • 「2015 12/15(木) - 2016 01/07(木)」

説明

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

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ぐらい使った気がします。

【コードゴルフ】シンプル・ライフゲーム 参加日記

ここ数日コードゴルフという競技で遊んでいました。

codeiq.jp

題材としてはライフゲームというゲームをいかに短く書くかの勝負で、今回Ruby部門で一番短くかけました。

d.hatena.ne.jp

今回書いたコードです。(136byte)

n,h,w,*f=*$<;n.to_i.times{z=w=w.to_i;f=f.map{|l|l.gsub(/./){(?*+$&+?.*z+=1)[(0..8).count{|e|(f*2)[~-z/w-e/3][(z-e%3)%w]<?.}-3]}}};puts f

ちょっと見づらいので整形します

n,h,w,*f=*$<;

n.to_i.times{
  z=w=w.to_i;

  f=f.map{|l|
    l.gsub(/./){
      (?*+$&+?.*z+=1)[(0..8).count{|e|(f*2)[~-z/w-e/3][(z-e%3)%w]<?.}-3]
    }
  }
};

puts f

1つずつ解説していきます。

n,h,w,*f=*$<;

今回は入力の形が「世代、高さ、幅、フィールド」という形で与えられていたので、「*$<」で与えられた入力を展開して、それぞれに割りふります。最初の3行を受け取れば残りはフィールドなので「*f」で回収します。

n.to_i.times{
.
.
.
}

n世代分繰り返します。ここは色々試しましたがこれが一番短かったです。

z=w=w.to_i;

wの値は後で頻繁に使用するのでここで数値化しておきます。ついでにz変数もwで初期化しておきます。(後で使用)

f=f.map{|l|
.
.
.
}

現在fの要素にはフィールド情報の各行が文字列として格納されています。ライフゲームでは次の世代のフィールド情報を作成して更新する必要があるのですが、一時変数を使用するとどうしても長くなってしまうので、fにmapを適用してその返り値を再度fに代入することで一時的な変数を使用せずに実現します。lには行の情報が入ります。

l.gsub(/./){
    (?*+$&+?.*z+=1)[(0..8).count{|e|(f*2)[~-z/w-e/3][(z-e%3)%w]<?.}-3]
}

1つずつのセルを見ていく必要があるのですが、ここで「l.chars.map」を使用した場合には最後に「*''」で終わる必要があるので、gsubで1文字ずつキャプチャし、その1文字に対して置換を行っていきます。(返り値は置換された文字列が返ってくるので「*''」もいらない!、あと本来はブロック変数にキャプチャした文字が入ってきますが、$&にも同じ値が入っているのでこれを使用することで1文字減ります)

(0..8).count{|e|(f*2)[~-z/w-e/3][(z-e%3)%w]<?.}

周囲のセルを数える処理ですが、今回は画面の端がループする仕様でした。しかしRubyでは幸運なことに-1の値は配列の後ろから数えた値を取ってくるので、負値に関しては気にすることなく参照できるのですが、(hもしくはw)の値をオーバーした場合にはnilを返してしまうので泣く泣く「%hか%w」をする必要があります。

f:id:simanman:20151119201019p:plain

そこで最初のy座標については元の配列の大きさを2倍にすることでオーバしても「%h」せずに済むようにしました。

f:id:simanman:20151119201454p:plain

これで「(hoge)%h」な記述を避けることができて良いです。

[~-z/w-e/3]

この記述ですが、通常周りのセルを参照する場合には「-y-1,-y,-y+1」なコードを書くのですが、これだと「y+e/3-1」になります、そこで、どこか事前にyを+1しておくことで「y-e/3」の記述に変更することができます。自分の場合はzの初期化の際に+1の処理を書いています。ただ、このままだと最後の値が1つ繰り上がってしまうので「~-」で実際のzの値より1小さい値にしておく必要があります。(x方向の参照も同様に事前に+1してます)

<?.

これは取得した文字を比較して「*」の時にtrueを返すようにしてます。「==?*」より1文字お得です。

最後に取得した生きているセルの値を文字列のindex参照として使ってます。rubyでは文字列に対して[]メソッドが使えるので、普通に書けば

"...*#{c}....."[index]

の記述で次の世代の文字に更新されるのですが(まず生きてる死んでるにかかわらず生きてるセルの数が3つであれば無条件で生き残ります。あとは4つパターンが生きてる状態だと生、死んでる状態だと死です。なのでこれはそのままキャプチャした値を返せばOKです)これだと少し長いので、まず左方向に3つずらして

"*#{c}........"[index]

「.」が連続するので文字に*メソッドを使って圧縮します。(5になっているのは*が9個あっても-3されて6、つまりs[6]が参照できればOKなので5にしてます)

(?*+c+?.*5)[index]

この5はzで代用します(ついでにインクリメントします)

(?*+c+?.*z+=1)

でも、これは問題があって、最大で生きてるセルが(9-3=6)出るはずなので、3x3フィールドで全部のセルが生きていた場合には、参照しきれずnilが返って、出力が異なってしまいます("*x....".size #=> 6)。が、今回のテストケースはPassしたのでスルーします。(グレー感ある


今回の個人的なキーポイントは

  • countがブロックを取れる
  • gsubがブロックを取れる

この2つでした。

取り組んだ時間は多分50hぐらいだと思います。

まだ雰囲気的に短くなりそうな感じがあるので、これより短いコードを思いついたら是非教えてください!

追記(2015/11/19 23:21:00)

自分と同率1位だった@rotary-oさんのコードが公開されました。


n,h,w,*s=*$<;
s*='';
n.to_i.times{
  i=w=w.to_i;

  s.gsub!(/./){
    i+=1;
    (?*+$&+?.*5)[(0..8).count{|j|(s*2)[(i-j%3)%w-(~-i/w-j/3)*~w]<?.}-3]
  }
};
$><<s

3x3のコーナケースで落ちない正統派解答です。

i+=1;(?*+$&+?.*5)

を 

(?*+$&+?.*i+=1)

に変えれば、今回の問題に関して言えば2byteさらに短くなります。(グレーゾーン解答

自分も1次元で何回かトライしてたのですが、うまくいかなくて諦めちゃったんですよね。。。

正統派で行くのであれば、減るサイズは1byteですが

"...*#$&"[(0..8).count{|j|(s*2)[(i-j%3)%w-(~-i/w-j/3)*~w]<?.}]||?.

こんな感じで書けます。

さらに追記(2015/11/24 02:18)

前回の追記で134byteが最短だと思っていたのですが、shinhさんによってさらに3byte減りました。

はじめてのにき(2015-11-24)

テクニックとしては

n.to_i.times{
.
(繰り返しの処理)
.
}

としていたところを

eval "(繰り返しの処理)"*n.to_i

こんな感じで(繰り返し行う処理)を文字列化して「*n」をしてあげることで、「n.to_i.times」と同じ処理を行っています。evalを使ったテクニックなのですが、目から鱗でした。

MM89参加日記

初日

問題文公開、お題は「迷路が与えられるので、セルを修正してたくさん探索しような!」です

とりあえず、まず迷路の盤面から'U'を別の要素に置き換えてみるテスト。Uターンマスはその時点で探索失敗してしまうので(盤面の外側だと大丈夫だけど1pt)
邪魔以外の何者でもないのでとりあえず消してみる。


次に、ランダムじゃなくて貪欲にしてみる。(S, R, Lに置き換えてみて一番スコアが良いやつを採用)

ちょっと上がった。

点数低いやつの結果を見てみると、外周は探索しているけど、中心部まで到達しきれてない感じか。

適当に直線決めて、それに沿うように'S'に変えていけばとりあずF点は取れるのかな、細かい点を取りに行くなら、外周を'U'に変えるとか?(微妙)

外周は'S'のほうが良さそう。というより'S'以外の値が入っているとなかなかつらい感じがする。

Forumちょっと覗く、

The 'U' cells make the maze a bit more interesting. I'm not going to give you a hint on how to use the 'U' cells :)

'U'の使いみちがあるっぽいけど本当かよ

snuke氏が作った便利ツールを今回どんどん使っていくぞ!

Generic Grid Editor


ひたすらSを増やして遊んでる

今日はここまで、適当にSを追加するだけではだめそう

2日目

ある任意の点から探索をはじめて、最初の方角と反対の方向を向いた時に、セルを修正するようにしてみる。

色々やって6割ぐらいはとれそうな感じ。

4日目

いままでは経路を作ることを考えてたけど、盤面を一回Sで埋め尽くしてそこから、一部の盤面を元に復元していく戦略でいってみるか

1つのセルを通る方法は「上、右、左、下」の4方向あって、これが例えば正方形の盤面を全て埋め尽くした場合は各セルは4の値をもっていて、
これを元の盤面に戻すとこの値が各セルで減っていく訳だな、各セルで4つの状態を持っている

Eが存在している場合は、4つより大きくなることがある。

Uを設置すると隣接するセルの状態の数が最初は2減る、2つ目はSの場合は2減ってこのセルへの到達は不可能

Sのセルの回りにL字型にUを設置されるとそのセルへの到達ができなくなる。

5日目

色々あって、とりあず適当に盤面を生成してから、そこから山登りで盤面を更新していく方針にしてみた。

72.65

やっと7割台

最終日

日記が毎日続かないのはご愛嬌

結局5日目から方針をコロコロ変えて元に戻ってきた感じ。

戦略としては、まず山登りを始める前に初期盤面を生成します。


こんな盤面があったとして

f:id:simanman:20151026231918p:plain

探索ポイントがこうあるとする

f:id:simanman:20151027002245p:plain

例として、一番下側から探索を始めるとして

f:id:simanman:20151027002307p:plain

一歩目、いきなりUにぶつかってEND

f:id:simanman:20151027002333p:plain

だと、経路ができないのでここでSに置き換える

f:id:simanman:20151027002431p:plain

再度進める

f:id:simanman:20151027002455p:plain

今度はUでは無いが、Lを連続で踏んでしまった。この場合Uターンすると生存率が低めなので、Rに置き換えて方向を修正する

f:id:simanman:20151027002606p:plain

再度、探索。

f:id:simanman:20151027002628p:plain

ゴールすることができたので、これで1つの経路が完成。これを全ての探索ポイントから行い一番良さそうな奴を採用する。
これが1セットの作業。確定した経路のマスは次のターンから更新ができなくなる(更新したら経路が破壊されるので)

これをF(マスを修正出来る数)が0になるか、どの探索ポイントからもゴールにたどり着けなくなるまで進める。

ここまでが初期盤面作成処理。(この段階だと7割)

ここから余った時間で山登りで点数を地道に稼ぐ

実際に何するかというと、現在の盤面からEとWとSを除いたセルをランダムで2点選びこれをランダムな値に変更する。
変更後にスコア計算。スコアが上昇していたら採用。これを時間が切れるまで延々と繰り返す。(これで75点辺り)

あとはゴニョゴニョとパラメータをいじって3点伸ばす(78点)

ビジュアライザの編集

  • クエリの数が多くても表示するように
  • どのマスを変更したかがわかるように色づけ

f:id:simanman:20151027010802p:plain:w400

今後はこの辺りもっと力を入れていこう

感想

  • 見た目良さそうな問題だったけど、実際やってみると後半の伸びが無くて結講つらかった
  • スコア計算の計算量が重すぎて、盤面が大きいと初期盤面の生成段階で大分時間を使ってしまう。スコア計算の実装を軽くする方法がサッパリだった
  • 本当は焼きなましとかが良さそうな気がしてたけど、良い近傍が思いつかなかった。
  • パラメータ調整つらい
  • 時間調整つらい(80 * 80で落ちないように調整したけど、どうだろ)
  • 8割台に乗るまで10sampleで進めるつもりだったので、100すら通してない、絶対システムテストでスコア落ちる
  • Eマスつらい(計算量的に)

パラメータ調整時のテンション


終戦準備中