裏 RjpWiki

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

実力判定:Aランク-その2

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

極めよプログラミング道!【実力判定:Aランク】その2

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


【問題】
1階は1部屋、2階は1部屋、3階は2部屋、4階は3部屋、5階は5部屋、6階は8部屋、7階は13部屋と、増えていく塔があります。
3階以降は、下の2つの階にある部屋数の合計となります。ただし、部屋数が16以上になった場合は、合計を16で割った余りとなります。
ある階数が示された場合、その階に何部屋あるのか答えてください。
提示される階数は、1から1000000000の範囲とします。

【入力】
標準入力から、複数行のデータが与えられます。1行のデータが、1セットの数字になります。
1セットの数字は、1つの階数の数字です。

【出力】
1行ずつ計算して、答えとなる数字を1行ごと標準出力に出力します。

【入出力サンプル】
Input
4
5
6
8
 
Output
3
5
8
5
 
==========================================

周期24とは,短すぎるだろ。列挙しちゃうぞ。

g = function(n) {
    a = c(1, 1, 2, 3, 5, 8, 13, 5, 2, 7, 9, 0, 9, 9, 2, 11, 13, 8, 5, 13, 2, 15, 1, 0)
    cat(sprintf("%i\n", a[(n-1)%%24+1]))
}
arg = scan(file("stdin", "r"))
junk = sapply(arg, g)


コメント

実力判定:Sランク

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

実力判定:Sランク

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

【問題】
0から9の整数を、縦横それぞれN個並べた四角形があります。
左上から右下に、右あるいは下へと移動しながら、数を足していきます。
複数ある経路のうち、最小合計値となる経路をたどった場合の、合計値を答えてください。
ただし、Nは、2≦N≦20 の範囲の整数とします。# 20 ではなく 1000 だ!
 

567
133
502
上記の場合の全経路と合計値。
route: 56732, sum: 23
route: 56332, sum: 19
route: 56302, sum: 16
route: 51332, sum: 14
route: 51302, sum: 11
route: 51502, sum: 13
上記の場合の、最小合計値となる経路の図示。
567
133
502
最小合計値は「11」。
 
【入力】
標準入力から、複数行のデータが与えられます。縦横同じ文字数で、1つの正方形が作られます。
【出力】
最小合計値となる経路をたどった場合の合計値を、標準出力に出力します。
【入出力サンプル】
Input
567
133
502
 
Output
11
 
================================

R では簡単に書けるが,時間制限に引っかかる

f = function(s) {
    x = t(sapply(s, function(t) as.integer(unlist(strsplit(t, "")))))
    n = nrow(x)
    x[1:n, 1] = cumsum(x[1:n, 1])
    x[1, 1:n] = cumsum(x[1, 1:n])
    for (i in 2:n) {
        for (j in 2:n) {
            x[i, j] = x[i, j] + min(x[i-1, j], x[i, j-1])
        }
    }
    x[n, n]
}

cat(f(readLines(file("stdin", "r"))))

Java で書き直して OK となる

import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        int i, m;
        int n = 0;
        int[][] x = new int[1000][1000];

        Scanner cin = new Scanner(System.in);
        String line;
        while (cin.hasNextLine()) {
            line = cin.nextLine();
            if (line.length() == 0) {
                break;
            }
            String[] ch = line.split("");
            m = ch.length - 1;
            for (i = 0; i < m; i++) {
                x[n][i] = Integer.parseInt(ch[i + 1]);
            }
            n++;
        }
        System.out.println(f(x, n));
    }

    static int f(int[][] x, int n) {
        int i, j;
        for (i = 1; i < n; i++) {
            x[i][0] += x[i - 1][0];
            x[0][i] += x[0][i - 1];
        }
        for (i = 1; i < n; i++) {
            for (j = 1; j < n; j++) {
                x[i][j] += Math.min(x[i - 1][j], x[i][j - 1]);
            }
        }
        return x[n - 1][n - 1];
    }

}


コメント

