Educational Codeforces Round 66 (Rated for Div. 2)
ばｔｙ６あ
A. From Hero to Zero
問題：1を引く、kで割るを何回すればnを0にできるか求めよ
考察：
nが非常に大きいので、n%kを使い前者の操作を効率よくやります
3分でした。よい
B. Catch Overflow!
問題：3つの命令が与えられる。初期値0から最後にいくつになるか
命令：for 数字 endまでを数字の回数繰り返す
add 1を足す
end 直近のforの終了地点
実装：
forを与えられたとき再帰しました。
for以下の＋を回数分かけて今の値に足します。
オーバーフローに注意しましょう
C. Electrification
問題：n個の整数とkが与えられる。ある整数xについて、|ai-x|がｎ個あり、昇順に並べたとき、k+1番目をfk(x)とする。最小化せよ
考察：
x-fk(x)~x+fk(x)にk+1個の値があればよいです。
したがってai~ai+kが区間になり、この中央値がxになります。
n-k通り探索すれば間に合います。
はじめ二分探索を考えたのもあって時間かかっちゃいました。ちょっと反省
D. Array Splitting
問題：n個の整数と整数kが与えられる。k個の連続する部分列に分割する。aiがj番目の部分列にあるとき、コストはai*jである。コストの和を最大化せよ
考察：
出ました、コストを最大化するよくわからない問題。普通最小化だと思います。
全てのaiについて1回はコストに寄与します。
2個目以降の部分列では2回以上寄与します。
このように考えていくと、後ろから見たときの累積和をk個足す問題になります。
これを最大化すればよいので、n個列挙して、ソートすればよいです。
7分くらいでした。結構はやかったとおもいます。うれしいね
E. Minimal Segment Cover
問題：区間がｎ個与えられる。ｍ個のクエリに答えよ
考察：マージして二分探索しましたが、嘘でした
解説：
座標がある程度小さめなので全探索から考えます。
ある座標より左側からスタートしたとき、一番右にいける1つの区間を見つけます。
xからスタートして、この移動を何回繰り返せばy以上になるかがクエリの回答です。
移動をする際に、動いた点ごとに、終着点と距離を記録しておきます。
これによって最大でも座標分しか調べないため間に合います。
移動不可能なときとかの実装が甘かったので、今度通します。
F. The Number of Subpermutations
問題：ｎ個の整数列の連続する部分列で、１～長さが1回ずつ含まれるものはいくつあるか。
考察：１を起点に左右に考えましたが、どちらからも要素を取るパターンに対応できなくて破滅しました。
そのうち解説読んで通します。
感想
早解きがうまくいって、200位台と良い順位が出せました。
リサブがなかったのもよかったですね。
その一方でEFが考察すらうまくいかなかったのはよくなかったです。
Eは解説読んでも実装に苦労しているので、2000点の壁を感じます。
がんばろー
