Codeforces Round #667を埋めた感想文
登録したので適当に過去問をといた。 https://codeforces.com/contest/1409
総括
英語に慣れてない。ちょっと実装がだるいとすぐ萎える。
Problem A
AをBに変更するまでの最小操作回数を出力する。操作は以下。
- 1以上10以下の好きなxを決めて、AをA+xまたはA-xに変更する
考えたこと
- 制約から、一発で求めたい。
- AをBにするのもBをAにするのも同じこと。とにかくこの2数の差を埋めればいい。
- 操作は基本的にx=10としたい。それが最も効率的。
- Bとの差が10以下になった時に初めて10未満を使えばいい。
- AとBの差を10で割ったらだいたい近い答えが得られそう。
- 余りが出る時はxを10未満の値でとって余分に1回操作する。
- ならば、AとBの差の絶対値を10で割って切り上げたものが答え。
- 大小関係が面倒なので、実装時はd=abs(A-B)としてそれを10で割って切り上げればいい。
ひとこと
最初、連続して同じxを選べないものと思っていた（mayをmustと勘違いしていた）。なお、この場合は19で割った商とあまりを使って解ける（はず）。
Problem B
a,b,x,y,nが与えられる。n回まで、aかbの好きなほうを-1できる。ただし、aはx以上、bはy以上でなければならない。a×bを最小化するように操作したときのa×bの値はいくらか。
考えたこと
- 制約から、一発で求めたい。
- 操作すれば必ずa×bは小さくなる。
- だから操作は可能な限り行ったほうがよい。以後、可能な限り行うものとして考える。
- 同じ回数操作を行うとき、どのように操作しても操作後のaとbの和は結局同じ値になる。
- 微積の授業で確かめたが、a+bが固定されているとき、a×bはa=bの時が最大。
- 逆に、最小化したいならaとbはなるべく偏らせるべき。
- とりあえずどちらかをできるだけ小さくして、操作回数が余っていればもう片方を小さくするのがよさそう。
- どちらから手を付けるべきか？
- わからないが、わからないなら両方試せばよい。
Problem C
以下の条件を満たす数列を構築せよ。制約下で可能である。複数ある場合、最大の要素が最小のものを出力せよ。
- n要素。
- 1以上1e9以下の整数からなる。
- xとyを含む。x<y
- 昇順ソートすると等差数列になる。
考えたこと
- 最初から等差数列として考えてよさそう。
- 公差はいくつであるべきか？
- y-xを割り切る整数であるべき。
- 公差はこのうち最小のもの（=1）でよいか？
- 否。要素数によってはxとyを両方含めることができない。
- 公差の候補は少なく、全部試せる。試す。
- 構築時のことを考える。最大要素と公差さえわかっていれば、全要素を復元可能。
- 公差wでxとyを含むために必要な要素数は((y-x)/w+1)であり、これ未満なら却下。
- そうでない場合、最大要素を計算し、最小の最大要素とその時の公差を更新していく。
- x以上y以下が((y-x)/w+1)要素、x未満は(x-1)/w要素。max(nからこれらを引いた分,0)だけyより大きい要素が存在する。
- 最大要素は残りa要素としてy+a×w。
- ベストな最大要素とその時の公差をもとに数列を復元して終わり。
Problem D
数nとsが与えられる。nの桁和をs以下にするためには最小でいくつ足せばよいか。
考えたこと
- まずは非本質ケースを排除する。最初から桁和がs以下なら0を吐いて終了。
- 初めて桁和がs以下になる数と、元の数の差が答え。
- 初めて桁和がs以下になる数を求めればよい。
- 1足すと、たいてい桁和は増える。
- 例外は、繰り上がるとき（9→10になると、桁和は9→1に減少）。
- おそらく、桁和がs以下になるのは繰り上がりが発生した瞬間。
- よって、求める数は...xxx000...と表せるものと予想できる。
- 上のほうの桁はなるべく変更したくない。下のほうの桁で片づけたい。
- 上の桁から見て、まずった時にどうにかする。
- 文字列で扱ったほうがよさそう。
- 文字列化するだけでなく、繰り上がりを見据えて先頭に0を付けておく。
- 桁和を更新しつつ上の桁から見る。
- 桁和<sならばそのまま。
- 桁和>=sの場合、今見ている桁の上の桁を+1して今見ている桁とその下は0で埋める。
- 「上の桁を+1」した結果、繰り上がったらどうすればよいか？
- さらに上の桁を+1する。繰り上がりがなくなるまでやる。先頭は0なので終わる。
- あとは数字に戻して元の数との差を出力。
ひとこと
桁和>=sについて。桁和==sで、以下全部0埋めされているようなケースの場合バグる。しかしそのケースは最初に「非本質」として排除済みなのでうまくいく。
Problem E
x軸が水平方向、y軸が重力方向の二次元座標上にn個の点があり、これらが降ってくる。好きな整数座標(x1,y1)と(x2,y2)を選び、それぞれ(x1+k,y1)、(x2+k,y2)にかけて長さkの水平な駅をつくる。これに引っかかった点は止まる。最大でいくつの点を止められるか。
考えたこと
- yは無視して一次元で考えてよい。低い位置に設置すれば止まる。
- 「[x1,x1+k]または[x2,x2+k]にある点」の個数を最大化すればよい。
- 閉区間。絶対めんどくさい。
- 座標圧縮いりそう。めんどくさい。
- 点を最も多く拾えるx1を決めた後その点を全部排除し、同様にx2を決める方法は正しいか？
- 否。k=1で座標(0,1,2,3)に(1,3,3,1)個の点がある場合、[0,1][2,3]で全部回収できるがx1=[1,2]としてしまうと挽回できない。
- したがってx1とx2は同時に決める必要がある。
- 左区間と右区間は重ならないほうがよい。得をしない場合があるが、損はしない。
- 一旦計算量を無視すると、ある境界（イメージとして境界はi+0.5にある）から左を左区間の守備範囲、右を右区間の守備範囲として境界を全探索して、各境界について左右の区間がそれぞれ拾える点数の最大値の和、の最大が答え。
- 各範囲いちいち求めるのは時間がかかる。
- 小さい範囲での答えを使って、それより少し大きい範囲の答えがわかりそう。
- [0,x]内で区間[p,p+k]をとるのが最適なとき、[0,x+α]内での最大数は[p,p+k]と[x+α-k, x+α]で拾える点数の大きいほう。
- という更新を左右両方に対してしていくことで、効率的に各守備範囲で拾える点の最大値が求まる。
- 境界に注目したいので、x1+k（左区間の右端）の位置とx2（右区間の左端）の位置を基準に全探索。
- 座標圧縮した配列での区間和を（しかも閉区間）累積和使って求めるのめんどくさい。
- めんどくさいめんどくさいめんどくさいめんどくさい
ひとこと
すごいバグった。上位層は超簡潔に書いててすごい。最適化のプロ。
Problem F
長さnの文字列sと2文字の文字列t、整数kが与えられる。k回までsのうち1文字を変更可能。sに含まれる部分文字列tを最大で何個にできるか
考えたこと
- DPだろうけどわかんなーい
解説AC後に考えたこと
- 解説のDP、むずくね？
- t[0]==t[1]の場合は簡単そう。
- この場合、可能な限り[0]に変更して、t[0]の個数xに対してx(x-1)/2。
- そうすると、ちょっとだけ簡単になる（DPの方針がわかっている前提ならば）。
