第3回 ドワンゴからの挑戦状 予選 D - ネタだけ食べたい寿司
dwacon2017-prelims.contest.atcoder.jp
n<=mであれば全ての寿司をネタだけ食べればいいのでm>nのときについて考える。
i番目までの寿司を食べるとすると、i番目をネタだけ食べ、1からi-1番目の中でネタだけ食べた時の幸福度の上昇が大きいものm-1個を選ぶのが最適な食べ方となる。そこで、i番目までの寿司でネタだけ食べた時の幸福度の上昇が上位m個のものを保持しておきたいのでpriority_queueを使う。
ukuku09コンテスト 001-photography
区間と言われたので累積和を取りたくなる。累積和をSで書くことにするとl番目の要素を区間の左端とするとき P+S[l-1] 以上のもっとも右にある要素の位置が分かればl番目が区間の左端のときの最適な区間が求まる。右端がO(1)かO(logn)くらいで求められればできそう。累積和がN以上のもっとも右にある要素の位置を持っておけばよさそう。累積和の値は大きすぎて配列でもつのは不可能なのでmapでもつ。
累積和を取ったあと後ろから見ていって、今まで見た中で一番大きい値であれば更新してmapに値を設定する。mapを使えば区間の左端を指定した時に二分探索すれば右端がO(logn)でわかるのでO(nlogn)でできる。
（嘘解法じゃないかちょっとこわい）
SRM716 div2 hard
概要
最初のm個がp[i] != iとなっているという条件を満たす長さn+mの順列pの個数をmod 10^9+7で求める。
解法
条件がなかったとしたら順列の個数は(n+m)!となる。次にm個のうち1個が条件を満たしていない個数を考える。m個の中から1個を選び、残りのm+n-1個の順列を取れば求まるため C(m, 1) * (m+n-1)!となり、これを引く。ここで、1点のみを固定して考えたとき重複してカウントしてしまっているパターンがある。m個の中から2個が条件を満たしていない場合の順列の個数は同様に考えると、C(m, 2) * (m+n-2)!となるため、これを足す。同様に重複して足した場合…と考えていくと、iが奇数の場合引いて、偶数の場合足している。つまり包除原理で解くことが出来る。
SRM 716 div2 med
概要
文字列sと文字列tが与えられる。sの各文字をtの文字で置き換えることができる。tの文字はそれぞれ1回ずつしか使用できない。書き換えた後の辞書順最大となるsを出力する。
解法
先に現れる文字を大きいものにしたほうが辞書順としては後のものになる。貪欲法でsの文字を最初から確かめていきtの文字より小さければ置き換えていく。
SRM 717 div2 easy
概要
要素が0か1の2次元配列tが与えられる。x[i] xor y[j] == t[i][j] となる要素が0か1の配列x、yを構成することが可能か判定する。与えられる配列のサイズは5×5以下。
解法
1行目(y[0])を0か1で固定すれば残りの列の数字(x[i])は一意に定まる。残りの行に対して正しければ"Nice"、正しくなければ"Not nice"を返す。
後から考えたらすべての行について同じものかbit反転したものかで判定できそう。
codeforces 415 div2 C
入力列をソートしておいても関係ないため、あらかじめソートされた入力列について考える。
また、関数F(a)は頂点の集合の最大値・最小値にのみ依存する。
例として数列8, 6, 5, 3, 2, 1が入力されたときを考える。
このときの答えは
(8-6)*1 + (8-5)*2 + (8-3)*4 + (8-2)*8 + (8-1)*16
+ (6-5)*2 + (6-3)*4 + (6-2)*8 + (6-1)*16
+ (5-3)*4 + (5-2)*8 + (5-1)*16
+ (3-2)*8 + (3-1)*16
+ (2-1)*16
= 8*(2^5-1) + 6*(2^4-1) + 5*(2^3-1) + 3*(2^2-1) + 2*(2^1-1)
-{1*(2^5-1) + 2*(2^4-1) + 3*(2^3-1) + 5*(2^2-1) + 6*(2^1-1) となる。最大値と最小値を固定したとき、その集合の個数は 1 + 2 + 4 + … + 2^(n-1) = (2^n)-1で求められる。よって、それぞれの数が最大値として使われる回数と最小値として使われる回数をO(1)で求めることができ、合計でO(n)で答えを求められる。オーバーフローに注意。
