実行時間の差は996倍以上。オンラインハッカソン最速コードの裏側に迫る！

2013年12月2日より2014年1月8日まで開催していたpaizaオンラインハッカソン（略してPOH![ポー！]）Vol.1「新人女子の書いたコードを直すだけの簡単なお仕事です！」で0.01秒を叩き出したコード(最遅コードとの差は最大996倍！詳しくは結果発表をご確認ください)はどんな過程で生み出されたのでしょうか？

今回は前回の最速コード発表レポート（【結果発表】新人女子PGを最も助けたプログラミング言語とは？）に引き続き、最速コードの裏側に迫ります。

※ちなみにこちらの野田ちゃん画像は、2014年1月17日に開催されたエンジニアサポートcross2014というイベントで等身大パネルとしてpaizaブースを盛り上げてくれました！

■高速化のアプローチ

前回のレポートでもふれましたが、POH Vol.1はアルゴリズムに変更による計算量(オーダー)の改善による大幅な高速化と、定数倍高速化と呼ばれる部分最適化(ソート、入出力部分など)による高速化の組み合わせで高速化を目指すことができます。
計算量（オーダー）については、何も考えずに実装するとO(DN^2)になり、よく考えると O(DNlogN) ⇒ O(DN)と高速化出来るような問題になっています。

■問題文の再確認

念のため初めて見る方もいらっしゃるかもしれませんので、paizaオンラインハッカソンVol.1の問題文を引用いたします

あなたはとあるECサイトのプログラマです。このECサイトではたくさんの商品を取り扱っていて、 一番安いもので10円、高いものでは100万円の商品まで存在します。 今回、そのECサイトを運営しているあなたの会社は、サイトの集客キャンペーンとして、「組み合せで無料キャンペーン」と銘打って、設定金額に最も近い商品の組み合わせを購入すれば無料となるキャンペーンを開催することにしました。その内容は以下の通りです。

・キャンペーン設定金額として毎日1つの設定金額(整数)mが決められます。
・ECサイトの利用客は、 2つの異なる商品（値段は同じでも構わないが必ず二つ） を購入し、その 合計価格がキャンペーン設定金額m円以下で、かつ最大となるような商品の組合せだった場合、その商品を無料で手に入れることができます。
・設定金額が23150円、商品は３つ（シュークリーム12,000円とスルメイカ17,000円、大根は11,120円）だった場合、シュークリームと大根(合計23,120円)の組み合わせが無料になります。
・すべての商品の価格と、イベント期間中の各日のキャンペーン設定金額m円(キャンペーン日数分) が与えられるので、各日のキャンペーン設定金額mに対し、上記ルールのもとでの最大値を計算するプログラムを作成するのがあなたの仕事です。

※POH Vol.1は応募期間は過ぎたため、プレゼント対象、計測対象には成りませんが、コードの実行は引き続き可能です。

■O(DN^2)をO(DNlogN)にする

何も考えずに全商品の組み合わせを算出して、キャンペーン設定金額をに近い値を探していく方法で実装すると計算量が O(DN^2)の「全探索」になりテストケース1しか通りません。よく考えると O(DNlogN)の「二分探索」となりテストケース２までとおり、さらによく考えると O(DN)のテストケース３がとおる「しゃくとり法」と高速化出来るような問題になっています。
※「二分探索」と「しゃくとり法」の詳細は後述

◆O(DN^2)のコード（C言語）

#include <stdio.h>
 
int main(void) {
  int N, D; scanf("%d %d", &N, &D);
 
  int p[500000];
  int i, j, k;
  for(i = 0; i < N; i++) {
    scanf("%d", &p[i]);
  }
 
  for(i = 0; i < D; i++) {
    int m; scanf("%d", &m);
 
    int ans = 0;
    for(j = 0; j < N; j++) {
      for(k = j + 1; k < N; k++) {
          int s = p[j] + p[k];
          if (s > m) continue;
          if (ans < s) ans = s;
      }
    }
 
    printf("%d\n", ans);
  }
 
  return 0;
}

※他の言語を見たい方はpaizaサイト内で公開しておりますので、会員登録(30秒で完了します)をしてみてください！
https://paiza.jp/users/new

