paizaオンラインハッカソンVol.1での商品数と価格存在確率の関係
以前、このブログで記事にした paizaオンラインハッカソンVol.1 について、他の方々がどのようなコードを書いているのかと google で探していたところ、なんと、キャンペーン設定価格をそのまま出力するプログラムが正解になるというブログがありました。
野田さんをハメたコード - あーるPG - 社会人のデジタル生活
私の書いたコードも、そのときの記事に書いたように以下の想定に基づいた実装だったのですが、まさか設定価格をそのまま出力して正解になるとは想像していませんでした。そこで今回は、このことについて実際に調べてみたいと思います。
一方、リンク先の問題設定をみてもらうとわかるように、10 ～ 100 万の範囲で 20 万点サンプリングするということは、それが単純に一様分布から取られたサンプルであれば、大半のケースにおいては設定価格に極めて近いところで簡単に答えが見つかりそうです。
問題を一般化すると、ある価格範囲に N 種類の商品が分布しているとき、合計価格が X になるような商品の組が存在する確率を求めることになります。紙とエンピツで解いてやろうと挑戦したのですが、私には難しすぎたので早々に諦め、以下のようなプログラムで様子を眺めてみることにしました。
#include <cstdlib> #include <iostream> #include <vector> #include <boost/random.hpp> int main(int, char **argv) { using namespace std; using namespace boost::random; const int price_min = 0; const int price_max = atoi(argv[1]); const int n = atoi(argv[2]); mt19937 gen(static_cast<unsigned long>(time(0))); uniform_int_distribution<> dst(price_min, price_max); variate_generator<mt19937&, uniform_int_distribution<> > rand(gen, dst); vector<int> results(price_max * 2 + 1, 0); for (int t = 0; t < 100; ++t) { vector<int> counts(price_max + 1, 0); for (int i = 0; i < n; ++i) { ++counts[rand()]; } for (int k = 0; k <= price_max * 2; ++k) { bool found = false; for (int i = max(0, k - price_max), j = k - i; i < j; ++i, --j) { if (counts[i] != 0 && counts[j] != 0) { found = true; break; } } found |= (k % 2 == 0 && counts[k / 2] >= 2); if (found) { ++results[k]; } } } for (int k = 0; k <= price_max * 2; ++k) { cout << results[k] << endl; } return 0; }
最大価格を 100, 商品数を 10 としたときの実行例は以下のようになります。実行結果は、100 回の試行中で合計 0 円となる商品の組が存在したのは 1 回、合計 100 円となる商品の組が存在したのは 37 回、という意味です。プログラムでは最小価格を 0 円に固定しているので、二つの商品の組み合わせによる合計価格は 0 円から 200 円 (最大価格の二倍) の範囲になります*1。
$ g++ -O3 -o test test.cpp $ ./test 100 10 | awk '{ print NR - 1, $1 }' 0 1 1 1 2 1 3 2 4 4 ... 98 26 99 37 100 37 101 37 102 42 ... 196 2 197 1 198 2 199 2 200 0
さて、最大価格と商品数を変えながらこのプログラムの実行を繰り返し、それぞれの結果をグラフにまとめます。最初のグラフは、上記の実行例のように最大価格を 100 とした場合です。各系列は、それぞれ商品数 10, 20, 30, 50, 100 での結果を示します。X 軸の中央付近ほど、そのような合計価格になる商品価格の組み合わせが多くなるため、グラフの形状は山形になります。当然ながら、商品数が大きくなるほど各合計価格の存在可能性も高くなります。商品数 50, 100 では、中央付近の価格については 100 回の試行のすべてで、そのような商品の組み合わせが存在したことが読み取れます。
最大価格を 1000, 10000 とした場合が次の二枚のグラフです。全体的な形状は変わりませんが、最大価格が大きくなっても、商品数は比較的少ないところでグラフが上辺に張り付く (100 回の試行すべてで商品の組み合わせが存在する) ことが見て取れます。たとえば、上に示した最大価格 100 のグラフでは、商品数を 100 とした場合に、ようやく合計価格 20 ～ 180 の範囲で上辺に張り付いていましたが、最大価格 1000 では商品数 300 程度、最大価格 10000 では商品数 1000 程度で、同様の状態になっている様子がわかります。
最後に、paizaオンラインハッカソンVol.1 の設定でどのようになるか調べてみます。私が挑戦した PHP の設定では、最大価格が 1,000,000、商品数が最大 200,000 という設定になっています。この設定でシミュレーションしてみた結果、以下のようになりました。なお、実際の設定では最小価格が 10 なのですが、これは無視して 0 ～ 1,000,000 の価格範囲で実行しています。
$ ./test 1000000 200000 | awk '{ if ($1 < 100) print NR-1, $1 }' 0 3 1 7 2 6 ... 501 99 552 99 1999521 99 1999549 99 ... 1999998 5 1999999 3 2000000 3
553 ～ 1,999,520 の範囲にあるすべての価格について、100 回の試行のすべてで商品の組が存在したという結果になりました。ハッカソンの PHP の設定では、キャンペーン日数は 75 となっています。75 日分の設定価格も一様分布から取られていると仮定すれば、すべての 設定価格がこの範囲に収まっている確率は ((1999520 - 553 + 1) / (2000000 + 1)) ^ 75 = 0.962 程度になります。したがって、もし TestCase3 のデータがこのような方法で作成されているなら、キャンペーン設定価格をそのまま出力するプログラムが正解を出力できそうです。
C, C++ では、最大価格 1,000,000、商品数 500,000、キャンペーン日数 300 と、より大きな設定になっています。こちらの設定で同様に試してみると、以下のようになりました。
$ ./test 1000000 500000 | awk '{ if ($1 < 100) print NR-1, $1 }' 0 9 1 11 2 22 ... 73 99 102 99 1999914 99 1999927 99 ... 1999998 30 1999999 24 2000000 8
PHP 等での設定と比較すると、同じ価格範囲で商品数が増えた結果、103 ～ 1,999,913 までのより広い範囲で、100 回の試行すべてで商品の組が存在するようになっています。キャンペーン日数 300 の場合で、すべてがこの範囲に収まる確率を同様に計算すると、約 0.972 となりますので、こちらの場合でもキャンペーン設定価格をそのまま出力するプログラムで正解を期待できそうです。
