ツリーの中にない数
締め切りが 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 10:00 AM なので，その 1 分後に投稿されるように予約
あなたはレースゲームの開発に携わっており、プレイヤーの最終順位を決めるアルゴリズム開発を任されました。
そのゲームは、複数のレースを行い、各レースの順位から最終順位を決めるのですが、順位はそのまま合計したり、算術平均してもおかしな結果になってしまいます。
これは、順位は大小には意味があっても、間隔には意味はないため、1位＋2位が3位を意味しないように、足し算引き算が成立しないことに起因します。
そこで、ひとまず「調和平均」を用いて、解決してみることにしました。
求められるプログラムの前提条件は、以下の通りとなります。
・ 標準入力から、各レースの順位（スペース区切り）が、次のようにプレイヤーの人数分複数行送られる
（プレイヤー1） １回目のレースの順位 ２回目のレースの順位 ３回目のレースの順位 ...
（プレイヤー2） １回目のレースの順位 ２回目のレースの順位 ３回目のレースの順位 ...
:
:
・ 入力されるテキストの行番号をプレイヤーの番号とみなす
・ プレイヤーの人数は、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
上記の１番目の例の場合、各プレイヤーの順位の調和平均は、小数点第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
PVアクセスランキング にほんブログ村
