裏 RjpWiki

文字通り,RjpWiki の裏を行きます
R プログラム コンピュータ・サイエンス 統計学

素数の日付を含む最長期間

2017年05月30日 | ブログラミング

素数の日付を含む最長期間

締め切りが 2017/05/30 10:00 AM なので,その 1 分後に投稿されるように予約

設問

日付をYYYYMMDD形式で表現し、8桁の数値としてみたとき、その値が素数かどうかを判定します。
1970年1月1日~2019年12月31日までの50年間のうち、素数がちょうど n 個含まれる期間で最長のものを考え、その日数を求めます。
なお、日数は両端の日付を含んで数えるものとします。
また、閏年は考慮するものとします。

例えば、n = 3 のとき、以下の青色で塗りつぶした範囲が最長になり、その日数は「202」です。

2015-04-11 : 素数
2015-04-12 : 開始日
2015-05-13 : 素数
2015-08-21 : 素数
2015-10-11 : 素数
2015-10-30 : 終了日
2015-10-31 : 素数

標準入力から n が与えられたとき、その最長日数を求め、標準出力に出力してください。
なお、n は1000以下の自然数とします。

【入出力サンプル】
標準入力
3

標準出力
202

-------------------------------------

R で書くと実行時間が1秒以内に収まらない

is.prime = function(n) {
    if (n %% 2 == 0) return(FALSE)
    else if(n %% 3 == 0) return(FALSE)
    maxitr = as.integer(sqrt(n))
    i = 1
    repeat {
        i = i+4
        if (i > maxitr) return(TRUE)
        else if (n %% i == 0) return(n == i)
        i = i+2
        if (i > maxitr) return(TRUE)
        else if (n %% i == 0) return(n == i)
    }
}

J.day = function(iy, jm, kd) {
    tmp = -(jm < 3)
    kd - 32075 + (1461 * (iy + 4800 + tmp))%/%4 + (367 * (jm - 2 - tmp * 12))%/%12 - (3 * ((iy + 4900 + tmp)%/%100))%/%4
}

date2 = function(jul) {
    l = jul + 68569
    n = (4 * l)%/%146097
    l = l - (146097 * n + 3)%/%4
    iy = (4000 * (l + 1))%/%1461001
    l = l - (1461 * iy)%/%4 + 31
    jm = (80 * l)%/%2447
    kd = l - (2447 * jm)%/%80
    l = jm%/%11
    jm = jm + 2 - 12 * l
    iy = 100 * (n - 49) + iy + l
    iy*10000+jm*100+kd
}

f = function(n) {
    begin = J.day(1970, 1, 1)
    end = J.day(2019, 12, 31)
    count = 0
    p.date = integer(1100)
    for (i in begin:end) {
        date = date2(i)
        if (is.prime(date)) {
            count = count+1
            p.date[count] = i
        }
    }
    Max = 0
    for (i in 1:(count-n-1)) {
        Max = max(Max, p.date[i+n+1]-p.date[i]-1)
    }
    cat(Max)
}
# f(scan(file("stdin", "r")))

# f(3) # 202
# f(10) # 413
# f(333) # 5771
# f(876) # 14708
# f(999) # 16724

awk で書いて少し速くなって,パスした

function isPrime(n,     maxitr, i) {
    if (n % 2 == 0) return 0
    else if(n % 3 == 0) return 0
    maxitr = int(sqrt(n))
    i = 1
    for (;;) {
        i = i+4
        if (i > maxitr) return 1
        else if (n % i == 0) return n == i
        i = i+2
        if (i > maxitr) return 1
        else if (n % i == 0) return n == i
    }
}

function Jday(iy, jm, kd,     tmp) {
    tmp = -(3 > jm)
    return kd - 32075 + int((1461 * (iy + 4800 + tmp))/4) + int((367 * (jm - 2 - tmp * 12))/12) - int((3 * (int((iy + 4900 + tmp)/100)))/4)
}

