結果発表

さはらさんスコア2,733,098

suganoさんスコア2,709,467

totoさんスコア2,695,908

kimiyukiさんスコア2,684,068

kotamanegiさんスコア2,680,399

最終ランキング TOP 30

順位ニックネーム区分応募日時スコア時間(秒)
1 さはら 学生 2018-10-18 06:13:15 2,733,098 57.1171
2 sugano ハル研 2018-10-17 23:57:55 2,709,467 47.8359
3 toto 学生 2018-10-18 09:57:36 2,695,908 50.2187
4 kimiyuki 学生 2018-10-16 21:51:51 2,684,068 50.7031
5 kotamanegi 学生 2018-10-18 04:20:00 2,680,399 9.7500
6 nii 学生 2018-10-17 22:57:28 2,668,109 56.0703
7 kurenai3110 学生 2018-10-11 00:14:10 2,665,473 57.6562
8 masayuki ハル研 2018-10-18 08:10:40 2,660,022 57.3906
9 hirata ハル研 2018-10-18 00:28:32 2,649,289 49.6718
10 鮟鱇狸鍋 学生 2018-10-18 04:45:32 2,629,277 21.5000
11 むらため 学生 2018-10-18 06:27:32 2,619,871 54.2500
12 risujiroh 学生 2018-10-17 18:01:43 2,619,351 2.4531
13 sk 学生 2018-10-16 14:40:54 2,615,461 23.2109
14 NOSS 学生 2018-10-17 19:31:24 2,594,947 3.5234
15 c7c7 学生 2018-10-10 17:41:58 2,589,527 9.6796
16 mai 学生 2018-10-17 21:19:50 2,585,662 42.5546
17 suetsugu ハル研 2018-10-18 09:51:51 2,583,158 38.6406
18 iqeiq 学生 2018-10-17 16:41:05 2,583,005 0.2656
19 学生 2018-10-17 23:37:17 2,580,535 1.2890
20 nari 学生 2018-10-17 02:30:22 2,575,277 26.1562
21 noge ハル研 2018-10-17 23:19:12 2,572,093 38.7187
22 aquaCS 学生 2018-10-13 23:50:47 2,569,278 4.6562
23 Ark 学生 2018-10-18 01:06:40 2,562,220 52.9531
24 shamal 学生 2018-10-18 11:59:52 2,561,779 0.6015
25 aru 学生 2018-10-18 04:45:20 2,561,293 25.5000
26 Nagiss 学生 2018-10-18 11:56:59 2,560,625 7.4531
27 REKAI 学生 2018-10-12 00:27:32 2,555,487 1.0078
28 yutaka ハル研 2018-10-17 21:51:42 2,555,291 5.4609
29 ninja 学生 2018-10-18 08:16:53 2,554,959 4.7187
30 Intyamada 学生 2018-10-18 11:23:50 2,552,359 1.3671

チャレンジスコア賞

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

  • atonoさん
  • onduruさん
  • lvBさん
  • takeo1116さん
  • カツキさん

実行委員会による総評

問題の特徴

今年の問題は、限られたオーブンのスペースでなるべく多くのクッキーを焼く、という配置を効率化する問題でした。

問題の制作過程では、クッキーがおかしな形になったり、オーブンの火力が強くなったり、と紆余曲折ありましたが、最終的には大小2レーンに流れるクッキーを1つのオーブンで焼くという、シンプルな形に収まりました。


問題自体はシンプルですが、未来の予測が困難で、高得点をとるには難易度の高い問題だったのではないかと思います。

オーブンがある程度埋まるまでは点数が伸びやすいですが、クッキー同士が干渉し始めるととたんにスコアを伸ばすことが難しくなり、干渉を回避するために配置の調整、探索、確率予測といった様々な工夫が必要になる問題だったと思います。

作品の傾向

「プロコン速報 vol.1」のヒントでも触れていましたが、大きいクッキーは小さいクッキーに比べ得点率が高くなっています。

