競プロとゲームをしていません

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

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

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

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

ABの2完。

A Subrectangle Guess

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

B Circle Game

山の数が奇数

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

山の数が偶数

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

C Zero Path

わからなかった🙃。

↓→を→↓に変えると、経路重み和が-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の解法を思いつくのは不可能に見える。 類似問題を沢山解いてパターンマッチングする以外の攻略法はあるのか。