function revJday(jul,     l, n, iy, jm, kd) {
    l = jul + 68569
    n = int((4 * l)/146097)
    l = l - int((146097 * n + 3)/4)
    iy = int((4000 * (l + 1))/1461001)
    l = l - int((1461 * iy)/4) + 31
    jm = int((80 * l)/2447)
    kd = l - int((2447 * jm)/80)
    l = int(jm/11)
    jm = jm + 2 - 12 * l
    iy = 100 * (n - 49) + iy + l
    return iy*10000+jm*100+kd
}

function max(x, y) {
    return x >= y ? x : y
}

function f(n,     i, begin, end, count, primeDate, date, Max) {
    begin = Jday(1970, 1, 1)
    end = Jday(2019, 12, 31)
    count = 0
    for (i = begin; end >= i; i++) {
        date = revJday(i)
        if (isPrime(date)) {
        primeDate[++count] = i
        }
    }
    Max = 0
    for (i  = 1; count-n-1 >= i; i++) {
        Max = max(Max, primeDate[i+n+1]-primeDate[i]-1)
    }
    print Max
}
BEGIN {
f(3)
f(10)
f(333)
f(876)
f(999)
}

コメント

異なる整数で作る逆三角形

2017年05月23日 | ブログラミング

異なる整数で作る逆三角形


締め切りが 2017/05/23 10:00 AM なので,その 1 分後に投稿されるように予約

設問

n 個の自然数を1段目に並べます。
2段目は n-1 個の自然数を、3段目は n-2 個の自然数を、…というように、図のように逆三角形の形に並べます。
このとき、2段目以降の自然数はそれぞれ、その自然数の左上と右上の数の和とします。

n 段目までに登場するすべての数が重複しないように1段目の数を選んだ時、n 段目の数が最小になるものを求めます。
ただし、いずれの数も正の整数とします。
例えば、n = 3 のとき、以下の左のようにすると3が重複しています。
そこで、右のように配置すると重複はなく、3段目が最小である「8」となります。

標準入力から n が与えられたとき、標準出力に n 段目の値を出力してください。
なお、n は 1≦n≦7を満たす整数とします。

【入出力サンプル】
標準入力
3

標準出力
8

===================================

R で,簡単に書ける。が,n = 7 のときは 6 秒ほどかかるので,後で Java で書き換える。

F = function(n) {
    G = function(X) {
        for (k in 1:nrow(p)) {
            x = X[p[k,]]
            if (sum(x * weight) >= Min) {
                next
            }
            a[1, ] = x
            for (i in 2:n) {
                for (j in 1:(n-i+1)) {
                    a[i, j] = a[i - 1, j] + a[i - 1, j+1]
                }
            }
            result = a[n, 1]
            if (result < Min && length(unique(a[a!=0])) == elements) {
                Min = result
            }
        }
        Min
    }
    elements = n*(n+1)/2
    Min = 1e10
    library(e1071)
    p = permutations(n)
    a = matrix(0, n, n)
    x = combn(13, n)
    x = x[, x[1,] == 1]
    x = x[, x[2,] == 2]
    weight = choose(n-1, 0:(n-1))
    for (i in 1:ncol(x)) {
        Min = min(Min, G(x[,i]))
    }
    cat(Min)
}

> system.time(F(3)) # 8
8   ユーザ   システム       経過  
     0.043      0.002      0.045
> system.time(F(4)) # 20
20   ユーザ   システム       経過  
     0.004      0.000      0.003
> system.time(F(5)) # 43
43   ユーザ   システム       経過  
     0.066      0.003      0.068
> system.time(F(6)) # 98, 0.961 seq.
98   ユーザ   システム       経過  
     0.524      0.007      0.521
> system.time(F(7)) # 212, 6.095 sec.
212   ユーザ   システム       経過  
     5.822      0.052      5.850

計算処理時間対策のため,Java に移植。
あっという間に計算が終わる。

