ACの二完でした。Bは惜しくなかった。Dの方が惜しかったのかも？（ACしていないのではっきりしたことは言えないが）
B. Up the Strip
DP[x]がどこから足されるかを考える。
引き算については、DP[1]～DP[x-1]の和を足し込めば良い。これは累積和でOK。
割り算について。まず思いつくのは、$\sqrt{x}$で分ける方法だと思う。
DP[x/1], DP[x/2], ... , DP[x/$\sqrt{x}$]はそのまま計算、$\sqrt{x}$より大きい数で割る場合は、それぞれの商について何個ずつかを求める。
コンテスト中はこの方法しか思いつかなかった。
これで、Div. 2の部分点はもらえるが、Div. 1では点数にならない。
約数に注目するのが重要。
・(x-1)/yとx/yの整数部分の値が変わるのは、x/yが割り切れるとき
ということに注目する。これを考えると、xの約数についてだけ、変化分がどれだけ増加するかを調べていけば良い、と分かる。
が、これでも間に合わない（MLEになるはず）。
そこで、発想の逆転。約数を考えていたところを倍数で処理できないか考える。
DP[x-1]だった増加量がDP[x]に増えるのは、xの倍数のところである。それを利用し、xの倍数のところに、その増加量の変化を書き込んでいく。これなら、MLEを回避できる。
0 件のコメント:
コメントを投稿