裏 RjpWiki

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

三角形に分割しよう

2018年01月31日 | ブログラミング

三角形に分割しよう

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

三次元のグラフィックにおいて、立体的な形状を、メッシュと呼ばれる多数の三角形で表現します。

ここでは平面に与えられる多角形を対角線で分割して、三角形を組み合わせて表現されるようにします。
このとき、切断する対角線の長さの和が最小になるような切り方を求め、その対角線の長さの和を求めてください。

下図のような場合、緑の対角線とオレンジの対角線が考えられますが、緑の方が短いので、この長さが最小になります。

各頂点の座標は整数で与えられるものとし、最大10個が入力されます。

答えは小数第三位を四捨五入して小数第二位まで求めてください。
(ヒント:対角線の長さは三平方の定理で求めることができます。)

例えば、以下の入力が与えられる下図のような五角形の場合、図にある緑の対角線の長さを合計して、答えは「4.47」となります。
(与えられた順に線をつなぎ、最後の点と最初の点をつなぐものとします)

【入力】
1,2
2,1
4,1
5,2
3,3


なお、今回は凸多角形のみ対象とし、切断する対角線は頂点以外の場所で交差しないものとします。

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

f = function(x, y) {
  ans = Inf
  n = length(x) # 頂点数
  begin = end = integer(n*(n-3)/2) # 可能な対角線の始点と終点番号の対 1〜n
  m = n-3 # 実際に引かれる対角線の本数

  count = 0 # count = n*(n-3)/2 になる
  for (i in 1:(n-2)) {
    for (j in (i+2):(n-(i==1))) {
      count = count+1
      begin[count] = i
      end[count] = j
    }
  }
  # count 本の対角線から m 本の対角線を選び,内部で交差しないものを探す
  comb = combn(count, m)
  for (k in 1:ncol(comb)) {
    ok = TRUE
    for (i in 1:(m-1)) {
      for (j in (i+1):m) {
        if (!((begin[comb[i,k]] <= begin[comb[j,k]] && end[comb[j,k]] <= end[comb[i,k]]) ||
            (begin[comb[j,k]] <= begin[comb[i,k]] && end[comb[i,k]] <= end[comb[j,k]]) ||
            begin[comb[i,k]] >= end[comb[j,k]] ||
            begin[comb[j,k]] >= end[comb[i,k]])) {
          ok = FALSE
          break
        }
      }
      if (!ok) {
        break
      }
    }
    if (ok) {
      Length = 0
      for (i in 1:m) {
         Length = Length + sqrt((x[begin[comb[i,k]]] - x[end[comb[i,k]]])^2 +
            (y[begin[comb[i,k]]] - y[end[comb[i,k]]])^2)
      }
      ans = min(ans, Length)
    }
  }
  cat(round(ans, 2), "\n")
}
#arg = matrix(scan(file("stdin", "r"), sep=","), byrow=TRUE, ncol=2)
#f(arg[,1], arg[,2])

#f(c(1,2,4,5,3), c(2,1,1,2,3)) # 4.47
#f(c(0,1,3,4,2), c(1,0,0,1,2)) # 4.47
#system.time(f(c(0,2,3,3,2,0), c(1,0,1,3,4,3))) # 9.61
#system.time(f(c(0,1,2,3,3,2,1,0), c(1,0,0,1,2,3,3,2))) # 12.11, 0.133 s

Python3 に書き直してみる

import numpy as np
import itertools

def f(x, y):
    ans = np.Inf
    n = len(x) # 頂点数
    m = n-3 # 実際に引かれる対角線の本数
    begin = np.zeros(n*(n-3)/2) # 可能な対角線の始点番号 0〜n-1
    end = np.zeros(n*(n-3)/2)   # 可能な対角線の終点番号 0〜n-1
    count = 0 # count = n*(n-3)/2 になる
    for i in range(0, n-1):
        for j in range(i+2, n):
            if i != 0 or j != n-1:
                begin[count] = i
                end[count] = j
                count += 1
    # count 本の対角線から m 本の対角線を選び,内部で交差しないものを探す
    comb = list(itertools.combinations(range(count), m))
    for k in range(len(comb)):
        cb = comb[k]
        ok = True
        for i in range(m-1):
            for j in range(i+1, m):
                if not ((begin[cb[i]] <= begin[cb[j]] and end[cb[j]] <= end[cb[i]]) or
                (begin[cb[j]] <= begin[cb[i]] and end[cb[i]] <= end[cb[j]]) or
                begin[cb[i]] >= end[cb[j]] or begin[cb[j]] >= end[cb[i]]):
                    ok = False
                    break
            if not ok:
                break
        if ok:
            Length = 0
            for i in range(m):
                Length += np.sqrt((x[int(begin[cb[i]])] - x[int(end[cb[i]])])**2 +
                (y[int(begin[cb[i]])] - y[int(end[cb[i]])])**2)
            ans = min(ans, Length)
    print(round(ans, 2))

#f([1, 2, 4, 7, 8, 6, 3], [6, 4, 3, 3, 5, 8, 9]) # 19.49
#f([1,2,4,5,3], [2,1,1,2,3]) # 4.47
#f([0,1,3,4,2], [1,0,0,1,2]) # 4.47
#f([0,2,3,3,2,0], [1,0,1,3,4,3]) # 9.61
#f([0,1,2,3,3,2,1,0], [1,0,0,1,2,3,3,2]) # 12.11

