A面ダイス問題(1) - 思うだけで学ばない日記 2.0

『Short Coding』発売記念オフ会用問題 (id:yaneuraoさん出題)に挑戦。

まずは力ずくで解を求めるコードを書いてみる。N≦9のときは置くとして、先にメジャーなN≧10のケースを考える。この場合、ダイス1,2により1〜Nを表現する過程で、1の桁は0〜9の範囲をフルスイングするため、0〜9は必ずダイス1,2のどちらか(あるいは両方)の面に刻まれていないといけない。0〜9という10個の要素それぞれについて、ダイス1に刻むか、ダイス2に刻むか、両方に刻むか、の3通りなので、列挙すべき順列の数は3^10通り。で、題意は2つのダイスを最小の面数にまとめることなので、次のアルゴリズムになる。

上記3^10通りの順列を全部列挙し、個々の順列ごとに、以下の操作を実施
1. ダイス1,2に刻まれることが確定した数字の数を数える(それぞれc1, c2とおく)
2. 1〜Nを表現可能かチェック(エラトステネスの篩風に、表現できた数を消しこんでいく)
3. 消されなかった数の個数を数える(wとおく)
4. ダイス1,2の合計面数=c1+c2+w、ダイス1の面数≧c1、ダイス2の面数≧c2、という制約条件のもとで、ダイス1,2の面数をできるだけ均衡させ、その面数を求める(xとおく)
上記列挙過程の中で、最小のxを求める

こうして求められたxの最小値が、答え(A)となる。

xを求めるロジックはべつにややこしい探索とかではなくて、次のif文一発でいい。

      if(c[1]>c[2]){      /*未割り当ての数字をダイス1,2に割り振る*/
        t=c[1]-c[2];
        if(w>=t){
          x=c[1]+(w-t+1)/2;
        }else{
          x=c[1];
        }
      }else{
        t=c[2]-c[1];
        if(w>=t){
          x=c[2]+(w-t+1)/2;
        }else{
          x=c[2];
        }
      }

デバッグのため、具体的な割り当ても表示さしてみた(N=31のケースのみ抜粋)。上から下に順列の列挙が進行していき、xがその時点の最小値に等しくなったときだけ表示させている。行頭の二つの括弧が、それぞれダイス1,2の面の内容を表す。

