SRM526.5 Div1 Easy - MagicCandy
問題
最初キャンディがn個あり、左から昇順に1-nの番号が書かれている
キャンディが1つだけになるまで以下の操作を繰り返す
操作: 番号が平方数のキャンディを全て捨て、残ったキャンディにまた左から昇順に番号をつける
最後に残るキャンディは初期状態で何番か
解法
各操作で捨てるキャンディの個数はfloor(√n)個
番号を無視して個数についてのみシミュレーションすれば残り1個になるまでに必要な操作回数(=stとする)はわかる
その後キャンディが1個の状態から始めて、逆操作をst回行ってキャンディを増やしていくことを考える
すると最終的に求めたいものは「キャンディが1個ある状態から逆操作をst回行ったとき、"最初のキャンディ"の左側に何個のキャンディが追加されるか」と言い換えられる
逆操作で左側に何個キャンディが増えるかは二分探索で求められる
(x個ある状態で逆操作をするときは、k-√k = xとなるようなkの下限を求めればいい)
class MagicCandy { public: int whichOne(int n) { int st = 0, t = n, res = 1; while (t>1) t -= (int)sqrt(t), st++; while (st--) { int l = res, r = res*2+10; while (r-l>1) { int m = (l-r)/2 + r; if (m-(int)sqrt(m)<res) l = m; else r = m; } res = r; } return res; } };
あと↓はeditorialに「実はこんな簡単な解法もあるんだぜ😉(証明はできてない)」って書いてた解法
結構考えたけど証明はわからん
class MagicCandy { public: int whichOne(int n) { int res = n; while (n>1) { int s = (int)sqrt(n); if (s*s==n) res--; n -= s; } return res; } };
提出率86.64%正答率90.23%らしいけどこれ一般的にはそんなに簡単なのか?
500台のdiv1easyでダントツでわからなかった
なんでこんなに時間かかったのか自分でもわからん
逆操作って発想を典型として身に付けられてないせいか?🤔