C++で解く「Teemoの攻撃」問題：毒状態の合計時間を求めるアルゴリズム

問題概要

League of Legends(LOL)の世界には、ティーモ(Teemo)というヒーローがいます。彼の攻撃を受けると、敵のアーシュ(Ashe)は毒状態に陥ります。本記事では、ティーモがアーシュに対して行った攻撃の時刻を昇順に並べた時系列と、1回の攻撃ごとの毒の持続時間が与えられたとき、アーシュが毒状態であった時間の合計を求める問題を扱います。なお、ティーモはある時点の最初に攻撃を行い、その瞬間に相手を毒状態にできるものと仮定します。

入出力の例

たとえば、攻撃時刻が [1,4]、毒の持続時間が 2 秒の場合、出力は 4 になります。時刻 1 にティーモが攻撃を行うと、アーシュは即座に毒状態になり、その状態は時刻 2 の終わりまでの 2 秒間続きます。その後、時刻 4 に再び攻撃が行われ、さらに 2 秒間だけ毒状態が継続します。したがって、最終的に出力すべき値は 4 となります。

解法の考え方

この問題を解くには、以下の手順に従います。

• ret := 0、currEnd := -1、n := 時系列 t の要素数として初期化する
• i を 0 から n − 1 までループする
  • start := t[i]、end := t[i] + d − 1 とする
  • currEnd < start の場合(前回の毒が切れた後の攻撃)は、ret += end − start + 1 として新しい毒時間を丸ごと加算し、currEnd = end と更新する
  • それ以外の場合(毒の効果が前回と重なる場合)は、ret += end − currEnd として重複分を除いて加算し、currEnd := end と更新する
• 最後に ret を返す

ポイントは、次の攻撃による毒の効果が、前の毒の効果と重なる可能性があるという点です。現在の毒の終了時刻を表す currEnd を管理することで、同じ時間を二重にカウントすることを防げます。

C++による実装

理解を深めるために、以下の実装例を見てみましょう。

#include <bits/stdc++.h>
using namespace std;
class Solution {
    public:
    int findPoisonedDuration(vector<int>& t, int d) {
        int ret = 0;
        int currEnd = -1;
        int n = t.size();
        for(int i = 0; i < n; i++){
            int start = t[i];
            int end = t[i] + d - 1;
            if(currEnd < start){
                ret += end - start + 1;
                currEnd = end;
            } else {
                ret += end - currEnd;
                currEnd = end;
            }
        }
        return ret;
    }
};
main(){
    vector<int> v = {1,4};
    Solution ob;
    cout << (ob.findPoisonedDuration(v, 2));
}

入力

[1,4]
2

出力

4