競プロ典型90題 016 – Minimum Coins（★3）

今日は以下にチャレンジしました。

https://atcoder.jp/contests/typical90/tasks/typical90_p

今回の問題ですが、変数が３つで各変数の取りうる辺りは最大で9999通りとのこと。

なので、2重ループで全探索であれば、概ね計算量は10^8に収まるので、時間内に処理は終わりそうと思い、実装しました。

しかし、TLEが解消できない・・・

TLE発生時コード

function Main(input) {
    inputArray = input.split("\n");
    const N = inputArray[0];
    const coinArray = inputArray[1].split(" ").map(Number).sort((a,b)=>(b-a));
    const [A,B,C] = coinArray
    const AM = Math.floor(N/A)
    let minCount = 9999;
    let temp;
    let temp2;

    for (let j = AM; j >= 0;j--){
        for (let k = parseInt((N - A * j ) / B); k>=0;k-- ){
            temp = (N - A * j - B * k) / C
            temp2 = parseInt(temp)

            if(temp === temp2){
                if(minCount > j + k + temp2){
                     minCount = j + k + temp2
                }
                break;  
            }
        }
    }
    console.log(minCount)
}   

コードのロジック的には大きな問題は見当たらないように思っていましたが・・・

【この時点での処理速度】

ループ1回あたりの処理時間：0.000044342ミリ秒

10^8回の場合の処理時間＝4.4342

TLE解消後のコード

function Main(input) {
    inputArray = input.split("\n");
    const N = parseInt(inputArray[0]);
    const coinArray = inputArray[1].split(" ").map(Number).sort((a,b)=>(b-a));
    const [A,B,C] = coinArray
    const AM = Math.floor(N/A)
    let minCount = 9999;
    let temp;
    let temp2;

    for (let j = AM; j >= 0;j--){
        for (let k = Math.floor((N - A * j ) / B); k>=0;k-- ){
            temp = (N - A * j - B * k) / C
            temp2 = Math.floor(temp)

            if(temp === temp2){
                if(minCount > j + k + temp2){
                     minCount = j + k + temp2
                }
                break;  
            }
        }
    }
    console.log(minCount)
}   

ここで少し改修を入れてみました。

①Nに値を取得する時にparseIntを設定する。

②ループ内にparseIntをMath.floorに変えてみる。

【①parseInt設定後】

ループ1回あたりの処理時間：0.000008676ミリ秒

10^8回の場合の処理時間＝0.8676

【②ループ内parseInt -> Math.floor変更後】

ループ1回あたりの処理時間：0.000003558ミリ秒

10^8回の場合の処理時間＝0.3558

①がかなり効果ありました。推測するに、内部的に行われる文字列->数値変換自体がそもそも、重い処理ということなんでしょうね。

②についてもそこそこ効果はあったようで、Math.floorってparseIntより早いんですね。

結構学びが多い、演習でした。