実力判定:Aランク

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

実力判定:Aランク

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

【問題】
1から1,000,000までの整数の範囲で、連続する2値を合計します。
2値の合計が、整数Nの倍数になる組み合わせを、数えてください。
ただし、整数Nは、2≦N≦1,000 の範囲とします。


整数Nが11の場合、「5, 6(合計は11)」、「16,17(合計は33)」……という組み合わせが、整数Nの倍数になります。
また、連続する2値の最小は「1, 2(合計は3)」、最大は、「999999, 1000000(合計は1999999)」になります。

【入力】
標準入力から、複数行のデータが与えられます。1行のデータが、1つの整数Nになります。

【出力】
1行ずつ処理を行ない、その答えを1行ごと標準出力に出力します。

【入出力サンプル】
Input
307
456
545
165

Output
3257
0
1835
6061

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

1000行のテストデータがあるんだけど,その中に同じ値が複数個ある。
テストデータの準備としては,漫然としており,だらしない。

期待される結果と違うといわれたのであるが,テストデータがあまりにも多いので,どれが間違えているのか(あるいは,プログラムに不備があるのか)なかなかわからなかった。
結果としては,答えが 200000 となる場合に R では 2e+5 と出力されることがあるのが原因であった(options(scipen=100) とでもしておけばよいのだが)。

f = function(N) {
    invisible(sapply(N, function(n) {
        if (n %% 2 == 0) {
            m = 0
        } else {
            m = (1999999 %/% n + 1) %/% 2
        }
        options(scipen=100)
        cat(m, "\n", sep="")
    }))
}
f(scan(file("stdin", "r")))

より簡単に書くとこうなる。

f = function(N) {
    options(scipen=100)
    cat((ifelse(N %% 2, 1999999, 0) %/% N + 1) %/% 2, sep="\n")
}
f(scan(file("stdin", "r")))

コメント

実力判定:Cランク

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

実力判定:Cランク

締め切りが 2017/12/31 10:00 AM なので,その 1 分後に投稿されるように予約
きっと,締め切りは,再来年,再々来年...と繰り延べられるのだろうけど

【問題】

「0123456789」の10枚のカードの内、4枚のカードが提示されます。

通常は、「最も数値が大きなカード」が勝利者のカードです。
4枚の中に0があれば、「0以外で最も小さなカード」が勝利者のカードです。

勝利者のカードの数値を割り出してください。

【入力】

標準入力から、複数行のデータが与えられます。1行のデータが、1セットのゲームになります。

1行のデータは、数字4文字の文字列になります。この1文字ずつが、1枚のカードになります。

【出力】

1行ずつ結果を判定して、その答えとなる数字を、1行ごと標準出力に出力します。
 
【入出力サンプル】

Input

1234
6745
0149
3705

Output

4
7
1
3

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

R

f = function(S) {
    for (s in S) {
        s = as.integer(unlist(strsplit(s, "")))
        i = which(s == 0)
        if (length(i) > 0) {
            x = min(s[-i])
        } else {
            x = max(s)
        }
        cat(x, "\n", sep="")
    }
}
f(readLines(file("stdin", "r")))

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

AWK

awk '{
    split($0, x, "")
    Min = 100
    Max = -100
    zero = 0
    for (i = 1; 4 >= i; i++) {
        if (x[i] == 0) {
            zero = 1
        }
        else {
            Min = Min < x[i] ? Min : x[i]
            Max = Max > x[i] ? Max : x[i]
        }
    }
    if (zero == 1) {
        print Min
    }
    else {
        print Max
    }
        
}
'

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

Perl

use strict;
use warnings;
use utf8;
use List::Util qw/max min/; # min, max 関数を使うため

my ($line, $i, @char, $Min, $Max, $zero);

