LeetCoding Challenge Oct. 24: Bag of Tokens

LeetCode October Challenge の 24 日目。

今日の問題は Bag of Tokens。

問題

• パワーの初期値 P と各トークンのパワー消費量を記した配列 tokens が与えられるので、パワーとスコアをやりくりしながらゲーム (?) をプレイして最大のスコアを求める
  • スコアの初期値は 0
• ゲームのルール
  • 各トークンは face up / face down いずれかの操作を 1 回だけ行える
  • パワー消費量が現在のパワー残量以下であるトークンは face up できる
    • Face up すると、そのパワー消費量の分だけ現在のパワー残量が減るが、スコアは +1 される
  • スコアが 1 以上のとき、任意のトークンを face down できる
    • Face down するとスコアが -1 されるが、そのトークンのパワー消費量が逆に現在のパワー残量に加算される

考え方

• うーむ、ちょっと難しそう。枝刈りとか DP とか使いつつ総当り的に解かなきゃいけない問題だったりするのかな？ 🤔 (しばし考える)
• とりあえず、トークンの配列はソートした方がいいかな？
  • O(n * log(n)) の時間計算量になる
• あ、もしかして、パワー消費量の小さいトークンから順に可能な限り face up して、最もパワー消費量の大きいトークンを 1 つだけ face down、そしてまたパワー消費量の小さいトークンを face up... という操作を繰り返せばいいのかな 💡
  • この操作は O(n) で実現できそう 🤩
• 実装して submit → accept 🎉
  • Runtime は 3ms で、 Your runtime beats 89.08 % of java submissions.
  • せっかくなら beats 90% にたどり着きたいなー
• 実装をいろいろガチャガチャ変更して submit を繰り返し、何度か wrong answer を喰らう 😩
• 苦労が実ってついに 2ms 達成 🎊
  • Your runtime beats 99.75 % of java submissions.

コード

class Solution {
    public int bagOfTokensScore(int[] tokens, int power) {
        Arrays.sort(tokens);

        int left = 0, right = tokens.length;
        while (left < right) {
            if (power >= tokens[left]) {
                power -= tokens[left++];
            } else {
                if (left == 0 || tokens[right - 1] <= tokens[left]) {
                    break;
                }
                power += tokens[--right];
            }
        }

        return left - (tokens.length - right);
    }
}