import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner cin = new Scanner(System.in);
        String line;
        line = cin.nextLine();
        int n = Integer.parseInt(line);
        System.out.println(F(n));
    }

    static int G(int Min, int n, int [] weight, int [] X, int [][] p) {
        int i, j, k;
        int result;
        int [] x = new int[n+1];
        int nrow = p.length;
        int [][] a = new int[n+1][n+1];
        int [] check = new int[n*(n+1)/2];
        int m;
        boolean dup;
        for (k = 1; k < nrow; k++) {
            int sum = 0;
            for (j = 1; n >= j; j++) {
                x[j] = X[p[k][j]];
                sum += x[j]*weight[j];
            }
            if (sum >= Min) continue;
            for (j = 1; n >= j; j++) {
                a[1][j] = x[j];
            }
            for (i = 2; n >= i; i++) {
                for (j = 1; n-i+1 >= j; j++) {
                    a[i][j] = a[i-1][j]+a[i-1][j+1];
                }
            }
            result = a[n][1];
            m = 0;
            for (i = 1; n >= i; i++) {
                for (j = 1; n-i+1 >= j; j++) {
                    check[m++] = a[i][j];
                }
            }
            dup = false;
            for (i = 0; i < check.length-1; i++) {
                for (j = i+1; j < check.length; j++) {
                    if (check[i] == check[j]) {
                        dup = true;
                        break;
                    }
                }
                if (dup == true) break;
            }
            if (dup == false) {
                Min = result;
            }
        }
        
        return Min;
    }

    static int F(int n) {
        int elements = n * (n + 1) / 2;
        int [] weight = new int[n+2];
        int Min = 1000000000;
        int MAX = 15; // 実際には MAX = 13 で O.K.
        int    [][] p = permutations(n);
        int [] vec = new int[MAX+1];
        int [] y = new int[n+1];
        int i, j;
        for (i = 1; MAX >= i; i++) {
            vec[i] = i;
        }
        for (i = 1; n >= i; i++) {
            weight[i] = (int) (factorial(n-1) / factorial(i-1) / factorial(n-i));
        }
        int [][] x = combn(vec, MAX, n);
        int cols = (int) (factorial(MAX) / factorial(n) / factorial(MAX-n));
        for (i = 1; cols >= i; i++) {
            for (j = 1; n >= j; j++) {
                y[j] = x[j][i];
            }
            Min = Math.min(Min, G(Min, n, weight, y, p));
        }
        return Min;
    }

    static double factorial(int n) {
        int i;
        double result = 1;
        for (i = 1; n >= i; i++) {
            result *= i;
        }
        return result;
    }

    static int[][] permutations(int n) {
        int sizeZ = (int)factorial(n);
        int sizeX = sizeZ / (n - 1);
        int[][] z = new int[sizeZ + 1][n + 1];
        int[][] x = new int[sizeX + 1][n + 1];
        int nrowZ, ncolZ, nrowX, ncolX;
        int i, i2, j, j2;
        z[1][1] = 1;
        nrowZ = ncolZ = 1;
        for (i = 2; n >= i; i++) {
            for (i2 = 1; nrowZ >= i2; i2++) {
                for (j2 = 1; ncolZ >= j2; j2++) {
                    x[i2][j2] = z[i2][j2];
                }
                x[i2][ncolZ + 1] = i;
            }
            nrowX = nrowZ;
            ncolX = ncolZ + 1;
            for (j = 1; i >= j; j++) {
                for (j2 = 1; nrowX >= j2; j2++) {
                    for (i2 = 1; ncolX >= i2; i2++) {
                        z[(j - 1) * nrowX + j2][i2] = x[j2][(j + i2 - 2) % i
                                + 1];
                    }
                }
            }
            nrowZ = i * nrowX;
            ncolZ = ncolX;
        }

        return z;
    }

    static int[][] combn(int[] x, int n, int m) {
        int e, h, i, j, nmmp1, lenr;
        int[] a = new int[m + 1];
        int[] r = new int[m + 1];
        int count = (int) (factorial(n) / factorial(m) / factorial(n - m));
        int[][] out = new int[m + 1][count + 1];
        e = 0;
        h = m;
        for (i = 1; m >= i; i++) {
            a[i] = i;
            r[i] = x[i];
        }
        lenr = r.length - 1;
        for (j = 1; count >= j; j++) {
            for (i = 1; lenr >= i; i++) {
                out[i][j] = r[i];
            }
        }
        i = 2;
        nmmp1 = n - m + 1;
        while (a[1] != nmmp1) {
            if (e < n - h) {
                h = 1;
                e = a[m];
            } else {
                e = a[m - h];
                h++;
            }
            for (j = 1; h >= j; j++) {
                a[m - h + j] = e + j;
            }
            for (j = 1; m >= j; j++) {
                out[j][i] = x[a[j]];
            }
            i++;
        }
        return out;
    }
}