while (defined(my $line = )) {
    #    print $line;
    @char = split(//, $line);
    $Min = 10;
    $Max = -10;
    $zero = 0;
    for ($i = 0; $i < 4; $i++) {
        if ($char[$i] == 0){
            $zero = 1;
        }
        else {
            $Min = min($Min, $char[$i]);
            $Max = max($Max, $char[$i]);
        }
    }
    if ($zero) {
        print $Min, "\n";
    }
    else {
        print $Max, "\n";
    }
}

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

VB.net

imports System
module Crank
    sub Main()
        dim line as String
        dim m as Integer
        dim Min, Max, ans as Integer
        dim zero as Boolean
    for i as integer = 1 to 100
            line = Console.ReadLine() ' コンソールから入力
               Min = 10
            Max = -10
            zero = False
            for i as integer = 1 to 4
                   m = Integer.Parse(mid(line, i, 1)) ' 文字列を整数に変換
                    if (m = 0) then
                           zero = True
                    else
                        Min = Math.min(Min, m)
                        Max = Math.max(Max, m)
                    end if
            next
            if (zero) then
                ans = Min
            else
                ans = Max
            end if
            Console.WriteLine(ans) ' コンソールに出力 改行しないなら Console.Write()
        next
    end sub
end module

コメント

実力判定:Bランク

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

実力判定:Bランク

締め切りが 2017/12/31 10:00 AM なので,その 1 分後に投稿されるように予約
きっと,締め切りは,再来年,再々来年...と繰り延べられるのだろうけど

【問題】
20桁の数字が提示されます。
一番左の桁を先頭として、右の桁へと順に見ていきます。
そして、隣り合った数が連続する数だった場合は、その双方を削除して先頭に戻ります。
最終的に、削除ができなくなった時点で数字を出力してください。


「95422357545868773174」→「95422357545868773174」→
「922357545868773174」→「922357545868773174」→
「9257545868773174」→「9257545868773174」→
「92575868773174」→「92575868773174」→
「925758673174」→「925758673174」→
「9257583174」(削除ができなくなったので、これが答え)

【入力】
標準入力から、複数行のデータが与えられます。1行のデータが、1つの20桁の数字になります。
 
【出力】
1行ずつ処理を行ない、その答えを1行ごと標準出力に出力します。
 
【入出力サンプル】
Input
95422357545868773174
24566191298259441958
34757881545564825469
86423251489513547814

Output
9257583174
26619259441958
75818269
8642511314

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

R による例解の一つ

f = function(S) {
    invisible(sapply(S, function(s) {
        x = as.integer(unlist(strsplit(s, "")))
        repeat {
            n = length(x)
            found = FALSE
            if (n == 1) break
            for (i in 1:(n - 1)) {
                if (abs(x[i] - x[i + 1]) == 1) {
                    found = TRUE
                    break
                }
            }
            if (!found) break
            x = x[-(i + 0:1)]
        }
        cat(paste(x, collapse = ""), "\n", sep = "")
    }))
}
f(readLines(file("stdin", "r")))

コメント

切手の選び方は何通り?

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

切手の選び方は何通り?

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

設問

現在、普通切手は以下の19種類の金額が発売されています。
[1, 2, 3, 5, 10, 20, 30, 50, 62, 82, 92, 100, 120, 140, 205, 280, 310, 500, 1000]
※それぞれ、単位は円
(参考:日本郵便)

これらの切手をそれぞれ1枚ずつ持っているとき、ある金額を作る切手の選び方が何通りあるかを求めます。
※同じ金額でデザインが異なる切手はありますが、一つの金額に対して1枚ずつ持っているものとします。

例えば、70円を貼りたい場合、以下の5通りがあります。
(1) 62 + 5 + 3
(2) 62 + 5 + 2 + 1
(3) 50 + 20
(4) 50 + 10 + 5 + 3 + 2
(5) 30 + 20 + 10 + 5 + 3 + 2

標準入力から貼りたい金額が与えられたとき、その切手の選び方が何通りあるかを求め、標準出力に出力してください。
なお、入力される金額は3012円以下の正の整数とします。

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

標準出力
5

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

この問題は,R で制限時間内に解けた。bincombinations の再掲を除けば,簡単至極。

f = function(n) {
  bincombinations = function (p) {
    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
  }
  a = bincombinations(19)
  b = c(1,2,3,5,10,20,30,50,62,82,92,100,120,140,205,280,310,500,1000)
  x = a %*% b
  cat(sum(x == n))
}


# f(scan(file("stdin", "r")))

f(70) # 5
f(100) # 11
f(543) # 144
f(1234) # 240
f(3000) # 1

system.time(f(100)) # 0.103 s

Python3 だと,f(100) が 3.470 s で,とんでもなく遅い。

import numpy as np
import itertools as it

def f(n):
    a = list(it.product([0, 1], repeat=19))
    b = [1,2,3,5,10,20,30,50,62,82,92,100,120,140,205,280,310,500,1000]
    x = np.dot(a, b)
    print(sum(x==n))

f(70) # 5
f(100) # 11
f(543) # 144
f(1234) # 240
f(3000) # 1

import time
a = time.time(); f(100); time.time()-a # 3.470 s

コメント

回文数の中央値

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

回文数の中央値

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

【概要】
数の範囲を指定します。
その範囲内にある回文数( seeWikipedia - 回文数) の、真ん中の値を計算してください。

例えば下表の通りです:
値の範囲     回文数                真ん中の値
99〜120     99,101,111          101
200〜232     202,212,222,232    212,222
【入出力】
入力は
99,120
のように下限と上限がコンマ区切りで並んでいます。
下限以上で、上限以下の回文数の真ん中の値を求めてください。

出力も普通に10進数です。
範囲内にある回文数が奇数個の場合には、中央の値はひとつに決まるのでそれを。
偶数個の場合にはぴったり中央の値はありませんので、中央付近の2つの値をコンマ区切りで昇順に出力してください。
ただし、範囲内に回文数がひとつもない場合は"-"を出力してください。

【例】
入力            範囲内の回文数                    出力
99,120         99, 101, 111                    101
200,232        202,101,111,202,212,222,232     212,222
123,124                                        -
1234,1400      1331                            1331

【補足】
・ 不正な入力に対処する必要はありません。
・ 0 < 下限 < 上限 ≦ 一千兆 です。

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

g = function(n, odd) {
    a = unlist(strsplit(as.character(n), ""))
    b = rev(a)
    if (odd)
        b = b[-1]
    as.numeric(sprintf("%s%s", paste(a, collapse = ""), paste(b, collapse = "")))
}

h = function(begin, end) {
    options(scipen=100)
    ans = NULL
    for (i in begin:end) {
        a = unlist(strsplit(as.character(i), ""))
        if (all(a == rev(a))) {
            ans = c(ans, i)
        }
    }
    n = length(ans)
    if (n == 0) {
        cat("-")
    } else if (n %% 2 == 1) {
        cat(ans[n%/%2+1])
    } else {
        cat(sprintf("%i,%i", ans[n/2], ans[n/2+1]))
    }
}

concatenate = function(...) {
    paste(c(...), sep = "", collapse = "")
}

Begin = function(d) {
    if (9 >= d) {
        return(d)
    }
    s = d
    repeat {
        s = unlist(strsplit(as.character(s), ""))
        n = length(s)
        half = n%/%2
        odd = n%%2
        left = concatenate(s[1:half])
        middle = ifelse(odd, s[half + 1], "")
        right = concatenate(s[half:1])
        x = as.numeric(concatenate(left, middle, right))
        if (x >= d) {
            break
        }
        t = unlist(strsplit(as.character(as.numeric(concatenate(left, middle)) + 1), ""))
        if (odd == 0) {
            s = concatenate(t, rev(t))
        } else {
            s = concatenate(t, rev(t)[-1])
        }
    }
    x
}

End = function(d) {
    options(scipen=100)
    if (log10(d) == floor(log10(d))) {
        d = d-1
    }
    s = d
    repeat {
        s = unlist(strsplit(as.character(s), ""))
        n = length(s)
        half = n%/%2
        odd = n%%2
        left = concatenate(s[1:half])
        middle = ifelse(odd, s[half + 1], "")
        right = concatenate(s[half:1])
        x = as.numeric(sprintf("%s%s%s", left, middle, right))
        if (d >= x) {
            break
        }
        t = unlist(strsplit(as.character(as.numeric(concatenate(left, middle)) - 1), ""))
        if (odd == 0) {
            s = concatenate(t, rev(t))
        } else {
            s = concatenate(t, rev(t)[-1])
        }
    }
    x
}

f = function(begin, end) {
    order = log10(end)
    if (100 >= end-begin) {
        h(begin, end)
    } else if (begin == 1 && order == floor(order) && order < 4) {
        cat( c("5", "9,11", "454,464")[order])
    } else if (begin == 1 && order == floor(order)) {
        if (order %% 2 == 1 && order >= 5) {
            ans1 = ans2 = concatenate("45", rep(0, order-4), "54")
        } else if (order %%2 == 0 && order >= 4) {
            ans1 = ans2 = concatenate("9", rep(0, order-3), "9")
        }
        half = nchar(ans2)%/%2+1
        substr(ans2, half, half+1) = "1"
        cat(ans1, ans2, sep=",")
    } else {
        b = Begin(begin)
        bs = as.character(b)
        bs.nchar = nchar(bs)
        bs.odd = bs.nchar %% 2
        bs.half = bs.nchar %/% 2
        if (bs.odd == 0) {
            b2 = as.numeric(substr(bs, 1, bs.half))
        } else {
            b2 = as.numeric(substr(bs, 1, bs.half+1))
        }
        e = End(end)
        es = as.character(e)
        es.nchar = nchar(es)
        es.odd = es.nchar %% 2
        es.half = es.nchar %/% 2
        if (es.odd == 0) {
            e2 = as.numeric(substr(es, 1, es.half))
        } else {
            e2 = as.numeric(substr(es, 1, es.half+1))
        }
        if ((e2 - b2 + 1) %% 2 == 1) {
            ans1 = g((b2+e2) %/% 2, es.nchar %% 2)
            cat(ans1)
        } else {        
            ans1 = g((b2+e2) %/% 2, es.nchar %% 2)
            ans2 = g((b2+e2) %/% 2+1, es.nchar %% 2)
            if (ans2 > end) {
                cat("-")
            } else {
                cat(sprintf("%s,%s", ans1, ans2))
            }
        }
    }
}

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

f(1, 2) #  1,2
f(9, 10) #  9
f(10, 11) #  11
f(10, 12) #  11
f(123456, 124000) #  -
f(28228056190, 77331569708) #  52779797725,52779897725
f(174517247652, 237309752247) #  205912219502,205913319502
f(468178194014, 4647762198268) #  2557969697552,  2557970797552
f(29904128799113, 50953812820424) #  40428977982404
f(495630518704001, 919719574970542) #  707675040576707
f(1, 1e+15) # 450000000000054,450000010000054
f(999999999999999, 1e+15) # 999999999999999

コメント

目盛りの消えた円

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

目盛りの消えた円

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

設問

有名なパズル問題の一つに「Spacer Ruler(Wikipedia)」があります。
「目盛りの消えたものさし」とも言われ、できるだけ少ない目盛りの数で1cm単位の整数を測ります。

例えば、1cm刻みで目盛りが付いている長さ10cmのものさしの場合、左図の下側にある4つの目盛りが残っていれば、それを組み合わせて図のように1cm~10cmまで測ることが可能です。

これを右図のように円形で考えてみます。
円周を n 個に分割した目盛りのうち、できるだけ多くの目盛りを消して1~nまでを測ります。
例えば、n = 10 のとき、右図の赤色の4点だけ残すと1~nまでを測れます。
3点だけ残して、1~10までを測ることはできませんので、少なくとも4点が必要です。

標準入力から n が与えられたとき、残った目盛りの数が最も少なくなる場合を求め、その残った個数を標準出力に出力してください。
なお、n は30以下の整数とします。

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

標準出力
4

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

簡単なプログラムを作って,n が小さいときの答えを求め,規則性を調べる。

check = function(n, x) {
  x = c(x, n + x)
  m = length(x)
  a = matrix(-1, m, m)
  for (i in seq_along(x)) {
    for (j in seq_along(x)) {
      a[i, j] = (x[j] - x[i]) %% n
    }
  }
  all(1:(n - 1) %in% a[upper.tri(a)])
}

bincombinations = function (p) {
  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) {
  p = bincombinations(n)
  Sum = rowSums(p)
  o = order(Sum)
  p = p[o,]
  for (i in 2:nrow(p)) {
    x = which(p[i,] == 1)
    ans = check(n, x)
    if (ans) {
       cat(length(x), ":", ans, "  ", x, "\n")
       break
     }
  }
}

オンライン整数列大辞典にあるかと思ったら,やはりあった。
A283297 The smallest cardinality of a difference-basis in the cyclic group of order n.
そのままだ。
ただし,一般項は示されていない。
a(n) >= (1+sqrt(4n-3))/2 が挙げられているので,a(n) = ceiling((1+sqrt(4*n-3))/2) とすると n = 20, 29, 30 のとき以外は正しい答えになる。

そこで,

f = function(n) cat(ceiling((1+sqrt(4*n-3))/2+(n==20)))
f(scan(file("stdin", "r")))

ただ,それじゃあんまりなので,先のプログラムをチューニングした。
f(28) は当方では 1 秒を切るが,先方では 1 秒を超える。

f = function(n) {
  n1 = n-1
  for (k in ceiling((1+sqrt(4*n-3))/2):n) {
    p = combn(n, k)
    i2 = rep(1:k, each=k)
    j2 = rep(1:k, k)
    kk = i2 != j2
    i2 = i2[kk]
    j2 = j2[kk]
    for (i in 2:ncol(p)) {
      x = p[, i]
      a = logical(n1)
      a[(x[j2] - x[i2]) %% n] = TRUE
      if (all(a)) {
        return(cat(k))
      }
    }
  }
}
#f(scan(file("stdin", "r")))

# f(6)  # 3
# f(10) # 4
# f(14) # 5
# system.time(f(19)) # 5, 0.011s
# system.time(f(20)) # 6, 0.115s
# system.time(f(21)) # 5, 0.024s
# system.time(f(22)) # 6, 0.093s
# system.time(f(23)) # 6, 0.110s
# system.time(f(28)) # 6, 0.397s
# system.time(f(30)) # 7, 5.789s

コメント

「ペア・ドロップ」問題

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

「ペア・ドロップ」問題

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

n を自然数とします。1 から n までの自然数が 1 つずつ書かれた n 枚のカードが 2 組あります。
 
これら 2n 枚のカードをよく混ぜ、A と B の 2 人に n 枚ずつ配ります。
A と B は、それぞれ自分の持ち札の中に番号が一致するカードがあればその 2 枚を捨てます。
 
捨てられるカードを全て捨てた後の A の持っているカードの枚数が k である確率を F(n, k) とします。
例えば F(1, 0)=0, F(1, 1)=1, F(2, 0)=1/3, F(2, 1)=0, F(2, 2)=2/3, F(4, 2)=24/35 です。
 
標準入力から、自然数 n と k (1 ≦ k ≦ n ≦ 100)が半角空白区切りで与えられます。
標準出力に 10^6×F(n, k) の整数部分の値を出力するプログラムを書いてください。
 
例えば、(n, k)=(2, 2) であれば 666666 と出力してください。
(n, k)=(4, 2) であれば 685714 と出力してください。
なお、全てのテストケースで、 10^6×F(n, k) の値とその最寄りの整数は 10^(-3) 以上離れていることが保証されています
 
===================================

末尾に掲載するプログラムで,n, k の小さい部分を求める。

n について和を求めたものは,オンライン整数列大辞典の A000984 Central binomial coefficients a(n) = (2n)! / (n!)^2 であるこ。
更に,A005430(0, 2, 12, 60, 280, 1260, ...)の a(n-1) が Sum_{k=0..floor(n/2)} k*C(n,k)*C(n-k,k)*2^(n-2*k) であることより,以下の短いプログラムを得る。

 f = function(n, k) {
  k = n %/% 2 - k %/% 2
  cat(floor(1e6 * choose(n, k) * choose(n-k, k) * 2^(n-2*k) / choose(2*n, n)))
}

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

f(2, 2) # 666666
f(4, 2) # 685714
f(5, 1) # 238095
f(13, 9) # 211187
f(30, 20) # 67130
f(41, 17) # 126481
f(80, 24) # 226
f(99, 47) # 137249

== g(n, k) の分布====

> g = function(n) {
+   a = combn(rep(1:n, 2), n)
+   a = apply(a, 2, function(x) {
+             b = table(x)
+             b = b[b == 1]
+             length(b)
+   })
+   table(a)
+ }
> g(1)
a
1
2
> g(2)
a
0 2
2 4
> g(3)
a
 1  3
12  8
> g(4)
a
 0  2  4
 6 48 16
> g(5)
a
  1   3   5
 60 160  32
> g(8)
a
   0    2    4    6    8
  70 2240 6720 3584  256

コメント

体積から考える直方体の組み合わせ

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

体積から考える直方体の組み合わせ

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

いずれの辺の長さも整数である3つの直方体を考えます。

その直方体の体積の和が与えられたとき、考えられる直方体の組み合わせが何通りあるかを求めてください。
(縦、横、高さを入れ替えたものは一つとカウントします。また、直方体の順番を入れ替えたものも一つとカウントします。)

例えば、体積の和が10のとき、直方体の縦,横,高さは以下の16パターンがあります。

No 一つ目の直方体 二つ目の直方体 三つ目の直方体
 1 1, 1, 1  1, 1, 1  1, 1, 8
 2 1, 1, 1  1, 1, 1  1, 2, 4
 3 1, 1, 1  1, 1, 1  2, 2, 2
 4 1, 1, 1  1, 1, 2  1, 1, 7
 5 1, 1, 1  1, 1, 3  1, 1, 6
 6 1, 1, 1  1, 1, 3  1, 2, 3
 7 1, 1, 1  1, 1, 4  1, 1, 5
 8 1, 1, 1  1, 2, 2  1, 1, 5
 9
 1, 1, 2  1, 1, 2  1, 1, 6
10 1, 1, 2  1, 1, 2  1, 2, 3
11 1, 1, 2  1, 1, 3  1, 1, 5
12 1, 1, 2  1, 1, 4  1, 1, 4
13 1, 1, 2  1, 1, 4  1, 2, 2
14 1, 1, 2  1, 2, 2  1, 2, 2
15 1, 1, 3  1, 1, 3  1, 1, 4
16 1, 1, 3  1, 1, 3  1, 2, 2
標準入力から体積の和が与えられるとき、直方体の組み合わせの数を標準出力に出力してください。
なお、体積の和は300以下の整数とします。

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

標準出力
16

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

R でも結構いいところまで行くが,Java には勝てない

ag = integer(300)

g = function(v) {
  count = 0
  for (i1 in 1:ceiling(v ^ (1 / 3))) {
    for (i2 in i1:v) {
      if (i1 * i2 > v) {
        break
      }
      i3 = v / (i1 * i2)
      if (i3 < i2) {
        break
      } else if (i3 == floor(i3)) {
        count = count + 1
        ag[count] = (i1 * 1000 + i2) * 1000 + i3
      }
    }
  }
  ag[1:count]
}

tbl = vector("list", 300)
for (i in 1:300) {
  tbl[[i]] = g(i)
}

f = function(v) {
  ah = matrix(0, 3000, 3)
  count = 0
  for (i1 in 1:ceiling(v / 3)) {
    lst1 = tbl[[i1]]
    for (i2 in i1:v) {
      if (i1 + i2 > v) {
        break
      }
      i3 = v - i1 - i2
      if (i3 < i2) {
        break
      }
      lst2 = tbl[[i2]]
      lst3 = tbl[[i3]]
      l1 = length(lst1)
      l2 = length(lst2)
      l3 = length(lst3)
      count2 = 0
      for (j1 in 1:l1) {
        for (j2 in 1:l2) {
          for (j3 in 1:l3) {
            mx = max(lst1[j1], lst2[j2], lst3[j3])
            mn = min(lst1[j1], lst2[j2], lst3[j3])
            me = lst1[j1] + lst2[j2] + lst3[j3] - mx - mn
            count2 = count2 + 1
            ah[count2, ] = c(mn, me, mx)
          }
        }
      }
      count = count + nrow(unique(ah[1:count2, , drop = FALSE]))
    }
  }
  cat(count)
}

# f(scan(file("stdin", "r")))

system.time(f(9)) # 11
system.time(f(10)) # 16
system.time(f(20)) # 133
system.time(f(64)) # 4563
system.time(f(100)) # 17251
system.time(f(300)) # 438379

コメント

半径が同じ円を重ならないように描く

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

半径が同じ円を重ならないように描く

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

設問
座標平面において、x軸上の点を中心とする円をいくつか描くことを考えます。
ただし、中心となるx軸上の点のx座標はいずれも m 以下の「素数」とします。
これらの点の中から中心とする点を n 個選び、直径が同じ円を描くとき、いずれの円も重ならないようにします。
(円が外接するときは問題ないものとします)

例えば、m = 30, n = 4 のとき、以下の位置を中心にする円を描くと、いずれの円も重なりません。
中心:(2, 0), (11, 0), (19, 0), (29, 0)

この条件を満たす円を描いたとき、直径が最大になるのは上記の図のときで、その直径は8です。

標準入力から m と n が与えられたとき、直径が最大となる場合を求め、その「直径」を標準出力に出力してください。
なお、m, n はいずれも正の整数とし、m < 1,000,000を満たすものとします。

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


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

R でのプログラムは f(999999, 1111) が 0.450 秒であるが,回答先のシステムが遅くて 1 秒の時間制限に引っかかる。
なお,Python3 では 1.5 秒かかる。
そこで,最終的には Java で書いて O.K. という,いつものパターン。

f = function(m, n) {
  divisor = function(n) {
    if (n %% 2 == 0) return(2)
    else if(n %% 3 == 0) return(3)
    maxitr = as.integer(sqrt(n))
    i = 1
    repeat {
      i = i+4
      if (i > maxitr) return(n)
      else if (n %% i == 0) return(i)
      i = i+2
      if (i > maxitr) return(n)
      else if (n %% i == 0) return(i)
    }
  }

  findPrev = function(k) {
    while (divisor(k) != k) {
      k = k-1
    }
    k
  }

  findNext = function(k) {
    if (k %% 2 == 0) k = k+1
    while (divisor(k) != k) k = k+2
    k
  }

  m = findPrev(m)
  n = n-1
  r = ((m-2) %/% (2*n))*2
  repeat {
    count = 0
    center = 2
    repeat {
      center = findNext(center+r)
      if (center > m) {
        break
      } else {
        count = count+1
        if (count == n) {
          break
        }
      }
    }
    if (m >= center) {
      break
    }
    r = r-2
  }
  cat(r)
}

#arg = scan(file("stdin", "r"))
#f(arg[1], arg[2])
system.time(f(30, 4)) # 8, 0.023 sec.
system.time(f(100, 8)) # 12, 0.001 sec.
system.time(f(1000, 49)) # 16, 0.001 sec.
system.time(f(12345, 210)) # 52, 0.012 sec.
system.time(f(999999, 1111)) # 890, 0.450 sec.


コメント