裏 RjpWiki

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

目標を達成する手順は何通り?

2017年06月27日 | ブログラミング

目標を達成する手順は何通り?

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

設問

こども向けのプログラミング教育が話題です。
ソースコードを書くというよりは、論理的な思考を養うことが求められ、小学校低学年のこどもにもイメージしやすい例が使われています。
例えば、横に m マス、縦に n マスの格子状のマスを左上から右下に移動するための手順を考える、という例があります。
使用可能な操作は「前に進む」「左を向く」「右を向く」の3つです。
このマスの外側には移動できず、最短の経路である必要はありません。
なお、右下のマスに着くとその時点で終了とします。
(つまり、右下のマスでは「左を向く」「右を向く」の操作はできません。)
m = 3, n = 2で、右向きに開始するとき、以下の4回の操作で左図のように移動できます。
1. 前に進む
2. 前に進む
3. 右を向く
4. 前に進む

では、左上から右下に5回の操作で移動させるにはどうすればよいでしょうか?
例えば、左上の位置で最初の向きを下向きの状態にしておけば、以下の5回の操作で右図のように移動できます。
1. 左を向く
2. 前に進む
3. 前に進む
4. 右を向く
5. 前に進む
標準入力から m、n、操作する回数がスペース区切りで与えられます。
このときの操作方法が何通りあるかを求め、標準出力に出力してください。
例えば、 m = 3, n = 2のとき、5回の操作で移動する方法は上記の右図の他に4通りあり、合計5通りですので、以下のように出力します。
なお、入力として用いられる値は、出力が32bit整数の範囲内となるものとします。

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

標準出力
5

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

時間制限をクリアできない


tricombinations = function (p) {
    retval = matrix(" ", nrow = 3^p, ncol = p)
    for (n in 1:p) {
        retval[, n] = rep(c(rep("R", (3^p/3^n)), rep("L", (3^p/3^n)), rep("F", (3^p/3^n))),
            length = 3^p)
    }
    retval
}

g = function(m, n, step, a, e, dx, dy) {
    p = m*n
    r = apply(e, 1, function(s) {
        x = y = 2
        for (i in seq_len(step)) {
            dxy = dx*2+dy
            if (s[i] == "R") { # 右旋回
                if (dxy == 2) { # dx = 1, dy =  0
                    dx = 0
                    dy = 1
                } else if (dxy == -2) { # dx = -1, dy = 0
                    dx = 0
                    dy = -1
                } else if (dxy == 1) { # dx = 0, dy = 1
                    dx = -1
                    dy = 0
                } else { # dx = 0, dy = -1
                    dx = 1
                    dy = 0
                }                
            } else if (s[i] == "L") { # 左旋回
                if (dxy == 2) { # dx = 1, dy =  0
                    dx = 0
                    dy = -1
                } else if (dxy == -2) { # dx = -1, dy = 0
                    dx = 0
                    dy = 1
                } else if (dxy == 1) { # dx = 0, dy = 1
                    dx = 1
                    dy = 0
                } else { # dx = 0, dy = -1
                    dx = -1
                    dy = 0
                }
            } else { # if (s[i] == "F") 前進
                x = x+dx
                y = y+dy
            }
            if (a[x, y] == 0) { # はみ出した
                return(0)
            } else if (a[x, y] == 2) { # 出口
                return(i)
            }
        }
        return(0) # 途中
    })
    return(sum(r == step))
}

f = function(m, n, step) {
    a = matrix(0, n+2, m+2)
    a[1:n+1, 1:m+1] = 1
    a[n+1, m+1] = 2
    e = tricombinations(step)
    count = g(m, n, step, a, e, 1, 0) # dxy = 2*dx+dy = 2
    count = count + g(m, n, step, a, e, -1, 0) # dxy = -2
    count = count + g(m, n, step, a, e, 0, 1) # dxy = 1
    count = count + g(m, n, step, a, e, 0, -1) # dxy = -1
    cat(count)
}

f(3, 2, 5) # 5
f(6, 6, 12) # 12
f(8,3, 20)
f(80,80,162)
f(77,13,96) #

コメント
この記事をはてなブックマークに追加

メビウスの亀

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

メビウスの亀

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

【概要】

右写真のようなメビウスの帯の上を、不思議な亀が歩いています。
亀の初期位置は「1a」のマスで「2a」の方を向いています。

亀はコマンドのとおりに進みます。コマンドは下表のとおりです:

