トップクラスだけが知る「このアルゴリズムがすごい」――「探索」基礎最速マスター：最強最速アルゴリズマー養成講座（4/4 ページ）

[高橋直大，ITmedia]

今回の問題の解法

　今回の問題は、ある1つのことに気づけるかどうか、がポイントになると述べました。「K番目に長い棒の長さをAにする」という語句を「長さA以上の棒がK本以上ある」と言い換えられるかどうかに尽きます。これに気づくことができれば、この問題は解けたも同然です。解法が分からずにこのページを開いてしまい、今の文章でひらめいた方は、今すぐに戻るボタンをクリックして、解き直してみましょう。

　あまりこういった考え方に慣れていない人は、「それがどうした」と思われる方も多いでしょう。しかし、分かってみると非常に簡単ですし、「どうして気づかなかったんだろう」と思ってしまう方も多いでしょう。

　今回の問題でこのような考え方が有効な理由は、目的の長さが分かってしまえば、それ以上の長さの棒が何本作れるかは、すぐに分かってしまうからです。

　1つ例を見てみましょう。7本の棒の長さ、

stick = { 200, 160, 100, 80, 60, 20, 10}

が与えられたとしましょう。ここで、切る回数Cが8であったとしましょう。これで、K番目に長い棒の長さを最大にしろ、といわれても、何をどう切っていいのかはよく分かりませんし、プログラムで表すのも困難ですよね。

　そこで、問題を変えてみましょう。長さが40以上の棒は、幾つ作れるでしょうか？　これを求めるのは非常に簡単です。長さ40以上の棒ができるだけ多く作れるように、順番に切っていけばよいのですから。例えば、長さ200の棒からは、200/40で、5本作れますね。同様に、長さ160の棒からは4本、長さ100の棒と長さ80の棒からは2本、長さ60の棒からは1本作ることができます。この際、各棒について、（作れる本数-1）回だけ棒を切る必要が出てきますから、合計で、

4＋3＋1*2＝9（回）

切ることが可能です。ここで、切ることのできる回数は8回だけなので、作ることのできる本数が1本減ってしまいます。従って、長さ40以上の棒を作ることのできる本数は、

5＋4＋2＋2＋1−（9−8）＝13（本）

となります。つまり、Kが13以下のとき答えは40以上となり、Kが14以上のときは答えは40未満となるわけです。今回は長さ40で考えましたが、この考え方は、求めたい長さが変わったときにも当然適用できます。

　ここまで分かれば後は簡単です。存在し得る答えで最長の答えは、問題設定から10億となりますし、最短の答えはもちろん0となります。ということは、0と10億の間で直接二分探索を使って探索することで、答えを直接求めることができます。これをソースコードにすると、以下のようになります。

using System;
using System.Collections;
using System.Collections.Generic;
using System.Text;
public class CutSticks {
    public double maxKth(int[] sticks, int C, int K)
    {
        double low = 0;
        double high = 1e9;
        int i,j;
        for (i = 0; i < 100; i++)
        {
            long count = 0;
            double mid = (low + high) / 2;  //真ん中の数字を調べる
            long cut = 0;
            for (j = 0; j < sticks.Length; j++)
            {
                long next = (long)(sticks[j] / mid);  //作れる本数
                cut += Math.Max(0, (next - 1)); //切る回数
                count += next;    
            }
            count -= Math.Max(0, cut - C);  //切った回数が多すぎたらその分引く
            if (count >= K) low = mid;  //ここで範囲を半分に狭める
            else high = mid;
        }
        return low; //誤差の制限が甘いので、lowでもhighでもかまわない
    }
}

　シンプルに記述できましたが、実は、二分探索というのは、非常にバグの発生しやすいプログラムの1つです。ここで、よくあるバグの例を挙げてみましょう。1つの例は、今回、

for(i=0;i<100;i++)

と、定数回のループにしている部分を、

while(high-low<1e-9)

などと書いてしまうことです（1e-9というのは指数表示で、1ek = 10^kとなります。例えば、1e2と書くと100を、1e-1と書くと0.1を意味します）。これは、highとlowの差が十分に小さくなったら打ち切る、という意味のコードで、いかにも正しいように見えますが、実はここには大きなわなが潜んでいます。

「double型の丸め誤差」に注意

　それは、double型の丸め誤差によるものです。かいつまんで説明すると、double型は、小数を表すことが可能ですが、無限に小数を格納できないため、格納しきれない部分で誤差が発生します。double型は、符号部1ビット、指数部11ビット、仮数部52ビットで構成されているため、2進数で52けた分の精度しか格納できません。が、今回の問題では、答えは最大10億＝1e9であり、

log_2(1e9 / 1e-9) = log_2(1e18)

= 59.79

となり、1e-9の精度を表すには精度が足りません。つまり、両方の差がこれ以下になることがなく、無限ループが発生してしまいます。この説明が分からない場合には、「二分探索は、十分な定数回で打ち切る」ということをしっかりと覚えておいてください。

　今回の問題とは関係がありませんが、同様に、二分探索の範囲を整数に限定した場合、上下の差が1から縮まらずに終了しない、といったことが発生することもあります。これは、動かしてみればすぐに気づくバグなのですが、こちらも注意したいポイントです。

　なお、過去に今回の問題とよく似た問題が出題されています。SRM421のDiv1Mediumの問題ですが、解き方はまったく違うものになります。興味のある方は、こちらの問題も参照していただけると、より理解が深まるでしょう。

　また、この問題は、二分探索を使わずに解くことも可能です。この問題ですと、二分探索で解くのが一番解きやすいと思いますが、たとえそれを知らなかったとしても、解けないわけではありません。強烈な個性を発揮している回答もありますので、ぜひ、いろいろな回答をご覧いただければと思います。

　探索自体は、特に難しいことをしているわけではないのですが、プログラムを組み慣れていない人にとっては、非常に組みづらいものの1つだと思いますので、今回出てきた二分探索のほかにも、幅優先探索や深さ優先探索のコードも組んでみることを推奨します。幅優先探索は、連載第2回の問題で登場していますので、まだプログラムの組めていない人は、ぜひ挑戦してみてください。

　今回紹介したものよりも美しい実装方針を思いついたり、きれいなコードが書けたら、ぜひご意見いただければと思います。ソーシャルブックマークのコメントでも、わたしのブログに書き込んでいただいても構いません。可能な限り反応したいと思っていますので、どんどんご意見をお寄せください。それでは、次回もお楽しみに！

著者プロフィール：高橋直大（たかはし　なおひろ）

Microsoftが主催する技術コンテスト「Imagine Cup」の2008年アルゴリズム部門で世界第3位に入賞した若きアルゴリズマー。TopCoderでは誰もが恐れるRedcoderとして活躍中。2009年に開催された「天下一プログラマーコンテスト」では特別賞を受賞した。現在、慶應義塾大学環境情報学部2年。口癖は「みょんみょん」。直近では2月21日に開催されるIT勉強会で「プログラミングをしない人は人生の3割くらい損してる」などのテーマで語る予定。

世界でも有数のRedcoder、高橋直大がアルゴリズムの魅力と極意を伝授する「最強最速アルゴリズマー養成講座」はこちらから