裏 RjpWiki

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

三角形は何通り?

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

いつもの通り,締め切りが 2016/12/31 10:00 AM なので,その 1 分後に投稿するように予約

【問題】
入力nに対して
1≦a≦b≦c≦n(a, b, c, nはすべて整数)を満たすa, b, cの中で、これらを3辺とする三角形が成り立つ場合の組み合わせを求めるプログラムを書いてください。

【入力】
標準入力から、整数n(1≦n≦1000000)が与えられます。

【出力】
標準出力に、条件を満たす組み合わせの総数のみを出力してください。

たとえばn = 3とすると、(a, b, c)のすべての組み合わせは、

    (1, 1, 1)
    (1, 2, 2)
    (1, 3, 3)
    (2, 2, 2)
    (2, 2, 3)
    (2, 3, 3)
    (3, 3, 3)

の7通りになりますので、7と出力します。

==========

 

いつもの定石。簡単なプログラムを書いて,n=1,2,3,... の場合の答えを求め,「オンライン整数列大辞典」を参照する。

f = function(n) {
    options(scipen=100)
    cat(floor((n+1)*(n+3)*(2*n+1)/24))
}

> f(3)
[1] 7
> f(1000)
[1] 83708750
> f(10000)
[1] 83370837500
> f(1000000)
[1] 83333708333750000

コメント

html タグの入れ子の間違い探し

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

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

 【問題】
htmlが標準入力から与えられるので、htmlタグの入れ子が間違っている、閉じタグが現れる最初の行番号を、標準出力に出力するプログラムを作ってください。
htmlは最大20行、1行あたり最大100文字です。
ただし、liタグに関しては、タグが閉じていても閉じてなくてもよいものとします。
間違いがない場合には0を出力してください。

=====

テストデータが 3 個しかなく,しかも簡便化されているので,一般的な html ファイルを扱うプログラムを書くなどとは馬鹿馬鹿しくまともに取り合う気になれず,テストに合格するプログラムを書いただけ...

