A面ダイス問題(2)
A面ダイス問題の考え方最終版。
Nの十の桁をq、一の桁をrとする。
- q≦rのとき(ex.11,12,36,49)：
ダイス1,2双方が文字セット"12...q"を含まねばならない。(N以下の11,22,33,...の表現ため。ただしq=0の場合は空のセットとする。)
さらに、9-q文字からなる文字セット"st...9"(s=q+1,t=q+2,...)を両方のダイスで分け合う必要がある。(ただし1≦N＜9のときは9のかわりにNとする。)
最大面数A最小、という題意から、後者の文字セットの分け方はceil((9-v)/2)要素v.s.floor((9-v)/2)要素に限られる。(両方ceil()な分け方も題意を満たすが、トリビアルな上に組み合わせが増えるだけなのでここでは無視する。) - q＞rのとき(ex.10,21,31,55)：
ダイス1,2双方が文字セット"12...u"(u=q-1)を含まねばならない。(N未満の11,22,33,...の表現のため。ただし、u=0の場合は空のセットとする)
さらに9-u(=10-q)文字からなる文字セット"st...9"(s=u+1,t=u+2,...)を両方のダイスで分け合う必要がある。(ただし1≦N＜9のときは9のかわりにNとする。)
最大面数A最小、という題意から、後者の文字セットの分け方はceil((9-v)/2)要素v.s.floor((9-v)/2)要素に限られる。(両方ceil()な分け方も題意を満たすが、同上で無視する。)
ただし、上記に加え、一方のダイスが"q"を含み、他方が"0..r"を含む必要がある。(さもないと、例えばq=3のとき、30〜Nが表現できない。)
場合分け酷ス＿|￣|○|||
あと、上記は必要条件を述べているにすぎず、十分性(1〜Nの表現可能性)は証明しきれていないがそれは置くとするっていうか見逃してください 人(´Д`;)
多分十分性も満たしてる…ハズ。
計算量を検討してみる。これはTLE 1秒の壁を破れるか？
昨日のアルゴリズムは、N=1〜99について、順列の列挙(3^10通り)×サイズNの篩処理を行うので、ループ回数は99×3^10×50=2.9E8回。うちのマシン(Pentium4 2.8 GHz)で、N=1〜99で8秒ぐらいかかる(TLEは満たせない)。一方、上述の考え方だと、N=1〜99について、9-qまたは10-q個のもの(10個以下)を、半分(奇数個の場合はほぼ半分)に分ける組み合わせを列挙する。ループ回数は、99×nCr≦99×252=24948回を越えない(n≦10,r=n div 2のケースなので)。これはいけそうだ…！
と思って大喜びでコードを書いたが nCr 部分がうまくいかず頓挫中、、(解の重複が除去できない&&コードが長い)。
