7完86:01 + 1ペナ 261位
Gで詰まりすぎ＆Ex解かれすぎ
A camel Case
isupper, islower忘れがち、 'A' < S[i] && S[i] < 'Z'でやった
(AC 1:13)
B Trimmed Mean
スキーとかのあれ、ソートして足すだけ
setprecision久しぶりな気がする
(AC 3:42)
C LRUD Instructions 2
setにpairをいれて判定する、ほぼ同じようなの解いた気が？？
(AC 6:24)
D Flip Cards
無限にやった、裏返したかもつDPやるだけ
(AC 10:45)
E Find Permutation
こういうのどこまでが必要十分かわからないがち
ざっくり考えると、「i より jのほうが大きい」という情報が与えられて、それを満たすものが一意か判定せよ、ということなのでそもそもの「それを満たす順列は？」を考えると、トポロジカルソートをすればいいことがわかります
ということで、「トポロジカルソートが一意ですか？」という問題になります
トポロジカルソートを考えると、それぞれの時点で「入次数が0」のものが次に来る候補になるので、「一意になる = 次に来る候補が1通り」であると考えられます
あとは、実際にトポロジカルソートをしてそのときのqueueに値が1つだけか判定すればよいです
(AC 23:25)
F Teleporter and Closed off
いつものFよりはかなり簡単に感じた
「iを除いたときに」というタイプの問題では、両側から計算しておいてそれをくっつけることが多いです
今回はそれがドンピシャで使えて、「1~iまでの最短回数」「i~Nまでの最短回数」を求めておきます
「i~Nまでの最短回数」は愚直にやると全体でO(N^2 M)になりますが、Nから逆側にたどることで全体でO(NM)にできます
「1~iまでの最短回数」「i~Nまでの最短回数」がわかれば、あとはそこまで大変ではなくて、ありえるところを愚直に試します
iを使わないということは、「どこかでiをまたぐ」ことになるのでどこでまたぐかを全探索します
M≦10なので左側10個、右側10個だけみてあげればよいです
到達できない場合のINFをintで管理していると、INF+INFでオーバーフローする可能性があるので注意です(1敗)
(AC 36:25)
G OR sum
Fまでサクサクだったので、わくわくしながらGをみます
「動かしながら計算した時の値のmax, min」という抽象化をすると、過去の問題に近いものがあります
こういう形に帰着できないか考えていきます
畳み込みの形を用いるのであれば、反転させた方がindexの都合がよさそうなので、Bのindexは反転させることにします
N = 3の時で考えてみます
0 1 2 3 4 5
A : 1 2 3 1 2 3
B : 7 6 5 7 6 5
という感じでそれぞれ2倍にしておいてみます(実はBは2倍にしない方が楽です)
i+j = 0のとき
(1|7)
i+j = 1のとき
(1|6) + (2|7)
i+j = 2のとき
(1|5) + (2|6) + (3|7)
i+j = 3のとき
(1|7) + (2|5) + (3|6) + (1|7)
i+j = 4のとき
(1|6) + (2|7) + (3|5) + (1|6) + (2|7)
...のようになります
こうすると、Aに対してBはきちんとcyclic shiftしていることがわかります
求めたいものは i+j = N-1 ~ 2N-2の値で十分です
ただし、i+j > N-1のときは余分なものがついています
i+j = Kのときに、i+j = K-Nの部分だけ無駄なのでこれを取り除いてあげればよいです
方針としては、畳み込みをして(Ai|Bi)の和を高速に求めればよさそうだとわかります
ただし普通の畳み込みでは(Ai|Bi)であるOR演算をうまく扱えません
ここで先ほどのSubstring 2を改めて考えてみます
Substring 2では0,1に置き換えることでAND演算を計算していました
今回はORですが、0または1のA,Bに対して
「A OR B = 0」 = 「notA AND notB = 1」であることがわかります
これを用いてORをANDに変換できます
つまり、1つのbitにのみ着目した時、bitを反転させた結果AND演算が0でなければ、もともとのOR演算の結果は0になります
この0,1をうまく扱うためにはbitごとに計算しないといけないですが、bitごとに5回畳み込みをすることで、OR演算の結果を計算できます
i+j = N-1 ~ 2N-2の値を各bitに対して計算してあげて最大値をとれば解けます
(AC 86:01)
総括
7完うれしいけど、重心分解そんなに解かれる？
