極めよプログラミング道！【実力判定：Aランク】その２
締め切りが 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 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 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 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 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 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 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 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 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 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 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.
PVアクセスランキング にほんブログ村