コメント

相異なる素数の足し算で

2017年05月23日 | ブログラミング

相異なる素数の足し算で

締め切りが 2017/05/23 10:00 AM なので,その 1 分後に投稿されるように予約

【概要】
整数を、ある範囲の相異なる素数の足し算で表現することを考えます。
例えば、39 を 3以上19以下の、相異なる素数のみを使った足し算で表現する方法は、
    3+5+7+11+13
    3+17+19
    7+13+19
の3通りあります(つまり、順序が異なるだけのものは同一とみなします)。
「39」、「3〜19」 のような情報を与えますので、場合の数(この例だと 3)を計算するプログラムを書いてください。

【入出力】
入力は
39 3 19
のような感じです。
空白区切りで、合計、足し算に使う数の最小値、足し算に使う数の最大値 が並んでいます。
出力は、
3
のような感じで、普通に10進数で出力してください。

【例】
入力        出力
39 3 19        3
70 9 30        2
40 21 39    0

【補足】

    不正な入力に対処する必要はありません。
    合計は、1以上 100 以下の整数です。
    足し算に使う数の最小値は 1 以上の整数で、足し算に使う数の最大値は最小値以上 100 以下の整数です。
    ライブラリなどに素数の判定や列挙を行う関数などがある場合、遠慮なく使っていただいて構いません。

====================================

R では実行時間がちょっと掛かりすぎるので,Java で書いたら OK

R では

f = function(x, begin, end) {
    mx = end
    tbl = 1:mx
    tbl[1] = 0
    for (i in 2:floor(sqrt(mx))) {
        if (tbl[i]) {
            mx2 = mx%/%i
            tbl[2:mx2 * i] = 0
        }
    }
    prime = tbl[tbl > 0]
    prime = prime[prime >= begin]
    ans = 0
    m = length(prime)
    if (m != 0) {
        for (n in 1:min(9, m)) {
            y = combn(m, n, function(z) prime[z])
            if (length(dim(y)) == 1) {
                y = matrix(y, 1)
            }
            y = colSums(y)
#            if (sum(y > x) == length(y)) {
#                break
#            }
#            dump(c(n, sum(y == x)))
            ans = ans + sum(y == x)
        }
    }
    cat(ans)
}

f(1, 100, 100) # 0
f(3, 3, 3) # 1
f(63, 27, 27) # 0
f(12, 5, 7) # 1
f(72, 25, 46) # 2
f(59, 6, 58) # 6
f(84, 25, 61) # 3
f(79, 13, 43) # 5
f(88, 10, 49) # 7
f(20, 2, 20) # 4
f(72, 3, 29) # 8
system.time(f(100, 1, 100)) # 198

Java では

