SRM508 Div1Easy DivideAndShift

22 Aug 2018, 16:30

SRM / Brute Force

URL

$\sim N</annotation></semantics></math>$ のスロットが1列に並んでいる．プレイヤーは常にスロット $1$ の中身しか取得することができない．ゲームの目的は，開始時にスロット $M$ にあった中身を取得することである．

スロットには2通りの操作を行うことが出来る．

Divide
- $N$ を割り切れる素数 $p$ を選びスロットを $encoding="application/x-tex">[1,\frac{N}{p}],[\frac{N}{p}+1,\frac{2N}{p}],…</annotation></semantics></math>$ に分割する．この内，目的のスロットを含む部分列のみを保持する．その後， $encoding="application/x-tex">N←\frac{N}{p}</annotation></semantics></math>$ とし，スロットの番号を $\sim \frac{N}{p}</annotation></semantics></math>$ に振り直す．
Shift
- スロットを左/右にシフトする．シフトするとスロット番号が $- 1 / + 1$ だけ変化する．スロット $0$ は $N$ に， $N + 1$ は $1$ に別途移動する．

最低で何回操作をすれば目的を達成できるか．

全然できなかった．調べたら「DivideとShiftの操作は可換」ということがわかって（証明は知らない）そこからはノーヒントで行けた．これで250ptなんだ…

Shiftは数えるだけなので先にDivideを行う．Divideのやり方は高々、2^(素因数の数)だから全列挙してやればいい．あとは各々についてShiftの回数を求める．

のんきに数えてたらTLEしたので，剰余で考える必要があるのだが，これが難しかった．右にShiftする場合の式がよくわからなくて，手元のサンプルと帳尻を合わせるように書いたら通った（最悪）

[展開する]