2021/03/02
ペンキの色
JOI 難易度7
解法は一瞬で思いついたけど、実装にかなり時間がかかった。
座圧してbfsをした。
強い人はUnionfindを使っていた。こっちの方が楽そう。座圧用の配列に各値を+1した値も入れたが、必要なかった。
Grouping
EDPC U
3^Nになるやつ。
AtCoder Jumper
青diff
答えは知っていた。ページxからはx*2とx*2+1をリンク先にする。10回移動したら1024x+1~1024x+1023に移動できる。
庭園
黄diff 試験管
2つの長方形は上下か左右に分けることができる。
上下に分けるパターンを考える(左右はBを90度回転したものを同じようにすればいい)。
ue[i]:(i行目までの区画を使ってできる長方形の総和の最大値)
sita[i]:(i行目以降の区画を使ってできる長方形の総和の最大値)
を求めればいい。2次元累積和を使えばO(N^3)で求めることができる。
Binomial Coefficient is Fun
黄diff
分からなくて解説動画を見た。天才だった。