コマンド     意味
R     90度右に向きます。
L     90度左に向きます。
B     紙の裏側に移動します。向きは変わりません。この記述が誤解を生みやすい。以下の解説をちゃんと読むこと。
たとえば、
 「1a」の位置にいて「1b」の方を向いている
   ↓Bコマンド
 「1E」の位置で「1D」の方を向いている
という具合です。
1〜9     1〜9マス 進みます。紙のフチに到達したら、裏側に行きます。
たとえば、
 1c→1d→1e→1A→1B→1C
という具合です。

最終的に到達するマスの名前を計算して下さい。

メビウスの帯は、片面が (1〜32)×(a〜e)、反対側の面が(1〜32)×(A〜E) となっている紙をメビウスの帯になるようにしたものです。

【入出力】

入力は
L9R9B9
のようになっています。
コマンドの列が区切り文字なしで並んでいます。

出力は、
19a
のような感じです。

最終的に到達するマスを答えて下さい。

【例】
入力     出力
L9R9B9     19a
RRRB1     1D

【補足】
 不正な入力に対処する必要はありません。
 コマンドの長さは1以上 20 以下です。
 
================================================

f = function(s) {
    a = cbind(
    rbind(outer(1:32, letters[1:5], paste0), outer(1:32, LETTERS[1:5], paste0)),
    rbind(outer(1:32, LETTERS[1:5], paste0), outer(1:32, letters[1:5], paste0))
    )
    locationX = locationY = 0
    b = strsplit(s, "")[[1]]
    xy = rbind(c(0,1), c(-1,0), c(0,-1), c(1,0))
    p = 0
    for (i in seq_along(b)) {
        c = b[i]
        if (c == "R") {
            p = (p+1) %% 4
        } else if (c == "L") {
            p = (p-1) %% 4
        } else if (c  == "B") {
            if (p == 1) p = 3 else if (p == 3) p = 1 # ここに注意!!
            locationX = (9-locationX) %% 10
        } else {
            step = as.integer(c)
            deltaX = xy[p+1, 1]
            deltaY = xy[p+1, 2]
            locationX = (locationX+deltaX*step) %% 10
            locationY = (locationY+deltaY*step) %% 64
        }
    }
    cat(a[locationY+1, locationX+1])
}

f("99999999999999999999") # 21A
f("LL999999999999999999") # 31a
f("9B9R7L9B9R7L9B9R7LB1") # 24c
f("8L8L7L4R2B8R9R6BL3L6") # 24d
f("6BR9B1BR2B4LB9L6LBL4") # 23B
f("2BR4B3L6BLL8B3R7L6RB") # 14E
f("RB4R6B3LLLL1B6L4BLB3") # 20C
f("R1B3B7LL9BL3R4R7L6RR") # 29B
f("L8R6L7L9LL3L2L7B6BR2") # 20e
f("B3R1B6LB5L6RBLL4L3L7") # 28b
f("1L8B1L4L6R9R8L6L3R9L") # 30b
f("8L3BR3L4B6LL6LB4B5RB") # 15c

コメント
この記事をはてなブックマークに追加

crontab書式を解釈しよう

2017年06月16日 | ブログラミング

crontab書式を解釈しよう

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

設問

あなたはとあるジョブ管理ツールの開発を任されており、定時実行のためにcrontab(Wikipediaへのリンク)の書式で記述されたスケジュールに対応することになりました。
そこで、まず与えられたスケジュールを正しく解釈できるかテストするためのプログラムを作ることにしました。



求められるプログラムの前提条件は、以下の通りとなります。
    標準入力から、crontabの書式で記述されたスケジュールの文字列が1行送られる
    文字列は、9文字以上80文字以下とし、フィールド間はスペースで区切られているものとする
    文字列のうち、解釈の対象となるのは"時フィールド"のみとし、その他は無視するものとする
    文字列に、コメントや、第6フィールド以降(コマンド記述)は含まれないものとする
    文字列から、何時(0-23)に実行されるかを求め、数値が複数の場合はスペース区切りで標準出力に送ること
    複数の値を指定する特殊記号として、アスタリスク (*) スラッシュ(/) ダッシュ (-) コンマ(,)を考慮すること
    それぞれのルールはWikipedia上のcrontabの解説(リンク先)に従うこと
    入出力例にはないが、範囲外の値(0未満または24以上)の指定がある場合も、無視すること
    出力する数値に重複があった場合は、除外した上で出力すること
    出力する数値は、小さい値から大きい値の順になるようソートすること

以下、入出力例になります。

入力            出力
0 1,3,2 * * *        1 2 3
0 5,5,6 * * *         5 6
0 */6 * * *         0 6 12 18
0 3-4,7-8 * * *     3 4 7 8
0 1-10/5 * * *        1 6

