Codeforces Round #801 (Div. 2) and EPIC Institute of Technology Round

1324 (+39), pupil Rank: 3067 Codeforces Round #801 (Div. 2) and EPIC Institute of Technology Round Jun/18/2022 17:35

ABの2完。

どうおいても最大値が含まれるような部分長方形。

Mikeの勝ち。 Mikeは石全部取るのが最適戦術。 Mikeが石取った山から次に石を取るのはJoeなので。

お互い1個ずつ取るのが最適戦術。愚直にシミュレーションするとTLEする。1ループでいい感じに処理。

わからなかった🙃。

↓→を→↓に変えると、経路重み和が $-2,0,+2$ のいずれかだけ変化する。

各マスの経路重み和の最大値 $max _ {i, j}$ と最小値 $min _ {i, j}$ をDPで求める。

経路重み和は $-2,0,+2$ だけ変化するので、経路重み和は $min _ {n, m} , min _ {n, m} +2, \cdots , max _ {n, m} -2, max _ {n, m}$ のうち任意の値を取るはずとのこと。

Cの解法を思いつくのは不可能に見える。類似問題を沢山解いてパターンマッチングする以外の攻略法はあるのか。

hotarunx's diary