(1 2 3 4 5 6 7 8 9 ),(0 1 2 ) p=0x5557E,A=9,c[1]=9,c[2]=3,w=0
(0 1 2 4 5 6 7 8 9 ),(1 2 3 ) p=0x555BD,A=9,c[1]=9,c[2]=3,w=0
(0 1 2 4 5 6 7 8 9 ),(0 1 2 3 ) p=0x555BF,A=9,c[1]=9,c[2]=4,w=0
(1 2 3 4 5 6 7 8 9 ),(0 1 2 3 ) p=0x555FE,A=9,c[1]=9,c[2]=4,w=0
(1 2 3 5 6 7 8 9 ),(0 1 2 4 ) p=0x5567E,A=8,c[1]=8,c[2]=4,w=0
(0 1 2 5 6 7 8 9 ),(1 2 3 4 ) p=0x556BD,A=8,c[1]=8,c[2]=4,w=0
(0 1 2 5 6 7 8 9 ),(0 1 2 3 4 ) p=0x556BF,A=8,c[1]=8,c[2]=5,w=0
(1 2 3 5 6 7 8 9 ),(0 1 2 3 4 ) p=0x556FE,A=8,c[1]=8,c[2]=5,w=0
(1 2 3 4 6 7 8 9 ),(0 1 2 5 ) p=0x5597E,A=8,c[1]=8,c[2]=4,w=0
(0 1 2 4 6 7 8 9 ),(1 2 3 5 ) p=0x559BD,A=8,c[1]=8,c[2]=4,w=0
(0 1 2 4 6 7 8 9 ),(0 1 2 3 5 ) p=0x559BF,A=8,c[1]=8,c[2]=5,w=0
(1 2 3 4 6 7 8 9 ),(0 1 2 3 5 ) p=0x559FE,A=8,c[1]=8,c[2]=5,w=0
(1 2 3 6 7 8 9 ),(0 1 2 4 5 ) p=0x55A7E,A=7,c[1]=7,c[2]=5,w=0
(0 1 2 6 7 8 9 ),(1 2 3 4 5 ) p=0x55ABD,A=7,c[1]=7,c[2]=5,w=0
(0 1 2 6 7 8 9 ),(0 1 2 3 4 5 ) p=0x55ABF,A=7,c[1]=7,c[2]=6,w=0
(1 2 3 6 7 8 9 ),(0 1 2 3 4 5 ) p=0x55AFE,A=7,c[1]=7,c[2]=6,w=0
(1 2 3 5 7 8 9 ),(0 1 2 4 6 ) p=0x5667E,A=7,c[1]=7,c[2]=5,w=0
(0 1 2 5 7 8 9 ),(1 2 3 4 6 ) p=0x566BD,A=7,c[1]=7,c[2]=5,w=0
(0 1 2 5 7 8 9 ),(0 1 2 3 4 6 ) p=0x566BF,A=7,c[1]=7,c[2]=6,w=0
(1 2 3 5 7 8 9 ),(0 1 2 3 4 6 ) p=0x566FE,A=7,c[1]=7,c[2]=6,w=0
(1 2 3 4 7 8 9 ),(0 1 2 5 6 ) p=0x5697E,A=7,c[1]=7,c[2]=5,w=0
(0 1 2 4 7 8 9 ),(1 2 3 5 6 ) p=0x569BD,A=7,c[1]=7,c[2]=5,w=0
(0 1 2 4 7 8 9 ),(0 1 2 3 5 6 ) p=0x569BF,A=7,c[1]=7,c[2]=6,w=0
(1 2 3 4 7 8 9 ),(0 1 2 3 5 6 ) p=0x569FE,A=7,c[1]=7,c[2]=6,w=0
(1 2 3 7 8 9 ),(0 1 2 4 5 6 ) p=0x56A7E,A=6,c[1]=6,c[2]=6,w=0
(0 1 2 7 8 9 ),(1 2 3 4 5 6 ) p=0x56ABD,A=6,c[1]=6,c[2]=6,w=0
(1 2 3 6 8 9 ),(0 1 2 4 5 7 ) p=0x59A7E,A=6,c[1]=6,c[2]=6,w=0
(0 1 2 6 8 9 ),(1 2 3 4 5 7 ) p=0x59ABD,A=6,c[1]=6,c[2]=6,w=0
(1 2 3 5 8 9 ),(0 1 2 4 6 7 ) p=0x5A67E,A=6,c[1]=6,c[2]=6,w=0
(0 1 2 5 8 9 ),(1 2 3 4 6 7 ) p=0x5A6BD,A=6,c[1]=6,c[2]=6,w=0
(1 2 3 4 8 9 ),(0 1 2 5 6 7 ) p=0x5A97E,A=6,c[1]=6,c[2]=6,w=0
(0 1 2 4 8 9 ),(1 2 3 5 6 7 ) p=0x5A9BD,A=6,c[1]=6,c[2]=6,w=0
(1 2 3 6 7 9 ),(0 1 2 4 5 8 ) p=0x65A7E,A=6,c[1]=6,c[2]=6,w=0
(0 1 2 6 7 9 ),(1 2 3 4 5 8 ) p=0x65ABD,A=6,c[1]=6,c[2]=6,w=0
(1 2 3 5 7 9 ),(0 1 2 4 6 8 ) p=0x6667E,A=6,c[1]=6,c[2]=6,w=0
(0 1 2 5 7 9 ),(1 2 3 4 6 8 ) p=0x666BD,A=6,c[1]=6,c[2]=6,w=0
(1 2 3 4 7 9 ),(0 1 2 5 6 8 ) p=0x6697E,A=6,c[1]=6,c[2]=6,w=0
(0 1 2 4 7 9 ),(1 2 3 5 6 8 ) p=0x669BD,A=6,c[1]=6,c[2]=6,w=0
(1 2 3 5 6 9 ),(0 1 2 4 7 8 ) p=0x6967E,A=6,c[1]=6,c[2]=6,w=0
(0 1 2 5 6 9 ),(1 2 3 4 7 8 ) p=0x696BD,A=6,c[1]=6,c[2]=6,w=0
(1 2 3 4 6 9 ),(0 1 2 5 7 8 ) p=0x6997E,A=6,c[1]=6,c[2]=6,w=0
(0 1 2 4 6 9 ),(1 2 3 5 7 8 ) p=0x699BD,A=6,c[1]=6,c[2]=6,w=0
(1 2 3 4 5 9 ),(0 1 2 6 7 8 ) p=0x6A57E,A=6,c[1]=6,c[2]=6,w=0
(0 1 2 4 5 9 ),(1 2 3 6 7 8 ) p=0x6A5BD,A=6,c[1]=6,c[2]=6,w=0
N=31,A=6

A=6が答えで、組み合わせは上記20通り。

これを指標に、さっきのURLのコメント欄で追加出題された、TLE 1秒を満足する全解出力に挑戦汁、
(つづく)