【問題】
標準入力から、crontabの書式で記述されたスケジュールの文字列が送られます。
この文字列を解釈し、何時に実行されるかを求め、その結果を標準出力に返してください。

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

f = function(S) {
    S = strsplit(S, " ")[[1]][2]
    S = strsplit(S, ",")[[1]]
    ans = NULL
    for (s in S) {
        if (grepl("/", s)) {
            s = strsplit(s, "/")[[1]]
            if (s[1] == "*") {
                s[1] = "0-23"
            }
            if (grepl("-", s[1])) {
                s2 = as.integer(strsplit(s[1], "-")[[1]])
                hour = seq(s2[1], s2[2], by = as.integer(s[2]))
                ans = c(hour, ans)
            }
        } else if (grepl("-", s)) {
            s = as.integer(strsplit(s, "-")[[1]])
            ans = c(s[1]:s[2], ans)
        } else {
            ans = c(as.numeric(s), ans)
        }
    }
    cat(unique(sort(ans)))
}

f("0 9-10,18-19 * * *") # 9 10 18 19
f("0 8-18/3 * * *") # 8 11 14 17
f("0 */8,18-23 * * *") # 0 8 16 18 19 20 21 22 23

コメント
この記事をはてなブックマークに追加

「タンジェント・フラクション」問題

2017年06月15日 | ブログラミング

「タンジェント・フラクション」問題

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

設問

α と β を、0 < α < β < π/2 を満たす実数とします。
α, β の組のうち、tan(α), tan(β), tan(α+β) がすべて単位分数(分母が自然数、分子が 1 の分数として書き表せる数)となるものを考えましょう。(α, β の単位はラジアンと見なします。)
 
例えば下図の青色の正方形の格子において、図のように α(≒0.3218)と β(≒0.4636)をとると、tan(α)=1/3, tan(β)=1/2 です。
さらに黒色の三角形が直角二等辺三角形となるため、tan(α+β)=1 となり、このような α と β が題意を満たすことが分かります。
 
正の実数 m に対し、m ≦ α+β の範囲で題意を満たす α, β の組の個数を F(m) と定義します。
 
例えば F(0.5)=1,F(0.3)=4,F(0.1)=15,F(0.01)=266 となることが確かめられます。
 
標準入力から、正の実数 m(0.001 < m < 1)が与えられます。
標準出力に F(m) の値を出力するプログラムを書いてください。
なお入力値の小数点以下の桁数は最大で 4 桁とします。
 
=====================================


tan(α+β) = (tan α + tan β) / (1-tan α tan β)
tan α = 1/a, tan β = 1/b なる a, b を用いて,
tan(α+β) = (1/a+1/b) /(1-(1/a)(1/b)) = (a+b) / (ab-1)
tan(α+β) が単位分数であるためには ab-1 が a+b で割り切れればよい。
よって,問題は 整数 a, b で ab-1 が a+b で割り切れる組み合わせを数えればよい。
ただし,1/a + 1/b > m であること 1/a + 1/b < π/2 という条件の下で。
出題の範囲では,1≦ a, b ≦ 10^6 で探索すればよいが,枝刈りが必須。

第一次解

F = function(m) {
    max = 1e+06
    count = 0
    for (a in 2:(2/m)) {
        limit = m - 1/a
        for (b in a:max) {
            if (b * limit >= 1) {
                break
            }
            abm1 = a * b - 1
            apb = a + b
            if (abm1%%apb == 0) {
                count = count + 1
            }
        }
    }
    cat(count)
}

system.time(F(0.6))    #    1,   0.015 sec.
system.time(F(0.5))    #    1,   0.304 sec.
system.time(F(0.3))    #    4,   0.548 sec.
system.time(F(0.1))    #   15,   2.478 sec.
system.time(F(0.02))   #  117,  13.545 sec.
system.time(F(0.012))  #  219,  22.501 sec.
system.time(F(0.01))   #  266,  26.629 sec.
system.time(F(0.0098)) #  272,  29.057 sec.
system.time(F(0.0048)) #  628,  55.406 sec.
system.time(F(0.0013)) # 2791, 205.393 sec.
system.time(F(0.0011)) # 3382, 244.198 sec.

時間が掛かりすぎる。

第二次解

F = function(m) {
    count = 0
    for (a in 2:(2/m)) {
        b = a:1e+06 # 内側の for をなくす
        b = b[1 > b * (m-1/a)]
        count = count + sum((a * b - 1) %% (a + b) == 0)
    }
    cat(count)
}