f = function(s) {
    stack = NULL
    s = sub(" .+>", ">", s)
    error.lno = 0
    for (i in seq_along(s)) {
        t = s[i]
        if (substr(t, 2, 2) == "/") {
            t = sub("/", "", t)
            if (length(stack) == 0) {
                error.lno = i
                break
            } else if (stack[1] == t) {
                stack = stack[-1]
            } else {
                error.lno = i
                break
        } else if (substr(t, 1, 4) != "<li>") {
            stack = c(t, stack)

        }
    }
    cat(error.lno)
}

 

コメント

硬貨の組み合わせの数

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

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

【問題】

小銭をたくさん持っている小銭王子は、小銭を使った支払いに興味を持ちました。
指定された金額になる小銭の出し方のすべてのパターンを調べ、王子に教えてあげてください。
例えば、10 円を支払うとき、「10 円玉 1 枚」「5 円玉 2 枚」「5 円玉 1 枚と 1 円玉 5 枚」「1 円玉 10 枚」の 4 通りあります。
※小銭は 500 円・100 円・50 円・10 円・5 円・1 円硬貨です。また、小銭王子はそれぞれの硬貨を 1000 枚ずつ持っています。

【入力】

標準入力から、整数値 N(1 ≦ N ≦ 1000)が与えられます。

【出力】

合計金額が N 円になる硬貨の出し方のすべての組み合わせを求め、そのパターン数を、標準出力に出力してください。

【入出力サンプル】

Input
10

Output
4

=====

規則性に基づき,テーブルを作成する。

f = function(n) {
    x = 1:5
    x = c(x, x*2+5, 18)
    x = cumsum(rep(x, each=2))
    x = cumsum(rep(x, each=5))
    x = cumsum(rep(x, each=2))
    x = rep(x, each=5)
    cat(x[n+1])
}

コメント

2 進表記の 1 の個数

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

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

【問題】

2 つの整数値 N, M が与えられます。
0 から  N ま での各整数(10 進数)について、2 進表記したときに 1 の数がM個になるものを数えてください。
たとえば、9 を 2 進表記すると 1001 ですので、1 の数は 2 ということになります。

【入力】

標準入力から、半角スペースで区切られた 2 つの整数値N(0 ≦ N ≦ 100000)、M(0 ≦ M ≦ 17)が与えられます。
 
【出力】

0 から N までの整数の中で、2 進表記したときに 1 の数が M 個あるものの個数を出力してください。

【入出力サンプル】
Input
10 2

Output
5

※11, 101, 110, 1001, 1010 の 5 つ

=====

intToBits という関数を使えば,超超簡単


f = function(s) {
    s = as.integer(unlist(strsplit(s, " ")))
    cat(sum(sapply(0:s[1], function(x) sum(as.integer(intToBits(x))) == s[2])))
}

コメント

整数値の集合に条件を満たす 2 数があるか?

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

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

【問題】

いくつかの整数値が与えられます。
それらの中で、和がちょうど 256 になるような 2 数が存在するかどうかを調べてください。
 
【入力】

標準入力から、整数値が与えられます。

 1 行目は整数値N(2 ≦ N ≦ 100)、2 行目はN個の整数値Ak( 0 ≦ Ak ≦ 256)が半角スペースで区切られています。
 
【出力】

和が 256 になる 2 数が存在する場合は "yes"、存在しない場合は "no" と、標準出力に出力してください。
 
【入出力サンプル】
Input
4
32 64 128 192

Output
yes

=====

f = function(s) {
    x = as.integer(unlist(strsplit(s, " ")))
    y = outer(x, x, "+")
    diag(y) = 0
    cat(c("no", "yes")[(256 %in% y)+1])
}

コメント

取り違えは何通り?

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

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

この問題,2 年前にも同じようなのが出題されたんだよね。( 完全順列 http://blog.goo.ne.jp/r-de-r/s/完全順列 )

 一人一台のパソコンを支給されている、社員N人の会社があります。
このパソコンは見た目がすべて同じため、他の人のパソコンを間違って持ち帰ってしまう場合がありました。

N人全員が他人のパソコンを持って帰ってしまうような組み合わせが何通りあるかを求めてください。
使用するプログラミング言語は問いません。

なお、出力は64bit整数に収まります。

【入出力サンプル】

Input
5

Output
44

==========

前は再帰で書いたので,別の書き方で 2 通りのプログラム

f = function(n) {
    options(scipen=100)
    a = 0
    b = 1
    for (i in 3:n) {
        x = (i - 1) * (a + b)
        a = b
        b = x
    }
    cat(x)
}

f = function(n) {
    options(scipen=100)
    k = 2:n
    cat(sum( (-1)^k * factorial(n) / factorial(k) ))
}

f(5) # 44
f(12) # 176214841
f(17) # 130850092279664

コメント

ヘックス上の最長狭義単調増加列

2016年12月29日 | ブログラミング

ヘックス上の最長狭義単調増加列
締切が 2016/12/29 10:00 AM なので,その 1 分後に投稿されるように予約

【概要】
1辺4マスの六角形状のマス目があり、各マスにはa〜zの文字が入っています。
a〜zの文字は、1〜26 の数を表しています。
適当なマス目から隣のマスへ隣のマスへとたどり、どんどん増えていく数列(狭義単調増加列)を作ることを考えます。

入力で与えられる配置の場合に作ることができる狭義単調増加列の中で、もっとも要素数が多いものの要素数を計算するプログラムを書いてください。

【入出力】

入力は
javc/fhqvv/nerncj/actuybv/unrutf/sxgff/xjdi
こんな感じで標準入力から来ます。

マス目の東西の一列が、北から順にスラッシュ(/)区切りで並んでいます。

出力は、最長の狭義単調増加列の要素数を、10進数で。
先程の例だと左図のように,緑色の線が最長となる場合の例になりますので、
10
を出力すると正解です。

  

【例】
入力                        出力     状況
javc/fhqvv/nerncj/actuybv/unrutf/sxgff/xjdi    10     左図
kmyv/fuhxe/hhnnvr/dygmgwo/jbwkfu/zqthb/jxbl     9     右図

【補足】
    不正な入力に対処する必要はありません。
    長さ1でも狭義単調増加列になります。考えられる最小値は 1 になります。
    a, d, f, x のように、ちゃんと毎回増えること。a, n, n, x のようなものは NG。

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

# ヘックスの番号
#        1   2   3   4
#      5   6   7   8   9
#   10  11  12  13  14  15
# 16  17  18  19  20  21  22
#   23  24  25  26  27  28
#     29  30  31  32  33
#       34  35  36  37

# r[[i]] は,i 番目のヘックスに隣接するヘックスの番号のリスト
r = vector("list", 37)
r[[1]] = c(2, 5, 6)
r[[2]] = c(1, 3, 6, 7)
r[[3]] = c(2, 4, 7, 8)
r[[4]] = c(3, 8, 9)
r[[5]] = c(1, 6, 10, 11)
r[[6]] = c(1, 2, 5, 7, 11, 12)
r[[7]] = c(2, 3, 6, 8, 12, 13)
r[[8]] = c(3, 4, 7, 9, 13, 14)
r[[9]] = c(4, 8, 14, 15)
r[[10]] = c(5, 11, 16, 17)
r[[11]] = c(5, 6, 10, 12, 17, 18)
r[[12]] = c(6, 7, 11, 13, 18, 19)
r[[13]] = c(7, 8, 12, 14, 19, 20)
r[[14]] = c(8, 9, 13, 15, 20, 21)
r[[15]] = c(9, 14, 21, 22)
r[[16]] = c(10, 17, 23)
r[[17]] = c(10, 11, 16, 18, 23, 24)
r[[18]] = c(11, 12, 17, 19, 24, 25)
r[[19]] = c(12, 13, 18, 20, 25, 26)
r[[20]] = c(13, 14, 19, 21, 26, 27)
r[[21]] = c(14, 15, 20, 22, 27, 28)
r[[22]] = c(15, 21, 28)
r[[23]] = c(16, 17, 24, 29)
r[[24]] = c(17, 18, 23, 25, 29, 30)
r[[25]] = c(18, 19, 24, 26, 30, 31)
r[[26]] = c(19, 20, 25, 27, 31, 32)
r[[27]] = c(20, 21, 26, 28, 32, 33)
r[[28]] = c(21, 22, 27, 33)
r[[29]] = c(23, 24, 30, 34)
r[[30]] = c(24, 25, 29, 31, 34, 35)
r[[31]] = c(25, 26, 30, 32, 35, 36)
r[[32]] = c(26, 27, 31, 33, 36, 37)
r[[33]] = c(27, 28, 32, 37)
r[[34]] = c(29, 30, 35)
r[[35]] = c(30, 31, 34, 36)
r[[36]] = c(31, 32, 35, 37)
r[[37]] = c(32, 33, 36)

search = function(x, start) {
    # アルファベット列 x で,start 番目のヘックスからの径路を探索
    path = vector("list", 37) # 次のヘックス番号の候補リスト
    PATH = integer(37) # それまでにたどってきたヘックスの番号リスト
    i = 1
    path[[i]] = start
    mx = 0 # 最長径路
    repeat {
        if (length(path[[i]]) == 0) { # このノードから次のヘックス探索は終了
            i = i - 1 # 一つ前のリストに戻って繰り返し
            if (i == 0) { # 全部探索したら終わり
                break
            }
        }
        PATH[i] = start = path[[i]][1] # リストの先頭を start にして
        path[[i]] = path[[i]][-1] # 先頭を取り除く(処理済みにする)
        nxt = r[[start]] # 隣接するヘックス番号ベクトル
        nxt = nxt[x[start] < x[nxt]] # そのうちで,より大きなアルファベットのもの
        valid = setdiff(nxt, PATH) # さらに,既に通ってきたヘックス番号ではないもの
        if (length(valid) > 0) { # 次のヘックスに移動できる(径路がある)
            i = i + 1
            path[[i]] = valid # 径路の候補をリストアップ
            if (i  > mx) { # 最長経路の更新
                PATH0 = c(PATH[1:(i-1)], valid[1]) # 径路のヘックス番号ベクトル
                mx = i # 径路の長さ
            }
        }
    }
    PATH0 # 最長経路のヘックス番号ベクトル
}

f = function(s) {
    x = unlist(strsplit(gsub("/", "", s), ""))
    mx = 1 # デフォルトの最短経路は長さ 1
    for (start in seq_along(r)) { # すべてのヘックスをチェック
        # 周りのどのヘックスよりも小さいアルファベットなら本当のスタート候補
        if (all(x[start] < x[r[[start]]])) { # 周りのどのヘックスよりも小さいアルファベット
            path = search(x, start) # start から始まる径路を捜す(径路のヘックス番号ベクトルを返す)
            if (length(path) > mx) {
                mx = length(path) # 最長経路の更新
                path.max = path # 実際の径路のヘックス番号の更新
            }
        }
    }
#    cat(path.max)
    cat(mx)
}

f("javc/fhqvv/nerncj/actuybv/unrutf/sxgff/xjdi") # 10
f("kmyv/fuhxe/hhnnvr/dygmgwo/jbwkfu/zqthb/jxbl") # 9
f("ukps/kjcrl/ymfsqq/kbzfidr/dktjby/submc/ktps") # 8
f("zxgm/jzcwp/yacivm/ibckuek/bgoznq/svqfp/gfwn") # 7
f("pfqr/qvplf/kkrxqk/tbvravh/hurwxp/vnvwv/xjzt") # 6
f("onjw/cmtxj/jntmsv/ffttgre/sxsveu/deuey/qygd") # 5
f("neoo/boifu/dpgzxz/jhlqwwi/oijunp/fseev/tpwj") # 11
f("abcd/rstue/qpqrvf/povwswg/onutxh/nmzyi/mlkj") # 26
f("dddd/dcccd/dcbbcd/dcbabcd/dcbbcd/dcccd/dddd") # 4
f("gggg/ffffg/eeeefg/ddddefg/cccdef/bbcde/abcd") # 7
f("kjih/xyzag/wvutbf/jklmsce/ihgnrd/bcfoq/adep") # 26
f("dddd/ddddd/ccccdd/cccccdd/bbbccd/bbbcc/abbc") # 2
f("mmmm/mmmmm/mmmmmm/mmmmmmm/mmmmmm/mmmmm/mmmm") # 1
f("yxwv/zkjiu/slcbht/rmdagst/qnefru/popqv/zyxw") # 26

コメント

急行停車駅をどこにする?

2016年12月27日 | ブログラミング

急行停車駅をどこにする?

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

設問

電車で移動するとき、距離が長くなると各駅停車よりも急行や特急といった電車を利用したくなります。
今回は急行と特急の停車駅を考えます。

全部で n 個の駅があり、そのうち急行の停車駅が a 個、特急の停車駅を b 個とします。
なお、特急の停車駅には必ず急行が停車するものとします。
駅が環状につながっていることはなく、開始駅と終了駅は急行、特急のいずれも停車します。

与えられる n, a, b には n > a > b > 1 の関係があるものとします。
このような停車駅の配置が何通りあるかを求めてください。

例えば、n = 4, a = 3, b = 2 のとき、以下の2通りがあります。
駅     急行停車駅     特急停車駅
A     〇     〇
B     〇     ×
C     ×     ×
D     〇     〇
    
駅     急行停車駅     特急停車駅
A     〇     〇
B     ×     ×
C     〇     ×
D     〇     〇

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

標準出力
2

なお、出力内容が32bitの整数で収まるような入力が与えられるものとします。

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

ご大層な問題説明だが,数 I レベルの問題
同じもの a が p 個,b が q 個,c が r 個,… ,合計 n 個あるとき,これらを全部使って1列に並べる順列の総数は n!/(p!q!r!···) 通り というやつだ
n 個の駅の始発駅と終着駅は急行も特急も停まるので,場合の数には関係ない。
残りの n-2 個の駅は,特急も急行も停まるのは,b-2 個,急行だけが停まるのは a-b 個,特急も急行も停まらないのは n-a
上の公式から求めるのは (n-a)! / (b-2)! / (a-b)! / (n-a)!

f = function(n, a, b) {
    both = b-2
    express.only = a-b
    dont.stop = n-a
    N= (b-2) + (a-b) + (n-a)
    cat(factorial(N) / factorial(both) / factorial(express.only) / factorial(dont.stop))
}

> f(26, 14, 7)
2141691552

コメント

サンタの持ち場を計算しよう

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

サンタの持ち場を計算しよう

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

問題

あなたはサンタさんです。
サンタさんは、プレゼントを配るべき家を割り当てられます。
配る家は複数あり、1〜15の整数のX, Y座標で、位置が示されます。
全ての家を含む、X軸に平行な辺を持つ正方形(辺の長さは整数、家は線上でもよい)の面積を計算するプログラムを書いてください。



以下、入力の例です。
数字は標準入力から、カンマと改行で区切られた文字として渡されます。
改行で区切られた各行が家を表します。
カンマで区切られた値は順に、X座標、Y座標を表します。

6,3
2,5
4,7
8,6

以下、グラフによる図解と各種数値です。

X最小値 : 2
Y最小値 : 3
正方形の辺の長さ : 6
正方形の面積 : 36
正方形の左下の座標 : (2, 3)
正方形の右上の座標 : (8, 9)

正方形の辺の長さは「6」なので、正方形の面積は「36」になります。

答えは、以下のように標準出力に出力してください。

36

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

f = function(xy) {
    a = matrix(xy, 2)
    cat(max(diff(range(a[1,])), diff(range(a[2,])))^2)
}
f(scan(file("stdin", "r"), sep=","))

コメント

「スパイラル・ウォーク」問題 (その2)

2016年12月22日 | ブログラミング

「スパイラル・ウォーク」問題

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

設問
自然数 w, h に対し、横と縦の長さがそれぞれ w, h となる格子状の道を考えます。
この左上の点からスタートして、同じ交差点を二度以上通らないように、らせんを描いて進みます。
最初は下方向にまっすぐ進み、これ以上前に進めなくなったところで左折し、再びまっすぐ進みます。
これを繰り返し、全ての交差点に到達したところで終了します。
(w, h)=(4, 3) の場合の進み方を下に示します。このとき進んだ距離は 19 であることが分かります。



自然数 m に対し、上のように進んだ時の距離がちょうど m となるような組 (w, h) の個数を F(m) と定義します。
例えば F(11)=4 です。進んだ距離が 11 となる組 (w, h) は、(1, 5), (2, 3), (3, 2), (5, 1) の 4 通りです。



同様に、F(3)=1, F(23)=6, F(28)=0 となることが確かめられます。
さらに、自然数 n に対し、1≦m≦n となる全ての m に対する F(m) の和を G(n) と定義します。
例えば、G(11)=12, G(100)=283, G(1000)=5076 となることが確かめられます。
標準入力から、自然数 n(1 ≦ n ≦ 106)が与えられます。
標準出力に G(n) を出力するプログラムを書いてください。
※ テストケースは全部で 6 つあります。全てをPASSすれば正解です。

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

いやはや,説明にミスリードされて,馬鹿正直なブルートフォースによるプログラムを書いてしまった。

考えて見れば,G(23) を求めるのに F(1) 〜 F(23)  の和を求める必要は全くない

以下の図をみればわかるが,F(x) があろうがなかろうが行ごとに見てセルの値が x+1 より小さいセルの個数の和が求める答え G(x) である。

G(11) = 5+3+2+1+1 = 12
G(23) = 11+7+5+3+3+2+2+1+1+1+1 = 37



R プログラム

g = function(m) {
    m = m+1
    sum = 0
    for (h in seq.int(m%/%2-1)) {
        sum = sum+m%/%(h+1)-1
    }
    cat(sum, "\n")
}

> system.time(g(991245)) # 11856448
11856448
   ユーザ   システム       経過  
     0.354      0.002      0.348

コメント

「スパイラル・ウォーク」問題

2016年12月22日 | ブログラミング

「スパイラル・ウォーク」問題

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

設問
自然数 w, h に対し、横と縦の長さがそれぞれ w, h となる格子状の道を考えます。
この左上の点からスタートして、同じ交差点を二度以上通らないように、らせんを描いて進みます。
最初は下方向にまっすぐ進み、これ以上前に進めなくなったところで左折し、再びまっすぐ進みます。
これを繰り返し、全ての交差点に到達したところで終了します。
(w, h)=(4, 3) の場合の進み方を下に示します。このとき進んだ距離は 19 であることが分かります。



自然数 m に対し、上のように進んだ時の距離がちょうど m となるような組 (w, h) の個数を F(m) と定義します。
例えば F(11)=4 です。進んだ距離が 11 となる組 (w, h) は、(1, 5), (2, 3), (3, 2), (5, 1) の 4 通りです。



同様に、F(3)=1, F(23)=6, F(28)=0 となることが確かめられます。
さらに、自然数 n に対し、1≦m≦n となる全ての m に対する F(m) の和を G(n) と定義します。
例えば、G(11)=12, G(100)=283, G(1000)=5076 となることが確かめられます。
標準入力から、自然数 n(1 ≦ n ≦ 106)が与えられます。
標準出力に G(n) を出力するプログラムを書いてください。
※ テストケースは全部で 6 つあります。全てをPASSすれば正解です。

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

行列を考えて,h 行 w 列の要素は h*w+h+w なので,(h+1)*(w+1) = h*w+h+w+1 ということから,約数の個数を求めるということに帰着できる。



つまり,F(11) は,11+1 つまり 12 の自明でない約数の個数ということ,12 の自明でない約数(1 と 12 を除く)は 2, 3, 4, 6 の 4 個で,w-1 が 2, 3, 4, 6 ということは w は 1,  2,  3,  5 それに対応する h は 5, 3, 2, 5 つまり,4 通りの格子なので,F(11) = 4。
G は,効率だけを考えてコーディング。

R で書いたけど,とても遅い。短くて簡潔なんだけどね。
AWK にしても,まだ遅い。
Java にしたら,0.5 秒ほどでできてしまった。
不公平だよね。

R プログラム

prime = function(m) {
    tbl = 1:m
    tbl[1] = 0
    for (i in 2:floor(sqrt(m))) {
        if (tbl[i]) {
            m2 = m%/%i
            tbl[2:m2 * i] = 0
        }
    }
    tbl[tbl != 0]
}

G = function(M) {
    if (M < 2) {
        return(0)
    }
    PRIME = prime(M + 1)
    sums = 0
    for (m in 1:M) {
        m = m + 1
        limit = sqrt(m)
        ans = 1
        for (i in PRIME) {

            if (i > limit) {
                ans = ans*2
                break
            }
            count = 1 # 素因子分解 i^count からの取り出し方は count+1 通り
            while (m%%i == 0) {
                m = m/i
                count = count + 1
            }
            ans = ans * count
            if (m == 1) {
                break
            }
        }
        sums = sums + ans - 2
    }
    cat(sums)
}
system.time(G(11)) # 12
system.time(G(100)) # 283
system.time(G(1000)) # 5076

system.time(G(25)) # 40
system.time(G(298)) # 1152
system.time(G(1234)) # 6518; 0.022 seq.
system.time(G(137945)) # 1377974; 6.799 seq.
system.time(G(876459)) # 10375657; 86.505 seq.
system.time(G(991245)) # 11856448; 102.718 seq.

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

AWK スクリプト

function prime(m, tbl2,     i, j, m2, count) {
    for (i = 1; m >= i; i++) {
        tbl[i] = i
    }
    tbl[1] = 0
    for (i = 2; int(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) {
            tbl2[++count] = tbl[i]
        }
    }
    return count
}

BEGIN {
#   G(25)
#   G(298)
#   G(1234) # 6518; 0.021u
#   G(137945) # 1377974; 98.223u, 62.740u, 3.211u
#   G(876459) # 10375657; 40.984u
    G(991245) # 11856448; 53.748u
}

function G(M,      PRIME, n, sums, m, m1, m2, ans, i, p, count) {
    if (M < 2) {
        return 0
    }
    n = prime(M+1, PRIME)
    sums = 0
    for (m = 1; M >= m; m++) {
        m1 = m + 1
        m2 = sqrt(m1)
        ans = 1
        for (i = 1; n >= i; i++) {
            p = PRIME[i]
            if (p > m2) {ans *= 2; break}
            count = 1
            while (m1%p == 0) {
                m1 /= p
                count = count + 1
            }
            ans = ans * count
            if (m1 == 1) {
                break
            }
        }
        sums += ans - 2
    }
    print sums
}

#{G($0)}

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

Java プログラム

import java.util.*;

class Main {

    public static void main(String[] args) {
        Scanner cin = new Scanner(System.in);
        String line;
        line =cin.nextLine();
        int M = Integer.parseInt(line);
        G(M);
    }

    static int[] prime(int m) {
        int i, j, count;
        int[] tbl = new int[m + 1];
        int[] tbl2 = 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) {
                tbl2[++count] = tbl[i];
            }
        }
        return tbl2;
    }

    static void G(int M) {
        int n, sums, m, m1, m2, ans, i, p, count;
        int[] PRIME = new int[M + 1];
        if (M < 2) {
            return;
        }
        PRIME = prime(M + 1);
        n = PRIME.length;
        sums = 0;
        for (m = 1; M >= m; m++) {
            m1 = m + 1;
            m2 = (int) Math.sqrt(m1);
            ans = 1;
            for (i = 1; n >= i; i++) {
                p = PRIME[i];
                if (p > m2) {
                    ans *= 2;
                    break;
                }
                count = 1;
                while (m1 % p == 0) {
                    m1 /= p;
                    count++;
                }
                ans *= count;
                if (m1 == 1) {
                    break;
                }
            }
            sums += ans - 2;
        }
        System.out.println(sums);
    }
}

