Educational Codeforces Round 27

スポンサーリンク

A. Chess Tourney

上位下位 $n$ 個ずつに分けて下位の max と上位の min を比べます.

B. Luba And The Ticket

$10^6$ 通りすべてを試してもよいです.

C. Two TVs

区間の重なる枚数の最大値が $2$ 以下であるというのが条件です.

D. Driving Test

奇数番号と偶数番号のイベントは独立.1 や 2 が起きたときに貪欲に無視する必要があるものを決めます.

E. Fire in the City

近傍は 8 近傍.

二分探索判定問題を考えると,次のようになります.正方形が $k$ 個与えられる.もうひとつ正方形を置いて,領域全体を被覆できるか?座圧して $O(k^2)$ 個の区画に分けて,どの区画を被覆できたかを累積和で求めておきます.未被覆の点の bounding box をとって目的の大きさの正方形に収まるかを判定します.

F. Guards In The Storehouse

$nm\leq 250$ より列の個数が $15$ 以下としてよいです.最後の $1$ 行分 $m$ マスの状態を保持しながら,$1$ マスずつの置き方を決めていく dp をすればよいです.

G. Shortest Path Problem?

パスのひとつにサイクルを足していけばよいです.複数の walk の違いはサイクルで書けるからです.サイクルはサイクル基底の和でかけます.全域木をとったあと余分な辺ひとつに対してひとつサイクルがとれて,それらが基底です.検索ワード:サイクル空間,サイクル基底等.

結局次の線形代数の問題になります:

非負整数 $x$ とxor 基底 $e_1,\ldots,e_k$ が与えられたとき,$x$ に $e_i$ を xor していって $x$ を最小化せよ.

CodeForces
スポンサーリンク
シェアする
maspyをフォローする
maspyのHP
タイトルとURLをコピーしました