不出来
■A - Dial Up
どこが間違ってるのかがわからなくて
ゼロから書き直す糞ムーブ
Tが01で切り替わる時は、一回Sの01の境目のとこまで行っていれば
以降は1回シフトすればいい。
■B - Squares
x^2 - y = z^2
x^2 - z^2 = y
平方数と平方数の差は
(2x-1) + (2x-3)+......になるので
書くと
1^2 - z^2 = 1
2^2 - z^2 = 3 + 1
3^2 - z^2 = 5 + 3 + 1
(右辺はzで変わる)
で、右辺のyは、足される個数がiなら
((2 * x + 1 - 2) + (2 * x + 1 - 2 * i ) )* i / 2=(2 * x - i)*i
なのでこれがnを超えるラインを二分探索で適当にやる。
■C - LIS to Original Sequence
こういうの無理です僕。
結局、減少列がK個あり、それぞれに与えられた配列の要素が含まれていれば満たす。
あとは辞書順を意識して振り分ければいい。
■D - Unique Subsequence
こっち考えるべきだったかも。
わりとシンプルなdp
選んだやつと選んだやつ(LRとする)の間に
選んでいないLかRと一致するやつがあったら駄目。
それだけを考えてdpをうまいことすればいい。
明からに区間和なので、セグ木を用意する
問題は区間がどこからどこまでなのか。
駄目な条件は上に書いたとおりなので、直前の同じものの位置を
pre配列にメモしておく。それ以降を全部足せばいい。
でもこれだと、L(L)Rみたいなのを数えてしまうので
セグ木の更新は、今更新するdpをpreの位置を0にすればいい。
・サンプル１とセグ木のデバッグログ
3
1 2 1
1 1 0 0 0
1 1 2 0 0
1 0 2 3 0
1 0 2 3 6
5
最初と最後に0とNを足すと処理が楽。(0とNは絶対使う)
最後に1を引くのを忘れない。
■E - Snack
これ賢いですね。
フローを流したいが、辺の数が多すぎるので
フローのお気持ちになる。
最大流量＝最小カットなので最小カットを考える
Sに含まれるお菓子を決めてしまうと、
子どもたちをTに含ませるべきかSに含ませるべきか(つまりどこを切るのか)
が決まる。なのでSに含まれる数を全部考えて最小カットの値を答えればいい。
■F - Tree Degree Subset Sum
今の僕には関係なさそう。
