2017-10-29
■ Codeforces Round #443 Div1
参加してないんですが、ACDEをupsolvingしました。最近のこどふぉらしからず(?)(B以外)どれも結構面白かったので書きます。
A
問題概要
N(<=5*10^5)回、0以上1023以下の値をAND,XOR,ORする。これと等価な操作を5回以内の0以上1023以下の値をAND,XOR,ORすることで作れ。
解法
はじめのi番目のbit(0<=i<10)が0,1だった時、操作を終えた時どうなっているかを見る。
0,1 -> 0,0となっているものは0とのANDで、0,1 -> 1,0となっているものは1とのXORで、0,1 -> 1,1となっているものは1とのORで作れるので実は必ず3回で出来る。O(N)
C
問題概要
N(<=5*10^4)人の人にK(<=10)種類のパラメーターが定まっている。
「ある2人があるパラメーターの値で競い、小さい方が敗北し、消える」
という操作を繰り返す時、1....i番目(1<=i<=N)の人に対して最後の1人になり得る人の数を求めよ。
解法
人i -> 人j iff 人iは人jに勝るパラメーターがある
として有向グラフを作る。
このとき、このグラフをSCCすると任意の2人に対し双方向、あるいは一方向の辺が貼られているのでクリークになり、
かつ全順序が定まっていることが分かる。
よって、一人ずつ追加していくと
どこかに挿入される or 連続した部分列と新規の人が一つの強連結成分になる
が起こるので、setで持って列を管理すると解ける。 O(NK log NK)
D
問題概要
K(<=12)匹の生き物が居て、N(<=10^5)種類のパラメーターが定まっている。
Q(<=10^5)個のクエリが来るので処理してください。クエリは以下の3種類:
- ある2匹の生き物から全部のパラメーターが2匹の対応するパラメーターのmaxになる生き物を作る
- ある2匹の生き物から全部のパラメーターが2匹の対応するパラメーターのminになる生き物を作る
- ある生き物のあるパラメーターの値を出力する
解法
2乗を1/64パワーでゴリ押す解法をしたくなるが我慢して考えると、これを思い出す。
2分探索をすることを考えると、値がmid以上 -> 1 otherwise -> 0と変換して、同じ操作をし0か1を見る、ということをすればよいとわかる。
ここで、考えられる0と1のパターンは2^K通りしかないので、2^K通りすべてに対してクエリの順番に操作を行っておくと解ける。O(2^K * Q)
E
問題概要
長さN(<=10^5)の数列aが与えられる。Q(<=10^5)個のクエリに答えよ。クエリの形式は以下の通り:
L,R(1<=L<=R<=N)が与えられるのでa[L..R]に対し
「隣接する2要素を選び(x,yとする)、削除してx+2yをその場所に追加する」
ということを要素が1つになるまで繰り返すとき、最後の値の最大値をmod 10^9+7で求めよ。
解法
2^b_i * a_iの形の値の和になることは明らかで、b_iの条件を考えると
- b_L = 0
- 1<=b_i<=b_(i-1)+1(L
となりそうなことが手を動かすとわかる(未証明)ので、
以下この問題を解く。
b_iをb_(i-1)+1にしない時のことを考えると、明らかに1にするしかないことが分かる。(中途半端な値を取るメリットはないため)
よって、b_iは0,1,2,...,x,1,2,...,y,1,2,...z,...のような階段を繰り返す感じが最適とわかる。
どこで区切るべきかを考えると、
後ろから見たときに負になったところで切るべきで、逆に負になったところで切らないのは最適ではないことが分かるから、
c_i = a_1 + 2 * a_2 + ....+ 2^(i-1) * a_i
とすると、Xが右端の階段は
c_Wはc_Xよりも大きく、かつそのようなWの中で一番右の値(Yとする)が左端になることが分かる。(ないときはL)
よって、c_iをソートし、ダブリングをすると解ける。 O((N+Q) log N)くらい?
