G解かれすぎーーー、こまっちゃう
6完 64:05で202位、安定はしてる
A Power
std::powを使ったら、指数表記になってこわかったので普通にforでかけた
9 9でチェックしててよかった～
(AC 2:18)
B First Query Problem
い つ も の
さすがに無限回やったことある
(AC 4:41)
C Cash Register
ちょっと考察あるけど簡単～
今の位置から見て「00」なら2つ進めて、そうでなければ1つ進めるシミュレーション
(AC 7:00)
D Scope
問題文に「気を失う」って書いてあってなんだ？？って思った
括弧列どこまでできるか？が重要なんだけど、どうせこういうのは括弧列の対応と相場が決まっているので、stackを使って括弧列の対応をだしておきます
あとは、各文字の最も右の位置をもっておいて、削除できるか判定しながらシミュレーションすればよいです
(AC 13:55)
E Don't Isolate Elements
まず、反転系の典型なんですが「順序は関係なくて、反転するなら1回でよい」です
で、ある行がちゃんと条件を満たしているかを確認するとしたら、i-1行目、i行目、i+1行目の反転状態がわかればよいです
dp[i][j][k] := i-1行目が反転しているかわかっていて(j = 0 / 1)、i行目が反転しているかわかっている(k = 0 / 1)ときにi行目が条件を満たすか？
という風にしたいのですが、i-1行目が反転しているかわかっていてi行目が反転しているかわかっているときに判断ができるのはi-1行目なので、
dp[i][j][k] := i-1行目が反転しているかわかっていて(j = 0 / 1)、i行目が反転しているかわかっている(k = 0 / 1)ときにi-1行目が条件を満たすか？
というDPを定義して計算していきます
条件を満たすかどうかは結構細かいところに考慮しないといけないので、関数にしておくとよいと思います
周囲を0,1以外の数でうめておくと端っこの処理が不要になり、ちょっと楽になります
(AC 44:33)
F Permutation Distance
| Pi - Pj | + | i - j |の最小化ですが、絶対値はかなりめんどくさいので外したいです
たとえば、Pi < Pjを固定してあげると、絶対値は1つ外せます
同様に考えると、(Pi, Pjの大小) × (i,jの大小)の4パターンしかないことがわかります
まあちょっとめんどくさいかもしれませんが、ほとんど同じなので4パターンすべて解けばいいです
たとえば、 Pi < Pj かつ i < jのときを考えてみましょう
最小化するべき値は Pj - Pi + j - iであり、-Pi - iはiを決めると固定されるので、Pj+jの最小化ができればよいです
Piをみるときには、それより値が大きなものがどこにあるかわからないといけないので、Piの大きい順に処理を行います
セグメント木を用いて、iの位置にPi+iをsetすることにします
そうすると、iより右にあるものについて最小値をとればPj+jの最小値をO(logN)で求められます
同様のことを残りの3パターンすべてについて考えて、その最小値をとればよいです
(AC 64:05)
G Partial Xor Enumertation
どうせ基底をとって、うまく小さい順に並べられればなと思って、noshi基底をとったんですが、小さい順に並びませんでした(ちーん)
(AC --:--)
総括
こういうE頭壊れるけど意外とパフォでる
