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

simanのブログ

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

現在開催中 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マスつらい(計算量的に)

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


終戦準備中

PathDefense日記(Topcoderマラソンマッチ)

0日目

今日からTCO MM Round2の始まり始まりー、いつも対戦後に戦略とかをツイッターに流しているけど、
今回は日記を使ってコンテスト中の考えとかを雑にまとめてみるテスト。

1日目(2015/05/26)

5:00 起床

起きて問題文を読む。和訳が面倒だ...ひたすらGoogle翻訳に英文を投げ続ける

「Path Defense」
https://www.topcoder.com/longcontest/?module=ViewProblemStatement&compid=48152&rd=16471



タワーディフェンスだ」!

7:00 問題文大体翻訳終わった

とりあえず何もしないAIを投げる

165000.00

正のスコアが取れた!圧倒的感謝!

19:00 帰宅

とりあえず基本的な部分のコードを書き始める。

ぼーっと何もしないビジュアライザを眺める

「波状攻撃きつそう」

そういえばcreepって侵略者って認識だけど完全にコイツで再生される

f:id:simanman:20150526205839j:plain

ぶつかったら爆発して消失するところとか似てる

22:00

色々足回りのコード書いてるだけで終わりそう

今のところhoshiさんとhogeさんが上位

問題がCODEVSっぽいというか1.0ってタワーディフェンスだったような(参加していないので詳細は知らず)

23:45

testerに修正があったみたいyowaさんのツイートで気づく

とりあえず「攻撃範囲 * 攻撃力 / コスト」でタワーの価値を計算してみる、ゴミのようなタワーからコスパ最強のタワーまで色々あった。攻撃範囲のことを考えても使うタワーそんなに多くなさそう。

2日目(2015/05/27)

0:00

とりあえずタワーの射程範囲を見える化しておこう

グリッド系の問題では毎回お世話になってる「PathFinding.js」で確認
PathFinding.js

範囲1
f:id:simanman:20150527000231p:plain:w300

範囲2
f:id:simanman:20150527001008p:plain:w300

範囲3
f:id:simanman:20150527001339p:plain:w300

範囲4
f:id:simanman:20150527001702p:plain:w300

範囲5
f:id:simanman:20150527002024p:plain:w300


範囲5デカっ

範囲3から使い物になりそう。範囲1とか2はテストケース次第って感じかな

0:30

とりえあず眠いので寝よう

7:00

起きる。支度して会社

22:00

ひたすら足回りを実装、まだ終わらない

3日目(2015/05/28)

1:00

のんびり考えてたらこんな時間。

これ波状攻撃を以下に防ぐか、そして捨て基地が必要なのかが気になる。
端から4マスしか離れていない場所にある基地とか、近場のスポーン地点から波状攻撃があったら
即詰みしそう

3:00

コメントをdoxgen風に
明日には提出できるといいな

7:00

起床

20:40

帰宅

タワーを立てる条件を考えよう

  • 1. 敵が出現する
  • 2. 現在の建設状態で敵が基地に到達出来ない場合はスルー
  • 3. 敵を止めきれない場合、建設を行う

この「敵を止めきれない場合」を判定するのが難しい。

22:45

とりあえずコードに「やりたいこと」をコメントで残して「実装まだですコメント」を入れていこう

4日目(2015/05/29)

最初の1週間は何も出来ないマンになってる気がする

0:25

マップの各要素をセルとして扱っていたけど、各セルに対して「防御価値」をつけて
防御価値の高いセルを多く守れるようにタワーを設置してみよう。

防御価値の高いセルとは

  • 多くの基地への経路の一部となっている(ここを通る敵が多いので守るべき)
  • 基地に近い(基地に近いところは火力を高くしておく)

あまり思いつかないけど、とりあえずこの辺りで

5日目(2015/05/30)

ひたすら実装、想像以上に実装が多い

2:30

とりあえず欲しい機能をAmazonウィッシュリスト感覚で追加していったら
コード量がどんどん増えていく...

3:00

結講実装したつもりだけどまだ出せない...土日頑張ろ

6:00

おはようございます!そしておやすみなさい!

10:30

おはようございます!

頑張って今日で2投目投げたい、とりあえず戦略を一度整理して少しずつ実装していくことに

12:00

kindle 50%還元セールが始まってた。購入作業

6日目(2015/05/31)

機能はkindleのセールでほとんど作業できなかった


19:30
やっと完成したけど、バグ

7日目(2015/06/01)

バグが取れたので投げてみる

226754.39

うん。まぁこんなもんか、とりあえずここからここから

3:00

2投目を投げる

384385.96

やっぱり波状攻撃に対応しないとこんなもんか

8日目(2015/06/02)

セルに対して「防御価値」をつけて、その合計値が高いところにタワーを置くようにする

3投目

520472.44

まだちょっと評価値が変な感じ、あとは「捨てタワー」もどうするか出来てないし

13日目(2015/06/07)

日記つけるのさぼってました

日本勢の順位が1位(eitahoさん)、5位(hoshiさん)、11位(takaptさん)とかなり上がってきてる。

正直このゲームまだ「敵をひたすら殲滅」するゲームなのか「タワーを犠牲にしても良い」
のかよくわかってない

最終日(2015/06/08)

スプラトゥーン楽しい(∩´∀`)∩

Rubyで配列の最大値と最小値を同時に取得

rubyでは配列の最大値と最小値を同時に取得出来るminmaxメソッドがあります。

minmaxを使わないver

array = [1,2,3,4,5]

min = array.min
max = array.max

puts min
puts max
1
5

使うver

array = [1,2,3,4,5]

min, max = array.minmax

puts min
puts max
1
5

ちょっとだけ記述量が減ります。minmax_byで条件をつけた最小値、最大値を取得出来ます。

京都旅日記 最終日

今日で最終日です。

朝は荷物をまとめて、忘れ物がないかチェックしてホテルのチェックアウトを行いました。ちょっと荷物が増えてるのでトランクの中身がかなりギチギチになりました。。。

サイクリング

京都駅から関西空港までは特急はるかで向かうことにしたのですが、それまでちょっと時間が空いたので近くのレンタルサイクル屋さんで自転車を借りて京都の町をひたすら回ってました。(どちらかと言うと鴨川を北上した感じ)

f:id:simanman:20150322104432j:plain

f:id:simanman:20150322105256j:plain

さよなら京都

2時間ぐらいのサイクリングを終えて、京都駅に戻ってきました。そこから特急はるかに乗って関西空港

f:id:simanman:20150322130613j:plain

お土産たくさん

関西空港に着くと、サッサと搭乗手続きを済ませてお土産を購入しに向かいました。今回、SamurAIcodingで得た賞金2万円があったので、全部お土産に使いました。ありがとうございます。

f:id:simanman:20150322150149j:plain

昼飯は天ざるです。

自宅

那覇空港に到着 → 自宅。今回5泊6日というとても長い帰還京都にいましたが、観光地が多すぎて結局全部回れませんでした。あと2週間くらい滞在すれば桜も満開になって観光地も全部回れる気がしたのですが、長時間の徒歩によって腰をいためたのと、主に諭吉さんが大量に飛んでいったので断念しました。(あと有給がそんなに無い)

次回訪れるのがいつになるのかわかりませんが、次はまた別の所を巡ってみたいと思います。