def get_input():
    while True:
        try:
            yield ''.join(input())
        except EOFError:
            break

a = list(get_input())
x = np.zeros(len(a))
y = np.zeros(len(a))
for i in range(len(a)):
    b = a[i].split(",")
    x[i] = b[0]
    y[i] = b[1]
f(x, y)
# 1,2
# 2,1
# 4,1
# 5,2
# 3,3  # 4.47

コメント

R での文字列連結

2018年01月30日 | ブログラミング

https://t.co/Qongkd0zar

他にないかと思って検索すると

http://rpubs.com/hoxo_m/5731

が見つかった。paste を paste0 にして,以下の定義が好き。

"&" <- function(e1, e2) {
  if (is.character(c(e1, e2))) {
    paste0(e1, e2)
  } else {
    base::"&"(e1, e2)
  }
}

> "abc" & "12345" & "あいうえお"
[1] "abc12345あいうえお"

> "aa" & 123
[1] "aa123"

> TRUE & FALSE

[1] FALSE

 

# あのね,同じスクリプトで 1 千万回も繰り返し記述するわけではないのだから,paste0("aaa", "bbbb") でいいと思うワ。

 

コメント

迷路

2018年01月27日 | ブログラミング

迷路

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



【概要】
右図のような迷路があります。
一歩で、上下左右に進めますが、太線は壁なので超えられません。
右図の a, b, c, d は、門を表しています。
門は開いているかもしれませんし、閉じているかもしれません。

開いている門・スタート地点・ゴール を指定します。
スタートからゴールに行くには最低何歩必要なのかを計算してください。
※入力で指定された門以外は、全て閉じているものとします

【入力】
入力は三文字で、
a8K
のようになっています。

開いている門・スタート・ゴール の3つが区切り文字なしで並んでいます。

【出力】
スタート地点からゴール地点まで何歩なのかを10進数で出力してください。
先ほどの入力の場合、a が通行可能であれば 8 から K まで 4歩で行けるので、
4
を出力すれば正解です。

【例】
入力
出力
状況
a8K
4

b9L
4

cAS
3

dR3
8


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

f = function(s) {
    d = matrix(
      c("6"," "," "," ", # 0 は 6 への径路
        "2"," "," "," ",
        "1","3","8"," ",
        "2","4"," "," ",
        "3","5","A"," ",
        "4"," "," "," ",
        "0","7"," "," ",
        "6","8","aD"," ",# gate 'a' 指定されたら小文字の a,b,c,d を取り径路候補に加える
        "2","7"," "," ",
        "A","F"," "," ",
        "4","9","G","dB",# gate 'd'
        "H","dA"," "," ",# gate'd'
        "D"," "," "," ",
        "C","J","a7"," ",# gate 'a'
        "K","bF"," "," ",# gate 'b'
        "9","bE"," "," ",# gate 'b'
        "A","cM"," "," ",# gate 'c'
        "B","N"," "," ",
        "J","O"," "," ",
        "D","I","K","P",
        "E","J","L"," ",
        "K"," "," "," ",
        "N","S","cG"," ",# gate 'c'
        "H","M","T"," ",
        "I","U"," "," ",
        "J"," "," "," ",
        "R","W"," "," ",
        "Q","S"," "," ",
        "M","R"," "," ",
        "N","Z"," "," ",
        "O","V"," "," ",
        "U","W"," "," ",
        "Q","V"," "," ",
        "Y"," "," "," ",
        "X","Z"," "," ",
        "T","Y"," "," "),36,byrow = TRUE)
    node = c(0:9, LETTERS)
    rownames(d) = node
    s = unlist(strsplit(s, ""))
    gate = s[1]
    d = sub(gate, "", d) # 指定されたゲートを開ける
    if (gate == "a") { # 指定以外のゲートは閉じるだけでなくパスから除く
      d = sub("[bcd][0-9A-Z]", " ", d)
    } else if (gate == "b") {
      d = sub("[acd][0-9A-Z]", " ", d)
    } else if (gate == "c") {
      d = sub("[abd][0-9A-Z]", " ", d)
    } else if (gate == "d") {
      d = sub("[abc][0-9A-Z]", " ", d)
    }
    start = c(s[2], " ", " ", " ")
    goal  = s[3]
    path = NULL

    push = function(x) { # パスのプッシュ
      rbind(x, path) ->> path
    }

    pop = function() { # パスのポップ
      if (is.null(path)) {
        push(start)
      }
      top = path[1,]
      path[-1,] ->> path
      return(top)
    }

    push(start)
    log = NULL
    repeat {
      x = pop()
      found = FALSE
      for (i in 1:4) {
        if (x[i] != " " && !x[i] %in% log) {
          log = c(x[i], log)
          found = TRUE
          break
        }
      }
      if (found) {
        if (x[i] == goal) {
          #cat("I got it!! ", rev(log), "\n")
          cat(length(log)-1)
          break
        }
        y = d[x[i],]
        x[i] = " "
        push(x)
        push(y)
      } else {
        log = log[-1]
      }
    }
}
#f(scan(file("stdin", "r"), what=""))

