233, 456, 787メートルの板で100 億メートルの塀を作る

プログラミング勝負！ Google Code Jam 2011

あなたは、板を並べて、丁度ぴったり 100 億メートルの、長い長い塀を作ろうと思い立ちました。馴染みの工芸店では、233 メートル、456 メートル、あるいは 787 メートルの板なら、注文すれば何枚でも売ってくれます。板をうまく組み合わせて、最小の枚数でぴったり 100 億メートルを作るには何枚の板を買えばよいでしょうか？

注意してください。作りたい塀は、とても長いのです。膨大な枚数が必要ですが、1 枚も間違わず、正確に計算してくださいね！


この問題は、データの数値が小さい時は、多くのアルゴリズムの教科書でも見かける「よくある」問題なのですが、データが大きくなると、別の工夫が必要になってきます。そして、データの巨大さがある一線を越えると、それを逆手にとったまったく違う発想の巧い解決が可能になるのです。ぜひぜひ、考えてみてください。

D言語を使って運良く、20分程度で解けた、と思う（回答が見当たらない）。
こんなごくシンプルなコードで、果たして解けたと言えるのか・・・。
編集しました。最適解かどうかはともかく、結果はこれで合ってると思う。

import std.stdio : writefln;

void main ()
{
    ulong wall, x, y, z;

LOOP:
    for (x = 10000000000 / 787; x != ulong.max; x--)
    {
        y = (wall = 10000000000 - (787 * x)) / 456;

        for (wall %= 456; y != ulong.max; y--)
            if (wall % 233) wall += 456;
            else { z = wall / 233; break LOOP; }
    }

    assert(10000000000 == ((x * 787) + (y * 456) + (z * 233)));
    writefln("sum:%d, 787:%d, 456:%d, 233:%d", x + y + z, x, y, z);
}

ちなみに動作結果は

sum:12706489, 787:12706469, 456:19, 233:1

787メートルの板が12706469枚、456メートルの板が19枚、233メートルの板が1枚。
合計12706489枚。

そして、データの巨大さがある一線を越えると、それを逆手にとったまったく違う発想の巧い解決が可能になるのです。

これは何なのだろう・・・。またやる気が起きたら考えてみよう。