一流を見分けられるのは誰？

一流を見分けられるのは誰？

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

今日のTVでは芸能人に何が一流品かを当てさせてその人を格付けする番組が人気ですが、こういった順位付けするという処理は、検索エンジンやレコメンドシステムといった日常的に使われるサービスの中でも極めて重要な役割を担っています。

さて、こうした順位付け問題はどのように評価するのが良いでしょうか？
順位付けを行う側を”評価者”、順位付けされる側を”アイテム”と呼ぶとき、TV番組であれば一番のアイテムがどれかを当てればOKかもしれませんが、サービスで使われるプログラムはすべて、あるいは上位10件という風に複数のアイテムを順位付けしないといけません。

ここで、例えばアイテムが３つあったときに、１位と２位を間違えるプログラムよりも、２位と３位を間違えるプログラムの方がまだ望ましいのは自明でしょう。

こうした評価者を評価するための精度評価指標として様々なものが提案されているのですが、今回の設問ではDCG(Discounted Cumulative Gain)と呼ばれる指標を使ってみたいと思います。

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

標準入力から、各アイテムの評価値（数値が大きいほど、評価が高いことを示す）が、次のように評価者の人数分複数行送られる
（評価者1）　アイテム1の評価値 アイテム2の評価値 アイテム3の評価値 ...
（評価者2）　アイテム1の評価値 アイテム2の評価値 アイテム3の評価値 ...
このとき、アイテムの順位ではなく評価値（順位とは逆で数値が大きいほど、評価が高い）が与えられることにご注意ください。
・ 入力されるテキストの行番号を評価者の番号とみなす
・ 評価者の人数は、3人以上5人以下とする
・ アイテムの数は、3個以上5個以下とする
・ 評価値は1以上10以下の整数とし、その組み合わせは固定される
・ 評価値はアイテムごとに異なり、重複や欠落はないものとする
・ アイテムの順序は、真の評価値が高い順に並んでいることを前提とする
・ よって、最も望ましい評価値は5>3>1という風に単調減少する場合となる
・ DCG(Wikipediaへのリンク)をすべてのアイテムに適用して評価者の順位を求めること。
・ ここでrel iと称される関連度を示す変数にはアイテムiの評価値を、変数pにはアイテム数をそのまま用いること。
・ またDCGの求め方は複数提案されているが、最初に解説される下記の数式を用いること

・ DCGの値が同じ評価者同士は、同じ順位とし、下の順位に合わせる。
例えば、評価者が3人で、上位2人が同じDCGの場合、2位が2名、3位が1名となる
・ 求めた順位を評価者の番号順に、改行区切りで標準出力に送ること

以下、入力と出力例です。

入力
3 1 2
1 3 2
3 2 1
出力
2
3
1

入力
6 10 3 1
10 3 1 6
10 3 6 1
10 3 6 1
出力
4
3
2
2

上記の１番目の例の場合、各評価者のDCGは、小数点第5位以下切捨てで、次のようになります。

3 + 1/log2(2+1) + 2/log2(2+2) = 4.6309
1 + 3/log2(2+1) + 2/log2(2+2) = 3.8927
3 + 2/log2(2+1) + 1/log2(2+2) = 4.7618

この数字が高いほど上位となるので、評価者の番号順に 2位 3位 1位となるわけですね。

いかがでしょうか？
一流だけを見分けるのか、一流以下のすべてを見分けるのかによって問題の複雑さがまるで変わってくることに気づかされますね。
本設問を通じて、検索エンジンやレコメンドシステムとサービスの裏側にも興味を持っていただければ幸いです。

【問題】
標準入力から、各アイテムの評価値（数値が大きいほど、評価が高いことを示す）が、評価者の人数分複数行送られます。
このとき評価されるアイテムの順序は、真の評価値が高い順に並んでいることを前提とした上で、順位付け問題の精度評価指標であるDCGを用いて各評価者の順位を求め、その結果を標準出力に返してください。

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝

設問が大げさな割りには，簡単に書けるプログラム