コメント

左と右の有理数

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

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

【概要】

有理数を、図のようにならべます。

図では、紙面の都合で7段目までしか書かれていませんが、下に無限に広がっています。
与えられた有理数の、図上での左隣と右隣(図にある x は無視して)の有理数を求めてください。

【詳細】

有理数を並べるツリーは以下のルールに従っています:

    自分が p/q の場合、左の子は p/(p+q)
    自分が p/q の場合、右の子は (1-p/q)。ただし、自分が 1/2 以上の場合には右の子はいない。

入力は
3/7
という具合に標準入力から来ます。

出力は、左隣と右隣の有理数を、コンマ区切りで出力してください。
こんな
4/5,2/7
具合です。

ただし、左隣や右隣に有理数がない場合には、そこには有理数の代わりにハイフンをおいてください。
例えばこんな
-,4/5
3/4,-
具合です。

【例】

入力     出力
3/7     4/5,2/7
1/6     -,4/5
2/5     3/4,-

【補足】

不正な入力に対処する必要はありません。
入力の分母・分子 はいずれも正の整数で、分子<分母<二百五十 です。

=====

g = function(p, q) { # 親のノードを得る
    if (2 * p == q) {
        p = q = 0
    } else if (2 * p > q) {
        p = q - p
    } else {
        q = q - p
    }
    list(p = p, q = q)
}

