裏 RjpWiki

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

アダムズ方式で議席数を計算

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

当初決められていた締め切りが 6月21日(火)10:00 AM なので,その 1 分後に投稿されるように予約
なお,締め切り日が延期されても,関知しない

衆院選挙制度改革法が成立し、「アダムズ方式」による議席数の割り当てが2020年の国勢調査に基づき用いられることが決まりました。
アダムズ方式は、各都道府県の人口を「ある同じ数値」で割って、その答えの合計が全国の議席数と同一になるように割る値を調整する計算方式です。
商が小数になる場合は切り上げることになっています。


例えば、250人、200人、150人の3つの県から10議席を選ぶとき、それぞれ65で割ると3.84…、3.07…、2.30…なので4,4,3となり合計が10になりません。
それぞれ75で割ると3.33…、2.66…、2なので4,3,2となりこれも合計が10になりません。
しかし、それぞれ70で割ると3.57…、2.85…、2.14…なので4,3,3となり合計が10になります。


標準入力の一行目に「議席数の合計」と「小選挙区の数」、二行目以降に小選挙区の数の分だけ人口が与えられます。
このとき、標準出力に各小選挙区の議席数を出力してください。


なお、人口として与えられる数は最大で1500万、小選挙区の数は最大で50とします。
「議席数の合計」「小選挙区の数」「人口」「割る数」のいずれも整数です。
※各小選挙区の議席数が一意に決まらないような入力は考えなくてもよいものとします。


【入出力サンプル】
標準入力
10,3
250
200
150

標準出力
4
3
3

例解

EPS = 1-1e-14

root = function(k, n) {
    f = function(x) sum(as.integer(k/x+EPS))-n
    left = 1
    right = max(k)
    repeat {
        mid = as.integer((left+right)/2)
        if (100 > right - left) {
            return(c(left, right))
        } else if (f(mid)*f(right) > 0) {
            right = mid
        } else {
            left = mid
        }
    }
}

func = function(s) {
    n = as.integer(unlist(strsplit(s[1], ",")))[1]
    k = as.numeric(s[-1])
    ans = root(k, n)
    for (i in ans[1]:ans[2]) {
        l = as.integer(k/i+EPS)
        if (sum(l) == n) {
            cat(paste(l, "\n", sep="", collapse=""))
            break
        }
    }
}

con = file("stdin", "r")
s = readLines(con)
func(s)

コメント

排他的 n 乗数(その2)

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

table は高くつくので以下のようにすれば十数倍速くなる。だが,まだまだ時間が掛かりすぎる。

func = function(s) {
    options(scipen=100)
    s = as.integer(unlist(strsplit(s, ",")))
    m = s[1]-1
    n = s[2]
    for (i in m:1) {
        a = as.integer(strsplit(as.character(i), "")[[1]])
        y = integer(10)
        y[a+1] = 1
        if (sum(y) == length(a)) {
            b = strsplit(as.character(i^n), "")[[1]]
            if (!any(b %in% a)) return(i)
        }
    }
    return("-")
}

コメント

排他的 n 乗数

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

「排他的 n 乗数」と呼ばれる数は,
    (a) 10 進数で表記したときに,同じ数字を含まない
    (b) n 乗した結果(10 進数表記)に,元の数に現れる数字が含まれない
というもので,例えば,608 は,608^3=224755712 なので「排他的3乗数」,284 は 284^4 = 6505390336 なので「排他的4乗数」である。

しかし,22^2=484 は,条件 (a) に合わないので 22 は「排他的 2 乗数」ではなく,123^4=228886641 は,条件 (b) に合わないので,123 は「排他的 4 乗数」ではない。

2 つの正の整数 m と n があるとき,m より小さい「排他的 n 乗数」のうち,もっとも大きな値を求めよ。そのようなものがない場合には "-" を返すものとする。

以下の R プログラムでは,時間が掛かりすぎる。

func = function(m, n) {
  options(scipen=100)
  for (i in (m-1):1) {
    a = unlist(strsplit(as.character(i), ""))
    if (!any(table(a) > 1)) {
      b = unlist(strsplit(as.character(i^n), ""))
      if (!any(b %in% a)) return(i)
    }
  }
  return("-")
}

コメント

スーパーマーズ?

2016年06月02日 | 雑感

> 31日、火星が地球に最接近します。「スーパーマーズ」とも言われ、

そんな言葉聞いたこともない

最接近とは言っても,当然,目で見えるほどの大きさになるわけでもなく,

数十パーセントも大きく見えるわけでもないので,「これぞ誇大広告!!」の最たるもんでしょう。

また,31日が過ぎると,突如普通の大きさに戻るわけでもないので,慌てる必要もない。

別のサイトで「どこで見られる?」ともあったが,「晴れていれば,日本国内,どこで見ても同じ」とうのが正解。

曇っていたら見えないでしょうが!!!!!

コメント