[プログラマー]疲労度

問題の説明

XXゲームには疲労度システム(0以上の整数で表示)があり、一定の疲労度探索コピーを使用できます.このとき,各レプリカには,探検開始に必要な「最小必要疲労度」と,レプリカ探検完了時に消費される「消費疲労度」がある.「最小必要疲労度」は、探検コピーに必要な最小疲労度を表し、「疲労度の消費」は、探検コピー後に消費される疲労度を表します.例えば、「最小需要疲労度」が80、「消耗疲労度」が20のコピーを探索するためには、プレイヤーの現在の残りの疲労度は80以上でなければならず、探検コピー後は20の疲労度を消費する.
このゲームには1日に1回探検できるコピーが複数あり、1人のプレイヤーが今日のコピーをできるだけ多く探検したいと思っています.プレイヤーの現在の疲労度kと各レプリカの「最小必要疲労度」、「消耗疲労度」の2次元配列がパラメータとしてしっかり与えられている場合は、解題関数を完了し、プレイヤーが探検できる最大レプリカ数を返してください.

せいげんじょうけん

kは1以上5000以下の自然数です.

刑務所の長手方向(行)の長さ(すなわち、コピーの個数)は1または8未満である.

地牢の横方向(列)の長さは2である.

刑務所の各行は、各コピーの[「最小必要疲労度」「消費疲労度]]である.

「最低必要疲労度」は、常に「消費疲労度」以上である.

「最低必要疲労度」と「消費疲労度」は1以上1000以下の自然数です.

の異なるコピーの［「最小必要疲労度」、［消費疲労度］は同じである可能性があります.

I/O例

I/O例説明

今の疲労度は80です.
1つ目→2つ目→3つ目のコピーの順に探検すると

現在の疲労度は80であり、「最小必要疲労度」は80であり、最初のコピーを探索するために使用することができる.最初のコピーの「消耗疲労度」は20で、探検コピー後の残りの疲労度は60です.

の残りの疲労度は60で、2番目のコピーを回転するのに必要な「最小必要疲労度」は50で、2番目のコピーを探検することができます.2番目のコピーの「消耗疲労度」は40で、探検コピー後の残りの疲労度は20です.

の残りの疲労度は20であり、3番目のコピーを回転するのに必要な「最小必要疲労度」は30である.そのため、3番目のコピーは探検できません.

1つ目→3つ目→2つ目のレプリカの順に探検すると

現在の疲労度は80であり、「最小必要疲労度」は80であり、最初のコピーを探索するために使用することができる.最初のコピーの「消耗疲労度」は20で、探検コピー後の残りの疲労度は60です.

の残りの疲労度は60で、3番目のコピーを回転するのに必要な「最小必要疲労度」は30で、3番目のコピーを探検することができます.3つ目のコピーの「消耗疲労度」は10で、探検コピー後の残りの疲労度は50です.

の残りの疲労度は50で、2番目のコピーを回転するのに必要な「最小必要疲労度」は50で、2番目のコピーを探検することができます.2番目のコピーの「消耗疲労度」は40で、探検コピー後の残りの疲労度は10です.

したがって,この場合3つのコピーを探検することができ,プレイヤーが探検できる最大コピー数は3である.

Solution

コピーのシーケンスを作成します.

シーケンスの要素を探索し、探索コピーが最も多い回数を返す.

function adventure(k, dungeons) {
    let count = 0
    for (let i = 0; i < dungeons.length; i++) {
        let [need, con] = dungeons[i]
        if (k >= need) {
            k -= con
            count++
        }
    }
    return count
}
function solution(k, dungeons) {
    var answer = 0;
    const getPermutations= function (arr, len) {
        const results = [];
        if (len === 1) return arr.map((el) => [el]);

        arr.forEach((fixed, index, origin) => {
            const rest = [...origin.slice(0, index), ...origin.slice(index+1)]
            const permutations = getPermutations(rest, len - 1);
            const attached = permutations.map((el) => [fixed, ...el]);
            results.push(...attached);
        });
        return results;
    }
    let candi = getPermutations(dungeons, dungeons.length)
    for (let i = 0; i < candi.length; i++) {
        let count = adventure(k, candi[i])
        if (count === dungeons.length) return count
        if (count > answer) {
            answer = count
        }
    }
    return answer;
}

いずれも通過したが,時間的複雑さと空間的複雑さを考慮していないため,並べ替えは不適切な解決策である.

Refactoring

レプリカは、所与のkよりも低い最初の要素を必要とするレプリカが探検できないため、キャンセルされる.

深度優先ブラウズ(dfs)が使用されるため、レプリカにアクセスするかどうかを記録するために、アクセス者が作成される.

dfsは、検索された答えがフィルタ配列内の要素の個数と同じである場合、すぐにすべてのコピーを返します.

function solution(k, dungeons) {
    var answer = 0;
    let filtered = dungeons.filter(el => el[0] <= k)
    let visited = new Array(filtered.length).fill(false)

    const dfs = (energy, cnt) => {
        for (let i = 0; i < filtered.length; i++) {
            if (visited[i]) continue
            let [need, con] = filtered[i]
            if (energy < need) continue
            visited[i] = true
            let nextEnergy = energy - con
            let nextCnt = cnt + 1
            if (nextCnt > answer) answer = nextCnt
            if (answer === filtered.length) return answer
            dfs(nextEnergy, nextCnt)

            visited[i] = false
        }
    }
    dfs(k, 0)
    return answer
}

より良い演技を披露する.

GItHub repo