CodeIQ Blog

自分の実力を知りたいITエンジニア向けの、実務スキル評価サービス「CodeIQ(コードアイキュー)」の公式ブログです。

「マラソンマッチ:効率的に敵を撃滅せよ」2013年7月15日24時時点暫定ランキング発表 #javascript #MarathonMatch

CodeIQ中の人、millionsmileです。

CodeIQ初のマラソンマッチ問題です!「マラソンマッチをCodeIQで出してほしい」というリクエストもと、誕生したのが「マラソンマッチ:効率的に敵を撃滅せよ」という問題です。本家のTopCoderと比べれば少し易しめです。

さて、初のマラソンマッチ問題の、初の暫定ランキング発表です。出題者の柳井さんより解説記事も届いておりますので、参考にしてみてください。そして更なる上位をめざしてください。

=======================================

● 順位

 2013年7月15日、24時時点の順位は、以下の通りになりました。


1位(1294点)sapics 様
2位(1134点)hellowd 様
3位(1119点)ayuzak 様
4位(1111点)mad_p 様
5位(1076点)takryo 様
6位(1033点)ciel 様
7位(1017点)hm001 様
8位( 812点)とさ 様

特殊解 iehn 様

 得点としては、sapics 様が突出して高かったです。また、グループとしては、1100点台が第2グループ、1000点台が第3グループといった感じでした。


● 感想

 1位の sapics 様は、最初のフィードバック時点では20秒をわずかにオーバーしており、ランキング圏外でした。しかし、最終的な順位判定の際には15秒台に処理時間を収めてきて、見事ランキングに入りました。

 sapics 様のコードは、長大なコードがminify(圧縮)されていました。JavaScriptでは、コードをminifyした方が、パースの時間が節約されて実行時間が短くなります。

 sapics 様のコードが最初に処理時間をわずかにオーバーしていたことから、以下の過程でプログラムを作成したのだろうと推測しています。

 1.最初に、得点は高いが時間が掛かるコードを作成した。

 2.そのコードを、処理時間内に収めるために、高速化を施した。

  (その手法の1つとして、minifyを行った)

 これは、コードと実行時間から推測したことです。そのため、実際は他の手順で作成されたのかもしれません。sapics 様のコードは、最終的に実行時間が15秒ほどになっており、余裕をとって処理時間を短くしたのだろうと想像しました。


● 第2戦について

 問題は、パラメータを変えて、第2戦に突入します。

 新しいコードを送っていただいた場合は、最新のコードで順位用の判定を行います。また、そのままの場合は、第1戦のコードをそのまま使って、順位の判定を行います。

 というわけで、同じアルゴリズムでも、問題の環境が変わったために、順位が変動する可能性があります。

 さて、第2戦は、第1戦よりも敵の数を増やして、索敵範囲を広げました。

 そのため、より敵の中心位置を狙って攻撃しやすくなっています。しかしその分、計算に掛かる時間も増えています。

 処理に使える時間は、前回の1砲撃セットあたり160msecから、340msecに増えています。ただし、敵の数は2倍に増えています。

 処理の内容によっては、計算時間が2倍ではなく、4倍などになり、時間がオーバーする可能性があります。


● 敵の生成アルゴリズム

 問題文にも途中で記述を加えましたが、敵は以下の手順で生成されています。

1. 「巣穴の数」の巣穴が、マップ上に散布される。

f:id:codeiq:20130717162017p:plain

2. 巣穴から出てきた敵は、「最大移動回数」以内で、「X方向/Y方向移動量」以内ずつ移動する。


移動1回

f:id:codeiq:20130717162055p:plain



移動2回

f:id:codeiq:20130717162109p:plain



移動6回

f:id:codeiq:20130717162123p:plain

3. 敵は「視界範囲」にいる仲間の平均値の位置に移動して寄り集まる。


視界範囲5

f:id:codeiq:20130717162143p:plain



視界範囲9

f:id:codeiq:20130717162158p:plain



視界範囲13

f:id:codeiq:20130717162211p:plain

 このアルゴリズムは、生物が巣穴から出て移動する様子を模しています。

1.風に運ばれて、女王蟻が土地に降下する。

2.巣穴から出てきた蟻のランダムウォーク。

3.互いに身を守るための協調行動。

 このアルゴリズムによって、敵の配置は以下の特徴を持ちます。

A.巣穴の位置には大量の敵がいる。

B.巣穴から離れると、敵の密度は減る。

C.巣穴から周囲に、いくつかのヒトデ状の足(直線状の敵の配置)が伸びる。

 ABは必ず現れる特徴で、Cは条件によっては現れます。Cが発生する理由は、敵が視界の範囲内で寄り集まるためです。


特徴の例

f:id:codeiq:20130717162232p:plain

 また、敵の配置は、ドラクエのマップのように、上下と左右でループしています。そのため、端近くを砲撃した場合は、索敵範囲として見えている範囲から、逆側の端の状況も推測可能です。

 生成アルゴリズムは、JavaScriptなので自由に見ることができます。こういった生成アルゴリズムの特徴を上手く生かすと、敵を狙いやすくなると思います。

=======================================
まだまだ暑い夏は続きますし、マラソンマッチも続きます。
問題文も少しずつ変化しているので、ちょろちょろ確認してみてください。

みなさまの挑戦お待ちしておりますー。

https://codeiq.jp/ace/yanai_masakazu/q378
f:id:codeiq:20130717164618j:plain

CodeIQ中の人の一言:リラックマの隠れファンです。

エンジニアのための新しい転職活動!CodeIQのウチに来ない?の特集ページを見る