f("a8K") # 4
f("a8K") # 4
f("b9L") # 4
f("cAS") # 3
f("dR3") # 8
##
f("a5G") # 3
f("aBL") # 14
f("aAB") # 19
f("bP1") # 10
f("b5B") # 19
f("b7D") # 11
f("c1F") # 6
f("cXF") # 9
f("cFE") # 15
f("d0E") # 22
f("dC0") # 22
f("dMG") # 5



コメント

ドット絵の丸が2つ

2018年01月26日 | ブログラミング

ドット絵の丸が2つ

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

【概要】
マス目に沿った、円のような形を2つ指定します。
両者に含まれるマスの数を計算してください。

【入出力】
入力は
1,2,3 4,5,4
のようになっています。
空白区切りで2つの図形が並んでいます。

各図形は、コンマ区切りで 中心のx座標、中心のy座標、半径 をならべたものです。
マス目の中心と中心の距離が、半径以下のマスが図形に含まれます。

具体的には下のとおりです:

上 0,0,0
中 1,2,3
下 4,5,6


出力は、普通に10進数です。
2つの図形の両方に含まれるマスの数を答えてください。

【例】
上 入力 1,2,3 4,5,4 出力 10
中 0,1,5 4,8,6 出力 16
下 0,1,6 3,2,3 出力 28


【補足】
    •    不正な入力に対処する必要はありません。
    •    中心座標は 0以上一万以下です。
    •    半径の値は 0以上一万以下です。
    •    中心座標・半径は、いずれも0以上の整数ですが、マス目はマイナスの座標にもあります。

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

R だと,ベクトル演算とかその他のこそくな手段を用いても,制限時間の 1 秒を超える場合がある。

f = function(x1, y1, r1, x2, y2, r2) {
    r12 = r1^2
    r22 = r2^2
    count = 0
    for (x in (x1 - r1):(x1 + r1)) {
        x.x1 = r12-(x - x1)^2
        x.x2 = r22-(x - x2)^2
        if (x.x1 >= 0 && x.x2 >= 0) {
            temp = floor(sqrt(x.x1))
            count = count+sum(x.x2 >= ((y1 - temp):(y1 + temp) - y2)^2)
        }
    }
    cat(count)
}

#arg = as.integer(unlist(strsplit(readLines(file("stdin", "r"), "[, ]"))))
#f(arg[1], arg[2], arg[3], arg[4], arg[5], arg[6])

f(1, 2, 3, 4, 5, 4) # 10
f(0, 1, 5, 4, 8, 6) # 16
f(0, 1, 6, 3, 2, 3) # 28
f(0,0,0, 0,0,0) # 1
f(0,1,1, 0,2,1) # 2
f(1,1,1, 6,6,6) # 0
f(1,1,3, 7,7,7) # 5
f(7,14,17, 2,2,1) # 5
f(9,7,13, 8,4,18) # 529
f(12,15,17, 7,16,12) # 440
f(8,4,7, 16,16,7) # 0
system.time(f(2915,2254,4079, 9917,3046,7286)) # 24893077, 0.591sec.
system.time(f(5520,1032,740, 1982,2459,2672)) # 0, 0.091sec.
system.time(f(10000,10000,10000, 10000,10000,10000)) # 314159053, 5.600sec.
system.time(f(0,0,10000, 10000,10000,10000)) # 57079527, 2.815sec.

=====

Java では,あまり懲りすぎると帰って遅くなるので,以下の程度の最適化で十分。

    static int sq(int x) {
        return x * x;
    }

    static void f(int x1, int y1, int r1, int x2, int y2, int r2) {
        int minX, minY, maxX, maxY, count, x, y, r12, r22;
        minX = x1-r1;
        minY = y1 - r1;
        maxX = x1 + r1;
        maxY = y1 + r1;
        r12 = r1 * r1;
        r22 = r2 * r2;
        count = 0;
        for (x = minX; x
            if (sq(x-x1) > r12 || sq(x - x2) > r22) continue;
            for (y = minY; y
                if (r12 >= sq(x - x1) + sq(y - y1) && r22 >= sq(x - x2) + sq(y - y2)) {
                    count++;
                }
            }
        }
        System.out.println(count);
    }

コメント

連続する正の整数の和

2018年01月23日 | ブログラミング

連続する正の整数の和

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

ある数を「連続する正の整数の和」で表現することを考えます。
例えば、15は「1+2+3+4+5」「4+5+6」「7+8」のように表現できます。
このように複数の表現が可能で、しかもその表現で使われる数が連続するものを探します。
例えば、15の場合は「4+5+6」「7+8」が「4, 5, 6, 7, 8」のように連続します。

このように連続する表現が可能な数を小さい方から順に調べると、3, 15, 27, …となります。

・ 3 … 1 + 2, 3
・ 15 … 4 + 5 + 6, 7 + 8
・ 27 … 2 + 3 + 4 + 5 + 6 + 7, 8 + 9 + 10

標準入力から整数 n が与えられたとき、小さい方から n 番目の数を標準出力に出力してください。
なお、n は80以下の整数とします。

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

標準出力
15

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

これは,オンライン整数列大辞典の A110703 であるが,漸化式のようなものは知られていないようだ。
ただし,これを満たす n は 3 の倍数であること,数列を (a, a+1, ..., b) と (b+1, b+2, ..., c) としたとき,
a * (1 - a) + b * (1 + b) = 2n
-b * (1 + b) + c * (1 + c) = 2n
a * (1 - a) + c * (1 + c) == 4n
という関係式があるの(2つで十分,他の1つは従属)で,探索範囲を狭めることができる。

