AtCoder Beginner Contest 163の解説 - private-yusuke’s diary

A - Circle Pond

入力: $R$
出力: 半径 $R$ の円の周長
制約: $1 \le R \le 100$
求めるものは、 $2 \pi R$ です。

auto R = readAs!real;
writeln(2*R*PI);

感想: "%.4f" とかしなくても大丈夫です。

B - Homework

入力:
$N\ M$
$A_1\ \dots\ A_M$
出力: 高橋君が遊ぶことのできる日数、または、'-1'
制約:

$1 \le N \le 10^6$
$1 \le M \le 10^4$
$1 \le A_i \le 10^4$

複数の宿題を同日にすることはできないので、全ての宿題を終わらせるのに必要な日数は $\displaystyle{S}=\sum_{{i}}{A}_{{i}}$ です。
したがって、 $N - S$ が非負ならその値、負なら $-1$ が答えです。

auto ip = readAs!(int[]), N = ip[0], M = ip[1];
auto A = readAs!(int[]);
auto S = A.sum;
if(N - S < 0) writeln(-1);
else writeln(N-S);

感想: やるだけ。

C - management

入力:
$N$
$A_2\ \dots\ A_N$
出力: 各社員に直属する部下の人数
制約:

$2 \le N \le 2 \times 10^5$
$1 \le A_i \le i$

m[社員A] = 社員Aの直属の部下の配列として考えます。

auto N = ri;
auto A = readAs!(int[]);
int[][] m = new int[][](N);
foreach(i, v; A) {
	m[v-1] ~= i.to!int;
}
foreach(i; 0..N) {
	m[i].length.writeln;
}

感想: C問題にしては簡単？

D - Sum of Large Numbers

入力: $N\ K$
出力: 条件を満たすものの個数 $\mod (10^9+7)$
制約:

$1 \le N \le 2 \times 10^5$
$1 \le K \le N+1$
入力は全て整数

まず、 $10^{100}$ について考えてみます。 $N$ の最大値は $2 \times 10^5$ であるから、1からNの整数の総和の最大値は $\displaystyle\frac{1}{{2}}\cdot{\left({2}\cdot{10}⁵\right)}\cdot{\left({2}\cdot{10}^{5}+{1}\right)}={20000000000}+{100000}\stackrel{\sim}{=}{10}^{{{10.3010321671}\ldots}}<{10}^{{{100}}}$ です。したがって、 $10^{100}$ に対して、選んだ整数の総和が影響しないことがわかります。
また、 $X = 10^{100}$ とおくと、 $k$ 個の数を選ぶときの和としてあり得るものは $\displaystyle{k}\times{X}+\square$ で表されます。したがって、これらより「それぞれの $k$ で作れる和は、他の $k$ の値のときと被ることはない」といえます。
これ以降は、 $10^{100}$ のことを無視します。

$\displaystyle{S}{\left({n}\right)}=\frac{1}{{2}}\cdot{n}\cdot{\left({n}+{1}\right)}$ とします。
$k$ 個の数を選ぶとき、その和としてあり得るものの最小値は、 $S(k-1)$ です。
$k$ 個の数を選ぶとき、その和としてあり得るものの最大値は、 $S(N) - S(N-k)$ です。
したがって、 $k$ 個の数を選ぶとき、その和としてあり得るものの個数は、 $\displaystyle{S}{\left({N}\right)}-{S}{\left({N}-{k}\right)}-{\left({S}{\left({k}-{1}\right)}-{1}\right)}$ です。
実装上は、 $K \le k \le N$ でこれらの値を求め、最後に $k = N+1$ の分の $1$ を答えに足します。

auto ip = readAs!(int[]), N = ip[0], K = ip[1];

long su(ulong n) {
	return n * (n + 1) / 2;
}

long res;
const long MOD = 1000000007;
foreach(k; K..N+1) {
	auto m = su(N) - su(N-k) - su(k-1);
	res += m+1;
	res %= MOD;
}
(res+1).writeln;

感想: 添字ゲームに時間をかけすぎた。

A: Submission #12082896 - AtCoder Beginner Contest 163
B: Submission #12082483 - AtCoder Beginner Contest 163
C: Submission #12092478 - AtCoder Beginner Contest 163
D: Submission #12130748 - AtCoder Beginner Contest 163