O(DNlogN)にするにはどういう方法があるかというと、二分探索と呼ばれる探索法を使う事で高速に探索が出来るようになります。二分探索についての詳しい解説ははググっていただければと思いますが、簡単に説明すると、ソートされた探索対象の中間地点をみて、探したい値が中間地点の前にあるか後ろにあるかを確認する、という行為を繰り返しながら探索する方法です。

価格が徐々に大きくなっていくよう昇順に商品価格リスト(p)をソートした場合、価格が小さいp[i] (1 ≦ i ≦ N[商品点数])からスタートし、p[i]のペアとなる商品p[k](k番目の商品、1 ≦ k ≦ N[商品点数])を二分探索することになります。

O(DNlogN)にするためには、

商品価格リストをソート
各キャンペーン設定金額毎にループ
1. 商品一つづつ、ペアとなる商品を二分探索する
2. 各キャンペーン設定金額に最も近い値を出力する

というアルゴリズムになります。
ただしこの方法だとテストケース2しか通りません

◆O(DNlogN)のコード（C言語）

#include <stdio.h>
#include <stdlib.h>
 
int CompareInt(const void *_v1, const void *_v2) {
  int v1 = *((const int *)_v1);
  int v2 = *((const int *)_v2);
 
  if (v1 == v2) return 0;
  return v1 > v2 ? 1 : -1;
}
 
int UpperBound(int *p, int N, int r) {
  int lb = 0, ub = N; //[lb, ub)
 
  while(ub - lb != 1) {
   int mid = (ub + lb) / 2;
   if (p[mid] <= r) lb = mid;
   else ub = mid;
  }
 
  return ub;
}
 
int main(void) {
  int N, D; scanf("%d %d", &N, &D);
 
  int p[500000];
  int i,j;
 
  for(i = 0; i < N; i++) {
    scanf("%d", &p[i]);
  }
 
  qsort(p, N, sizeof(int), CompareInt);
 
  for(i = 0; i < D; i++) {
    int m; scanf("%d", &m);
    int ans = 0;
    for(j = 0; j < N; j++) {
      int r = m - p[j];
      int ub = UpperBound(p, N, r);
      ub--;
      if (j >= ub) continue;
      if (p[ub] > r) continue;
 
      int s = p[j] + p[ub];
      if (s <= m && ans < s) {
          ans = s;
      }
    }
 
    printf("%d\n", ans);
  }
 
  return 0;
}

■O(DN)にする

テストケース３を通すためには、二分探索を用いた解法よりも効率のよい解法にする必要があります。より効率より解法い近づくためには、キャンペーン設定金額に最も近い商品の組み合わせがどのようなものになっているのか理解する必要があります。

前述した二分探索法でp[i](i番目の商品)を基準にp[k]を探索する場合、p[i](i番目の商品)+p[k](k番目の商品) <= M(キャンペーン設定金額)を満たす中でp[k]が最大となる商品を二分探索するという事に成ります。

キャンペーン設定金額が58,000円だとした場合、まずp[i]は一番価格の安い商品からスタートするので10円等になります。その10円を基準に57,990円以下の商品（p[k]）を探すということです。

このp[k] の値の変化を見てみるとk は降順になっていることに気付く事が出来ます。例えば99個の商品だったとしてp[1]=10円 p[99]=57,970円(i=1,k=99)、p[2]=40円 p[98]=57,950円(i=2,k=98)、p[3]=50円 p[98]=57,950円(i=3,k=98)...となります（p[2]=40円 p[99]=57,970円の組み合わせは58,000円を超えてしまいますので除外）
これは、i の値が増加するごとにk の値は減少もしくは同じ値をとるということを表しています。

この事実が分かれば、k を求める際に、i を増加させるごとにk を二分探索をするのではなく、ひとつ前の商品組み合わせのk の値からループで1つずつ減少させることで効率的にk を求めることができます。

このアルゴリズムを適切に実装した場合、k の値すべてを求めるために回るループ回数の合計はO(N) にしかならないので、結局キャンペーン設定金額m が1つ与えられるごとにO(N) で計算できることが分かります。