解答先のシステムの R が極端に遅く,Python3 は速い。
当方では R が速く,Python3 が遅いという。
なんとも,間抜けな事態である。

R プログラム

当方では f(80) が 0.1 秒ほどだが,投稿先ではなんと 1 秒を超える??

f = function(n) {
  ans = NULL
  for (a in 1:255) {
    for (b in a:255) {
      b2 = b*(1+b)
      x = a*(1-a)+b2
      for (c in b:255) {
        y = c*(1+c)-b2
        if (y > x) {
          break
        } else if (y == x) {
          ans = c(ans, x)
        }
      }
    }
  }
  cat(sort(unique(ans/2))[n])
}

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

system.time({
  f(80)
}) # 0.109 seq.

f(2) # 15
f(10) # 147
f(35) # 945
f(70) # 3267
f(80) # 3978


Python プログラム

import numpy as np

def f(n):
  mx = 4000
  ans = np.zeros(mx)
  count = 0
  for a in range(1, 256):
    for b in range(a, 256):
      b2 = b*(1+b)
      x = a*(1-a)+b2
      for c in range(b, 256):
        y = c*(1+c)-b2
        if y > x:
          break
        elif x == y:
          ans[count] = x
          count += 1
  ans = np.sort(ans/2)
  g = ans
  count = 0
  for i in range(1, mx):
    if ans[i] != ans[i-1]:
      g[count] = ans[i]
      count += 1
  print(int(g[n-1]))

f(int(input()))

f(80) が 0.268 seq.

コメント

あ?ここまで来たか?

2018年01月22日 | 雑感

https://www3.nhk.or.jp/news/html/20180122/k10011297461000.html

>「不要不急」って何? ネットに判断迷うという声

そんなことも,自分で決められないようになってしまったのか

あるいは,「だって,○○だっていわれたから」という,言い訳が必要になってしまったのか

 

いずれにせよ,なげかわしい。

コメント

何種類の直方体が作れるか?

2018年01月14日 | ブログラミング

設問

直方体の辺の長さ a, b, c (a ≦ b ≦ c) は整数で,a+b+c = n とする。
n を与えたとき,何通りの直方体があるかを求める関数 f(n) を書け。
f(10) = 12, f(50) = 225, f(100) = 867 である。
f(50000) を求めよ。どのような言語を使っても良いが,実行時間はおおむね 1 秒以内とする。

解答例はコメントを参照。

コメント (1)

割り算

2018年01月14日 | ブログラミング

割り算

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

【概要】
割り算をしてください。

【入力】
入力は
1230/10
のようになっています。
除算記号は「/」です。
除数・被除数ともに、正の整数です。

【出力】
出力は、下のルールに従ってください。
除算の結果と出力形式
整数の場合        整数として出力してください。
            小数点や「/1」などをつけてはいけません。
有限小数で表現できる場合
            有限の小数として出力してください。
            先頭は、値が1未満の場合は「0.」で、それ以外は 0 以外にしてください。
            末尾は 0 以外にしてください。
上記以外の場合
            既約分数として出力してください。
            右の例の通り「/」の前後に空白は不要です。

【例】
入力        出力
1230/10    123
12345/10   123.45
123/45     41/15
2/5        0.4

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

10 進数で有限小数として表現できるためには,既約分数にしたときの分母の素因子が 2 または 5 のみであること(分母 = 2^m * 5^n)

f = function(s) {
  euclid = function(m, n) {
    while ((temp <- n %% m) != 0) {
      n <- m
      m <- temp
    }
    return(m)
  }
  two.five = function(n) {
    while(n %% 2 == 0) {
      n = n/2
    }
    while(n %% 5 == 0) {
      n = n/5
    }
    return(n == 1)
  }
  n = as.numeric(unlist(strsplit(s, "/")))
  n1 = n[1]
  n2 = n[2]
  n0 = euclid(n1, n2)
  n1 = n1/n0
  n2 = n2/n0
  if (two.five(n2)) {
    cat(sprintf("%.16g", n1/n2))
  } else{
    cat(sprintf("%.16g/%.16g", n1, n2))
  }
}
#f(readLines(file("stdin", "r")))

f("1230/10") # 123
f("12345/100") # 123.45
f("123/45") # 41/15
f("2/5") # 0.4

f("623329371537/799485550592") # 0.7796630859375
f("495306592950/219031126016") # 2.2613525390625
f("877176068377/716862166016") # 1.2236328125
f("96472946117/384354367") # 251
f("1/1") # 1
f("797441094684/769082312705") # 125892/121415
f("951731929962/379731426601") # 198/79
f("1000000000000/1") # 1000000000000
f("1/1000000000000") # 1e-12
f("1000000000000/999999999999") #
f("1/762939453125") # 1.31072e-12
f("541130809335/549755813888") # 0.9843112081125582


コメント

英語でプリーズ!

2018年01月10日 | ブログラミング

英語でプリーズ!

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