f = function(s) {
  x = sapply(s, function(t) as.integer(unlist(strsplit(t, " "))))
  n = nrow(x)
  y = 1/log2(1:n+1)
  z = apply(x, 2, function(a) sum(a*y))
  cat(sprintf("%d\n", rank(-z, ties.method="max")), sep="")
}

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

「LCM・パレード」問題

「LCM・パレード」問題

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

自然数 a, b に対し、a と b の最小公倍数を LCM(a, b) と定義します。
例えば、LCM(6, 8)＝24 です。
 
さらに、自然数 n, k に対し、n 以下の全ての自然数 m に対する LCM(k, m)÷k の値の和を F(n, k)と定義します。
 
例えば F(9, 12)＝22 です。以下の表の最下列の数の和です。

同様に、F(10, 3)＝43, F(20, 9)＝162 となることが確かめられます。
 
標準入力から、自然数 n と k （1 ≦ n ≦ 10^8, 1 ≦ k ≦ 10^5）が半角空白区切りで与えられます。
標準出力に F(n, k) の値を出力するプログラムを書いてください。
 
 ===== ===== ===== ===== ===== =====

末尾に示す素直な R プログラムでは，n が大きくなると計算時間が掛かりすぎる。

なぜわざわざ LCM(k, n)/k なんて使うのだ？というところに実はヒントがあるのだろう。
k = 50 のときの LCM(50, m)/50, m=1, 2, ..., 50 を書き出してみれば，以下のようになる。

つまり，和を求める数値 LCM(k, m)/k は，m が k の素因数で割り切れるときにはその値で割る（同じ素因数が複数個ある場合も同様に）。
これらの和をとったものが F(n, k) である。


この方針で R プログラムを書いても，さすがに n = 100000000 では時間制限にひっかかる。
C で書き直して OK となるが，R プログラムは簡潔。

divisor = function(n)    {
  for (i in 2:sqrt(n)) {
    if (n %% i == 0) {
      return(i)
    }
  }
  return(n)
}

f = function(n, k) {
  x = as.numeric(1:n)
  while (k > 1) {
    div = divisor(k)
    if (n >= div) {
      i = 1:(n %/% div)*div
      x[i] = ifelse(x[i] %% div == 0, x[i] / div, x[i])
    }
    k = k/div
  }
  options(scipen=100)
  cat(sum(x))
}

f(9, 12) # 22
f(40, 50) # 502
f(312, 41) # 47708
f(7122, 360) # 10778909
system.time(f(1234567, 17200)) # 414701577895, 0.318 s
system.time(f(98777, 98999)) # 4878497253, 0.001 s
system.time(f(100000000, 98765)) # 4199787396686968, 2.080 s


C プログラム

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

int divisor(int n)    {
  for (int i = 2; sqrt(n) >= i; i++) {
    if (n%i == 0) {
      return i;
    }
  }
  return n;
}

double f(int n, int k) {
  int i;
  int x[n+1];
  for (i = 1; n >= i; i++) {
    x[i] = i;
  }
  while (k > 1) {
    int div = divisor(k);
    for (i =1; n / div >= i; i++) {
      int i2 = i*div;
      if (x[i2] % div == 0) {
        x[i2] /= div;
      }
    }
    k /= div;
  }
  double sum = 0;
  for (int i = 1; n >= i; i++) {
    sum += x[i];
  }
  return sum;
}

int main() {
  int n, k;
  scanf("%d %d", &n, &k);
  printf("%.0f\n", f(n, k));
  return 0;
}

簡単に書けるが，遅い R プログラム

LCM = function(m, n) {
  n0 = n
  while ((temp = n %% m) != 0) {
    n = m
    m = temp
  }
  n0/m
}

f = function(n, k) {
  sum = 0
  for (m in 1:n) {
    sum = sum+LCM(k, m)
  }
  options(scipen=100)
  cat(sum)
}

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

f(9, 12) # 22
#f(40, 50) # 502
#f(312, 41) # 47708
#f(7122, 360) # 10778909
#system.time(f(1234567, 17200)) # 414701577895, 2.831 s
#f(98777, 98999) # 4878497253
#system.time(f(100000000, 98765)) # 4199787396686968, 298.946 s