商品価格リストをソート
各キャンペーン設定金額毎にループ
1. 上端p[i]の商品と下端p[k]の商品の合計値を出す
2. 以下を繰り返す
  1. 各キャンペーン設定金額以上であれば下端を一つ安い商品に移動 (k = k - 1)し合計値を出す
  2. 各キャンペーン設定金額以下になったら上端を一つ高い商品に移動 (i = i + 1)し合計値を出す
3. 各キャンペーン設定金額に最も近い値を出力する

このアルゴリズムは、i とk の特徴的な動きから、しゃくとり法、しゃくとりメソッドなどと呼ばれることがあります。
i を頭、k をお尻と考えるとその動きが尺取り虫が移動する際の動きに似ていることに由来しています。
今回のアルゴリズムは縮むだけで伸びない上に頭が後ろに動くので、あまり尺取り虫の移動のイメージにそぐわない気がしますが、本質的に違いはありません。
しゃくとり法は特定の問題にだけ有効なピンポイントなアルゴリズムというよりは、応用範囲が広く様々な形で現れるアルゴリズムですので、ぜひ他にも適用できる問題がないかどうか考えチャレンジしてみてください。

◆O(NlogN + DN)のコード（C言語）

#include <stdio.h>
#include <stdlib.h>
 
int CompareInt(const void *_v1, const void *_v2) {
  int v1 = *((const int *)_v1);
  int v2 = *((const int *)_v2);
 
  if (v1 == v2) return 0;
  return v1 > v2 ? 1 : -1;
}
 
int main(void) {
  int N, D; scanf("%d %d", &N, &D);
 
  int p[500000];
  int i;
  for(i = 0; i < N; i++) {
    scanf("%d", &p[i]);
  }
  qsort(p, N, sizeof(int), CompareInt);
 
  for(i = 0; i < D; i++) {
    int m; scanf("%d", &m);
    int h = 0, t = N - 1;
    int ans = 0;
    while(h != t) {
      int s = p[h] + p[t];
      if (s > m) t--;
      else {
        if (ans < s) ans = s;
        h++;
      }
    }
    printf("%d\n", ans);
  }
 
  return 0;
}

※上記コードに対して後述のソートの高速化を組み合わせることでO(DN) を達成することができます
※他の言語を見たい方はpaizaサイト内で公開しておりますので、会員登録(30秒で完了します)をしてみてください！
https://paiza.jp/users/new

■ソートの高速化

各言語によるところがるのと、解説が長くなるため、さらなる高速化についてはソートの概要だけ触れさせていただきます。

キャンペーン設定金額は全部でD 個与えられるので、前処理にO(NlogN) のソートを用いれば全体でO(NlogN + DN) で解が求まります。
また、今回商品価格の上限は100万ですのでバケットソート(wikipedia:バケットソート) などの特殊なソート法を用いればO(DN) で実現することも可能です。

■POH Vol.1をハックする

今までの解説は実は正攻法のやり方でしかありません。POH Vol.1のテストケース3はよく考えると抜け穴があります(事務局側で意図したことではりませんでしたが汗)。

今回の問題の条件を見てみると商品点数は最大20万点（C、C++は50万点）と膨大な数になります。そして商品価格が10円～100万円の範囲です。

よくよく考えると、キャンペーン設定金額ぴったりの組み合わせが出現する確率は、商品点数が増えれば増えるほど高くなります。つまり商品点数が多い場合は、キャンペーン金額をそのまま答えとして出力すれば正解となる可能性が非常に高くなります。・・・なんとなんと！
※上記は一定の乱数の場合です。その他の分布に従った乱数を用いた場合はこの方法で正答するのは難しくなることがあります。今回は一様乱数を用いてテストケースを生成していたのでこの方法が通用してしまいました。

問題文に書かれている手順にとらわれているとみえない、なんたるコペルニクス的転回。野田ちゃん恐るべし。

この方法が通るテストケースではO(N + D) まで計算量が縮められることになります。※読み込みにO(N)、出力にO(D)

では何点ぐらいの商品点数があれば、キャンペーン設定価格とぴったりの組み合わせが出てくることになるのでしょうか？　y_utiさんがこの答えについてブログに書いておられます。

　　paizaオンラインハッカソンVol.1での商品数と価格存在確率の関係
　　http://y-uti.hatenablog.jp/entry/2014/01/04/100945