【英語でプリーズ!】
与えられた整数値を、英語に変換するプログラムを作成してください。
たとえば"123"なら"One Hundred Twenty Three"、"-50000"のような負の数は、"Negative Fifty Thousand"のように出力してください。
必要な英単語は以下になります。

Zero
One
Two
Three
Four
Five
Six
Seven
Eight
Nine
Ten
Eleven
Twelve
Thirteen
Fourteen
Fifteen
Sixteen
Seventeen
Eighteen
Nineteen
Twenty
Thirty
Forty
Fifty
Sixty
Seventy
Eighty
Ninety
Hundred
Thousand
Million
Billion
Negative

【入力】
標準入力から1行目には入力データ数N(1≦N≦100)が、2行目以降には整数値が与えられます。
2行目以降のN行分の整数値を英語に変換してください。
ただし、入力データは符号付き32bit整数の範囲で収まるものに限ります。

【出力】
標準出力に、変換後の英語を出力してください(入力データ毎に改行してください)。
アルファベットの大文字・小文字は問いません。

【入出力サンプル】
Input

7
123
4567
89012
0
-34
-5678901
1111111111

Output

One Hundred Twenty Three
Four Thousand Five Hundred Sixty Seven
Eighty Nine Thousand Twelve
Zero
Negative Thirty Four
Negative Five Million Six Hundred Seventy Eight Thousand Nine Hundred One
One Billion One Hundred Eleven Million One Hundred Eleven Thousand One Hundred Eleven

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

g = function(n) {
    o1 = c("", "One", "Two", "Three", "Four", "Five", "Six", "Seven", "Eight", "Nine",
        "Ten", "Eleven", "Twelve", "Thirteen", "Fourteen", "Fifteen", "Sixteen",
        "Seventeen", "Eighteen", "Nineteen")
    o2 = c("Twenty", "Thirty", "Forty", "Fifty", "Sixty", "Seventy", "Eighty", "Ninety")
    o3.1 = ""
    o3.2 = c("One Hundred", "Two Hundred", "Three Hundred", "Four Hundred", "Five Hundred",
        "Six Hundred", "Seven Hundred", "Eight Hundred", "Nine Hundred")
    and = "" # \and\""
    a = c(t(outer(o3.1, c(o1, t(outer(o2, o1[1:10], paste))), paste)), t(outer(o3.2,
        paste(and, c(o1, t(outer(o2, o1[1:10], paste)))), paste)), "One Thousand")[-1]
    a[n]
}

f = function(n) {
    if (n == 0) {
        "Zero"
    } else {
        unit = c("Billion ", "Million ", "Thousand ", "")
        m = integer(4)
        negative = n < 0
        n = abs(n)
        for (i in 1:4) {
            m[5 - i] = n%%1000
            n = n%/%1000
        }
        a = ifelse(negative, "Negative", "")
        for (i in 1:4) {
            if (m[i] != 0) {
                a = c(a, g(m[i]), unit[i])
            }
        }
        a = paste(a, collapse = " ")
        a = gsub(" +", " ", a)
        a = sub("^ ", "", a)
        sub(" $", "", a)
    }
}
# arg = scan(file("stdin", "r"))[-1]
# for (i in arg) {
#   cat(sprintf("%s\n", f(i)))
# }

f(123) # One Hundred Twenty Three
f(4567) # Four Thousand Five Hundred Sixty Seven
f(89012) # Eighty Nine Thousand Twelve
f(0) # Zero
f(-34) # Negative Thirty Four
f(-5678901) # Negative Five Million Six Hundred Seventy Eight Thousand Nine Hundred One
f(1111111111) # One Billion One Hundred Eleven Million One Hundred Eleven Thousand One Hundred Eleven
f(15674873) # Fifteen Million Six Hundred Seventy Four Thousand Eight Hundred Seventy Three
f(4620818) # Four Million Six Hundred Twenty Thousand Eight Hundred Eighteen
f(14440117) # Fourteen Million Four Hundred Forty Thousand One Hundred Seventeen
f(6868461) # Six Million Eight Hundred Sixty Eight Thousand Four Hundred Sixty One
f(14181126) # Fourteen Million One Hundred Eighty One Thousand One Hundred Twenty Six
f(-311541354) # Negative Three Hundred Eleven Million Five Hundred Forty One Thousand Three Hundred Fifty Four
f(504349000) # Five Hundred Four Million Three Hundred Forty Nine Thousand
f(126556530) # One Hundred Twenty Six Million Five Hundred Fifty Six Thousand Five Hundred Thirty
f(1301679771) # One Billion Three Hundred One Million Six Hundred Seventy Nine Thousand Seven Hundred Seventy One
f(-223594969) # Negative Two Hundred Twenty Three Million Five Hundred Ninety Four Thousand Nine Hundred Sixty Nine

コメント

ファミリーレストランのテーブルを配置して!

2018年01月09日 | ブログラミング

ファミリーレストランのテーブルを配置して!

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

客の人数に合わせてテーブルを動かすファミリーレストランを考えます。
例えば、1人客や2人組の客を、4人掛けのテーブルに通せば、残りの席が無駄になります。
そこで、2人掛けテーブルを組み合わせて、できるだけ効率よくテーブルを配置しています。

店内に2人掛けテーブルが m 個あり、n 人の客が店内にいるとき、テーブルの組み合わせ方として考えられるものが何通りあるか求めてみます。
このとき、どの客がどのテーブルのどこに座っているかは区別せず、テーブルの位置も区別しないものとします。
つまり、以下のような配置はいずれも同じ(1通り)とします。

