Joshephus or MamakoDate Sequence EASY

anarchy golf C Groovy js

Joshephus or MamakoDate Sequence EASY はなかなか面白い問題だった。C トップのinaniwa さんの解は少し解読しようとしたけど、ちょっとわからないな。301 さんの解も同じアルゴリズムのようだ。いずれにせよ、配列になんらかデータを蓄積するのではなく、一つ一つの値を計算している。以下の部分だ。

for(t=n*i;t>m;t/=n-1)t=n*(t-m)-1

意味不明。
私の解は、111B@C、105B@js、110B@Groovy とも最終的にはすべて同じアルゴリズムで解いた。配列を用いるが、すでに使った数字をチェックするのではなく、使った数字を取り除いたものを後ろに追加していき、その配列を、入力の n おきに出力していくという方法だ。たとえば、例として、m=7, n=3 とすると以下のようになる。

1 2 3 4 5 6 7
1 2 3 4 5 6 7 1
1 2 3 4 5 6 7 1 2
                                            // 3 を出力
1 2 3 4 5 6 7 1 2 4
1 2 3 4 5 6 7 1 2 4 5
                                            // 6 を出力
1 2 3 4 5 6 7 1 2 4 5 7
1 2 3 4 5 6 7 1 2 4 5 7 1
                                            // 2 を出力
1 2 3 4 5 6 7 1 2 4 5 7 1 4
1 2 3 4 5 6 7 1 2 4 5 7 1 4 5
                                            // 7 を出力
1 2 3 4 5 6 7 1 2 4 5 7 1 4 5 1
1 2 3 4 5 6 7 1 2 4 5 7 1 4 5 1 4
                                            // 5 を出力
1 2 3 4 5 6 7 1 2 4 5 7 1 4 5 1 4 1
1 2 3 4 5 6 7 1 2 4 5 7 1 4 5 1 4 1 4
                                            // 1 を出力
1 2 3 4 5 6 7 1 2 4 5 7 1 4 5 1 4 1 4 4
1 2 3 4 5 6 7 1 2 4 5 7 1 4 5 1 4 1 4 4 4
                                            // 4 を出力

結構縮んで、111B@C までいったが、トップに 1B 及ばず。
問題終了後、問題文で参照されていた文献を見てみた。すると、以下のような再帰的な定義が出ていた。

j(m,n,i)=(n+j(m-1,n,i-1))%m     // i>1
j(m,n,1)=(n-1)%m                // i==1

m, n は本問と同じ意味。i は、i 番目の出力を表す。
これをそのまま以下の通り実装してみたが、あまり縮まず 122B どまり（頑張ればもう少し縮むかも。深追いはしていない）。

n;
j(i,m){return(--i?n+j(i,m-1):n-1)%m;}
main(i,m){
    for(;i++<m||~scanf("%d%d",&m,&n,i=1);)printf(i/m?"%d\n":"%d ",j(i,m)+1);
}

単純な再帰的定義なので、初期値から逆にループして値を求めるように書き換えたら縮んで記録を更新（108B@C）できた。以下の通り。

i,d;main(c,m,n){
    for(;d=i=i?:scanf("%d%d",&m,&n)/2*m;printf(--i?"%d ":"%d\n",1-c))
        for(c=1;c=(c-n)%d,d++<m;);
}

構造は前述の inaniwa さんの解に似ているが、計算式の部分はかなり異なっている。というのは、参照した文献にあった、再帰的定義では、MOD 演算(%)が現れるからだ。inaniwa さんの計算式にはそれがない。考え方が違うのだと思う。
それにしても、事前にきちんと文献を読めばよかったな。残念。
なお、js も同様に短くなったので submit しておいた（102B@js）。