system.time(F(0.6))    #    1,  0.027 sec.
system.time(F(0.5))    #    1,  0.048 sec.
system.time(F(0.3))    #    4,  0.089 sec.
system.time(F(0.1))    #   15,  0.448 sec.
system.time(F(0.02))   #  117,  2.336 sec.
system.time(F(0.012))  #  219,  3.880 sec.
system.time(F(0.01))   #  266,  4.738 sec.
system.time(F(0.0098)) #  272,  4.909 sec.
system.time(F(0.0048)) #  628, 10.261 sec.
system.time(F(0.0013)) # 2791, 38.881 sec.
system.time(F(0.0011)) # 3382, 45.998 sec.

第三次解

F = function(m) {
    max = 1e+06
    count = 0
    for (a in 2:(2/m)) {
        b = a:min(max-1, a * (a - 1) + 1) # 範囲を絞る
        b = b[1 > b * (m - 1/a)]
        count = count+sum((a * b - 1) %% (a + b) == 0)
    }
    cat(count)
}

system.time(F(0.6))    #    1,  0     sec.
system.time(F(0.5))    #    1,  0     sec.
system.time(F(0.3))    #    4,  0     sec.
system.time(F(0.1))    #   15,  0     sec.
system.time(F(0.02))   #  117,  0.004 sec.
system.time(F(0.012))  #  219,  0.017 sec.
system.time(F(0.01))   #  266,  0.028 sec.
system.time(F(0.0098)) #  272,  0.029 sec.
system.time(F(0.0048)) #  628,  0.297 sec.
system.time(F(0.0013)) # 2791, 12.958 sec.
system.time(F(0.0011)) # 3382, 18.321 sec.

最終解 爆速

F = function(m) {
    max = 1e+06
    count = 0
    for (a in 2:(2/m)) {
        b = as.integer((a*(a-1:a)+1) / 1:a) # 大幅に絞る
        b = b[b >= a]
        b = b[1 > b*(m-1/a)]
        count = count+sum((a * b - 1) %% (a+b) == 0)
    }
    cat(count)
}

system.time(F(0.6))    #    1, 0     sec.
system.time(F(0.5))    #    1, 0     sec.
system.time(F(0.3))    #    4, 0     sec.
system.time(F(0.1))    #   15, 0     sec.
system.time(F(0.02))   #  117, 0     sec.
system.time(F(0.012))  #  219, 0.001 sec.
system.time(F(0.01))   #  266, 0.002 sec.
system.time(F(0.0098)) #  272, 0.002 sec.
system.time(F(0.0048)) #  628, 0.004 sec.
system.time(F(0.0013)) # 2791, 0.084 sec.
system.time(F(0.0011)) # 3382, 0.070 sec.

コメント
この記事をはてなブックマークに追加

ホーム画面を整理して!

2017年06月13日 | ブログラミング

ホーム画面を整理して!

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

設問

多くの人が使うようになったスマートフォン。
そのホーム画面には多くのアプリのアイコン(以下、アイコン)が並びます。
そこで、このアイコンをフォルダにまとめて整理することを考えます。

1つのフォルダには1個~9個のアイコンを登録でき、登録するとフォルダ1つのアイコンにまとまり、そのフォルダに登録されているアイコンの数が識別できるようになります。
なお、フォルダの中にフォルダを作ることはできません。
n 個のアイコンを整理するとき、そのフォルダ構成について、アイコンの数の組み合わせがいくつ考えられるかを求めます。
ただし、個々のアイコンは識別せず、並び順も考えないものとし、アイコンの数の組み合わせだけを考えます。
(フォルダ内にあるアイコンの数が異なる場合は、別々のフォルダ構成としてカウントします。)
なお、ホーム画面には最大で24個のアイコンを並べられるものとし、n は 1≦n≦216を満たす整数とします。
例えば、n = 5 のとき、以下の7通りがあります。
(図の黄色はフォルダを、数字はアイコンの数を表します。)
当然、n = 216のときは、すべてフォルダにまとめた1通りしかありません。

標準入力から n が与えられるとき、アイコンの数の組み合わせがいくつあるかを求め、標準出力に出力してください。

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

標準出力
7

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

整数分割問題だが,分割数が 24 以下という制約があるもの。
n=108 で対称。つまり,f(128) == f(88), f(214) == f(2)。
R だと,制限時間オーバー

initDiv = function(length, max) {
    ary = NULL
    repeat {
        if (max >= length) {
            ary = c(ary, length)
            return(ary)
        } else {
            ary = c(ary, max)
            length = length - max
        }
    }
}

