「クロッシング・ワード」問題
締め切りが 2017/04/06 10:00 AM なので,その 1 分後に投稿されるように予約
設問
クロスワードの盤面では、格子状のマス目に白マスまたは黒マスを配置します。
以下は、縦 3 個×横 4 個のマス目に白マス・黒マスを配置する例です。
白マス・黒マスの配置には次のルールがあります。
黒マスによって白マスの領域が分断されてはならない。
黒マスが縦・横に連続してはならない。
例えば以下は不適切な配置例です。
自然数 n に対して、縦 3 個 × 横 n 個のマス目に白マス・黒マスを配置する場合の数を F(n) と定義します。
例えば F(1)=4,F(2)=11 です。以下に n=2 の場合の配置の仕方を示します。
同様に、F(3)=39,F(4)=121,F(5)=387 となることが確かめられます。
標準入力から、自然数 n(1 ≦ n ≦ 10^8)が与えられます。
標準出力に F(n) を 10^6 で割った余りを出力するプログラムを書いてください。
===========================
以下のような単純なプログラムを書いて,n が小さいときの解を求める
pentacombinations = function(p) { # 列のパターンの組み合わせ 5^n 通り
retval = matrix(0, nrow = 5^p, ncol = p)
for (i in 1:p) {
retval[, i] = rep(c(rep(0, (5^p/5^i)), rep(1, (5^p/5^i)), rep(2, (5^p/5^i)), rep(3, (5^p/5^i)), rep(4, (5^p/5^i))), length = 5^p)
}
retval + 1
}
check = function(x) { # クロスワード配列で,縦横に黒が並んだり,白を黒が分断したりという場合には false,そうでない場合は true を返す
n = ncol(x)
if (ncol(x) > 1) {
if (x[2, 1] + x[3, 2] == 2 || x[2, 1] + x[1, 2] == 2 ||
x[2, n] + x[3, n-1] == 2 || x[2, n] + x[1, n-1] == 2) {
return(FALSE)
}
for (j in 1:3) {
for (i in 2:ncol(x) - 1) {
if (x[j, i] + x[j, i + 1] == 2)
return(FALSE)
}
}
for (i in 2:ncol(x) - 1) {
if (x[1, i] + x[2, i + 1] + x[3, i] == 3 || x[1, i + 1] + x[2, i] + x[3, i + 1] == 3)
return(FALSE)
}
}
if (ncol(x) > 2) {
for (i in 3:ncol(x) - 2) {
if (x[1, i] + x[2, i + 1] + x[3, i + 2] == 3 || x[1, i + 2] + x[2, i + 1] + x[3, i] == 3)
return(FALSE)
if (x[3, i] + x[2, i+1] + x[3, i+2] == 3 || x[1, i] +x[2, i+1] + x[1, i+2] == 3)
return(FALSE)
}
}
return(TRUE)
}
F = function(n) {
pattern = matrix(c(0, 0, 0, 0, 0, 1, 0, 1, 0, 1, 0, 0, 1, 0, 1), 3) # 縦方向に黒が続かないパターンは 8 通りのうちの 5 通り
a = pentacombinations(n)
b = matrix(0, 3, n)
count = 0
for (i in seq_len(nrow(a))) { # クロスワード配列を生成して
x = b
for (j in seq_len(n)) {
x[, j] = pattern[, a[i, j]]
}
count = count + check(x) # 妥当なクロスワード配列をカウントする
}
count
}
このプログラムにより以下の解を得る
n F(n)
1 5
2 11
3 39
4 121
5 387
6 1237
7 3955
8 12637
9 40387
10 129069
これ以上の n, F(n) を求めるのは時間が掛かるので,漸化式があるかどうかをチェックする
a1 a2 a3 a4 a5 a6
5 11 39 121 387 1237
11 39 121 387 1237 3955
39 121 387 1237 3955 12637
121 387 1237 3955 12637 40387
387 1237 3955 12637 40387 129069
1237 3955 12637 40387 129069
3955 12637 40387 129069
12637 40387 129069
40387 129069
129069
a1, a2 を使って a3 を求められるか lm(a3 ~ 0+a1+a2)
a1, a2, a3 を使って a4 を求められるか lm(a4 ~ 0+a1+a2+a3)
:
> a = lm(a6~0+a2+a3+a4+a5, d); summary(a)
Call:
lm(formula = a6 ~ 0 + a2 + a3 + a4 + a5, data = d)
Residuals:
1 2 3 4 5
-1.245e-12 -1.245e-12 -1.868e-12 -1.245e-12 6.226e-13
Coefficients:
Estimate Std. Error t value Pr(>|t|)
a2 2.000e+00 2.590e-12 7.722e+11 8.24e-13
a3 2.000e+00 3.053e-12 6.550e+11 9.72e-13
a4 3.000e+00 3.017e-12 9.945e+11 6.40e-13
a5 2.000e+00 1.109e-12 1.804e+12 3.53e-13
Residual standard error: 2.92e-12 on 1 degrees of freedom
Multiple R-squared: 1, Adjusted R-squared: 1
F-statistic: 5.413e+32 on 4 and 1 DF, p-value: < 2.2e-16
> predict(a)
警告メッセージ:
summary.lm(a) で: essentially perfect fit: summary may be unreliable
1 2 3 4 5
1237 3955 12637 40387 129069
これで,
a[2] = 11
a[3] = 39
a[4] = 121
a[5] 387
i >= 6 のときは
a[i] = 2*a[i-4]+2*a[i-3]+3*a[i-42]+2*a[i-1]
と予想がつく
なお,F(1) は,上のプログラムの 5 ではなく,実際は □□□,■□□,□□■,■□■ の4個なんだけど(特別なのかな??)
以下のプログラムでは F(1) = 3 として,解を求める。
f = function(n) {
a = integer(n)
a[1] = 3
a[2] = 11
a[3] = 39
a[4] = 121
for (i in 5:n) {
a[i] = (2*(a[i-4]+a[i-3]+a[i-1])+3*a[i-2]) %% 1e6
}
cat(a[n])
}
により F(9978) までは制限時間 1 秒以内で求められたが,F(70013454) 時間オーバー
そこで,Java で書いて,すべて OK ということになった。めでたしめでたし。
import java.util.Scanner;
public class crossingWord {
public static void main(String[] args) {
if (false) {
// System.out.println(f(6)); // 1237
// System.out.println(f(7)); // 3955
// System.out.println(f(12)); // 318221
// System.out.println(f(100)); // 193677
// System.out.println(f(5190)); // 461261
// System.out.println(f(9978)); // 464781
// System.out.println(f(70013454)); // 184013
// System.out.println(f(99999991)); // 885187
} else {
Scanner cin = new Scanner(System.in);
String line;
line = cin.nextLine();
int n = Integer.parseInt(line);
System.out.println(f(n));
}
}
static int f(int n) {
int a1, a2, a3, a4, a5 = 0, i;
a1 = 3;
a2 = 11;
a3 = 39;
a4 = 121;
for (i = 5; n >= i; i++) {
a5 = (2 * (a1 + a2 + a4) + 3 * a3) % 1000000;
a1 = a2;
a2 = a3;
a3 = a4;
a4 = a5;
}
return a5;
}
}
※コメント投稿者のブログIDはブログ作成者のみに通知されます