RSS

結果発表

hirokazu1020さんスコア57,916

hirataさんスコア58,027

kkさんスコア59,335

りあんさんスコア59,403

mayokoさんスコア59,621

最終ランキングトップ30

TOP30

順位ニックネーム区分応募日時総ターン数時間(秒)
1 hirokazu1020 学生 2016-11-22 20:58:44 57,916 56.7617
2 hirata ハル研 2016-11-25 00:50:49 58,027 59.2167
3 kk 学生 2016-11-24 23:26:43 59,335 55.4296
4 りあん 学生 2016-11-25 11:57:58 59,403 55.9375
5 mayoko 学生 2016-11-25 07:47:48 59,621 59.9863
6 noge ハル研 2016-11-25 09:45:10 59,879 59.2851
7 suetsugu ハル研 2016-11-25 11:13:26 60,434 59.0664
8 masayuki ハル研 2016-11-25 02:28:49 60,445 57.2851
9 walkkyou 学生 2016-11-25 01:29:28 60,616 54.6972
10 ninja 学生 2016-11-25 06:41:05 61,776 41.8144
11 phox4098 学生 2016-11-24 00:53:39 62,415 54.6542
12 tatsuya ハル研 2016-11-24 21:31:09 63,164 57.1718
13 tanifuji ハル研 2016-11-24 22:07:11 63,273 47.6699
14 femto 学生 2016-11-24 16:38:46 63,661 39.1757
15 Kmcode 学生 2016-11-25 00:51:46 64,251 18.4863
16 kurenai3110 学生 2016-11-24 03:53:09 64,717 37.4550
17 cormoran 学生 2016-11-25 11:56:06 64,850 58.5000
18 atono ハル研 2016-11-24 23:57:14 65,437 55.2324
19 wat_shun 学生 2016-11-25 00:37:35 65,949 57.9609
20 ZABURO 学生 2016-11-25 03:55:48 65,999 39.4160
21 たこし 学生 2016-11-25 10:34:30 66,919 46.0976
22 REKAI 学生 2016-11-19 17:49:03 67,066 1.3925
23 yutaka ハル研 2016-11-25 11:59:30 67,090 15.0703
24 pekosuan 学生 2016-11-16 03:25:23 67,101 35.7050
25 yuki 学生 2016-11-25 06:00:02 67,304 49.1738
26 敬愛 学生 2016-11-20 04:19:51 67,645 6.9199
27 aru 学生 2016-11-24 03:20:23 67,968 19.0996
28 shinya ハル研 2016-11-24 12:56:41 68,234 59.0234
29 NonSense 学生 2016-11-14 20:58:41 68,289 53.0175
30 efutea 学生 2016-11-18 03:26:25 68,609 0.5605

チャレンジスコア賞

全応募者のうち21%の方が72,000ターンのチャレンジスコアを達成されました。
厳正な抽選の結果、以下の5名の達成者がチャレンジスコア賞に決定しました。

  • カエルさん
  • reminさん
  • とりぷるさん
  • あべけそさん
  • duさん

実行委員会による総評

問題の特徴

今年のプロコンは、実数平面上を自由に動ける問題です。選択できる行動は「移動」と「レーザー発射」のみ、さらにスコアの決定方法は「小惑星すべてを早く壊すほど良い」と、非常にシンプルな問題となっています。問題を作る過程では「小惑星に当たったらゲームオーバー」「小惑星に引力を持たせる」など様々な追加ルールが案として上がりましたが、取り組み易さや分かり易さを考慮して、最終的に現在の形に仕上がりました。

また、例年好評をいただいているビューアを今年も用意し、問題パッケージに組み込みました。今年は新たに「連続再生機能」を追加して、宇宙船がステージを攻略していく様子を観察できるようにしました。小惑星が次々と消えていく光景は見ているだけで楽しく、スコア向上のモチベーションに繋げられたのではないかと思っています。

ビューア

作品の傾向

今年はサンプルプログラムが賢く、少し改良するだけで80000~100000ターンくらいの、そこそこ良いスコアを出すことができます。また、サンプルプログラムをさらに工夫して改良することで、70000ターン台まで到達している方もいらっしゃいました。それより上位の作品は、制限時間の60秒をギリギリまで使って探索するプログラムが多いようでした。中には60000ターンを切る作品もあり、予想以上の高いレベルの戦いに実行委員も驚かされました。

