～ これだけ解けば十分闘える！過去問精選 10 問 ～ の8問目 Otoshidama をPHPで

すでにPHPの記事があった orz

Qiitaで珍しくAtCoderの記事が話題になっていました。

AtCoder に登録したら次にやること ～ これだけ解けば十分闘える！過去問精選 10 問 ～

これのPHPで解いてみた版を書こうと思ったら、もうありました orz

ただ、特に解説とかなかったので、書いてみても良いかなぁ、と。

過去問と言っても、だいたい解いちゃってるかなぁ、なんて思っていたんですが、8問目以降の300点問題は全部やってませんでした。

そんな訳で、今回は8問目を。

お年玉の合計金額とお札の合計枚数が与えられるので、
1万円札と5000円札と1000円札それぞれの枚数を1例出力せよ。

実現不可能な場合は「-1 -1 -1」を出力せよ。

という問題です。

1万円札と5000円札の枚数を仮に決めれば、1000円札の枚数は必然的に求まりますので、 O(n^2) で計算可能です。

もちろん、その場合には、時間制限に引っかかります。

<?php
fscanf(STDIN, "%d %d", $N, $Y);

for ($k10 = 0; $k10 * 10000 <= $Y; $k10++) {
    for ($k5 = 0; $k10 * 10000 + $k5 * 5000 <= $Y; $k5++) {
        $k1 = ($Y - $k10 * 10000 - $k5 * 5000) / 1000;
        // printf("k10:%d k5:%d k1:%d\n", $k10, $k5, $k1);
        if ($k10 + $k5 + $k1 == $N) {
            echo "{$k10} {$k5} {$k1}" . PHP_EOL;
            exit;
        }
    }
}
echo "-1 -1 -1" . PHP_EOL;

引っかかりませんでした ((((;ﾟДﾟ))))ｶﾞｸｶﾞｸﾌﾞﾙﾌﾞﾙ

とは言え、実行時間が442ms(0.442秒)かかっています。
もうちょっと工夫してみましょう。

もうちょっと工夫して高速化

まず、1万円札の枚数だけ、仮に決めます。
残りを一旦、1000円札だけにします。
その後に、1000円札を5000円札に交換する儀式をすることにします。
変動するのは1万円札の枚数だけなので、計算量は O(n) です。

1000円札を5000円札に交換する儀式をすると、1000円札 5 枚が5000円札 1 枚になるので、 1回儀式を行うたびに、お札の合計が 4 枚減ります。
つまり、1万円札と1000円札の時点で、Nより 4の倍数枚 多い場合は、儀式によってピッタリの枚数にすることができます。
(※計算上、お札が0枚未満になる場合は除外します)

最初のプログラムでは、5000円札もループしていましたが、今回は5000円札の枚数を1回の計算で求めているので、高速になるはずです。

コードで書くと、こんな感じです。

<?php
fscanf(STDIN, "%d %d", $N, $Y);

$answer = "-1 -1 -1";

$k10max = floor($Y / 10000);
for ($k10 = 0; $k10 <= $k10max; $k10++) {
    $k1 = ($Y - $k10 * 10000) / 1000;
    if ((($k10 + $k1) - $N) % 4 == 0) {
        $k5 = (($k10 + $k1) - $N) / 4;
        $k1 -= $k5 * 5;
        if ($k5 < 0 || $k1 < 0) continue;

        $answer = "{$k10} {$k5} {$k1}";
        break;
    }
}

echo $answer . PHP_EOL;

実行時間が9ms(0.009秒)になりました。
ざっくり計算すると50倍くらいの速さで計算が終了したことになります。

……では！