読者です 読者をやめる 読者になる 読者になる

y_uti のブログ

統計、機械学習、自然言語処理などに興味を持つエンジニアの技術ブログです

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 回の試行のすべてで、そのような商品の組み合わせが存在したことが読み取れます。
f:id:y_uti:20140104063308p:plain

最大価格を 1000, 10000 とした場合が次の二枚のグラフです。全体的な形状は変わりませんが、最大価格が大きくなっても、商品数は比較的少ないところでグラフが上辺に張り付く (100 回の試行すべてで商品の組み合わせが存在する) ことが見て取れます。たとえば、上に示した最大価格 100 のグラフでは、商品数を 100 とした場合に、ようやく合計価格 20 ~ 180 の範囲で上辺に張り付いていましたが、最大価格 1000 では商品数 300 程度、最大価格 10000 では商品数 1000 程度で、同様の状態になっている様子がわかります。
f:id:y_uti:20140104063404p:plain
f:id:y_uti:20140104063433p:plain

最後に、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 となりますので、こちらの場合でもキャンペーン設定価格をそのまま出力するプログラムで正解を期待できそうです。

*1:paizaオンラインハッカソンVol.1 では、キャンペーン価格の最大値は商品価格の最大値と同じ値に設定されていますが、ここでは、全体の様子を見るために可能な範囲全体について調べました。