多くの作品はここに注目し、大きいクッキーを優先して焼く、という戦略を取っていました。


高得点を出している作品では、さらに無駄な隙間を埋めるために、ビームサーチなどの探索を駆使する、特定のルールで評価値を算出し、評価値の高い状態を採用するなどのアプローチが取られていました。

他にも、壁沿いへの配置を優先したり、ステージ終了までに焼き終わらないクッキーを除外するなど、様々な工夫が見られました。

大きいクッキーと小さいクッキーの役割分担

今回の問題では「捨てる」という選択肢は問題に組み込まれていませんでした。

そのため、流れてきたクッキーは遅かれ早かれほぼ全て焼くことになり、「何枚焼いたか」が得点に直結することになります。

さらに前述の通り、大きいクッキーと小さいクッキーには明確に得点の差があり、高得点のためには大きいクッキーを優先して焼く必要があります。

そのため、最終的に「大きいクッキーを焼いた枚数を最大化」しつつ、その上で「小さいクッキーを焼いた枚数を最大化」していくことが高得点への鍵となっていました。


具体的なアプローチを見てみます。

まず大きいクッキーは得点率が高いので、これをできるだけたくさん敷き詰めるようにすると良さそうです。

次に、空いた隙間に小さいクッキーを詰めて得点を稼ぐということが考えられそうです。

しかし、「現在」だけを見て隙間を埋めてしまうと、後々焼き終わっていない小さいクッキーが邪魔をして大きいクッキーを置けなくなってしまう、ということが起きてしまいます。

大きいクッキーと小さいクッキーの役割分担

ここで思うように点数が伸びない、あるいは逆に点数が下がってしまった、という方もいらっしゃったのではないでしょうか。

これを回避するために、小さいクッキーが大きいクッキーを邪魔しないように置いていくための工夫が必要になってきます。

3D の問題として捉える

既にお気づきの方もいらっしゃるかと思いますが、実はこの問題は、「焼き時間」を Z 軸とすることで3次元の充填問題として考えることができます。

各クッキーのスコアもこの3次元空間における体積を基準にしており、同じレーンのクッキーは単位体積あたりのスコアが均一になるよう設定されていました。


このことに気づくと、解き方をシンプルに考えられたり、既知のアルゴリズムを当てはめやすくなったりしたのではないでしょうか。

実際に投稿された作品の中にも、問題を 3D で捉えて解答している方もいらっしゃいました。

3Dの問題として捉える

評価環境

評価環境で使われた乱数は、

randomSeedX = 0x2b895058; randomSeedY = 0x522fb11d; randomSeedZ = 0xf638264a; randomSeedW = 0x90c9ee0e; randomSpinX = 0xd22; randomSpinY = 0x6b; randomSpinZ = 0x3;

でした。

今回は例年と違い、プログラムの各所で乱数の空回しを行っていました。

これは乱数の予測を難しくするための試みでした。

また、評価環境全体としてもビルドオプションの見直しや評価結果を見やすくする試みなど、参加者の方々が問題に集中できるよう改善を加えています。

まとめ

今回のプロコンは、開催期間が14日間と例年と比べて短いにも関わらず、昨年の3倍近い投稿数がありました。

乱数によって結果が変わりやすい問題だったこともあり、皆さん調整に余念が無かったのではないかと感じています。


開催中も抜きつ抜かれつの接戦が繰り広げられ、委員会一同、固唾をのんで見守っていました。

最終的には委員会の予想を上回る 270 万点台が叩き出されるという結果になり、参加者の方々の熱意と技量に驚かされました。


余談ですが、委員会の調べによると、開催期間中に焼かれたクッキーの総枚数は推定でおよそ... 2億枚以上!

一枚 10g だとすると重量にして 2000t、凄まじい量のクッキーが焼き上がりましたね。


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

参加者のみなさんのおかげで、プロコン2018も大いに盛り上がりました。

熱のこもった作品をご応募いただき、本当にありがとうございました。