import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        int x, begin, end;
        if (false) {
            x = 100;
            begin = 1;
            end = 100;
            // x = 1; begin = 100; end = 100;
            // x = 3; begin = 3; end = 3;
            // x = 63; begin = 27; end = 27;
            // x = 12; begin = 5; end = 7;
            // x = 72; begin = 25; end = 46;
            // x = 59; begin = 6; end = 58;
            // x = 84; begin = 25; end = 61;
            // x = 79; begin = 13; end = 43;
            // x = 88; begin = 10; end = 49;
            // x = 20; begin = 2; end = 20;
            // x = 72; begin = 3; end = 29;
        } else {
            Scanner cin = new Scanner(System.in);
            String line;
            String[] line3 = new String[3];
            line = cin.nextLine();
            line3 = line.split(" ");
            x = Integer.parseInt(line3[0]);
            begin = Integer.parseInt(line3[1]);
            end = Integer.parseInt(line3[2]);
        }
        f(x, begin, end);
    }

    static void f(int x, int begin, int end) {
        int i, j, k;
        int[] PRIME = prime(end);
        int[] vec = new int[PRIME.length];
        int count = 0;
        int ans = 0;
        boolean found;
        for (i = 1; i < PRIME.length; i++) {
            if (PRIME[i] >= begin && end >= PRIME[i]) {
                vec[++count] = PRIME[i];
            }
        }
        for (k = 1; count >= k; k++) {
            int size = (int) (factorial(count) / factorial(k) / factorial(count
                    - k));
            int[][] z = new int[k + 1][size + 1];
            z = combn(vec, count, k);
            int big = 0;
            for (j = 1; size >= j; j++) {
                int sum = 0;
                for (i = 1; k >= i; i++) {
                    sum += z[i][j];
                }
                if (sum > x) {
                    big++;
                } else if (sum == x) {
                    ans++;
                    // System.out.println(k+", "+ans);
                }
            }
            // System.out.println(" big="+big+"    size="+size+"   count="+count+"   k="+k);
            if (big == size - 1) {
                break;
            }
        }
        System.out.println(ans);
    }

    static double factorial(int n) {
        int i;
        double result = 1;
        for (i = 1; n >= i; i++) {
            result *= i;
        }
        return result;
    }

    static int[][] combn(int[] x, int n, int m) {
        int e, h, i, j, nmmp1, lenr;
        int[] a = new int[m + 1];
        int[] r = new int[m + 1];
        int count = (int) (factorial(n) / factorial(m) / factorial(n - m));
        int[][] out = new int[m + 1][count + 1];
        e = 0;
        h = m;
        for (i = 1; m >= i; i++) {
            a[i] = i;
            r[i] = x[i];
        }
        lenr = r.length - 1;
        for (j = 1; count >= j; j++) {
            for (i = 1; lenr >= i; i++) {
                out[i][j] = r[i];
            }
        }
        i = 2;
        nmmp1 = n - m + 1;
        while (a[1] != nmmp1) {
            if (n - h > e) {
                h = 1;
                e = a[m];
            } else {
                e = a[m - h];
                h++;
            }
            for (j = 1; h >= j; j++) {
                a[m - h + j] = e + j;
            }
            for (j = 1; m >= j; j++) {
                out[j][i] = x[a[j]];
            }
            i++;
        }
        return out;
    }

    static int[] prime(int m) {
        int i, j, count;
        int[] tbl = new int[m + 1];
        for (i = 1; m >= i; i++) {
            tbl[i] = i;
        }
        tbl[1] = 0;
        for (i = 2; Math.sqrt(m) >= i; i++) {
            if (tbl[i] != 0) {
                for (j = 2 * i; m >= j; j += i) {
                    tbl[j] = 0;
                }
            }
        }
        count = 0;
        for (i = 2; m >= i; i++) {
            if (tbl[i] != 0) {
                count++;
            }
        }
        int[] tbl2 = new int[count + 1];
        count = 1;
        for (i = 2; m >= i; i++) {
            if (tbl[i] != 0) {
                tbl2[count++] = tbl[i];
            }
        }
        return tbl2;
    }

}

コメント

「ロンリー・ルーク」問題

2017年05月18日 | ブログラミング

「ロンリー・ルーク」問題


締め切りが 2017/05/18 10:00 AM なので,その 1 分後に投稿されるように予約


設問

