はまやんはまやんはまやん

hamayanhamayan's blog

Codeforces Round #404 問題と解説

http://codeforces.com/contest/785

A. Anton and Polyhedrons

http://codeforces.com/contest/785/problem/A
"Tetrahedron"なら4面体, "Cube"なら6面体, "Octahedron"なら8面体, "Dodecahedron"なら12面体, "Icosahedron"なら20面体である。
N個の上の5つの内の立体の種類が与えられるとき、全ての立体の面数の総和は?

B. Anton and Classes

http://codeforces.com/contest/785/problem/B
N個のチェスの授業、M個のプログラミングの授業がある。
各授業で開始時間と終了時間が決まっている。
チェスとプログラミングの授業を1つずつとる時、2つの授業の間の休み時間の最大値は?
(必ずかぶる場合は0とする)

C. Anton and Fairy Tale

http://codeforces.com/contest/785/problem/C
N個収容できる倉庫がある(最初はN個入っている)。
以下の行動が毎日繰り返される時、何日目で終了するか。

(i日目とする)
1. 倉庫からi個取り出す(取り出し切れないor空っぽから終了)
2. M個倉庫に入れる(N個を超える時は満杯のN個が倉庫に入った状態にする)

D. Anton and School - 2

http://codeforces.com/contest/785/problem/D
文字列Sの(非連続OKの)部分列のうち、RSBSである部分列は何通りあるか(mod10^9+7)。
※ RSBS: (),(()),((())), (((()))), ... みたいな文字列

E. Anton and Permutation

http://codeforces.com/contest/785/problem/E
N個の数列があり、中身は{1,2,3, ... ,N}である。
これについてQ個の以下のクエリを処理する。

1. L[i]番目とR[i]番目の要素をスワップする
2. 数列全体について反転数を答える













以下、解説

A. Anton and Polyhedrons

http://codeforces.com/contest/785/submission/25502869
各立体についてmapを用意しておいて、面数を足して答える。

B. Anton and Classes

http://codeforces.com/contest/785/submission/25506203
以下の2パターンのみ考えればよい
1. 「一番早くに終わるチェスの授業」と「一番遅く始まるプログラミングの授業」
2. 「一番早くに終わるプログラミングの授業」と「一番遅く始まるチェスの授業」

C. Anton and Fairy Tale

http://codeforces.com/contest/785/submission/25511808
まず、M日目までは取り出して入れると倉庫にはN個入っている。
M+i日目では取り出して入れると倉庫にはN-(1+2+...+i)個入っている。
この考察を前提に場合分けして解く。

(1) N <= M のとき
1~N-1日目では倉庫の中身はN個で変化しない。
丁度N日目で倉庫の中身が全て無くなり、終了する。
なので、N日目が答え

(2) M < N のとき
1~M日目では倉庫の中身はN個で変化しない。
ここでは、M+i日目で始めてN-(1+2+...+i-1)-(M+i)が0以下となるiが求まれば、M+iが答え。
(最後のM+iだけ別になっているのは操作1だけして操作2をしないから)
これは二分探索で解く。
bool chk(int x) := M+x日目で倉庫の個数が負となる瞬間があるか

D. Anton and School - 2

http://codeforces.com/contest/785/submission/25528993
端から全列挙していくことを考える。
重複しないように一部を固定して列挙していく方針で考える。
[0, i]番目の文字の'('と[i+1,N-1]番目の文字の')'を使ってRSBSとなる組合せを考えるが、条件を付けないとダブって数えてしまうため、S[i]番目の文字列が'('であり、この文字は必ず使うという条件を入れておく。
そのため、iを0~N-1まで動かしながら、「[0, i-1]番目の文字の任意個の'('とi番目の'('と[i+1,N-1]番目の文字の任意個の')'を使ってRSBSとなる組合せ」を順次計算していく。

[0,i-1]での'('の個数をL個、[i+1,N-1]での')'の個数をR個とする。
これは上手いこと計算する(うまいこと)。

ここで作ることのできるRSBSの長さは2*min(L+1,R)となるので、このRSBSの組合せを全て数え上げる。
具体的にはソースコードのnaive解法のようにやる。

これを高速化するのだが、方法1は


であり、以上のツイートのように変換できる(よく分かっていない)ので、数え上げがO(1)でできる。

方法2は


であり、wolframalphaに頼る。

あとはこれの総和を取れば答え。

E. Anton and Permutation

kmjpさんの解法をそのまま解読して書いた。
数列をAとして、i個のクエリについて以下の処理を行う。

1. クエリ処理前の反転数をinvとする(初期値0)
2. L < Rとなるようにswapしておく。
3. swapする数が関連している反転数を引く
 3-1. [0,R-1]でA[R]より大きい数である要素数をinvから引く
 3-2. [0,L-1]でA[L]より大きい数である要素数をinvから引く
 3-3. [R+1,N-1]でA[R]より小さい数である要素数をinvから引く
 3-4. [L+1,N-1]でA[L]より小さい数である要素数をinvから引く
4. swap後にその数が関連している反転数を足す
 4-1. [0,R-1]でA[R]より大きい数である要素数をinvに足す
 4-2. [0,L-1]でA[L]より大きい数である要素数をinvに足す
 4-3. [R+1,N-1]でA[R]より小さい数である要素数をinvに足す
 4-4. [L+1,N-1]でA[L]より小さい数である要素数をinvに足す
5. swap後にA[L] > A[R]ならば操作4でダブって足しているので、一個分引いておく
  swap後にA[L] < A[R]ならば操作3でダブって引いているので、一個分足しておく
6. invを出力

なので、区間である数より大きい数、小さい数である要素数を数えられる、かつ、数をswap(変更)できるデータ構造があればOK
これは、平方分割を使う(らしい。よく分かってない)
流石に自分の解答乗せるのはおこがましいので、kmjpさんの解法はこちら。
http://codeforces.com/contest/785/submission/25521039
pekempeyさんは
http://codeforces.com/contest/785/submission/25530899


赤黒木らしい。
natsugiriさんは2Dセグメントツリー???
http://codeforces.com/contest/785/submission/25528708
思い思いの実装をされてますけど、何一つ分からん。

平衡二分木をちゃんと勉強しなきゃいけない。さっぱりわからん
yosupo.hatenablog.com
プログラミングコンテストでのデータ構造 2 ~平衡二分探索木編~
平衡二分木で何ができるのかがよく分かってない。
勉強しろってことやん