謹賀新年（2017年） 〜覆面算〜
http://quiz-tairiku.com/q.cgi?mode=view&no=18772
とび
ひのととり ー たとう
＋ ひのとり ー たび
＋ のように ー とりの
＋ とうとい ＋ ように
−−−−−−−−−−− −−−−−−−−−−
２０１７に ２９
定数はそのまま（他の文字がかぶっても構わない）
f = function() {
library(e1071)
a = permutations(10)-1
a = a[a[,1] != 0 & a[,2] != 0 & a[,3] != 0 & a[,10] != 0 & a[,5] != 0,]
a1 = a[,c(1,2,3,3,4)] %*% 10^(4:0)
a2 = a[,1:4] %*% 10^(3:0)
a3 = a[,c(2, 5:7)] %*% 10^(3:0)
a4 = a[,c(3,6,3,8)] %*% 10^(3:0)
a5 = 20170+a[,7]
b1 = a[,c(3,9)] %*% 10^(1:0)
b2 = a[,c(10,3,6)] %*% 10^(2:0)
b3 = a[,c(10,9)] %*% 10^(1:0)
b4 = a[,c(3,4,2)] %*% 10^(2:0)
b5 = a[, 5:7] %*% 10^(2:0)
i = which(a1+a2+a3+a4 == a5 & b1-b2-b3-b4+b5 == 29)
cat(sprintf("%7d\n%7d\n%7d\n+%6d\n--------\n%7d\n\n", a1[i], a2[i], a3[i], a4[i], a5[i]))
cat(sprintf("%7d\n-%6d\n-%6d\n-%6d\n+%6d\n--------\n%7d\n", b1[i], b2[i], b3[i], b4[i], b5[i], 29))
}
f()
12338
1238
2967
+ 3634
--------
20177
30
- 536
- 50
- 382
+ 967
--------
29
謹賀新年(2017年) 覆面算
http://quiz-tairiku.com/q.cgi?mode=view&no=18773
(1) きんが + しんねん = 2017 となり，2, 0, 1, 7 をすべて含むもの
(2) とりにく + とりにく + … + とりにく = やきとり
すなわち，n(とりにく) = やきとり
となり，解に 2, 9 両方が含まれるもの
----------------------------------------
f = function(x) {
library(e1071)
a = permutations(5)
a = apply(a, 1, function(y) c(2, 0, 1, 7, x)[y])
きんが = 10^(2:0) %*% a[c(1, 2, 3), ]
しんねん = 10^(3:0) %*% a[c(4, 2, 5, 2), ]
ans = きんが + しんねん == 2017
if (any(ans)) {
cat(sprintf("%6d\n+%5d\n------\n%6d\n", きんが[ans], しんねん[ans], 2017))
}
}
for (x in c(3:6, 8, 9)) {
f(x)
}
270
+ 1747
------
2017
g = function() {
library(e1071)
a = data.frame(permutations(10) - 1)
a = as.matrix(unique(a[a[, 1] != 0 & a[, 5] != 0, 1:6]))
w = 10^(3:0)
とりにく = a[, c(1:4)] %*% w
やきとり = a[, c(5, 6, 1, 2)] %*% w
for (i in seq_along(とりにく)) {
ans = which(1:9 * とりにく[i] == やきとり[i])
if (any(ans) && # n 「とりにく」 = 「やきとり」
ans %in% a[i, ] == FALSE && # ただし，n は「とりにくやき」に含まれない
all(c(2, 9) %in% c(a[i, ], ans))) { # また，2, 9 を含む
cat(sprintf("\n%6d\nx%5d\n------\n%6d\n", とりにく[i], ans, やきとり[i]))
}
}
}
g()
答えは一意に決まると書いてあいるが，そうではないようだ（やはり，「適切な」総当たりというのは必要）
1402 これを唯一の解としているが
x 7
------
9814
1809 他にも 4 通りの解がある
x 2
------
3618
1859
x 2
------
3718
3819
x 2
------
7638
2709
x 3
------
8127
10 桁の数字 n（すなわち 1000000000 ≦ n ≦ 9999999999） において，n^n の末尾の 3 桁が 777 になるのは，何個あるか
1 桁の数字でそのようなものは，0 個
2 桁の数字でそのようなものは，0 個
3 桁の数字でそのようなものは，1 個
4 桁の数字でそのようなものは，9 個
:
f = function(x) {
y = 1
for (i in 1:x) {
y = (y*x) %% 1000
}
y == 777
}
sum(sapply(0:9, f)) # 0
sum(sapply(10:99, f)) # 0
sum(sapply(100:999, f)) # 1
sum(sapply(1000:9999, f)) # 9
# sum(sapply(1000000000:9999999999, f)) # oh! no!
10 桁の数字でそのようなものは，90000000 個
スコットランドの高校生（16〜18歳）対象の数学問題
1匹のワニが20メートル上流の川の対岸にいる獲物に忍び寄ろうとしている。
ワニの移動速度は地上と水中では異なる。
図に示されているxメートル上流にある対岸のP地点へ向けてワニが泳いだ場合，獲物に到達するまでの移動時間が最小となる。
この所要時間は，以下の等式によって求められる。（引用者注:時間の単位は特に定める必要がないので省略し，無名数とする）
T(x) = 5*sqrt(36+x^2)+4*(20-x)
(a) (i) ワニが地上を移動しなかった場合の所要時間を求めよ。
(ii) ワニの泳いだ距離が最小だった場合の所要時間を求めよ。
(b) これらの両極端の2つの選択肢の中間に，所要時間を最小化するxの値が1つある。そのxの値を求めよ。
この問題を R を用いて解く。
まず，T(x) の図を描いておこう（0 ≦ x ≦ 20)
> T = function(x) 5*sqrt(36+x^2)+4*(20-x)
> x = seq(0, 20, by=0.01)
> y = T(x)
> plot(x, y, type="l")
(a) (i) 「ワニが地上を移動しなかった場合」というのは，川を斜めに渡ったということ。すなわち，x = 20 のときの T(x) が答え。
> T(0)
[1] 110
答え 110
(a) (ii) 「ワニの泳いだ距離が最小だった場合」というのは，川を垂直に渡ったということ。すなわち，x = 0 のときの T(x) が答え。
> T(20)
[1] 104.4031
答え 104.4031
(b) T(x) が最小になるときの x を求めるということは，T(x) の微分係数が 0 になるときの x を求めるということ。
> g = deriv(~5*sqrt(36+x^2)+4*(20-x), "x", function.arg="x")
> g # 微分係数の関数
function (x)
{
.expr2 <- 36 + x^2
.value <- 5 * sqrt(.expr2) + 4 * (20 - x)
.grad <- array(0, c(length(.value), 1L), list(NULL, c("x")))
.grad[, "x"] <- 5 * (0.5 * (2 * x * .expr2^-0.5)) - 4
attr(.value, "gradient") <- .grad
.value
}
微分係数のグラフを描いておこう。
> plot(x, attr(g(x), "gradient"))
> plot(x, attr(g(x), "gradient"), type="l")
> abline(h=0, v=8, col="red", lty=2) # 結果論ではあるが x = 8 のとき，微分係数が 0 になることを図示しておく
関数の最小値を求めるのは optimize 関数が使える
> optimize(g, lower=0, upper=20, tol = .Machine$double.eps) # deriv 関数の戻り値 g を与える場合
$minimum
[1] 8
$objective
[1] 98
attr(,"gradient")
x
[1,] -5.039269e-08
または
> optimize(T, lower=0, upper=20, tol=.Machine$double.eps) # もとの関数を与える場合
$minimum
[1] 8
$objective
[1] 98
いずれにせよ $minimum ＝ 8 が解である（最短時間は $objective = 98）。
なお，deriv 関数が返す導関数 5 * (0.5 * (2 * x * (36 + x^2)^-0.5)) - 4 が 0 になる値は，uniroot でも求められる。
> h = function(x) 5 * (0.5 * (2 * x * (36 + x^2)^-0.5)) - 4
> uniroot(h, lower=0, upper=20, tol=.Machine$double.eps)
$root
[1] 8
$f.root
[1] 0
$iter
[1] 8
$init.it
[1] NA
$estim.prec
[1] 2.993504e-05
$root = 8 が解である（そのとき，$f.root = 0 となる）
> h(8)
[1] 0
左右に行ったり来たり
締め切りが 2017/03/28 10:00 AM なので，その 1 分後に投稿されるように予約
設問
一列に n 個のマスが並んでおり、各マスには 1～(n-1) のいずれかの数字が書かれています。
この一列のマスに対して、書かれている数字の数だけ左右に移動します。
このとき、進む方向は「左」「右」を交互に繰り返します。
最初、左端から右向きにスタートして、右端のマスに到達するような数字の配置を考えます。
なお、右端のマスに到達した時点で終了するため、右端のマスは0とします。
また、左端のマスより左、右端のマスより右には移動できないため、そのような数字の配置はできないものとします。
例えば、以下のマスのように配置されていると、図のように移動します。
このように、右端に到達できる数字の配置のうち、すべてのマスでちょうど一度ずつ止まるものが何通りあるかを求めてください。
例えば、n = 6 の場合は、上記の左図の他に右図のようなパターンがあり、全部で5通りです。
なお、n は12以下の整数とします。
【入出力サンプル】
標準入力
6
標準出力
5
===============================
小さな n の場合の結果を計算する，以下のような簡単なプログラムを書き，既知の数列かどうか検索する。
check = function(n, nm1, p) {
location = integer(nm1)
i = 1
for (j in 1:nm1) {
location[i] = p[i]
i = i+location[i]*ifelse(j %% 2 == 1, 1, -1)
if (i < 1 || i > n) {
return(FALSE)
} else if (i == n) {
return(all(location != 0))
} else if (location[i] != 0) {
return(FALSE)
}
}
return(FALSE)
}
f = function(n) {
nm1 = n - 1
p = rep(1, nm1)
p[1] = 2
ptr = nm1
count = 0
repeat {
count = count+check(n, nm1, p)
p[ptr] = p[ptr] + 1
if (p[ptr] == n) {
temp = ptr
repeat {
temp = temp - 1
if (temp == 0) {
break
} else if (p[temp] < nm1) {
p[temp] = p[temp]+1
p[(temp+1):nm1] = 1
break
}
}
if (temp == 0 || p[1] == nm1) {
break
}
}
}
count
}
n が奇数の場合は F(n) = 0
R だと，n = 8 はかなり時間が掛かる。
Java でも，n = 10 までで，n = 12 は止めておこうという気になる。
n = 2, 4, 6, 8, 10 に対して，F(n) = 1, 5, 61, 1385
結果として，既知の数列である。
https://oeis.org/search?q=1%2C5%2C61%2C1385&language=japanese&go=%E6%A4%9C%E7%B4%A2
a(n) = Sum_{k = 0..2*n} Sum_{j = 0..k} (-1)^(n-j) *binomial(2*n+1,k-j)*(j+1/2)^(2*n)
これを取り込んだプログラム
f = function(n) {
s = 0
if (n%%2 == 0) {
n = n/2-1
for (k in 0:(2 * n)) {
for (j in 0:k) {
s = s + (-1)^(n - j) * choose(2 * n + 1, k - j) * (j + 0.5)^(2 * n)
}
}
}
options(scipen = 100)
cat(s)
}
f(4) # 1
f(5) # 0
f(6) # 5
f(8) # 61
f(10) # 1385
f(12) # 50521
f(14) # 2702765
f(16) # 199360981 であるが，計算誤差のため 199360916 になってしまう
gmp を使えばよい。
縦線と横線でマス目を塗る
締め切りが 2017/03/22 10:00 AM なので，その 1 分後に投稿されるように予約
【概要】
マス目をルールに従って黒く塗っていきます。
黒く塗られたマス目の数を数えてください。
【詳細】
マス目を塗る方法は、以下の二通りあります（以下、座標系はyが大きい方が上、xが大きい方が右です）：
方向を表す記号 状況
V 下から上に塗る（y座標が大きい方向に塗りすすめる）
H 左から右に塗る（x座標が大きい方向に塗りすすめる）
【入出力】
入力は
H,1,2,8 V,4,1,8 H,1,7,5 V,7,7,2
のようになっています。
塗り方が、空白区切りで並んでいます。
塗り方は、「方向を表す記号」「塗りはじめのマスのx座標」「塗りはじめのマスのy座標」「マスの数」が、コンマ区切りで並んでいます。
出力は、
21
のような感じです。
塗られている面積を10進数で普通に出力してください。
【例】
入力 出力
H,1,2,8 V,4,1,8 H,1,7,5 V,7,7,2 21 
V,3,9,4 H,0,4,13 H,4,10,2 V,8,2,11 29 
V,8,7,2 H,8,10,6 V,9,9,7 H,10,14,4 H,11,0,3 21 
【補足】
不正な入力に対処する必要はありません。
x座標・y座標 は、いずれも 0以上 一千万 以下の整数です。
長さ は、1以上 一千万 以下の整数です。
「塗り方」の個数は 十 個を超えることはありません。
=========================
f = function(s) {
s = matrix(unlist(strsplit(s, "[, ]")), 4)
x = as.integer(s[2, ])
y = as.integer(s[3, ])
n = as.integer(s[4, ])
t = s[1, ]
L = length(t)
for (i in 1:(L - 1)) {
for (j in (i + 1):L) {
if (t[i] == "H" && t[j] == "H") {
if (y[i] == y[j] && (x[j] >= x[i] || x[i] >= x[j] || (x[i] >= x[j] && x[j]+n[j] >= x[i]+n[i]))) {
x[i] = min(x[i], x[j])
n[i] = max(x[i]+n[i], x[j]+n[j])-x[i]
n[j] = 0
t[j] = ""
}
} else if (t[i] == "V" && t[j] == "V") {
if (x[i] == x[j] && (y[j] >= y[i] || y[i] >= y[j] || (y[i] >= y[j] && y[j]+n[j] >= y[i]+n[i]))) {
y[i] = min(y[i], y[j])
n[i] = max(y[i]+n[i], y[j]+n[j])-y[i]
n[j] = 0
t[j] = ""
}
}
}
}
count = sum(n)
for (i in 1:(L - 1)) {
for (j in (i + 1):L) {
if (t[i] == "H" && t[j] == "V") {
count = count - (x[j] >= x[i] && x[i] + n[i]-1 >= x[j] && y[i] >= y[j] && y[j] + n[j]-1 >= y[i])
} else if (t[i] == "V" && t[j] == "H") {
count = count - (x[i] >= x[j] && x[j] + n[j]-1 >= x[i] && y[j] >= y[i] && y[i] + n[i]-1 >= y[j])
}
}
}
cat(count)
}
f(readLines(file("stdin", "r")))
幅優先の二分木を深さ優先探索
締め切りが 2017/03/21 10:00 AM なので，その 1 分後に投稿されるように予約
設問
下図のように、ノードが左から順に埋まっている二分木を考えます。
この二分木に対し、根元の要素を「1」とし、幅優先で順番に番号を付与していきます。
（ノードの数が10個の場合は左図のような番号が付与されます。）
ノードの番号と探索順
この二分木に対して、深さ優先探索を行います。
深さ優先探索では、左から順にもっとも深くなるまで進み、その後はバックトラックを行いながら順に探索します。
例えば、左図の場合は、右図のような順番に探索を行います。
m 個の要素が存在する二分木について、n 番目に探索したノードの番号を求めます。
例えば、m = 10, n = 6 のとき 5, m = 10, n = 8 のとき 3 となります。
標準入力から m, n がスペース区切りで与えられるとき、n番目に探索したノードの番号を標準出力に出力してください。
(m, n は m ≧ n を満たす整数とし、m は最大で3000とします)
【入出力サンプル】
標準入力
10 6
標準出力
5
=====================================================================
f = function(m, n) {
tree = matrix(0, m, 3)
for (i in seq_len(m)) {
tree[i,] = c(i, ifelse(2*i <= m, 2*i, 0), ifelse(2*i+1 <= m, 2*i+1, 0)) # 値，左の子へのポインター，右の子へのポインター
}
node = count = 1
repeat {
if (count == n) { # 見つかった
return(tree[node, 1]) # 値を返す
}
if (tree[node, 2] != 0) { # 左の子へ
nxt = tree[node, 2]
tree[node, 2] = 0 # 子へのポインターを潰しておく
count = count+1
} else if (tree[node, 3] != 0) { # 右の子へ
nxt = tree[node, 3]
tree[node, 3] = 0 # 子へのポインターを潰しておく
count = count+1
} else { # 終端ならば，子を持つ先祖までさかのぼる
nxt = node
repeat {
nxt = nxt %/% 2
if (tree[nxt, 2] != 0 || tree[nxt, 3] != 0) break
}
}
node = nxt
}
}
f(10, 6) # 5
f(100, 43) # 21
f(543, 345) # 410
f(1234, 987) # 896
f(3000, 2999) # 2046
中澤さんの書いた記事にある折れ線グラフが，ちょっと見づらいのでいくつか試してみた
中澤さんのプログラムは以下のとおり
# revised version of
# http://minato.sip21c.org/demography-special/asfrworld.R
# minatonakazawa@gmail.com, 20 March 2017
# requires wpp2015 package
library(wpp2015)
data(percentASFR)
worldfertil wfnow z matplot(z, type="l", lty=1, col=topo.colors(201),
axes=FALSE, ylab="ASFR2010-2015", main="World Fertilities 2010-2015")
axis(1, 1:7, rownames(z))
axis(2, 0:5*10, 0:5*10)
添付図の左上がオリジナルで，col=topo.colors(201) によるもの。
その他の代替案として，いくつか
col=topo.colors(201, alpha=0.5)
col=topo.colors(201, alpha=0.2)
col=terrain.colors(201, alpha=0.2)
col=heat.colors(201, alpha=0.2)
col="#55000022"
alpha を採用することと，単純なモノクロを選択することが効果的と思われる。
できる人のおちんぎんあっぷ
締め切りが 2017/03/16 10:00 AM なので，その 1 分後に投稿されるように予約
ここは株式会社 人月査定。
人月査定では、開発者の離職が課題になっていました。
調査してみると、優秀な開発者から順に離職していることがわかりました。
その原因を調査すると、どうやら多くの成果物を生み出す優秀な開発者とほとんど成果物を生み出していない開発者の給与が全く同じであるためでした。
そこで人月査定では成果主義による評価制度を導入することを決定しました。
社名も株式会社 ステップ数見積もり に変更です。
こうして社内特命プロジェクト「おちんぎんあっぷ大作戦」が始動しました。
「ステップ数見積もり社」ではバージョン管理ツールKit（きっと）でプログラムの履歴管理をしています。
Kitの履歴をもとに「どの開発者が何%の成果物を仕上げているか？」を調べてください。
Kitの履歴は1ファイル1行単位で残ります。
1つの履歴を保存することをコミットと呼びます。
コミット履歴は20件しか残りません。仕様です。
標準入力
Kitの履歴が標準入力されます
・コミットした開発者名、ファイル名がカンマ区切りで入力されます
・コミットした開発者名は [a-z] の文字列で構成されます
・コミットした開発者名は 3-8 文字です
・開発対象は「hoge.rb hige.rb hage.rb hoo.rb bar.rb」の5ファイルです
・入力データは20件
例（サンプルのため入力が3件ですが、実際は20件入力されます）
horiuchi,hoge.rb
hironaka,hige.rb
kondo,hoo.rb
標準出力
・出力形式は コミットした開発者名 + 半角コロン(:) + コミットしたファイルのパーセンテージ + 半角パーセント(%) です
・パーセンテージは小数点以下を切り捨ててください
例（標準入力の説明の入力が行われた場合の出力結果）
hironaka:33%
horiuchi:33%
kondo:33%
その他の仕様
・標準入力の末尾には改行があります
・標準出力の末尾に改行をつけてください
・同じファイルを複数の開発者が更新した場合、最後にファイルを更新した人がその成果物を仕上げた人としてください
例えば hoge.rb を tanaka さん、 suzuki さん、 sato さんの順番で更新していたら
hoge.rb の開発者は sato さんとして集計します
・標準入力の後半の行に出たほうが後から更新しているものとします
・標準入力の仕様で説明した内容以外の入力は行われません（不正入力に対するチェックは不要）
======================================================
素直に書くしかない
f = function(S) {
m = sapply(S, function(s) unlist(strsplit(s, ",")))
n = ncol(m)
PROG = sort(unique(m[2,]))
nProg = length(PROG)
who = integer(nProg)
for (j in seq_along(PROG)) {
prog = PROG[j]
for (i in seq_len(n)) {
if (m[2, i] == prog) {
who[j] = m[1, i]
}
}
}
who = table(who)
invisible(mapply(function(x, y) cat(sprintf("%s:%i%%\n", x, y)), names(who), floor(who/nProg*100)))
}
f(readLines(file("stdin", "r")))
[input] [output]
mashimo,hoge.rb ara:40%
hakuryu,bar.rb hakuryu:20%
hironaka,hoge.rb horiuchi:20%
kondo,hige.rb kondo:20%
kuga,hige.rb
kondo,hoo.rb
hano,hige.rb
hamakawa,hoge.rb
kuga,hige.rb
hakuryu,hage.rb
hironaka,bar.rb
horiuchi,bar.rb
hakuryu,hoo.rb
ara,bar.rb
horiuchi,hage.rb
hironaka,hoo.rb
kuga,hoge.rb
hakuryu,hoo.rb
ara,hoge.rb
kondo,hige.rb
[input] [output]
hironaka,hoge.rb ara:20%
horiuchi,hoo.rb hada:20%
mashimo,hoo.rb hakuryu:20%
hano,hige.rb hamakawa:20%
hironaka,hage.rb kondo:20%
hada,hoo.rb
hano,hige.rb
ara,hoge.rb
kondo,hige.rb
hamakawa,bar.rb
hakuryu,hage.rb
kondo,hige.rb
mashimo,hoo.rb
hamakawa,hoo.rb
kondo,hoge.rb
kuga,hoo.rb
ara,hige.rb
hamakawa,bar.rb
hada,hoge.rb
kondo,hoo.rb
[input] [output]
hakuryu,hoo.rb hamakawa:60%
hironaka,bar.rb hironaka:40%
hakuryu,hoo.rb
hakuryu,hige.rb
hamakawa,hage.rb
hironaka,bar.rb
hironaka,hige.rb
hironaka,hige.rb
hironaka,hige.rb
hakuryu,bar.rb
hano,hoo.rb
hamakawa,hige.rb
kuga,bar.rb
kuga,hige.rb
kuga,hoo.rb
hamakawa,hoge.rb
hironaka,hige.rb
hamakawa,hoo.rb
ara,bar.rb
hironaka,bar.rb
放物線とマス目の関係
締め切りが 2017/03/15 10:00 AM なので，その 1 分後に投稿されるように予約
【概要】
放物線の方程式とマス目を指定するので、位置関係がどうなっているのかを計算してください。
【詳細】
放物線とマス目の位置関係は下表の5種類があります（以下、y 座標が大きい方向が上、x座標が大きい方向が右、になります）：
記号 状況 例
U 完全に放物線より上にある
u マス目の内部は放物線より上にあるが、マス目と放物線に共有点がある。
S マス目を放物線が分断し、放物線より上にも下にも 0 より大きな面積がある
L 完全に放物線より下にある
l マス目の内部は放物線より下にあるが、マス目と放物線に共有点がある。 
【入出力】
入力は
1 0 0 0 -3
のようになっています。
空白区切りになっていて、順に a, b, c, X, Y です。
a, b, c は、放物線
y=ax2+bx+c
の係数です。
X, Y はマス目の左下隅の座標です。マス目の大きさは、 1×1 です。
つまり、マス目の領域は
(x,y) = { |x,y| X≦x≦X+1, Y≦y≦Y+1 }
です。
出力は、
L
のような感じです。
U,u,S,L,lのいずれかを出力してください。
【例】
入力 出力
1 0 0 0 -3 L
1 0 -46 7 4 S
【補足】
不正な入力に対処する必要はありません。
a は、-100000 以上 100000 以下のゼロではない整数です。
b, c, X, Y は、-100000 以上 100000 以下の整数です。
分断される場合に出力されるSは、大文字です。ご注意ください。
==========================================================
f = function(par) {
g = function(x) (a*x+b)*x+c
par = as.integer(unlist(strsplit(par, " ")))
a = par[1]
b = par[2]
c = par[3]
x = par[4]
y = par[5]
x1 = x+1
y1 = y+1
top.bottom = c-b^2/4/a
center = -b/2/a
if (a > 0) {
if (x >= center) {
if (y > g(x1)) {
ans = "U"
} else if (y == g(x1)) {
ans = "u"
} else if (y1 == g(x)) {
ans = "l"
} else if (g(x) > y1) {
ans = "L"
} else {
ans = "S"
}
} else if (center >= x1) {
if (y > g(x)) {
ans = "U"
} else if (y == g(x)) {
ans = "u"
} else if (y1 == g(x1)) {
ans = "l"
} else if (g(x1) > y1) {
ans = "L"
} else {
ans = "S"
}
} else {
if (y > g(x) && y > g(x1)) {
ans = "U"
} else if (y == g(x) || y == g(x1)) {
ans = "u"
} else if (y1 == top.bottom) {
ans = "l"
} else if (top.bottom > y1) {
ans = "L"
} else {
ans = "S"
}
}
} else if (a < 0) {
if (x >= center) {
if (y > g(x)) {
ans = "U"
} else if (y == g(x)) {
ans = "u"
} else if (y1 == g(x1)) {
ans = "l"
} else if (g(x1) > y1) {
ans = "L"
} else {
ans = "S"
}
} else if (center >= x1) {
if (y > g(x1)) {
ans = "U"
} else if (y == g(x1)) {
ans = "u"
} else if (y1 == g(x)) {
ans = "l"
} else if (g(x) > y1) {
ans = "L"
} else {
ans = "S"
}
} else {
if (y > top.bottom) {
ans = "U"
} else if (y == top.bottom) {
ans = "u"
} else if (g(x) > y1 && g(x1) > y1) {
ans = "L"
} else if (y1 == g(x) || y1 == g(x1)) {
ans = "l"
} else {
ans = "S"
}
}
}
cat(ans)
}
f("-200 5160 -33275 12 6") # S
f("8 -8 2 0 -1") # l
f("110 -198 90 0 0") # S
f("40 -40 10 0 1") # S
f("10 -5 0 0 2") # S
f("10 -10 0 0 2") # U
f("-8 8 -2 0 1") # U
f("-3 7 4 -2 -6") # u
f("1 -10 25 3 4") # u
f("-200 5160 -33275 12 6") # S
f("4 -4 1 0 0") # S
f("10 -18 9 0 0") # S
f("-1 3 0 1 1") # l
HTMLをスクレイプしてCSVに変換
締め切りが 2017/03/15 10:00 AM なので，その 1 分後に投稿されるように予約
設問
Webページに含まれるテーブルの中身をスクレイプして、Excelなどで集計がしやすいようCSVファイルに変換する。
定期的に行う必要があるため、手作業で行うのではなく自動化したい。
求められるプログラムの仕様は、以下の通り。
標準入力から、HTML準拠(Wikipedia参照）のテキストデータが送られる
入力されるHTMLはフォーマットが正しい、具体的にはW3Cの構文検証サイトでエラーがないことを前提とする
また、HTMLはUTF-8でエンコーディングされ、多バイト文字は含まれないものとする
HTMLには、tableタグが１つだけ含まれる（テーブルは単体である）
テーブル内のセルはtr, th, tdタグで構成され、セルが連結されることはない
HTML内のテーブルを表形式として抽出し、CSVフォーマット(Wikipedia参照）で標準出力に返すこと
出力するCSVはコンマ「,」(U+002C) 区切りで、すべてのフィールドをダブルクォート「"」(U+0022)で囲むこと
CSVのフィールドとして出力される文字列は、thまたはtdタグ内のテキストに限定すること
thおよびtdタグの扱いは、CSV出力時において変える必要はない
thおよびtdタグ内に、さらにタグが含まれる場合、タグ自体は除去し配下のテキストだけを抽出すること
文字列フィールドは文字実体参照(Wikipedia参照）を用いてアンエスケープ処理をすること
ただし、（大なり記号）、&（アンパサンド）のみの対応でよいものとする
【問題】
標準入力から、HTMLフォーマットのテキストが送られます。
このHTMLからtableタグで囲まれた領域をスクレイプし、CSVに変換した上で、その結果を標準出力に返してください。
なお、アンエスケープ処理も忘れずに。
=================================================
f = function(s) {
ncol = sum(grepl("", s))
s = gsub("", "", s)
s = gsub("title", "", s)
s = gsub("&", "&", s)
s = gsub("<", " s = gsub(">", ">", s)
s = (s[s != ""])[-1] # テストシステムでは先頭に 1 個の NULL が付いてしまっている
apply(matrix(s, byrow=TRUE, ncol=ncol), 1, function(x) cat('"', paste(x, collapse='","'), '"\n', sep=""))
}
cat(f(readLines(file("stdin", "r"))))
ホワイトデーのお返しの個数
締め切りが 2017/03/14 10:00 AM なので，その 1 分後に投稿されるように予約
この問題の挑戦終了日はホワイトデー。
ということで、バレンタインデーにもらったプレゼントにお返しを送ろうと思っています。
もらったプレゼントの金額はわからないので、もらった個数に対してお返しの個数を変えることにします。
・義務チョコの場合はもらった個数と同じ数
・義理チョコの場合はもらった個数の２倍の数
・本命チョコの場合はもらった個数の３倍の数
※もらった時点で「義務チョコ」か「義理チョコ」か「本命チョコ」かはわかるものとします。
バレンタインには合計 m 個のプレゼントをもらいました。
お返しに用意した個数が n 個のとき、もらったプレゼントの種類について、義務チョコ・義理チョコ・本命チョコの個数の組み合わせを考えます。
例えば、m = 5, n = 10 のとき、以下の3パターンがあります。
パターン 義務チョコ 義理チョコ 本命チョコ
(1) 0個 5個 0個
(2) 1個 3個 1個
(3) 2個 1個 2個
標準入力から m, n が与えられるとき、上記の組み合わせの数を標準出力に出力してください。
(m, n は m < n を満たす整数とし、n は最大で1,000,000とします)
【入出力サンプル】
標準入力
5 10
標準出力
3
---------------------------------
下図のように，m がある値をとるとき，n は m ≦ n ≦ 3m である。m = 13 のとき，水色で示した数列には規則性があるので，それをそのままコーディング
f = function(m, n) {
a = 0
if (n >= m && 2*m >= n) {
a = floor((n-m)/2)+1
} else if (n > 2*m && 3*m >= n) {
a = floor((3*m-n)/2)+1
}
cat(a)
}
mn = scan(file("stdin", "r"))
f(mn[1], mn[2])
この問題は，なかなか面白い
・義務チョコの場合はもらった個数の m1 倍の数
・義理チョコの場合はもらった個数の m2 倍の数
・本命チョコの場合はもらった個数の m3 倍の数
などとして，m1, m2, m3 をいろいろ変えると，ちょっと変態チックに面白い
あしあと問題
締め切りが 2017/03/09 10:00 AM なので，その 1 分後に投稿されるように予約が
仕様
9x9のマップの中を標準入力の内容に応じて移動します。
移動するとあしあとが残ります。
どのようなあしあとが残ったか標準出力してください。
標準入力
・「^v<>」のどれかの文字を組み合わせた文字列が入力されます
・ ^ は上に移動です
・ v は下に移動です
・ < は左に移動です
・ > は右に移動です
例
>>>>>>>>vvvvvvvv<<<<<<<<^^^^^^^^
標準出力
・9文字x9行の文字列を出力してください
・1行目1文字目の位置をスタート地点とします
・スタート地点は必ず「あしあと」が残ります
・同じ場所を2回通った場合は「あしあと」が残ります
・移動した場所は「Y」（半角大文字のワイ）を出力してください。鳥の足跡をイメージしています。
・移動しなかった場所は「x」（半角小文字のエックス）を出力してください
例（標準入力の説明の入力が行われた場合の出力結果）
YYYYYYYYY
YxxxxxxxY
YxxxxxxxY
YxxxxxxxY
YxxxxxxxY
YxxxxxxxY
YxxxxxxxY
YxxxxxxxY
YYYYYYYYY
その他の仕様
・標準入力の末尾には改行があります
・標準出力の末尾に改行をつけてください
・移動回数は最大で48回です
・標準入力の仕様で説明した内容以外の入力は行われません（不正入力に対するチェックは不要）
・9x9からはみ出す位置への移動をするような入力は行われません（不正入力に対するチェックは不要）
=============
f = function(S) {
x = y = 1
m = matrix("x", 9, 9)
m[x, y] = "Y"
S = unlist(strsplit(S, ""))
for (s in S) {
if (s == ">") {
x = x+1
} else if (s == "＜") # ＜ は半角で
x = x-1
} else if (s == "v") {
y = y+1
} else if (s == "^") {
y = y-1
}
m[x, y] = "Y"
}
for (i in 1:9) {
cat(sprintf("%s\n", paste(m[,i], collapse="")))
}
}
# f(readLines(file("stdin", "r")))
f(">>>>>>>>vvvvvvvv<<<<<<<<^^^^^^^^")
f(">>vv>>vv>>vv>>vv")
f(">>>><vvv")
「プライム・ペア」問題
締め切りが 2017/03/09 10:00 AM なので，その 1 分後に投稿されるように予約
設問
自然数 k に対し、1 から k までの自然数のうち k と互いに素なものの個数を F(k) と定義します。
（F(k) はオイラーのΦ関数とも呼ばれています。参考：オイラーのφ関数（Wikipedia））
例えば F(12)＝4 です。1 から 12 のうち 12 と互いに素なのは 1, 5, 7, 11 の 4 つです。
標準入力から、自然数 n（1 ≦ n ≦ 105）が与えられます。
標準出力に F(n！) を 1000003 で割った余りを出力するプログラムを書いてください。
例えば n＝10 のとき、F(10！)＝F(3628800)＝829440 です。
同様に、F(20！) を 1000003 で割った値は 961998 です。
===================================
F = function(n) {
mx = n # n 以下の素数リストを prime に作る
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]
# F(n!) = n! * Π(1-1/prime[i]) = 1*2*3*…*n × (prime[1]-1)/prime[1] × (prime[2-1)/prime[2] …
# F(20!) = 1*2*3*4*5*6*7*8*9*10*11*12*13*14*15*16*17*18*19*20 * (1-1/2)*(1-1/3)*(1-1/5)*(1-1/7)*(1-1/11)*(1-1/13)*(1-1/17)*(1-1/19)
# = 1*2*3*4*5*6*7*8*9*10*11*12*13*14*15*16*17*18*19*20 * 1/2 * 2/3 * 4/5 * 6/7 * 10/11 * 12/13 * 16/17 * 18/19
# = 1*4*6*8*9*10*12*14*15*16*18*20 * 1*2*4*6*10*12*16*18
# = 416084687585280000
# 416084687585280000 %% 1000003 = 961998
# i = 1 ~ n までの積。ただし，i が素数の場合は「i-1」
x = 1:n
x[prime] = x[prime] - 1
ans = 1
for (a in x) { # 要素の掛算（ただし，毎回 1000003 の剰余を結果とする）
ans = (ans*a) %% 1000003
}
cat(ans)
}
#F(scan(file("stdin", "r")))
F(10) # 829440
F(20) # 961998
F(30) # 845477
F(100) # 145380
F(431) # 945906
F(2017) # 272985
F(81645) # 603326
F(99100) # 799614
グループで乗るリフト
締め切りが 2017/03/07 10:00 AM なので，その 1 分後に投稿されるように予約
設問
m 人のグループがスキー場でリフトやゴンドラに乗ろうとしています。
このスキー場には n 人乗りのリフトやゴンドラがあります。
グループでまとまって移動するため、連続したリフトやゴンドラに乗ることにします。
グループのメンバーは区別せず、各リフトやゴンドラに乗る人数だけを考えるとき、
1回の移動における乗り方が何通りあるかを求めてください。
ただし、誰も乗らないリフトやゴンドラはないものとします。
また、m, n ともに 32以下の正の整数とします。
例えば、m = 5, n = 3 のとき、以下の13パターンがあります。
パターン 1台目 2台目 3台目 4台目 5台目
(1) 1人 1人 1人 1人 1人
(2) 1人 1人 1人 2人 -
(3) 1人 1人 2人 1人 -
(4) 1人 2人 1人 1人 -
(5) 2人 1人 1人 1人 -
(6) 1人 1人 3人 - -
(7) 1人 3人 1人 - -
(8) 3人 1人 1人 - -
(9) 1人 2人 2人 - -
(10) 2人 1人 2人 - -
(11) 2人 2人 1人 - -
(12) 2人 3人 - - -
(13) 3人 2人 - - -
【入出力サンプル】
標準入力
5 3
標準出力
13
=====================
下図のような規則性を持った二次元数列になる
各列のオレンジの部分以降の桝目の数値は，それ以前の n 個の桝目の和（広義のフィボナッチ数列） n = 2（C 列）を見ればわかる
f = function(m, n) {
a = integer(m+1)
a[1] = 1
a[2:n] = 2^(0:(n-2))
for (i in n:m+1) {
a[i] = sum(a[i-n:1])
}
cat(a[m+1],"\n")
}
if (0) {
mn = scan(file("stdin", "r"))
f(mn[1], mn[2])
} else {
f(5, 3) # 13
f(6, 4) # 29
f(10, 2) # 89
f(25, 10) # 16646200
f(32, 16) # 2147205120
}
PVアクセスランキング にほんブログ村
