RSS

結果発表

o0p1qさんスコア36,935,484(0.1210秒)

hirokazu1020さんスコア36,935,484(0.1250秒)

ustimawさんスコア36,935,484(0.1640秒)

最終ランキング

総合TOP3

順位ニックネーム応募日時スコア時間(秒)
1 o0p1q 2016-01-06 17:33:06 36,935,484 0.1210
2 hirokazu1020 2016-01-07 03:32:35 36,935,484 0.1250
3 ustimaw 2016-01-05 08:34:41 36,935,484 0.1640

学生部門TOP10

順位ニックネーム応募日時スコア時間(秒)
1 o0p1q 2016-01-06 17:33:06 36,935,484 0.1210
2 hirokazu1020 2016-01-07 03:32:35 36,935,484 0.1250
3 ustimaw 2016-01-05 08:34:41 36,935,484 0.1640
4 たこし 2016-01-05 16:03:51 36,935,484 0.2324
5 takapt 2016-01-07 11:58:25 36,935,484 0.3320
6 uafr_cs 2016-01-07 11:44:53 36,935,484 0.3554
7 ponyopoppo 2016-01-06 20:33:11 36,935,484 0.5664
8 __math 2016-01-07 04:14:26 36,935,484 0.9414
9 prime 2016-01-05 02:19:27 36,935,484 0.9960
10 maroon 2015-12-17 17:16:04 36,935,484 1.0097

ハル研部門TOP5

順位ニックネーム応募日時スコア時間(秒)
1 atono 2016-01-07 02:17:59 36,935,484 1.0332
2 ohnishi 2016-01-07 11:42:02 36,935,484 1.2070
3 tagoya 2016-01-06 02:30:32 36,892,548 3.7636
4 suetsugu 2016-01-06 05:17:06 36,891,638 14.1386
5 hirata 2016-01-05 20:16:53 36,733,694 9.8164

チャレンジスコア賞

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

  • fmhrさん
  • 風矢さん
  • tsukasaさん
  • エトさん
  • iwashi31さん

実行委員会による総評

問題の特徴

例年、正解はなく、工夫してスコアを上げていく問題が多いのですが、今回は、少し趣向を変えて、最適解(理論上の最高得点)を求めることができて、さらに高速化で勝負するという、二段階で楽しめる問題にしてみました。

また、例年好評をいただいているビューアを今年も用意し、問題パッケージに組み込みました。これによって一層問題に取り組みやすくなり、また街を走り回って荷物を配達する宅配業者の雰囲気も感じられたかと思いますが、いかがだったでしょうか。

作品の傾向

経路探索して、配達順序を工夫するなどしてチャレンジスコアである27,000,000点に到達している方が多くいらっしゃいました。時間帯指定されていない荷物をどの時間帯に配達するかの決め方が適当でも、各時間帯での配達順序をある程度がんばれば、チャレンジスコアには到達できます。

そこからは、時間帯指定されていない荷物をどの時間帯に配達するかの決め方を工夫するなどすると、少しずつスコアが上がっていきます。これで最適解のスコアにかなり近くなった方や、開催期間中は最適解と同じスコアなのに、最終評価で最適解と同じスコアにならないという方もいらっしゃいました。地道にスコアを上げていく手法で、厳密には最適解は求まらないのに、乱数のシード値によっては最適解と同じスコアになることもある、というところまでは行ったけれど、最終評価では乱数のシード値が変わることや、4回分実行することもあり、最適解と同じスコアにはならないという方もいたようです。

最終的に、24名の方が最終評価で最適解と同じスコアに到達していました。この中には、高速化のために意図的に、できないはずの枝刈りをされ、乱数のシード値を変えると最適解と同じスコアにならないような際どい作品を提出された方も含まれています。

経路探索

ここからは、最適解を求めるまでの手順について解説していきます。

この問題では、マップはステージ開始時に分かっていて、途中で変化することもないので、どこからどこに移動するかが決まれば、最短経路が求まります。

そして、移動の仕方として考えなければならないのは、営業所から配達先、配達先から別の配達先、および配達先から営業所だけです。

つまり、それらの最短経路と距離を最初に求めておけば、あとは配達順序を決めるだけで、その時間帯の最短経路が求まり、最小の消費燃料が求まります。

二点間の最短経路とその距離の求め方ですが、一般にはA*(Aスター)などがよく知られています。ここでは、経路探索の詳細は説明しませんので、興味のある方は検索してみてください。

このあと、二点間の距離はよく使いますので、使いやすいようにテーブルにしておきましょう。

例:マップ

フィールド
二点間の距離のテーブル
0123S
0-2586
12-7108
257-53
38105-2
S6832-

配達する順番の決め方

