Pythonで挑むボス戦アルゴリズム：戦闘員とボスの戦力を判定して勝敗行をふるい分ける方法

問題の概要

0と1だけで構成されたリスト fighters(戦闘員)と、同じく0と1からなる二次元リスト(行列)bosses(ボス)が与えられます。fighters内の「1」は戦闘員1人を表し、bossesの各行に含まれる「1」はその行にいるボスを表します。

戦闘員たちがあるボスの行に勝てるのは、戦闘員の総数がその行のボスの数より多い場合です。つまり、勝てない(倒しきれない)行だけを残し、撃破されたボスの行を取り除いた新しい bosses の行列を返すのがこの問題の目的です。

入力例

たとえば、fighters = [0, 1, 1](戦闘員は2人)で、bosses が次のような行列だったとします。

このとき、戦闘員2人に対してボスが2体以上いる行、すなわち [0, 1, 1] と [1, 1, 1] のみが残り、出力は次のようになります。

解き方のアプローチ

この問題はシンプルな集計とフィルタリングで解決できます。手順は以下の通りです。

• fighter_cnt: fighters の全要素の合計(= 戦闘員の総数)を求めます。

• result: 結果を格納するための新しい空リストを用意します。

• bosses の各行 row について以下を繰り返します。

  • もし fighter_cnt <= row の要素の合計 であれば、その行は撃破されていないため result の末尾に追加します。

• 最後に result を返します。

ポイントは条件式の向きです。「戦闘員の数がボスより多い行」が敗北した行なので、それ以外(fighter_cnt <= ボスの数)の行だけを残せばよい、というわけです。

実装例

理解を深めるために、実際のPythonコードを見てみましょう。

class Solution:
    def solve(self, fighters, bosses):
        fighter_cnt = sum(fighters)
        result = []
        for row in bosses:
            if fighter_cnt <= sum(row):
                result.append(row)
        return result

ob = Solution()
fighters = [0, 1, 1]
bosses = [[0, 0, 0], [0, 0, 1], [0, 1, 1], [1, 1, 1]]
print(ob.solve(fighters, bosses))

入力

[0, 1, 1], [[0, 0, 0], [0, 0, 1], [0, 1, 1], [1, 1, 1]]

出力

[[0, 1, 1], [1, 1, 1]]

計算量とまとめ

このアルゴリズムの時間計算量は O(n × m) です(n は bosses の行数、m は各行の要素数)。各行の合計を一度ずつ計算して比較するだけなので、非常に効率的です。

また、Pythonのリスト内包表記を使えば、さらに簡潔に次のように書くこともできます。

def solve(fighters, bosses):
    cnt = sum(fighters)
    return [row for row in bosses if cnt <= sum(row)]

「合計値を比較して条件に合う行だけを抽出する」というこのパターンは、データのフィルタリング全般に応用できる基本的かつ重要なテクニックです。ぜひマスターしておきましょう。