結果発表

sumoruさんスコア13,196

kurenai3110さんスコア13,323

hirataさんスコア13,981

ninjaさんスコア14,436

nariさんスコア14,710

最終ランキング TOP 30

順位ニックネーム区分応募日時総ターン数時間(秒)
1 sumoru 学生 2017-10-27 11:54:31 13,196 42.9218
2 kurenai3110 学生 2017-10-27 11:40:03 13,323 59.3750
3 hirata ハル研 2017-10-27 00:20:39 13,981 55.0468
4 ninja 学生 2017-10-27 11:55:03 14,436 57.3671
5 nari 学生 2017-10-27 11:46:24 14,710 51.5546
6 noge ハル研 2017-10-27 01:46:50 15,113 59.7968
7 Ark 学生 2017-10-27 03:19:33 15,137 57.7578
8 sugano ハル研 2017-10-22 18:35:15 15,608 2.0078
9 kimiyuki 学生 2017-10-16 07:44:37 16,000 46.7187
10 りあん 学生 2017-10-27 11:59:39 16,204 45.0312
11 shamal 学生 2017-10-27 11:25:23 16,231 59.6093
12 dohatsutsu 学生 2017-10-26 17:54:03 16,374 29.5000
13 aru 学生 2017-10-25 23:41:04 16,409 59.1015
14 垂象含筆 学生 2017-10-27 10:04:19 16,522 57.6093
15 たこし 学生 2017-10-25 21:54:19 16,536 51.2578
16 REKAI 学生 2017-10-26 18:50:21 16,654 51.2343
17 Kmcode 学生 2017-10-27 01:12:54 16,950 14.1015
18 cormoran 学生 2017-10-26 01:56:29 16,978 1.4921
19 TangentDay 学生 2017-10-27 02:44:38 17,133 13.4062
20 okeigo 学生 2017-10-27 03:41:06 17,162 52.7265
21 mak4026 学生 2017-10-26 18:55:02 17,190 47.6093
22 iqeiq 学生 2017-10-27 05:59:42 17,197 36.1093
23 nakanocchi 学生 2017-10-27 11:26:57 17,207 0.2187
24 Hopelimb 学生 2017-10-27 11:15:12 17,324 55.3906
25 femto 学生 2017-10-27 11:06:06 17,365 0.6718
26 masayuki ハル研 2017-10-27 09:33:21 17,380 0.2500
27 kosakkun 学生 2017-10-23 01:50:51 17,402 56.2578
28 WA_TLE 学生 2017-10-15 14:36:51 17,406 50.0000
29 spark 学生 2017-10-24 23:02:51 17,475 19.8828
30 not 学生 2017-10-27 10:57:00 17,602 55.8593

チャレンジスコア賞

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

  • simonchxさん
  • takemuraさん
  • Mt.Yさん
  • こあぷろさん
  • MasaPさん

実行委員会による総評

問題の特徴

今年のプロコンは、異なる特徴を持つ複数のUFOを連携させる問題でした。

家の配置をただランダムにするのではなく街のような集まりにすることで、「大型UFOは街を目指す」といった方針を立てやすくしたり、農場にある箱の総数を設定しないことで、シンプルでありながら奥深い問題になったかと思います。

また、例年好評をいただいているビューアを今年も用意し、問題パッケージに組み込みました。かわいく配達するUFOたちを眺めているだけでも楽しく、効率よく配達する方法を考える助けになったかと思います。

作品の傾向

今年は定番の解き方といえるようなものは無く、さまざまなアプローチが見られました。

チャレンジスコアである「総ターン数:22222」は簡単に到達できるスコアではないのですが、多くの方が達成されていて、皆さんの頑張りを伺うことができました。さらに、上位者は予想を大きく上回る13000台のターン数に到達し、これには実行委員も驚かされました。

UFOの数が多く、今回は最適解というものを出すことは難しいと思います。多くの参加者が取っていた手法として、「農場と大型UFOで近い方から箱を補給する」、「あるUFOが担当する家に配り終えた後に、他のUFOの担当する家へ効率よく配れる場合は担当を奪う」、「農場から見た家の方向(角度)でソートして担当を決める」などがありました。

小型UFOと大型UFOの使い分け

  • 移動が速いけど一度に積める箱が少ない「小型UFO」
  • 移動は遅いけどたくさんの箱を積める「大型UFO」

これらの特徴の違いをどう使い分けていくかが鍵となりました。


使い分けを全く考えていないサンプルプログラムをビューアで見ると気づくかと思いますが、移動の遅い大型UFOを小型UFOと同じように配達させてしまうと、どうしても足を引っ張ってしまいます。一方、移動の速い小型UFOは、あっという間に箱を配り終えて何度も農場まで戻っているかと思います。

そこで大型UFOは配達するよりも移動できる農場として考えてしまい、小型UFOは農場か大型UFOの近いほうから箱を受け取ることで、お互いの短所を補って無駄な移動を減らすことができます。

UFOの使い分け

街を見つける

ステージ内の家は完全なランダムではなく、街としてある程度まとまって配置されています。この街を見つけることができれば、街ごとに向かわせるUFOを決めて配達を分担することができます。

街の見つけ方としてはk-means法というアルゴリズムを使ったり、ステージをいくつかの区画に分割して区画ごとの家の密度で決めるという作品が多くありました。

街を見つける

さらに効率よく配る方法を探す

大型UFOの通り道になる家には小型UFOでは配達しないようにしたり、巡回セールスマン問題を解いて小型UFOの配達経路を求めたりなど、大小さまざまなテクニックを積み重ねていくことが、上位入賞への道につながりました。


今年のプロコンも制限時間が60秒と昨年同様に長めにしてありますが、こういったテクニックをどんどん試していただくために長めに設定しました。

シンプルに解くと数秒もかからないで終わってしまいますが、上位者の多くはこの60秒を使い切っています。その使い方もさまざまで、「パラメータをいろいろ変えながらひたすら試す」、「ターン数を先に決めてしまいそのターン数で配り終わる方法を探す」、「ステージごとに時間を決めてその間で試す」といった方法を採用している参加者もいました。

評価環境

今年は例年とは異なり、最終評価というものを行わずに問題パッケージと評価環境の乱数を別にすることで、開催期間中の評価がそのまま最終ランキングとなるようにしました。

評価環境で使われた乱数は「x = 0xbd3f8371, y = 0xc14d7726, z = 0x962cf9fe, w = 0xf9b35080」でした。

(ちなみに、例年最終評価の乱数決定で活躍していた16面ダイスはチャレンジスコア賞の抽選に使われました)

以前参加された方でお気づきの方もいらっしゃるかもしれませんが、実は最適化の見直しなどにより、評価環境が大幅に高速化されました。作品を応募してからスコアに反映されるまでが早くなり、快適になったかと思います。

まとめ

今年のプロコンはシンプルなルールでありながら効率を上げる方法がいくつもあり、難しく感じた方やアイデアを試しきれなかったという方もいたかと思います。

例年に比べて開催期間がやや短いのですが、作品数で見ると昨年の倍近くあり、しかも全作品の半数以上はなんと最終週の平日のみで応募されたもので、とても活気のあるプロコンになったと思います。

参加者の声や作品のコメントからは、初参加の方から常連の方まで各々のスキルに応じて取り組んでいただけたことが伺え、実行委員会としては大変うれしい限りでした。


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

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