gyouzasushi’s diary

競プロとか

今日の競プロ(2020/4/6)

Codeforces 4問

第一回日本最強プログラマー学生選手権-予選- D - Classified

これACできたの嬉しい。成長を感じちゃうね。

条件は「レベルが等しい通路のみに注目したとき、奇数長の閉路がない」ということなので、二部グラフのイメージで構築できそう！！

f:id:gyouzasushi:20200406135136p:plain

$N$ 室の場合はこんな感じで新たなレベルの通路（赤）を追加すればいける。 $N=2,3$ のときをベースに小さい $N$ から計算していく。

ARC098 E - Range Minimum Queries

解説AC。

最小値 $Y$ を決め打つ。
$Y$ より小さい要素を含む部分列に対しては操作ができない。
$Y$ が一定のとき、 $X-Y$ の最小化は $X$ の最小化。
問題の操作は最小値をみる操作。最小の最小は考えやすい。

了承！

ARC091 E - LISDL

f:id:gyouzasushi:20200407002223p:plain

Educational Codeforces Round 44 A - Chess Placing

バチャ。ソート忘れて2WA…。

Educational Codeforces Round 44 B - Switches and Lamps

Educational Codeforces Round 44 C - Liebig's Barrels

Educational Codeforces Round 44 D - Sand Fortress

f:id:gyouzasushi:20200407003743p:plain

最高峰の高さで二分探索。 $n,H \leq 10^{18}$ が怖かったのでpythonで書きました。

コメント

バチャのEFはいずれやります。