なお、相席になることはないものとし、1人客でも2人掛けのテーブルを使いますし、3人客の場合は2人掛けのテーブルを2つ使います。

例えば、m = 3, n = 5 のとき、以下の4通りが考えられます。
(●…座っている人、〇…空席)

標準入力から m, n がスペース区切りで与えられるとき、テーブルの配置が何通りあるかを求め、標準出力に出力してください。
なお、m, n は 0 < m < n ≦ 80 を満たす整数とします。


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

標準出力
4

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

整数分割法の問題であるが,m, n が大きくなると実行時間がかかる。
n が小さい部分での解を求め(図 1),規則性を探る。

この行列を各列とも,1行目から始まるように上揃えにする(図2)

各列は,1, 2, 5, 10, ... となるが,これは A000712 であるが,1行目から ceiling((j + 1)/2) 行目(水色で示したセル)までが有効。
黄緑で示したセル a[j + 1, j],j = 1,2,3, ... は A000041[j]
赤で示したセルは a[j, j],j = 3,4,5, ...
  a[j, j] = a[j, j-1] + a[j-1, j-1]
赤のセルの 1 つ上のセルは a[j-1, j],j=5,6,7, ...
  a[j-1, j] = a[j-1, j-1] + a[j-3, j-2]
更にその 1 つ上のセルは a[j-2, j],7,8,9, ...
  a[j-2, j] = a[j-2, j-1] + a[j-5, j-3]
更にその 1 つ上のセルは a[j-3, j],9,10,11, ...
  a[j-3, j] = a[j-3, j-1] + a[j-7, j-4]
:::
となっているので,以下のプログラムを得る。

f = function(M, N) {
  m = 80

  A000203 = function(n) {
    a = integer(n)
    s = 0
    for (i in 1:n) {
      for (j in 1:i) {
        s = s + cos((2 * pi * n * j)/i)
      }
    }
    s
  }
  a000203 = sapply(1:80, A000203)

  A000041 = function(m) {
    a = integer(m)
    for (n in 1:m) {
      b = 0
      for (k in 0:(n - 1)) {
        b = b + a000203[n - k] * ifelse(k == 0, 1, a[k])
      }
      a[n] = b/n
    }
    a
  }
  a000041 = A000041(80)
 
  A000712 = function(m) {
    a = integer(m)
    for (n in 1:m) {
      b = c(1, a000041[1:(n - 1)])
      a[n] = sum(b * rev(b))
    }
    a[1] = 1
    a
  }
  a000712 = A000712(80)

  n = m + 1
  a = matrix(0, n, m)

  for (j in 1:m) {
    i = 1:ceiling((j + 1)/2)
    a[i, j] = a000712[i]
  }

  for (j in 1:m) {
    a[j + 1, j] = a000041[j]
  }

  for (k in 0:(m/2 - 2)) {
    for (j in (2 * k + 3):m) {
      a[j - k, j] = a[j - k, j - 1] + a[j - k * 2 - 1, j - k - 1]
    }
  }
  cat(a[N - M + 1, M])
}

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

system.time(f(3, 5)) # 4
system.time(f(6, 10)) # 17
system.time(f(20, 30)) # 481
system.time(f(35, 62)) # 203415
system.time(f(45, 80)) # 2086851

参考までに,図1 を得るための,n の分割による解法プログラム

initDiv = function(length, max) {
  ary = NULL
  repeat {
    if (length <= max) {
      ary = c(ary, length)
      return(ary)
    } else {
      ary = c(ary, max)
      length = length - max
    }
  }
}

nextDiv = function(ary) {
  repeat {
    sum = 0
    for (pos in length(ary):1) {
      a = ary[pos]
      sum = sum + a
      if (a != 1) {
        break
      }
    }
    if (ary[1] == 1) {
      return(FALSE)
    }
    ary = ary[1:pos]
    ary[pos] = ary[pos] - 1
    max = ary[pos]
    sum = sum - max
    pos = pos + 1
    repeat {
      if (sum <= max) {
        ary[pos] = sum
        return(ary)
      } else {
        ary[pos] = max
        sum = sum - max
      }
      pos = pos + 1
    }
  }
}

f = function(m, n) {
  first = TRUE
  count = 0
  repeat {
    if (first) {
      d = initDiv(n, n)
      first = FALSE
    } else {
      d = nextDiv(d)
      if (d[1] == FALSE) {
        break
      }
    }
      cnt = 0
      for (k in d) {
        cnt = cnt + ceiling(k / 2)
        if (cnt > m) {
          break
        }
      }
    if (cnt == m) {
      count = count + 1
    }
  }
  cat(count)
}

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

#f(3, 5) # 4
#f(6, 10) # 17
#f(20, 30) # 481
#system.time(f(35, 62)) # 203415
#system.time(f(45, 80)) # 2086851


コメント

統計データからの知見と直感?のせめぎ合い

2018年01月08日 | 統計学

引き続き,陸王の4回目を見ている。

ソールの見直しを進言するシューフッターに,「最新マシンから得られた100項目以上のテストデータと,過去10年の全レース結果を解析して完成させたものだ。なんの問題があるんだ。」とお怒りモード。