h.l = function(p, q) { # 左側の子供のノードを得る
    list(p = p, q = p + q)
}

h.r = function(p, q) {# 右側の子供のノードを得る
    if (2 * p >= q) {
        p = q = 0
    } else {
        p = q - p
    }
    list(p = p, q = q)
}

case.r = function(p, q) { # 発端が右の子供の場合
    level = 0
    parent = g(p, q)
    l = h.l(parent$p, parent$q) # 発端者の左隣は親の左側の子供
    repeat { # 右隣の探索は,まず左側の子供を持つ親までさか上る
        parent = g(parent$p, parent$q)
        if (parent$p == 0) {
            return(list(l = l, r = parent))
        }
        level = level - 1
        r = h.r(parent$p, parent$q)
        if (r$p != p && r$q != q && r$p != 0 && r$q != 0) {
            break
        }
        p = parent$p
        q = parent$q
    }
    repeat { # しかる後に,左の子供をたどって下る
        if (level == 0) {
            break
        }
        level = level + 1
        r = h.l(r$p, r$q)
    }
    list(l = l, r = r)
}

case.ll = function(p, q) {
    level = -1
    parent = g(p, q)
    if (parent$p == 0 || parent$p == 1) {
        return(list(p = 0, q = 0))
    } else if (parent$p == 1) {
        return(h.l(parent$p, parent$q))
    }
    repeat { # 左隣の探索は,まず左側の子供を持つ親までさかのぼる
        parent = g(parent$p, parent$q)
        if (parent$p == 0) {
            return(list(p = 0, q = 0))
        }
        level = level - 1
        l = h.l(parent$p, parent$q)
        if (l$p != p && l$q != q && l$p != 0 && l$q != 0) {
            break
        }
        p = parent$p
        q = parent$q
    }
    level = level + 1
    l = h.l(parent$p, parent$q)
    if (level == 0) {
        return(l)
    }
    repeat {
        level = level + 1
        l = h.r(l$p, l$q)
        if (level == 0) {
            break
        }
        if (2 * l$p > l$q) {
            level = level + 1
            l = h.l(l$p, l$q)
            if (level == 0) {
                break
            }
        }
    }
    l
}

