ARC079D Decrease (Contestant ver.)
問題ページ
D - Decrease (Contestant ver.)
解法
n=50で考える。
k=0のとき 49 49 49 … 49 とする。
k=1のときは1回操作してこの数列になればよいので 99 48 48 … 48
k=2でも同様に 98 98 47 47 … 47
これを繰り返していくと、
k = 50 で 50 50 50 … 50
k = 100 で 51 51 51 … 51 となる。
したがって50回で周期が存在する。
speedrun001 FからL
F-見える数
読解が難しかったけど質問を見たらわかった。a[i]以前の最大の数がa[i]より小さければそのa[i]は見える。なので最大の数を保持して全てのa[i]を見ればできる。
G-あまり
10のa[i]の長さ乗を掛けたあとa[i]を足すを繰り返す。MODの取り忘れに注意。
H-LIS
LISでググってください。O(nlogn)で解ける。
I-和がNの区間
尺取り。今見ている区間の合計がn未満ならr+1, 今見ている区間の合計がnより大きければl+1する。
J-転倒数
転倒数でググってください。BITを使うとO(nlogn)で解ける。
K-辞書順で何番目？
a[i]の位置にa[i]未満の数が来るものの個数を合計すればいい。(a[i]より前で使っていないa[i]未満の数の個数) * (N-i-1)! を全てのa[i]について足し上げる。a[i]未満の数の個数はBITを使えばO(logN)で取得できる。
L-N回スワップ
1が1番目にいなかった場合、1と1番目の数を直接交換する以外1を1番目に持っていく方法はない。したがってiがi番目になければ適切な位置に持っていくのを繰り返すのが最適になる。 同じ位置について２回交換すれば元の位置関係に戻すことが出来、1回交換すると元の位置関係とは違うものになる。したがって最適な方法で交換したあとに、2の倍数回交換することができれば"YES"、そうでなければ"NO"となる。
第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の文字より小さければ置き換えていく。