今回の問題はシンプルな一方で、最適解を出すのは現実的には難しいと思っています。また、宇宙船の位置取り、小惑星を壊す順番、体当たり、レーザーを発射するタイミングなどと考える要素が多く、良いスコアを出すためには様々な工夫をする必要があります。そのため、いろいろな手法を試して応募されていた参加者が多くいらっしゃいました。

作品によって戦略や手法は様々でしたが、「一発のレーザーで多くの小惑星を壊す」という点は多くの参加者が共通して意識されていたようでした。

一発のレーザーで多くの小惑星を壊す

レーザーにはチャージ時間があり、一度レーザーを発射すると次の発射までにはチャージ時間が必要です。一定時間内に発射できるレーザーの数は制限されているため、「一発のレーザーで可能な限り多くの小惑星を壊すこと」が良いスコアに到達する鍵となります。

小惑星をたくさん壊すためには、宇宙船の位置取りと、レーザーを発射するタイミングが重要になります。

小惑星は端っこにレーザーを当てても破壊できるため、小惑星の中心位置だけでなく、半径も考慮して位置取りを考えなくてはなりません。つまり、効率よく破壊するためには小惑星の端っこを狙う必要があるのです。

惜しい例、良い例

また、レーザーのチャージが完了した時点でむやみに発射すればよいわけでもありません。チャージが完了してもすぐに撃たずに少し移動することで、小惑星をより多く破壊できる位置まで移動できるかもしれないので、それについても考慮する必要があるのです。

多くの小惑星を破壊できる

体当たりも上手に使う

良いスコアを狙うためには、レーザーだけではなく、体当たりも考慮する必要があります。例えば、レーザーを撃つ合間に体当たりをすることで、効率よく破壊できます。また、体当たりをするつもりの小惑星は、レーザーで破壊する必要がありません。体当たりを上手に考慮するのは、難しい問題の一つだったかもしれません。

参加者の作品では、

  • 常に、宇宙船を一番近い小惑星に向かわせて体当たりで壊す
  • あらかじめ、体当たりする小惑星とレーザーで破壊する小惑星を決めてしまう

という、2つのアプローチで体当たりを活用している作品が多数でした。

制限時間をギリギりまで使う

今年のプロコンは制限時間が60秒(最終評価では240秒)と、例年よりも長めに設定してあります。今回の問題で一定以上のスコアを出すためには効率的な探索を行う必要があり、時間をかけて実装したプログラムがタイムアウトになるとガッカリしてしまうだろうと考えて、制限時間を長めに設定しました。

上位入賞者の多くが制限時間をギリギリまで使い、ビームサーチや深さ優先探索などのテクニックを活用して効率よく探索するプログラムを書いていました。また、限られた制限時間を有効に使うために、高速化を行うことで広い領域を探索できるよう工夫した作品も多かったです。

高速化については、「悪いスコアになることが分かった時点でその先の探索を打ち切る」「平面をグリッド化して探索空間を小さくする」など、それぞれの参加者が様々な方法で高速化を行っていました。

最終評価

最終評価に使った乱数は
「x = 0x7d378f80, y = 0x33394521, z = 0xf1afb002, w = 0xb71066cd」でした。

この乱数は、16面ダイスを実行委員が8×4=32回ふって出た数字です。(実はチャレンジスコア賞の抽選でも16面ダイスを活用しています)

また、最終評価は、通常時の4回分実行しています。これは、Parameter.hpp の RepeatCount を 4 に変更することで実現しています。

ほとんどの方が、最終評価では途中評価よりターン数が多くなっていました。

まとめ

今年のプロコンはシンプルながらも効率のよい戦略を考えるのが難しい問題で、苦戦された方も多かったかと思います。

開始初日は応募数も少なく穏やかな滑り出しでしたが、締め切りが近づくにつれて応募数が段々と多くなりました。そして、締め切り当日は評価待ちがたくさん出てしまうほどの応募ペースで、熱気あふれるプロコンになったと思います。

参加者の声や作品のコメントからはチャレンジスコアを目指して頑張ってくださったこともうかがえ、各々のスキルに応じて取り組んでいただけたようで、実行委員会としては大変うれしい限りでした。

最後になりますが、プロコン2016はお楽しみいただけましたでしょうか。

このようにプロコンが盛り上がりましたのは参加者のみなさんのおかげと、実行委員会一同、感謝しております。熱心にご応募いただき、本当にありがとうございました。

PAGE TOP