グラフの掲載許可をy_utiさんからいただく事が出来ましたので、こちらにも掲載をさせていただきます。

さて、最大価格と商品数を変えながらこのプログラムの実行を繰り返し、それぞれの結果をグラフにまとめます。最初のグラフは、上記の実行例のように最大価格を 100 とした場合です。各系列は、それぞれ商品数 10, 20, 30, 50, 100 での結果を示します。X 軸の中央付近ほど、そのような合計価格になる商品価格の組み合わせが多くなるため、グラフの形状は山形になります。当然ながら、商品数が大きくなるほど各合計価格の存在可能性も高くなります。商品数 50, 100 では、中央付近の価格については 100 回の試行のすべてで、そのような商品の組み合わせが存在したことが読み取れます。
最大価格を 1000, 10000 とした場合が次の二枚のグラフです。全体的な形状は変わりませんが、最大価格が大きくなっても、商品数は比較的少ないところでグラフが上辺に張り付く (100 回の試行すべてで商品の組み合わせが存在する) ことが見て取れます。たとえば、上に示した最大価格 100 のグラフでは、商品数を 100 とした場合に、ようやく合計価格 20 ～ 180 の範囲で上辺に張り付いていましたが、最大価格 1000 では商品数 300 程度、最大価格 10000 では商品数 1000 程度で、同様の状態になっている様子がわかります。

まさにハックとはこういう事をいうのでしょう。この解法を思いついた方々はすごいと思いますが、さらにそれをここまで解析されたy_utiさんに脱帽です。

最大価格が 1,000,000、商品数が最大 200,000の設定だと553 ～ 1,999,520 の範囲にあるすべての価格について、100 回の試行のすべてで商品の組が存在したという結果になりました。

とのことです。つまり商品点数をみてテストケース3はキャンペーン設定価格をそのまま出力するとたやすく0.01秒が出せるわけです。

◆テストケース3をすり抜けるコード(tubocさんの提出コード)

※Nが1000となるところで切り分けています

# python 2.7.3

import sys,bisect

(N,D) = map(int, sys.stdin.readline().split(' '))
N = int(N)
D = int(D)

if N < 1000:
    ALL = map(int, sys.stdin.read().splitlines())
    items = sorted(ALL[0:N])
    campaigns = ALL[N:]
    for price in campaigns:
        start = 0
        end = bisect.bisect_right(items,price) - 1
        best_price = tmp = 0

        while start<end:
            while items[start]+items[end]>price: end-=1
            tmp = items[start]+items[end]
            if tmp>best_price:
                best_price = tmp
                if best_price==price: break
            start+=1

        print best_price
else:
    ALL = sys.stdin.read()
    ri = len(ALL)
    c = 0
    while c<=D:
        ri = ALL.rindex('\n',0,ri)
        ri-=1;
        c+=1
    ri+=2
    answer = ALL[ri:]
    print answer,

■まとめ

今回のpaizaオンラインハッカソンは初めての開催という事もあり、どのぐらいジャッジに負荷がかかるのかわからず3つのテストケースとしていたため、穴としてこのような解法が存在しておりました。この点は正攻法で解かれた方にはお詫びをしなければいけないのですが、ここまでハックしていただけたことに事務局サイドとしてはとても感謝しています。また結果的にですが、よりハッカソンとして今回のイベントが機能した事を嬉しくも感じています。

paizaオンラインハッカソンのレポートは今回で終了ですが、次回開催の準備も進めておりますので是非次回も皆様のご参加をお待ちしております！

paiza会員登録すると、今回のPOH Vol.1の各言語の各アルゴリズムの実装パターンが見れるほか、スキルチェックが出来る様々な問題が出題されています。
https://paiza.jp/users/new

paizaは、技術を追い続けることが仕事につながり、スキルのある人がきちんと評価される場を作ることで、日本のITエンジニアの地位向上を目指したいと考えています。

「paiza転職」は、自分のプログラミング力が他社で通用するか（こっそり）腕試しができる、IT／Webエンジニアのための転職サービスです。プログラミングスキルチェック（コーディングのテスト）を受けて、スコアが一定基準を超えれば、書類選考なしで複数の会社へ応募ができます。