TopCoder SRM619: ChooseTheBestOne

有名なヨセフスの問題のアレンジ版のため、ヨセフス数を求める再帰アルゴリズムを改造すると \(O(N)\) で解ける。

愚直にシミューレートした \(O(N^2)\) 解法でも通る。

public class ChooseTheBestOne {
    int dfs(int N, int pos, long k = 1) {
        if (N == 1) return 0;
        long target = (pos + k * k * k) % N;
        var p = dfs(N - 1, (int)target-1, k + 1);
        if (p >= target) p++;
        return p;
    }

    public int countNumber(int N) {
        return dfs(N, -1) + 1;
    }
}