どの時間帯にどの荷物を積み込むかは後で考えるとして、ここでは、積み込んだ荷物を、その時間帯に消費する燃料がもっとも少なくなるような配達順序の決め方について考えてみます。

荷物がn個あるとすると、配達する順序は、n!通りあります。

各行程で、積んでいる荷物が分かっているので、1マス移動するのに消費する燃料は分かります。また、次の目的地までの距離も分かっているので、次の目的地までに消費する燃料は分かります。つまり、順序さえ決まれば、営業所を出発してから、全部の荷物を配達して営業所に戻るまでに消費する燃料も分かります。

最悪でも、n!のすべての配達順序について消費燃料を求めれば、どの順序がもっとも消費燃料が少ないかは分かります。


さて、n!通りのすべてを考えると、nが多いときに、とても計算量が多くなってしまいますが、工夫すれば、計算量を減らすことができます。

たとえば、0~5の荷物を積んで出発する場合を考えます。

まずは、最初に0,1,2の順で回ったときのことを考えてみましょう。これは、どのような状態かというと、「現在地が2であり、残りの荷物が3,4,5」という状態となります。

では、最初の3つを1,0,2の順で回ったときはどうでしょうか。これも、現在地が2であり、残りの荷物が3,4,5となります。

つまり、最初の2つがどのような順序であれ、残りの荷物について考えることは同じなのです。

同じことを何度も計算するのは無駄なので、最初に計算したものを保存しておいて再利用するようにすれば、計算量を大幅に減らすことができます。詳しく知りたい方は、巡回セールスマン問題で検索してみてください。

最初に積み込んだ荷物が違うときも計算結果の再利用

積み込む荷物さえ決まれば、その時間帯の消費燃料を最小にする配達順序は求まることが分かりました。

しかし、ある時間帯に積み込む荷物の決め方は、各荷物について積み込む/積み込まないの2通りがあるので、2n通りあります。別の時間帯に配達するように指定されている荷物は、ここでは考えなくてよいのですが、配達時間帯がまったく指定されていないステージもあるので、最悪のケースについて考えなければいけません。

このとき、すべての積み方の最小消費燃料を求めるのは大変です。


ところで、前の項目で、配達する順番を決めるときに同じ状態を見つけて計算結果を保存しておき、次に同じ状態になったら再利用する方法を紹介しました。

最初に積んでいる荷物が違うときも、同様の方法で、再利用することができます。

たとえば0,2,3,4を積んで出発する場合を考えてみましょう。

配達順序を決めるときに、すべての配達順序を考えるので、最初の2個が0,2の場合も出てきます。このときの状態は、「現在地が2で、残りの荷物は3,4」です。

次に、1,2,3,4を積んで出発する場合を考えてみましょう。最初の2個が1,2の場合は、「現在地が2で、残りの荷物は3,4」です。

つまり、最初に積んでいた荷物が違っていたにもかかわらず、途中からは同じになるので、前回計算した結果が再利用できるのです。


イメージしやすいように、具体的な実装方法を紹介します。 以下のような関数を考えてみます。

int GetCost(int currentPos, int items);

この関数は、現在地と、残りの荷物を各ビットで表現したものを受け取り、最小の消費燃料を返します。

ここで、「残りの荷物を各ビットで表現したもの」とは、たとえば最下位ビットが1ならば荷物0がある、下から2番目のビットが1ならば荷物1がある、というふうに、各ビットに、その番号の荷物の有無を割り当てたものです。

また、現在地は、営業所またはいずれかの配達先を表す番号です。番号の決め方は何でもいいですが、たとえば、0~n-1までは配達先で、nは営業所などとします。

この関数は、残りのすべての荷物について、次にその荷物を配達したときの消費燃料を再帰的に調べて、もっとも消費燃料が少ないものを返します。残りの荷物がないときは、営業所に戻るまでの消費燃料を返します。

ここで、一度調べたものは計算結果を保存しておき、次に同じ引数の組み合わせで呼ばれたときは、前回計算したものを再利用するために、配列に計算結果を保存しておくことが重要です。

なお、この関数では、次にどこに行けば消費燃料が最小となるかを調べているので、必要であれば次の目的地も返すようにすることもできます。


ここで、計算量について考えておきましょう。

この関数は、荷物の個数をn個とすると、現在地として渡されるのが営業所を含めてn+1通り、荷物の組み合わせが2n通りです。

1回の呼び出しで計算するのは、次の配達先の個数分(1個もないときは、次は営業所)なので、最大でもn通りです。

つまり、計算量は、およそ O(n2 * 2n) となります。

これだけの計算量で、すべての荷物の積み込み方の組み合わせについて、最小となる消費燃料と、そのときの経路とが求まることになります。

荷物の個数は最大16個なので、最近のPCであれば、十分計算できます。