自然数 n, k に対し、縦横 n×n のマス目にチェスのルークの駒を k 個配置することを考えます。
このとき、自身から見て上下方向・左右方向のいずれにも他の駒が存在しないような駒を「はぐれルーク」と呼びます。
 
例えば以下は、(n, k)=(4, 5) のときの駒の配置例を示しています。
それぞれ、はぐれルークを灰色丸、そうでないルークを青色丸で示しています。
また、はぐれルークの個数は、左図では 1 個、右図では 2 個であることが分かります。

さて、1 つのマスに 2 個以上の駒を置かないよう、ランダムに駒を配置します。
このとき、はぐれルークの個数の期待値を F(n, k) と定義します。
 
例えば F(2, 2)=2/3 です。
可能な駒の配置は以下の 6 通りです。このうち真ん中の 2 通りでのはぐれルークの個数は 2 個で、他の 4 通りでは 0 個です。
したがって期待値は、0×(4/6)+2×(2/6) = 2/3 となります。

同様に、F(2, 1)=1, F(4, 2)=1.2, F(3, 3)=0.642…, F(4, 5)=0.461…, F(4, 11)=0 となることが確かめられます。
 
さらに、自然数 n, m に対し、1 ≦ k ≦ m の範囲の自然数 k に対する F(n, k) の和を G(n, m) と定義します。
例えば、G(2, 2)=5/3, G(4, 3)=3.228…, G(4, 5)=4.428… となることが確かめられます。
 
また、10^3×G(n, m) の整数部分を H(n, m) と定義します。
例えば、H(2, 2)=1666, H(4, 3)=3228, H(4, 5)=4428 です。
 
標準入力から、自然数 n と m (1 ≦ n ≦ 4, 1 ≦ m ≦ n^2)が半角空白区切りで与えられます。
標準出力に H(n, m) の値を出力するプログラムを書いてください。
なお全てのテストケースにおいて、10^3×G(n, m) の値と、最も近い整数値との差の絶対値は 10^(-3) 以上であることが保証されています。


 ===================================================

R で簡単に書けるが,計算時間は数秒かかる。

bincombinations = function(p) { # library(e1071) にある
    retval = matrix(0, nrow = 2^p, ncol = p)
    for (n in 1:p) {
        retval[, n] = rep(c(rep(0, (2^p/2^n)), rep(1, (2^p/2^n))),
            length = 2^p)
    }
    retval
}

f = function(n, m) {
    check = function(x) {
        rSum = rowSums(x) == 1
        cSum = colSums(x) == 1
        sum(outer(rSum, cSum, "&") & x)
    }
    len = 2^(n*n)
    a = array(t(bincombinations(n*n)), dim=c(n, n, len))
    s = apply(a, 3, sum)
    sm = apply(a, 3, check)
    tbl = table(s, sm)
    rSum = rowSums(tbl)
    F = colSums(t(tbl / rSum) * 0:n)
    G = cumsum(F)
    ans = G[m+1]
    H = floor(ans*1000)
    cat(H)
}

# s = scan(file("stdin", "r"))
# f(s[1], s[2])

#f(2, 3) # 1666
#f(3, 3) # 2642
#f(3, 4) # 2928
#f(4, 4) # 3967
#f(4, 7) # 4797
#f(4, 16) # 4857, 2.922 seq.

Java で書けば,計算は一瞬で終わるが,プログラムを書くのが面倒だ。