nextDiv = function(ary) {
    # 1でない要素を後ろから探す
    sum = 0
    for (pos in length(ary):1) {
        a = ary[pos]
        sum = sum + a
        if (a != 1 && (pos > 1 &&  ary[pos - 1] >= ary[pos])) {
            break
        }
    }
    if (ary[1] == 1) { # 全て1
        return(FALSE)
    }
    ary = ary[1:pos]
    ary[pos] = ary[pos] - 1
    max = ary[pos]
    sum = sum - max
    pos = pos + 1
    repeat {
        if (pos > 24) {
            ary[pos] = sum
            return(ary)
        }
        if (max >= sum) {
            ary[pos] = sum
            return(ary)
        } else {
            ary[pos] = max
            sum = sum - max
        }
        pos = pos + 1
    }
}

f = function(length, max) {
    length = min(length, 216 - length)
    d = initDiv(length, max)
    count = 1
    repeat {
        d = nextDiv(d)
        if (length(d) == 1) {
            break
        }
        count = count + (24 >= length(d))
    }
    cat(count)
}

f(128)
f(5, 9) # 7
f(10, 9) # 41
system.time(f(50, 9)) # 39777, 0.884 sec.
system.time(f(128, 9)) # 449718, 9.317 sec.
system.time(f(214, 9)) # 2

Java で書いて OK

import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        long start = System.currentTimeMillis();
        int n, i;
        if (false) {
            n = 88; // 449718
        } else {
            Scanner cin = new Scanner(System.in);
            String line;
            line = cin.nextLine();
            n = Integer.parseInt(line);
            n = Math.min(n, 216-n);
        }
            int m = 9;
            int[] d = initDiv(n, m);
            int count = 0;
            for (;;) {
                for (i = 0; i < d.length; i++) {
                    if (d[i] == 0 || i > 24) {
                        break;
                    }
                }
                if (24 >= i) {
                    count++;
                }
                if (nextDiv(d) == false) {
                    break;
                }
            }
            System.out.println(count);

            long end = System.currentTimeMillis();
            System.out.println((end - start)  + " ms");
    }

    static int length(int[] a) {
        for (int len = 0;; len++) {
            if (a[len] == 0)
                return len;
        }
    }

    static int[] initDiv(int length, int max) {
        int a = length / max;
        int[] ary = new int[1000];
        for (int i = 0; i < a; i++) {
            ary[i] = max;
        }
        ary[a] = length % max;
        return (ary);
    }

    static boolean nextDiv(int[] ary) {
        int sum, pos, a, max;
        sum = 0;
        for (pos = length(ary) - 1; pos >= 0; pos--) {
            a = ary[pos];
            sum += a;
            if (a != 1) {
                break;
            }
        }
        if (pos == -1) {
            return false;
        }
        max = --ary[pos];
        sum -= max;
        for (pos++;; pos++) {
            if (max >= sum) {
                ary[pos] = sum;
                for (int j = pos + 1; j < 1000; j++) {
                    ary[j] = 0;
                }
                return true;
            } else {
                ary[pos] = max;
                sum -= max;
            }
        }
    }
}

コメント
この記事をはてなブックマークに追加

スミス数

2017年06月12日 | ブログラミング

スミス数
 合成数で、その素因数の数字の和がもとの数の数字の和に等しい数

f = function(n) {
    library(matlab) # 素数判定関数 isprime, 素因数分解関数 factors
    if (isprime(n) == 0) {
        a = sum(as.integer(unlist(strsplit(as.character(n), ""))))
        b = sum(sapply(factors(n), function(x) sum(as.integer(unlist(strsplit(as.character(x), ""))))))
        cat(a == b, "\n")
    }
}

f(9985) # 9985 ==> 9+9+8+5 = 31, 9985 = 5x1997 ==> 5+1+9+9+7 = 31
f(6036)

コメント
この記事をはてなブックマークに追加

ハーディ・ラマヌジャン数

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

2 つの数の立方(3乗)の和として表す表し方が 2 通りある 4 桁の自然数を求めよ。

素直にプログラムしても,計算時間は無視できるほど。

mx = floor(9999^(1/3))                    # 1 から 21 までの 3 乗を調べればよい
res = integer(mx^3+(mx)^3)                # 2 数の 3 乗和をメモするためのベクトル
for (i in 1:(mx-1)) {
    for (j in (i+1):mx) {
        num = i^3+j^3                     # 2 数 i, j の 3 乗和
        res[num] = res[num]+1             # 表し方のカウントを増やす
        if (res[num] == 2) cat(num, "\n") # 2 通り目だったら,それが解
    }
}

結果は
1729
4104

for などを使わずに,既存の関数などを使って解を求める。

