11

先週、Facebook ハッカーカップのラウンド 1b に参加しました。

問題の 1 つは、基本的にヨセフス問題でした。

以前にジョセフス問題を離散数学の問題として研究したことがあるので、基本的に再帰を取得する方法を理解しています。

f(n,k) = (f(n-1,k) + k) mod n, with f(1,k) = 0

しかし、n の最大値が 10^12 だったので、Facebook Hacker Cup ではうまくいきませんでした。k の最大値は 10^4 でした。

ウィキペディアでは、k が小さく、n が大きい場合のアプローチについて言及しています。基本的に、1 回のラウンドから人を削除してから、番号を付け直します。しかし、それはあまり説明されておらず、なぜ再番号付けが機能するのか理解できません。

ソリューションのサンプル作業ソース コードを見ましたが、最後の部分がまだわかりません。

long long joseph (long long n,long long k) {
    if (n==1LL) return 0LL;
    if (k==1LL) return n-1LL;
    if (k>n) return (joseph(n-1LL,k)+k)%n;
    long long cnt=n/k;
    long long res=joseph(n-cnt,k);
    res-=n%k;
    if (res<0LL) res+=n;
    else res+=res/(k-1LL);
    return res;
}

私が本当に理解していないのは、res-=n%k（およびその後の行）から始まる部分です。それが結果を調整する方法であることをどのように導き出しますか?

誰かがこれがどのように導出されたかの背後にある理由を示すことができますか? またはそれを派生させるリンクですか？(UVA やトップコーダー フォーラムに関する情報は見つかりませんでした)

4

1 に答える 1

4

そうです、私はそれをクラックしたと思います。

n = 10、k=3で反復がどのように行われるかを見てみましょう。

0 1 2 3 4 5 6 7 8 9    n=10,k=3
1 2   3 4   5 6   0    n=7,k=3

2番目の反復の要素が最初の反復にどのようにマップされるかを観察しますn%k。円が折り返されるため、それらはによって転置されます。そのため、を減算して結果を修正します10%3。2行目の数字は、のグループで表示されるk-1ため、。による修正res/(k-1)です。

もう1つのケースは、反復に沿ってさらにヒットします

0 1 2 3 4     n=5,k=3
2 3   0 1     n=4,k=3

ここで、j（4,3）は0を返しますが、これを修正5%3すると-2になります。これは、2番目の行の結果が最後のグループにある場合にのみ発生します。その場合、結果に追加nすると、元のインデックスが得られます。

于 2011-01-30T22:37:58.433 に答える