case.lr = function(p, q) {
    level = 0
    repeat {
        parent = g(p, q)
        r = h.r(parent$p, parent$q)
        if (0 > level && r$p == 0) {
            return(r)
        }
        if (r$p != parent$p && parent$q != q && r$p != 0) {
            break
        }
        level = level - 1
        p = parent$p
        q = parent$q
    }
    repeat {
        if (level == 0) {
            break
        }
        level = level + 1
        r = h.l(r$p, r$q)
    }
    r
}

f = function(p, q) {
    options(scipen = 100)
    l = r = list(p = 0, q = 0)
    if (2 * p > q) { # 右の子供が発端
        ans = case.r(p, q)
        l = ans$l
        r = ans$r
    } else { # 左の子供が発端
        l = case.ll(p, q) # 左隣
        r = case.lr(p, q) # 右隣
    }
    l = ifelse(l$p == 0, "-", sprintf("%s/%s", l$p, l$q))
    r = ifelse(r$p == 0, "-", sprintf("%s/%s", r$p, r$q))
    cat(sprintf("%s,%s", l, r))
}

f(3, 7) # 4/5,2/7
f(5, 37) # 16/41,27/32
f(1, 2) # -,-
f(1, 3) # -,-
f(248, 248) # -,-
f(1, 249) # -,247/248
f(2, 249) # 14662949395604/23725150497407,245/247
f(3, 248) # 1032569015/1670731762,242/245
f(144, 233) # 89/322,-
f(247, 248) # 1/249,246/493
f(65, 81) # 16/97,49/114
f(65, 73) # 8/81,57/122
f(134, 205) # 71/276,55/338