x = (1:9999^(1/3))^3               # 1 〜 21 の 3 乗を要素とするベクトル
result = outer(x, x, "+")          # 外積(和)を求める
result = result[upper.tri(result)] # 対称行列なので,上側三角行列(対角を除く)の要素を取り出す
tbl = table(result)                # 度数分布を調べる
print(tbl[tbl == 2])               # 度数が 2 のものを書き出す

print 関数で書き出すと答えは
result
1729 4104
   2    2
のようになる。cat ではだめ。

後者のプログラムは前者のものより 2 倍以上速い。

コメント
この記事をはてなブックマークに追加

素因数分解で和が同じ

2017年06月06日 | ブログラミング

素因数分解で和が同じ

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

設問

整数を素因数分解し、分解した素数の和を求めることを考えます。
例えば、36を素因数分解すると2×2×3×3となり、分解した素数の和は 2+2+3+3=10 となります。
また、32を素因数分解すると2×2×2×2×2となり、分解した素数の和は 2+2+2+2+2=10 となります。

このように、分解した素数の和が同じになることがあります。
そこで、分解した素数の和 n が与えられたとき、元の整数がいくつあるかを求めます。
例えば、n = 10 のとき、上記の32, 36以外に21, 25, 30がありますので、全部で5つあります。

標準入力から n が与えられたとき、元の整数がいくつあるかを求め、標準出力に出力してください。
ただし、2≦n≦250とします。

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

標準出力
5

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

整数を,素数を要素として持つ複数の部分に分割する問題である。
計算制限時間の条件(1秒未満)を満たせない。
Java で書いても満たせない。
規則性もなし...
お手上げだ。

R では n=140 でも 3.557 秒掛かる。n=250 だと 790.520 秒
Java では n=250 で 3.745 秒掛かる。

Primes = function(mx) {
    tbl = 1:mx
    tbl[1] = 0
    for (i in 2:floor(sqrt(mx))) {
        if (tbl[i]) {
            mx2 = mx%/%i
            tbl[2:mx2 * i] = 0
        }
    }
    tbl[tbl > 0]
}

f = function(n) {
    primes = Primes(n)
    ary = integer(n/2)
    ary[1] = n
    count = n %in% primes
    lastpos = 1
    repeat {
        sum = 0
        for (pos in lastpos:1) {
            a = ary[pos]
            sum = sum + a
            if (a >= 3) {
                break
            }
        }
        if ((ary[1] == 3 || ary[1] == 2) && all(ary[-1] == 2)) {
            cat(count)
            break
        }
        max = 0
        for (p in primes) {
            if (p < a) {
                max = p
            } else if (p > a) {
                break
            }
        }
        ary[pos] = max
        sum = sum - max
        pos = pos + 1
        repeat {
            if (sum <= max) {
                ary[pos] = sum
                lastpos = pos
                break
            } else {
                ary[pos] = max
                sum = sum - max
            }
            pos = pos + 1
        }
        count = count+(ary[pos] %in% primes)
    }
}

system.time(f(40)) # 302, 0.073 sec.
system.time(f(140)) # 466711, 3.557 sec.
> system.time(f(250))
87778708   ユーザ   システム       経過  
   790.520     23.259    808.163

コメント
この記事をはてなブックマークに追加

◯はぴったり☓は無し

2017年06月01日 | ブログラミング

◯はぴったり☓は無し


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

【概要】
26×26のマス目に、◯と☓が配置されています。
数 n を指定します。マス目に沿った矩形のうち、◯をちょうど n 個含み、☓を含まない矩形として、最大となる矩形の面積を求めて下さい。
例えば、下図の場合、緑に塗られた部分が最大面積の矩形の例になります。





【入出力】
入力は、
2 Ip,Ni,Wl,Sl,Ih Cr,Lv,Pu,Uf,Hd
のようになっています。空白区切りで順に、n、◯のマスの座標、☓のマスの座標です。
一つ一つの座標はコンマで区切って並べられています。
座標は、x座標とy座標が区切り文字なしで並べられています。
(上記の入力が上図に対応しています)

出力は、
220
のように出力してください。
10進数で最大の面積を出力して下さい。
ただし、◯をちょうど n 個含み、☓を含まない矩形を作れない場合は
-
を出力して下さい。



【例】
入力
2 Ip,Ni,Wl,Sl,Ih Cr,Lv,Pu,Uf,Hd
出力
220

入力
7 Fl,Mi,Jl,Fp,Aq,Bm,Hn,Gz,Su,Fs Ul,Ko,Se,Xx,Jr,Xa,Wn,Jj,Hw,Zb
出力
-