import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        if (true) {
            System.out.println(f(2, 3));  // 1666
            System.out.println(f(3, 3));  // 2642
            System.out.println(f(3, 4));  // 2928
            System.out.println(f(4, 4));  // 3967
            System.out.println(f(4, 7));  // 4797
            System.out.println(f(4, 16)); // 4857
        } else {
            Scanner cin = new Scanner(System.in);
            String line;
            String[] line2 = new String[2];
            line = cin.nextLine();
            line2 = line.split(" ");
            int n = Integer.parseInt(line2[0]);
            int m = Integer.parseInt(line2[1]);
            System.out.println(f(n, m));
        }
    }

    static int pow2(int n) {
        int i, res = 1;
        for (i = 0; i < n; i++) {
            res *= 2;
        }
        return res;
    }

    static int check(int[][] subMat, int n) {
        int i, j;
        int [] rowSums = new int[n];
        int [] colSums = new int[n];
        for (i = 0; i < n; i++) {
            for (j = 0; j < n; j++) {
                rowSums[i] += subMat[i][j];
                colSums[j] += subMat[i][j];
            }
        }
        int sum = 0;
        for (i = 0; i < n; i++) {
            for (j = 0; j < n; j++) {
                if (subMat[i][j] == 1 && rowSums[i] == 1 && colSums[j] == 1) {
                    sum++;
                }
            }
        }
        return sum;
    }

    static int f(int n, int m) {
        int i, j, k;
        int[][] ary = bincombinations(n * n);
        int[][] subMat = new int[n][n];
        double[][] tbl = new double[n * n + 1][n + 1];
        for (i = 0; i < pow2(n * n); i++) {
            int s = 0;
            for (j = 0; j < n * n; j++) {
                s += ary[i][j];
            }
            for (j = 0; j < n; j++) {
                for (k = 0; k < n; k++) {
                    subMat[j][k] = ary[i][j * n + k];
                }
            }
            tbl[s][check(subMat, n)]++;
        }
        double ans = 0;
        for (i = 0; m >= i; i++) {
            int rSum = 0;
            for (j = 0; j < n + 1; j++) {
                rSum += tbl[i][j];
            }
            for (j = 0; j < n + 1; j++) {
                tbl[i][j] /= rSum;
                ans += tbl[i][j] * j;
            }
        }
        return (int) (ans * 1000);
    }

    static int[] c(int[] x, int[] y) {
        int lenX = x.length;
        int lenY = y.length;
        int i;
        int[] res = new int[lenX + lenY];
        for (i = 0; i < lenX; i++) {
            res[i] = x[i];
        }
        for (i = 0; i < lenY; i++) {
            res[lenX + i] = y[i];
        }
        return res;
    }

    static int[] rep(int[] x, int len) {
        int i, pos = 0;
        int[] res = new int[len];
        int m = x.length;
        for (;;) {
            for (i = 0; i < m; i++) {
                res[pos++] = x[i];
                if (pos == len) {
                    return res;
                }
            }
        }
    }

    static int[][] bincombinations(int p) {
        int[] zero = { 0 };
        int[] one = { 1 };
        int m = pow2(p);
        int[][] ary = new int[m][p];
        int[] x = new int[m];
        int n, i;
        for (n = 0; n < p; n++) {
            x = rep(c(rep(zero, pow2(p - n - 1)), rep(one, pow2(p - n - 1))), pow2(p));
            for (i = 0; i < m; i++) {
                ary[i][n] = x[i];
            }
        }
        return ary;
    }

}

コメント

取られたら取り返す!

2017年05月09日 | ブログラミング

取られたら取り返す!

締め切りが 2017/05/09 10:00 AM なので,その 1 分後に投稿されるように予約

設問

卓球では11点先取、バレーボールでは25点先取で1セットを取るようなルールがあります。
ただ、この得点よりも1点少ない得点以上の得点で同点となると「デュース」と呼ばれることがあり、その後は2点差を付けるまで続けられます。
(卓球やバドミントンにはデュースという言葉はありませんが、同様に進められます。)

A と B がn 点先取の試合を行ったとき、それぞれの点数が a 対 b になるまでの点数の推移を考えます。
例えば、n = 3, a = 4, b = 2 のとき、点数の推移は以下の6通りがあります。
(下記の記号は点数を取った側を表すものとします。)

(1) A -> A -> B -> B -> A -> A
(2) A -> B -> A -> B -> A -> A
(3) A -> B -> B -> A -> A -> A
(4) B -> A -> A -> B -> A -> A
(5) B -> A -> B -> A -> A -> A
(6) B -> B -> A -> A -> A -> A

