貪欲で 3 つ組の最大から目標を作る

3 つの数の組の並びからいくつかを選び、位置ごとの最大を取って目標の組を作れるかを返す。目標を 1 か所でも越える組は使えないので捨て、残りの組で目標の 3 つの値がそろうかだけを見れば判定できます。

海外で定番の問題リスト 4 本には入っていません

問題

ゲームの装備に、攻撃、守り、速さの 3 つの値があり、装備の一覧が 3 つの数の組の並び triplets で渡されます。いくつかの装備を選んで合成すると、合成した物の値は、選んだ装備の位置ごとの最大になります (攻撃は選んだ物の攻撃の最大、守りは守りの最大、速さは速さの最大)。目標の組 target とちょうど同じ値の物を作れるなら true、作れないなら false を返す関数を書いてください。

選ぶ装備は 1 つ以上で、同じ装備を 2 回選ぶことはありません
1 つだけ選んだときは、その装備の値がそのまま合成した物の値です
triplets の長さは 1 以上 100000 以下、値はどれも 1 以上 1000 以下です

入力と出力の例

例 1

[1, 6, 2] と [4, 3, 2] を選ぶと、位置ごとの最大は [4, 6, 2] です。[5, 6, 1] は攻撃が 5 で目標の 4 を越え、[2, 2, 7] は速さが 7 で目標の 2 を越えるので選べません。

triplets = [[1, 6, 2], [4, 3, 2], [5, 6, 1], [2, 2, 7]] target = [4, 6, 2]

true

例 2

[3, 5, 2] は守りが目標の 4 を越えるので選べません。残る [3, 1, 4] だけでは、守りが 1 のままです。

triplets = [[3, 1, 4], [3, 5, 2]] target = [3, 4, 4]

false

例 3

目標とちょうど同じ装備が 1 つあれば、それだけで作れます。

triplets = [[2, 9, 1], [7, 7, 7]] target = [7, 7, 7]

true

面接での聞かれ方

面接では、短い一文で渡されることが多いです。

「3 つ組の配列があります。いくつかを選んで要素ごとの最大を取ると、目標の 3 つ組になりますか」
「選ぶ数に決まりはありますか」と聞くと、「いくつでも」と返ってくるのがふつうです
書き終えたあとに「4 つ組、k 個組ならどうしますか」と、広げて聞かれることもあります

最大を取るのか合計を取るのかで、問題がまったく変わります。書く前に確かめておきます。

ヒント

まだ開いていません

付箋は 3 枚。下の段ほど答えに近づきます

ヒント 2
ヒント 3答えに近い

アルゴリズムのチートシートの「配列と文字列」に、この型の要点を表とコードでまとめています。

配列と文字列の問題は、全部の組を調べると手間が大きくなる所を、窓や左右の添字で減らす形が多いです。

まず考える手順

段 1

素直に考えると、選ぶ装備の組み合わせを全部試し、位置ごとの最大が目標と同じになるかを調べることになります。組み合わせは 2 の n 乗あるので、n が大きいと終わりません。

段 2

最大を取るので、値は選ぶほど大きくなる一方で、小さくはなりません。1 か所でも目標を越える装備を選ぶと、その位置は目標より大きいまま戻りません。そういう装備は、最初から捨ててよいと分かります。

段 3

捨てずに残った装備は、どれをいくつ選んでも、どの位置も目標を越えません。なら、残りを全部選ぶのが最もよく、位置ごとの最大が目標に届くかだけを見れば足ります。前から 1 回なめて、残った装備の値で位置ごとの最大を広げ、最後に目標と同じかを比べます。

解答

Python

def can_make_target(triplets, target):
    best = [0, 0, 0]
    for t in triplets:
        if any(
            t[k] > target[k]
            for k in range(3)
        ):
            continue
        for k in range(3):
            best[k] = max(best[k], t[k])
    return best == list(target)

JavaScript

function canMakeTarget(
  triplets, target
) {
  const best = [0, 0, 0];
  for (const t of triplets) {
    const over = t.some(
      (v, k) => v > target[k],
    );
    if (over) {
      continue;
    }
    for (let k = 0; k < 3; k++) {
      best[k] = Math.max(
        best[k], t[k],
      );
    }
  }
  return best.every(
    (v, k) => v === target[k],
  );
}

Go

func canMakeTarget(
	triplets [][]int, target []int,
) bool {
	best := [3]int{}
	for _, t := range triplets {
		if t[0] > target[0] ||
			t[1] > target[1] ||
			t[2] > target[2] {
			continue
		}
		for k := 0; k < 3; k++ {
			best[k] = max(best[k], t[k])
		}
	}
	return best[0] == target[0] &&
		best[1] == target[1] &&
		best[2] == target[2]
}

best を 0 から始めているのは、値がどれも 1 以上だからです。残った装備が 1 つも無いときは best が [0, 0, 0] のままで、目標とは必ず食い違うので false になります。

計算量

時間は O(n) です。装備を前から 1 回なめ、1 つごとに 3 か所を見るだけです
使う記憶は O(1) です。持つのは位置ごとの最大の 3 つだけです
位置ごとに「目標と同じ値を持つ装備が残りにあるか」の印を 3 つ持つ書き方でも、同じ計算量で解けます

よくある間違い

目標を越える装備も選ぶ。例 1 で全部の装備の最大を取ると [5, 6, 7] になり、目標と食い違って false を返します。越える装備は捨ててから最大を取ります
位置ごとに別々に「目標の値を持つ装備があるか」だけを見る。 triplets = [[3, 1, 4], [3, 4, 9]]、target = [3, 4, 4] では、守りの 4 を [3, 4, 9] が持っているので作れると答えてしまいます。[3, 4, 9] は速さの 9 が目標を越えるので選べず、本当は作れません。越えるかどうかは、3 か所を合わせて装備ごとに見ます
合計で考える。位置ごとに足すと、選ぶほど値が大きくなり、問題の意味が変わります。合成した物の値は最大です
1 つの装備で目標とちょうど同じ物だけを探す。例 1 にはそういう装備がありませんが、2 つを合わせれば作れます

解答を動かした版 Python 3.14.7Node.js 24.22.1Go 1.24.2確認日 2026年11月8日

main.py

def can_make_target(triplets: list[list[int]], target: list[int]) -> bool:
    """
    Goal: 何を返すか

    idea1: まず思いつく案
    -> runtime: O(?)  space: O(?)

    idea2: もっと速い案
    -> runtime: O(?)  space: O(?)

    edge case: 空、1 つだけ、など
    """
    # ここに書きます
    pass


# 「実行」を押すと、この行の結果が出ます
print(can_make_target([[1, 6, 2], [4, 3, 2], [5, 6, 1], [2, 2, 7]], [4, 6, 2]))

できているか「例で確かめる」を押すと、問題の例を全部この関数に渡して、通ったかをここに出します