入力
2 Xm,Po,Kl,Dv,Ri,Zc,Lz,Yz,Ev,Ay Nh,Bc,Vc,Ok,Hm,Lw,Hz,Rv,Mv
出力
184

【補足】
    •    不正な入力に対処する必要はありません。
    •    マス目に沿った矩形のみを考えます。つまり、傾いた矩形のことは考えません。
    •    x 座標は大文字のアルファベット、y座標は小文字のアルファベットです。
    •    ◯の数、☓の数 は、いずれも 20 個を超えることはありません。

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

素直に書いてみる。さいわいなことに,R では行列操作が容易である。
実行時間も,予想に反して十分に速い。

ff = function(s) {
    g = function(s) {
        s = unlist(strsplit(gsub(",", "", s), ""))
        s = matrix(sapply(s, function(S) utf8ToInt(S) %% 32), byrow=TRUE, ncol=2)
        s
    }
    tbl.o = tbl.x = matrix(0, 26, 26)
    s = unlist(strsplit(s, " "))
    n = as.integer(s[1])
    tbl.o[g(s[2])] = 1 # "o", 転置してもしなくても同じ結果になる
    tbl.x[g(s[3])] = 1 # "x", 転置してもしなくても同じ結果になる
    Max = 0
    for (iBegin in 1:25) {
        for (jBegin in 1:25) {
            for (iEnd in iBegin:26) {
                for (jEnd in jBegin:26) {
                    Matrix =
                    if (sum(tbl.x[iBegin:iEnd, jBegin:jEnd]) != 0) {
                        break
                    } else if (sum(tbl.o[iBegin:iEnd, jBegin:jEnd]) == n) {
                        Max = max(Max, (iEnd-iBegin+1)*(jEnd-jBegin+1))
                    }
                }
            }
        }
    }
    cat(ifelse(Max == 0, "-", Max))
}


if (0) {
    f("1 Bb Ab,Ba,Cb,Bc") # 1
    f("5 Oh,Be,Af,In,Eg,Rl Aa") # 650
    f("2 Ky,Zd,Yi,Av,Tk,Lz,Jk,Vx,Ga,Um,Ho Yr,Wc,Cb,Tf,Io,Bk,Yh,Yl,Bp,Qf,Ur") # 198
    f("1 Le,Dq,Qa,Qs,Sl,Xa,Nf,Qb,Ur,Sc,Ei,Mq Kw,Qe,Rv,Ry,Ih,Aq,Jb,Px,Yx,Lu,Kq,Qm") # 154
    f("3 Bl,Aq,Vl,Iu,Iy,Om,Te,Js,Fu,Xj,Kr,Ja,Nm He,Ki,Yu,Mr,Ua,Vw,Ha,Xy,Bv,Tp,Lw,Jr,Th") # 147
    f("0 Zy,Ze,Va,Yn,Hb,Cv,Co,Kh,Ml,Wh,Zr,Vh,Mm,Vj Hc,Pw,Ne,Iu,Jt,If,Wm,Dy,Uc,Lx,Xs,Sa,Hv,Ao") # 136
    f("2 Dn,Ve,Cf,Rh,Jg,Na,Bh,Ad,Xz,To,Fw,Ml,Bp,Vd,Go Py,Ol,Px,Qc,Bg,Ss,Vm,Xr,Eh,Kz,Dr,Kc,Tb,Vu,Ov") # 154
    f("4 Mg,Qb,Ae,Wo,Fg,Ke,Zx,Na,Us,Ky,Zm,Mi,Ls,Py,Ye,Ya Ux,Kj,Fo,Jw,Ug,Mt,Aw,Tb,El,Oo,Rv,Ri,Zd,Am,Bu,Il") # 126
    f("3 Ti,Oq,Wy,Dz,Xb,Ys,Mk,Ym,Ae,Ii,Wu,Ol,Ta,Mm,Eq,Vs,Cg Sa,Ub,Vf,Wv,Zf,No,Up,Zo,Ws,Bb,Uy,Yn,Xv,Yh,Ob,Zu,Gt") # 190
    f("1 Tv,Sg,Js,Lb,Mu,Sz,Za,Pl,It,Bs,Cl,Bf,Ik,Du,Te,Gc,Ge,Ub Kh,Mb,La,Dz,Wa,Jg,Ra,Ca,Rm,Yo,Um,Uz,Lo,Zn,We,Bb,Vv,Gw") # 104
    f("2 Pn,We,Au,Wz,Nc,Jr,Rr,Og,Yd,Sk,Zn,Fj,Ds,Nw,Rd,Sj,Zm,Ll,Mt Dx,Bt,Xo,Tg,Iv,Kp,Oa,Av,Ve,Yx,Nb,Ku,Vr,Wl,Gr,Gf,Md,Sd,Uy") # 126
    f("9 Lv,Nd,Jw,Ps,Br,Dg,Vq,Xs,Pj,Nw,Mn,Ce,Te,Ss,Mv,Tu,Rk,Xb Eo,Gg,Nz,Mo,Wp,Pk,Jn,Os,No,Ey,Vz,Uf,Xk,Pd,Iy,Lo,Zd,Pg,Gl,Nx") # -
} else {
    f(readLines(file("stdin", "r")))
}

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

