問題の分析
次の条件を満たすさいころは何種類あるかを求めなさい。NとKは引数として与えられる。
・使っていい数字は1からN
・同じ数字を二度使ってはならない
・すべての面について反対側の面との合計が同じ値になる
・ある面と反対側の面の合計がK以下
・回転させて同じになるさいころは1種類とみなす
方針
合計がKとなる2つの数字の組み合わせは(K - 1) / 2の切り捨てとなります。
NがK-2以下の場合は組み合わせの数が減ります。
例えば、合計が7になる数字のペアを6までの数字を使って作ると1-6,2-5,3-4となりますが5までで作ると2-5,3-4となるためです。
それらのペアを使ったさいころはペアを3つ選ぶ組み合わせの数×2となります。
2をかけるのは6つの数字を使ってさいころを作ると、回転して重ね合わせられないさいころが2つできるためです。
ソースコード
最初、最初合計がKとなる2つの数字の組み合わせが3以上でないとさいころができないことを考慮するのを忘れていました。
こういう条件を漏らさず実装するのはなかなか難しいですね。
using System; using System.Collections.Generic; using System.Text; public class FoxMakingDiceEasy { public int theCount(int N, int K) { int cnt = 0; for (int i = K; i < N * 2; i++) { int pairs = (i - 1) / 2; if (N <= i - 2) pairs -= i - 1 - N; if(pairs >= 3) cnt += pairs * (pairs - 1) * (pairs - 2) / 6 * 2; } return cnt; } }