なお、このような手法を一般に「動的計画法(DP)」といい、特に状態をビットで表現する手法を「BitDP」、また、計算した結果を保存しておいて再利用する手法を「メモ化」と呼んだりします。興味のある方は検索してみてください。

ところで、最小の消費燃料を調べるには、現在積んでいる荷物とトラックの重さが必要です。荷物が分かっているので、重さを調べることはできますが、毎回調べるのは大変なので、現在積んでいる荷物とトラックの重さの合計を引数として渡すと便利です。

各時間帯への荷物の割り当て

ここまでで、どのような組み合わせで積み込んでも、消費燃料を最小にする配達順序と、そのときの消費燃料が求まることが分かりました。

では、時間帯指定されていない荷物を、どのように積み込むかについて考えてみましょう。

すべての荷物の配達時間帯が指定されていれば、ここでは何も考えることはありません。決められてる通りに配達するだけです。

厄介なのは、配達時間帯が指定されている荷物が少ない場合や、まったくない場合です。

時間帯が4つあるので、1つも時間帯指定されていないとすると、4n通りの組み合わせがあります。(実際には、最大積載重量による制約があるため、これよりは少なくはなりますが、大きな違いはありません。)

荷物が16個だとすると、4nはちょっと多すぎますが、これも一工夫すれば大幅に減らすことができます。コツは、いかに状態数を少なくするかです。

一気に4つに分けようとすると組み合わせが多くなるので、時間帯を2つずつ、2つのグループに分けて考えます。

まずは最初のグループを時間帯0、時間帯1とします。そして、時間帯0に配達する荷物、時間帯1に配達する荷物、どちらでも配達しない荷物の3つに分けます。これで分け方は3nとなり、4nよりはかなり少なくなります。

そして、グループで配達する荷物を決めたときに、グループ内での2つの時間帯への最善の分け方が求まるようにテーブルにしておきます。

もう一方のグループも同様にし、最後に、全体での消費燃料が最小となるようにグループ間での割り当てを決めれば、すべての時間帯でどの荷物を配達するかが決まります。

ここまでで、制限時間内に最適解を求めることができます。

さらなる高速化

制限時間内に最適解を求める方法は分かりましたが、これだとまだ数秒かかってしまいます。

上位の方は、枝刈りや探索の順番を工夫するなどして高速化していました。

特に、4つの時間帯に分けるときに、2つずつ2つのグループに分ける方法が、実行委員会が事前の検証で想定していた解法だったのですが、上位の方は、そんなことはまったくせずに、枝刈りで高速化している方もいらっしゃいました。計算量だけ見ると、減っていないように見えるのですが、最初にある程度適当な分け方で消費燃料を求めておいて、それを超えそうになったら探索を打ち切るようにしたり、配達先が近い荷物は同じ時間帯に配達することが多いという特徴があるので優先的に探索するようにしたりすると、非常に効率よく枝刈りできるようです。このあたりは、皆さんの作品を拝見して我々も勉強になりました。

また、元々あまり時間がかからない経路探索も、マップの形状が特徴的であることを利用したり、同じ時間帯に配達しない配達先間は経路探索しないようにするなどして高速化している方もいらっしゃいました。

最終評価

最終評価に使った乱数は「x = 0xf0afe83f, y = 0x62c02791, z = 0xa5fa7d3f, w = 0xf2976096」でした。この乱数は、16面ダイスを実行委員が8×4=32回ふって出た数字です。(実はチャレンジスコア賞の抽選でも16面ダイスを活用しています)

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

ほとんどの方が、最終評価では途中評価よりスコアが下っていました。

16面ダイス

まとめとして

最適解が求まる問題ということで、ランキング上位陣は同じスコアで埋まってしまい、まるで最適解を出すのが当たり前で、それがスタート地点のような印象を与えてしまったかもしれません。それで敷居が高いと感じた方がいらっしゃいましたら申し訳ないと思います。

実際のところ、最適解を求めるのはそんなに簡単ではありません。ランキングでは上位の方しか見えないので、多くの方が最適解に到達していたように見えていただけです。最適解が求まらなくても、経路探索をして、巡回セールスマン問題を解いて、さらに配達先が近い荷物をなるべく同じ時間帯に配達するようにするなど、時間帯ごとの荷物の分け方を工夫して、スコアを上げている方が多くいらっしゃいました。それぞれの楽しみ方をしていただけたのであれば幸いです。

一方、上位の方は、実行委員会の事前の想定を大幅に超える高速化をしていて、レベルの高さに驚かされました。計測できる実行時間の最小単位が約0.0078秒だったのですが、正直に言いまして、これで足りなくなるとは思っていませんでした。力不足を痛感しているところです。

なお、最終評価では4回分実行して、その平均を実行時間としているので、実行時間まで同じという方はいらっしゃいませんでした。

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

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

PAGE TOP