コメント

連続する数字で作る回文数

2016年12月13日 | ブログラミング

連続する数字で作る回文数

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

設問

与えられた整数に対して、最上位の桁から最下位の桁に向けて一桁ずつ読んでいき、同じ数字が続いている場合、「その数字」と「連続する個数」を並べるという変換を考えます。
例えば、「332111」の場合、3が2個、2が1個、1が3個連続するため、「322113」を出力します。

a 以上 b 未満の整数に対し、この変換を行って「回文数」になるものを探します。
回文数とは逆から数字を並べても同じ数になる数です。(Wikipedia:回文数)
例えば、a = 100, b = 1000 のとき、112, 211, 333はそれぞれ1221, 2112, 33となり、条件を満たします。
他にはありませんのでこの範囲には3個存在します。

標準入力から整数 n が与えられたとき、10^(n-1) 以上 10^n 未満の整数の中から、上記の変換により回文数になるものがいくつあるかを求め、
標準出力に出力してください。
なお、n は 0 < n ≦ 9 を満たすものとします。

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

標準出力
3

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

どのレベルのプログラムを書くかというのが,落としどころ。

ブルートフォースならば,以下のように,しらみつぶしすればよいが,当然ながら,計算時間はバカにならない。。

f = function(n) {
    g = function(x) {
        y = c(t(matrix(unlist(rle(as.numeric(unlist(strsplit(as.character(x), ""))))), ncol=2)))
        all(y == rev(y))
    }
    h = function(x) {
        y = rle(strsplit(as.character(x), "")[[1]])
        v = y$values
        l = y$lengths
        n = seq_along(l)
        y = c(rbind(v, l))
        all(y[n] == rev(y)[n])
    }
    cat(sum(sapply((10^(n-1)):(10^n-1), h)))
}

