AOJ 2707 - 監獄

問題
提出コード

解法

まず、答えが仮にxであったとします。そのとき、xは1回目の操作でどこにいくか、ということを考えてみると、
x - 1 - x/k
となります。k、2k、3k…の人が処刑されるので、その人数分引けばいい、ということです。
次に、後ろから考えます。
1回目の操作について、処刑後から処刑前を復元する方法について調べてみます。
今の数列が1,2,...k-1,k+1,k+2,...2k-1...であったとすると、初期状態はもちろん
0,1,2,...k-1,k,k+1,k+2,...2k-1,2k,2k+1,...となっているはずです。
このことを踏まえると、

• 0番目の人がいる関係で、必ず番号が1増える

• 加えて、現在の列にk-1人いるごとに番号が1増える
  となります。
  ということで、現在pの番号がついている人は、1つ前の処刑の段階では、
  p + 1 + p / (k - 1)
  という番号であったことになります。
  あとはこれを(処刑の回数-1)回だけ繰り返せば答えがもとまります。