awk で書くと,長くなるし,とても時間が掛かる

{
    f($0) # コンソールから文字列を入力し,関数を呼ぶ
}

function charToInt(s) {
    return index("ABCDEFGHIJKLMNOPQRSTUVWXYZ", toupper(s))
}
           
function g(s, mark,     k, t, i) {
    gsub(",", "", s)
    k = split(s, t, "")
    for (i = 1; i < k; i += 2) {
        tbl[charToInt(t[i]), charToInt(t[i+1])] = mark
    }
}

function f(S,     i, j, n, Max, iBegin, jBegin, iEnd, jEnd, xs, os, area) {
    for (i = 1; i
        for (j = 1; j
            tbl[i, j] = "."
        }
    }
    split(S, s, " ")
    n = s[1]
    g(s[2], "o")
    g(s[3], "x")
    Max = 0
    for (iBegin = 1; 25 >= iBegin; iBegin++) {
        for (jBegin = 1; 25 >= jBegin; jBegin++) {
            for (iEnd = iBegin; 26 >= iEnd; iEnd++) {
                for (jEnd = jBegin; 26 >= jEnd
                    xs = os = 0
                    for (i = iBegin;  iEnd >= i; i++) {
                        for (j = jBegin; jEnd >= j; j++) {
                            if (tbl[i, j] == "o") {
                                os++
                                if (os > n) break
                            }
                            else if (tbl[i, j] == "x") {
                                xs = 1
                                break
                            }
                        }
                        if (xs == 1 || os > n) break
                    }
                    if (xs == 1 || os > n) break
                    else if (os == n) {
                        area = (iEnd-iBegin+1)*(jEnd-jBegin+1)
                        Max = area > Max ? area : Max
                    }
                }
            }
        }
    }
    print Max == 0 ? "-" : Max
}

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

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(); // コンソールから文字列を入力し,
        f(line);               // 関数を呼ぶ
    }

    static String[][] g(String s, String[][] tbl, String mark) {
        int k, i;
        char[] t;
        s = s.replace(",", "");
        t = s.toCharArray();
        k = t.length;
        for (i = 0; i < k; i += 2) {
            tbl[t[i] % 32 - 1][t[i + 1] % 32 - 1] = mark;
        }
        return tbl;
    }

    static void f(String S) {
        int i, j, n, Max, iBegin, jBegin, iEnd, jEnd, xs, os, area;
        String[] s;
        String[][] tbl = new String[26][26];
        for (i = 0; i < 26; i++) {
            for (j = 0; j < 26; j++) {
                tbl[i][j] = ".";
            }
        }
        s = S.split(" ");
        n = Integer.parseInt(s[0]);
        tbl = g(s[1], tbl, "o");
        tbl = g(s[2], tbl, "x");
        Max = 0;
        for (iBegin = 0; iBegin < 25; iBegin++) {
            for (jBegin = 0; jBegin < 25; jBegin++) {
                for (iEnd = iBegin; iEnd < 26; iEnd++) {
                    for (jEnd = jBegin; jEnd < 26; jEnd++) {
                        xs = os = 0;
                        for (i = iBegin; iEnd >= i; i++) {
                            for (j = jBegin; jEnd >= j; j++) {
                                if (tbl[i][j] == "o") {
                                    os++;
                                    if (os > n)
                                        break;
                                } else if (tbl[i][j] == "x") {
                                    xs = 1;
                                    break;
                                }
                            }
                            if (xs == 1 || os > n)
                                break;
                        }
                        if (xs == 1 || os > n)
                            break;
                        else if (os == n) {
                            area = (iEnd - iBegin + 1) * (jEnd - jBegin + 1);
                            Max = area > Max ? area : Max;
                        }
                    }
                }
            }
        }
        System.out.println(Max == 0 ? "-" : Max);
    }

}





コメント
この記事をはてなブックマークに追加

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

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



コメント
この記事をはてなブックマークに追加