このとき、以下のように点数が推移することはありません。
(途中で3点を先取してしまい、セットが終了するため)
A -> A -> B -> A -> B -> A

標準入力から n, a, b がスペース区切りで与えられるとき、点数の推移が何通りあるかを求め、標準出力に出力してください。
なお、n, a, b はいずれも25以下の正の整数とします。

【入出力サンプル】
標準入力
3 4 2

標準出力
6

=================================================

例によって,サイズの小さい場合について,馬鹿正直に計算するプログラムを書き,結果から規則性を見いだす。

n = 6 の場合については下図のようになる。



水色の部分は i, j > 1 において,x[i, j] = x[i-1, j] + x[i, j-1]
黄色の部分は近隣のコピー(コピーの順番に注意)

ということで,一般的には

f = function(n, a, b) {
    x = matrix(0, 28, 28) # 計算途中で添え字が溢れないように +2
    for (i in 1:n-1) {
        for (j in 1:n-1) {
            x[i+1, j+1] = choose(i+j, i)
        }
    }
    x[n+1, 1:n] = x[1:n, n+1] = x[n, 1:n]
    for (i in n:26) {
        x[i, i+1:2] = x[i+1:2, i] = x[i, i] = x[i-1, i] + x[i, i-1]

    }
    cat(x[a+1, b+1])
}
# s = scan(file("stdin", "r"))
# f(s[1], s[2], s[3])

f(3, 4, 2) # 6
f(10, 9, 8) # 24310
f(15, 0, 14) # 1
f(15, 17, 20) # 0
f(11, 25, 24) # 3027042304



コメント

140問目!素数列から抜き出してつぶやこう?

2017年05月02日 | ブログラミング

140問目!素数列から抜き出してつぶやこう?

締め切りが 2017/05/02 10:00 AM なので,その 1 分後に投稿されるように予約

設問

今週のアルゴリズムも140問目!
「140」といえばTwitterにおけるつぶやきの文字数の上限です。

m 以上 n 以下の素数を一列に並べ、その中から連続した数字列を最長140文字で抜き出したとき、最初と最後の数字が同じで、含まれる数の和が最大になるものを求め、その和を出力してください。

例えば、m = 5, n = 30 のとき、

57111317192329

という数字列の中から、最初と最後の数字が同じで、長いものを抜き出すと、含まれる数の和は

 7111317       -> 21
  1113171      -> 15
     3171923   -> 26
         92329 -> 25
          232  -> 7

となりますので、最大なのは26です。

標準入力から m と n がスペース区切りで与えられるとき、和の最大値を求め、標準出力に出力してください。
なお、m と n は 1 < m < n < 100000を満たす整数とします。

【入出力サンプル】
標準入力
5 30

標準出力
26

−−−−−−−−−−

素直にプログラムし,なんの最適化もしなかったが,計算時間も制限内に収まっていた

f = function(m, n) {
    mx = n # エラトステネスの篩で素数列生成
    tbl = 1:mx
    tbl[1] = 0
    for (i in 2:floor(sqrt(mx))) {
        if (tbl[i]) {
            mx2 = mx %/% i
            tbl[2:mx2*i] = 0
        }
    }
    prime <- tbl[tbl >= m] # m 以上,n 以下の素数
    x = as.integer(unlist(strsplit(paste(prime, collapse=""), ""))) # 繋いでばらす
    maxSum = 0
    for (i in seq_along(x)) {
        y = x[i:min(i+139, length(x))] # i 番目から 140 個以内の数字列
        z = which(y == x[i]) # 最初と同じ数字のある場所
        s = sum(y[1:max(z)]) #  最初から最後の位置までの数字の和
        maxSum = max(s, maxSum) # 最大のものを記録
    }
    cat(maxSum)
}

# s = scan(file("stdin", "r"), quiet=TRUE)
# f(s[1], s[2])

f(5, 30) # 26
f(2, 100) # 204
f(100, 10000) # 930
f(10000, 50000) # 860
f(2, 99999) # 1019



コメント