クロッシング・ワード

「クロッシング・ワード」問題

締め切りが 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;
    }

}