それに対して「統計学的データは大事ですが,選手は生身の人間です。パソコンのデータだけをみて判断するのは危険です。」と反論。

どっちもどっちだけど,「パソコンのデータだけをみて判断するのは危険」というのも程度問題。データをちゃんと解析して出した結果ならいいんだけど。結果ありきの解析だとそりゃだめだよね。

コメント

重回帰分析の用途---「陸王」より

2018年01月08日 | 統計学

いまやっとこさ,録りだめしていた「陸王」の第三回を見ていたのだけど,今回の話は陸王のソールにするシルクレイの最適な硬度を得るための試行錯誤の物語だった。

シルクレイの開発者は,繭を圧縮する工程パラメータを行き当たりばったりに求めようとしていた。開発者の助手を務める主人公の息子は,それに何の提言もできなかった。

幾多の失敗のあげく繭を煮る温度が関係するのではないかと,これまた偶然気づくわけだが,その根拠が開発者曰く「感だよ!感!!」。

息子は工学部卒とのことだったけど,「製品の硬度」を従属変数として「繭を圧縮する工程パラメータ」,「繭を煮る温度」を独立変数として数点のデータを得て重回帰分析(あるいは非線形回帰)をすれば,もっと速く正確に最適解が得られたのではないか?

その他にも重要なパラメータがあるやも知れず。

コメント

ツリーの中にない数

2018年01月05日 | ブログラミング

ツリーの中にない数

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

【概要】
数が並んでいるツリーがあります(下図)。

だいたいどの要素にも子供が2つあります。
2つの子供は
・ 親×(二分の一)-M( 端数切り捨て。M は入力で指定 )
・ 親×(三分の二)-N( 端数切り捨て。N は入力で指定 )
です。
ただし、子の値が正の整数にならない場合はその子要素は存在しないことにします。

ルートの要素と M と N を指定します。
ツリーに現れない正の整数で、もっとも小さな値を計算してください。

【入出力】
入力は
123 4 5
のようになっています。
ルート要素、M、N が空白区切りで並んでいます。

出力は、普通に10進数です。
図の通り、ツリーに現れない最小の正の整数は 9 なので
9
を出力すれば正解です。

【例】
入力            出力
123 4 5         9
456 5 43        1
1414 2 135      3

【補足】
不正な入力に対処する必要はありません。
・ 0 < ルート要素 ≦ 二十億 です。
・ 0 ≦ M ≦ 千, 0 ≦ N ≦ 千 です。
・ ルート要素、M、N はいずれも整数です。

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

R でシンプルに書けるが,実行時間が掛かる。
Java で書いて,なおかつ実行時間を稼ぐために,こそくな手段を用いる。

R プログラム

f = function(root, m, n) {
    pool = root
    ans = NULL
    while (length(pool) > 0) {
        oya = pool[1]
        pool = pool[-1]
        ko = floor(oya/2-m)
        if (ko > 0) {
            ans = c(ko, ans)
            pool = c(ko, pool)
        }
        ko = floor(oya*2/3-n)
        if (ko > 0) {
            ans = c(ko, ans)
            pool = c(ko, pool)
        }
    }
    missing = 1:max(ans)
    missing[ans] = NA
    cat(min(missing, na.rm=TRUE))
}

f(123, 4, 5) # 9
f(456, 5, 43) # 1
f(1414, 2, 135) # 3

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

Java プログラム

import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        if (true) {
            Scanner cin = new Scanner(System.in);
            String line = cin.nextLine();
            String[] line2 = line.split(" ");
            int root = Integer.parseInt(line2[0]);
            int M = Integer.parseInt(line2[1]);
            int N = Integer.parseInt(line2[2]);
            f(root, M, N);
        } else {
            // f(123, 4, 5); // 9
            // f(456, 5, 43); // 1
            // f(1414, 2, 135); // 3
            // f(2000000000, 992, 0); // 31715
            // f(2000000000, 2, 987); // 30233
            // f(2000000000, 953, 996); // 19543
            // f(128500249, 67, 151); // 4462
            // f(47736148, 133, 136); // 2327
            // f(21844316, 501, 56); // 6295
            // f(89128932, 320, 123); // 3871
            // f(293375679, 55, 161); // 6868
            // f(529943805, 130, 49); // 1957
            // f(1, 0, 0); // 2
            // f(1, 2, 3); // 2
            // f(3, 0, 0);
        }
    }

    static void f(int root, int M, int N) {
        int mx  = 500000;
        int mx2 = 100000000;
        boolean[] exists = new boolean[mx2];
        int[] pool = new int[mx];
        int[] ans = new int[mx];
        int n = 1;
        pool[n] = root;
        int count = 0;
        double oya;
        int ko;
        int i, j;
        while (n > 0) {
            oya = pool[n--];
            ko = (int) (oya / 2 - M);
            if (ko > 0) {
                if (ko < mx2) {
                    if (exists[ko]) {
                        i = 0;
                    } else {
                        i = count;
                        exists[ko] = true;
                    }
                } else {
                    for (i = 0; i < count; i++) {
                        if (ans[i] == ko) {
                            break;
                        }
                    }
                }
                if (i == count) {
                    ans[++count] = ko;
                    pool[++n] = ko;
                }
            }
            ko = (int) (oya * 2 / 3 - N);
            if (ko > 0) {
                if (ko < mx2) {
                    if (exists[ko]) {
                        i = 0;
                    } else {
                        i = count;
                        exists[ko] = true;
                    }
                } else {
                    for (i = 0; i < count; i++) {
                        if (ans[i] == ko) {
                            break;
                        }
                    }
                }
                if (i == count) {
                    ans[++count] = ko;
                    pool[++n] = ko;
                }
            }
        }
        if (count == 0) {
            System.out.println(root + 1);
        } else {
            for (i = 1; i <= root + 1; i++) {
                for (j = 1; j <= count; j++) {
                    if (ans[j] == i) {
                        break;
                    }
                }
                if (j > count) {
                    if (i == root) {
                        i++;
                    }
                    System.out.println(i);
                    break;
                }
            }
        }
    }
}