この問題は,整数を複数の整数に分解することに関係しているということがわかる。
たとえば,整数 5 は  (5), (1,1,1,1,1), (4, 1), (3,1,1), (3,2), (2,2,1), (2,1,1,1) の 5 通りに分割できる。
それぞれは,(3,1,1) はその他に(1,3,1), (1,1,1) など,何通りかの配置がある。それぞれに対応して,どの数字(0-9)が繰り返されるかが決まる。そして,(数字,繰り返し)の列が,左右対称であるものを求めよというのが,題意である。

そこで,以下のようなプログラミングになる。

permutations = function(n) { # 順列組み合わせの行列を生成
    z = matrix(1)
    if (n > 1) {
        for (i in 2:n) {
            x = cbind(z, i)
            a = c(1:i, 1:(i - 1))
            z = matrix(0, ncol = ncol(x), nrow = i * nrow(x))
            z[1:nrow(x), ] = x
            for (j in 2:i - 1) {
                z[j * nrow(x) + 1:nrow(x), ] = x[, a[1:i + j]]
            }
        }
    }
    z
}

partition = function(n) { # 整数 n を,いくつかの整数の和で表す方法を求める
        part.int.sub = function(n, k, a) {
        if (n == 0) {
            writeLines(paste(a, collapse=" "), f)
        } else if (n == 1) {
            writeLines(paste(c(a, 1), collapse =" "), f)
        } else if (k == 1) {
            writeLines(paste(c(a, rep(1, n)), collapse =" "), f)
        } else {
            if (n >= k) {
                part.int.sub(n - k, k, c(a, k))
            }
            part.int.sub(n, k - 1, a)
        }
    }
    f = textConnection("ans", "w")
    part.int.sub(n, n, NULL)
    close(f)
    ans # 各行に,解を格納する
}

g = function(p) { # 解の候補を精査する。合格なら 1,不合格なら 0 を返す
    num = NULL
    rev.p = rev(p)
    for (i in seq_along(p)) {
        num = c(num, rep(p[i], rev.p[i]))
    }
    ans = rle(num)
    ans = c(rbind(ans$values, ans$length))
    if (all(ans == rev(ans))) {
#            cat("num = ", paste(num, collapse=""), "\n") # 詳細表示が必要ならコメントアウト
#            cat("rle = ", ans, "\n")                     # 詳細表示が必要ならコメントアウト
        return(1)
    } else {
        return(0)
    }
}

