https://codeforces.com/contest/1288
突然ですがblog再開です。
A
凸なので解が小さくなり始めたらbreakすれば良いんですが条件を若干間違えてWA...
コンテスト後100000までやるってのを見て賢いと思いました。
B
bの桁数を固定してしまえばbは9999....のようにしかなりえません。Aは範囲内ならなんでもいいです。
C
数列内の不等式が成り立っていればあとはa_m <= b_mであればいいです。
a_mとb_mを固定して数列ごとに独立に場合の数をdpで求めました。
しかし長さ2mの数列に見立てれば一つのdpで済んだ上に、経路数に帰着してしまえばO(1)で済みます。
D
maxと見えたのでにぶたんしたら出来ました。2つの値のorを取ったら全bitが埋まっているという条件になるので前計算で
そのような値のpairを全て求めておきます。
E
最大が本質パートです。数列の先頭にn n-1 n-2 ... 1を追加すると、同じ数の間に入っている数の種類数を求めればいいことになります。
例えば5 4 3 2 1 3 5 1 4 1なら1同士の間には{3, 5}と{4}が含まれるので、max(|{3,5}|, |{4}|)+1=3を答えにすればいいです。
最初計算量を下げられる気がしなかったんですが(というか種類数を扱うので平方分割だと思った)、2次元座標で可視化したらあっさりでした。indexが小さい順から見ていって、同じ数内では一番最後に見たものだけ管理していけば良いです。これはBITで実装できます。
F
なんか線形計画問題にしてみたんですがよくわからなかったです…
