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

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

締め切りが 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 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書式を解釈しよう

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 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 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;
            }
        }
    }
}

スミス数

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

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)

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

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 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 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 では行列操作が容易である。
実行時間も，予想に反して十分に速い。

f = 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);
    }

}