f = function(n) { # 主関数
    perm = lapply(1:n, permutations) # 解の組み合わせを求める基礎
    part = partition(n) # 分割法法を得る
    m = length(part)
    count = 0
    for (i in seq.int(m)) { # それぞれの分割法法の組み合わせを検討
        p = as.integer(strsplit(part[i], " ")[[1]])
        k = length(p)
        if (n != 1 && k == n) { # すべての数字を 1 回ずつ繰り返すのは解になり得ない
            next
        }
        p = as.matrix(unique(as.data.frame(t(apply(perm[[k]], 1, function(x) p[x]))))) # チェックすべきパターンの生成
        for (i in 1:nrow(p)) {
            count = count+g(unname(p[i,])) # 左右対称の条件を満たせばカウントアップ
        }
    }
    cat(count)
}

f(1) # 1
f(2) # 1
f(3) # 3
f(4) # 4
f(5) # 7
f(6) # 14
f(7) # 23
f(8) # 39
f(9) # 71

なお,この数列は既知のものであり,個数だけを求めるならば,もっと簡単になる。

コメント

PPSP問題

2016年12月09日 | ブログラミング

PPSP問題

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

仕様

標準入力
・標準入力には4つのプログラム言語名がカンマ区切りで与えられます
・各言語名は Snake case で入力されます
・各言語名は [a-z] とアンダースコア( _ )の組み合わせからなります
【例】
ruby,java_script,python,c

標準出力
・1行目には各言語名の先頭の文字のみを結合し、大文字化した文字列を出力します
・2行目には各言語名を Pascal case に変換し、結合した文字列を出力します
【例(標準入力のケースに対応する出力)】
RJPC
RubyJavaScriptPythonC

Snake case とは
複合語をアンダースコアで結合し、全て小文字で書き表すこと。
地をはう蛇のように見えることからスネークケースと呼ばれる。
例えば SnakeCase を Snake case にすると snake_case になる。

Pascal case とは
複合語の各先頭を大文字にして結合し、先頭以外を小文字にして書き表すこと。
例えば pascal_case を Pascal case にすると PascalCase になる。

その他の仕様
・標準入力の末尾には改行があります
・標準出力の末尾に改行をつけてください
・標準入力の仕様で説明した内容以外の入力は行われません(不正入力に対するチェックは不要)

===========

できるだけ短くする

s = "ruby,java_script,python,c" # 入力
s = sapply(sapply(unlist(strsplit(s, ",")), function(t) unlist(strsplit(t, "_"))), function(t) {substr(t, 1, 1) = toupper(substr(t, 1, 1)); paste(t, collapse="")})
cat(substr(sapply(s, toupper), 1, 1), "\n", s, "\n", sep="") # 出力

コメント

ソートされないカード

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

ソートされないカード

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

設問
1〜n までの整数が1つずつ書かれている n 枚のカードを横一列に並べます。
カードを左から順に一枚ずつ見て、書かれている数字が i なら、左から i 番目のカードと交換する、
という作業を右端のカードまで繰り返します。

例えば、3, 2, 5, 4, 1の順に並んでいると、
最初のカードは 3 なので3番目のカードである 5 と交換し、5, 2, 3, 4, 1となります。
次のカードは 2 なので2番目のカードと交換(交換は発生しない)、
その次のカードは 3 なので3番目のカードと交換(交換は発生しない)、
その次のカードは 4 なので4番目のカードと交換(交換は発生しない)、
その次のカードは 1 なので1番目のカードである 5 と交換し、
1, 2, 3, 4, 5となり、昇順に並べ替えられます。
※カードは常に左から順番に見ていきます

右端まで処理した結果、書かれている数字が昇順に並ばない初期配置が何通りあるかを求めます。

標準入力から n が与えられるとき、書かれている数字が昇順に並ばない初期配置が何通りあるかを求め、
標準出力に出力してください。
例えば、n = 4 のとき、24通り中、以下の3通りがありますので、サンプルのように出力します。

2, 3, 4, 1
3, 4, 2, 1
4, 3, 1, 2
(n は最大で8とします。余裕がある人は、もう少し大きな n についても考えてみてください。)

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

標準出力
3

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

ブルートフォースでは,n=8 の場合に実行時間制限(1秒)に引っかかるのだが,細々したところをチューンアップして,なんとかねじ込んだ。

f = function(n) {
    z = matrix(1)
    if (n == 1) {
        cat(0)
    } else {
        for (i in 2:n) {
            x = cbind(z, i)
            a = c(1:i, 1:(i - 1))
            z = matrix(0, ncol = ncol(x), nrow = i * nrow(x))
            z[1:nrow(x), ] = x
            for (j in 2:i - 1) {
                z[j * nrow(x) + 1:nrow(x), ] = x[, a[1:i + j]]
            }
        }
        cat(sum(apply(z, 1, function(x) {
            for (i in seq_along(x)) {
                if (i != x[i]) {
                    t = x[i]
                    x[i] = x[t]
                    x[t] = t
                }
            }
            any(x != 1:n)
        })))
    }
}

f(3) # 0
f(4) # 3
f(5) # 35
f(6) # 325
f(7) # 2989
f(8) # 28630

コメント