2019-12-13
■ 冬休み0日目
今日から練習した問題を記録します。
Codeforces Round #604 (Div. 1)
ABCDEを解いた。
C
checkpointで区間に分けると値の増え方はかなり単純で、segtreeに乗るのでできる
D
「(,)の割り当て方全てに対して深さの総和」= 「(が入りうる場所について、(左の(の個数) < (右の)の個数) になる割り当て方の総和」になるので、これは二項係数の累積和を計算しておけばO(1)
E
どう見てもフローなのでその方向性で考えると、「サイクルになっていない」 <=> 「出次数が2になる頂点がただ1つ存在」なので、各頂点について出次数 choose 2の総和を最小化すれば良いことがわかる。これがmincost maxflowで解けるのは典型
DDCC2020 予選 F
本番誤読したやつ。
W,TのgcdとH,Tのgcd分同じ問題を解くことになるので、前処理でgcdで割る。
前処理後はT = 1として考えて差し支えないので、実験したり予想したりすると答えが求まる (雑)