コメント

レースゲームの最終順位を決めよう

2018年01月05日 | ブログラミング

レースゲームの最終順位を決めよう

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

あなたはレースゲームの開発に携わっており、プレイヤーの最終順位を決めるアルゴリズム開発を任されました。
そのゲームは、複数のレースを行い、各レースの順位から最終順位を決めるのですが、順位はそのまま合計したり、算術平均してもおかしな結果になってしまいます。

これは、順位は大小には意味があっても、間隔には意味はないため、1位+2位が3位を意味しないように、足し算引き算が成立しないことに起因します。
そこで、ひとまず「調和平均」を用いて、解決してみることにしました。

求められるプログラムの前提条件は、以下の通りとなります。

・ 標準入力から、各レースの順位(スペース区切り)が、次のようにプレイヤーの人数分複数行送られる
  (プレイヤー1) 1回目のレースの順位 2回目のレースの順位 3回目のレースの順位 ...
  (プレイヤー2) 1回目のレースの順位 2回目のレースの順位 3回目のレースの順位 ...
    :
    :
・ 入力されるテキストの行番号をプレイヤーの番号とみなす
・ プレイヤーの人数は、2人以上12人以下とする
・ レースの回数は、2回以上4回以下とする
・ 各レースにおける順位に、重複や欠落はないものとする
・ 最終順位は、プレイヤーごとの全レースの順位の調和平均(Wikipediaへのリンク)が低い順に求める
・ このとき調和平均が同じプレイヤー同士は、同じ順位とし、下の順位に合わせる。
  例えば、プレイヤーが3人で、上位2人が同じ調和平均の場合、2位が2名、3位が1名となる
・ 求めた最終順位をプレイヤーの番号順に、改行区切りで標準出力に送ること

そして 以下が、入力と出力例になります。

No.   入力例     出力例
1   2 4 3 4    3
      1 1 2 1    1
      3 2 1 2    2
      4 3 4 3    4
 
2     1 2        1
      2 5        3
      3 4        5
      4 3        5
      5 1        2

上記の1番目の例の場合、各プレイヤーの順位の調和平均は、小数点第5位以下切捨てで、次のようになります。
3.0000
1.1428
1.7142
3.4285

この数字が小さいほど上位となるので、プレイヤーの番号順に 3位 1位 2位 4位となるわけですね。
この最終順位は、直観的にも納得がいく結果ではないでしょうか。

実際のゲームでは順位を 1位→15pts、2位→12pts、3位→10pts という風にポイントに換算し、
ポイントの合計で最終順位を決めるのが一般的です。
ただ順位という数字を通じて、平均にもいろんな種類があり、適材適所で活用できることに気づいていただけたら幸いです。

【問題】
標準入力から、レースゲームにおける各レースの順位が、プレイヤーの人数分複数行送られます。
全レースの順位の調和平均から、各プレイヤーの最終順位を求め、その結果を標準出力に返してください。

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

f = function(s) {
    n = length(s)
    score = numeric(n)
    for (i in 1:n) {
        score[i] = 1/mean(1/as.numeric(unlist(strsplit(s[i], " "))))
    }
    cat(sprintf("%i\n", rank(score, ties.method="max")), sep="")
}

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

f(c("2 4 3 4", "1 1 2 1", "3 2 1 2", "4 3 4 3")) # 3,1,2,4

f(c("1 2", "2 5", "3 4", "4 3", "5 1")) # 1,3,5,5,2

コメント

大騒ぎしないこと(^_^)

2018年01月04日 | 雑感

いろんなサイト,特に,○○知恵袋とかエクィータ?とか,なんとかかんとか,自分のブログとか

自分が今まで知らなかったこと(関数)を見つけて,うれしくって,ほかの人にも発見の喜びを伝えたくて(?)記事を書く....

相当,恥ずかしいよね〜〜〜恥恥(^_^;)(^_^;) 今どき顔文字も恥ずかしいけどね〜〜〜(^_^;)

例えばね〜〜,head とか tail の第 2 引数に,マイナスを指定するとどうなると思う?とかね。

> a = 1:10
> head(a, -2)

[1] 1 2 3 4 5 6 7 8
> tail(a, -2)
[1]  3  4  5  6  7  8  9 10

head の方は,length を使わなくてもいいから,案外使い出があるのかも

> a[1:(length(a)-2)]
[1] 1 2 3 4 5 6 7 8
> a[-(1:2)]
[1]  3  4  5  6  7  8  9 10

コメント