CODE THANKS FESTIVAL 2018の解説 - private-yusuke’s diary

A - Two Problems

入力:
$T\ A\ B\ C\ D$
制約:
$1 \le T,A,B,C,D \le 10^9$
$T,A,B,C,D \in \mathbb{Z}$

出力: 高橋君の取りうる最大の得点

$A$ 分かけて $B$ 点
$C$ 分かけて $D$ 点とれます。
それで、 $T$ 分の時間があります。
$B \le D$ になっているので、まずは $C$ 分かけて $D$ 点取れないかを調べて、次に $A$ 分かけて $B$ 点とれないかどうかを判定すればよいです。

ulong res;
if(T - C >= 0) {
	T -= C;
	res += D;
}
if(T - A >= 0) {
	res += B;
}
res.writeln;

感想: 普通のA問題。

B - Colored Balls

入力:
$X\ Y$
出力: 箱を空にできるなら'Yes'、そうでないなら'No'
制約:
$0 \le X, Y \le 10^9$
$X+Y > 0$
$X, Y \in \mathbb{Z}$

$X$ と $Y$ を比較して、小さい方は3を引き、大きい方からは1を引く操作を繰り返します。 $X = 0 \land Y = 0$ になったら、'Yes'を出力します。
操作の途中で、 $X < 0 \lor Y < 0$ になってしまったら、'No'を出力すればよいです。

bool flag = true;
while(flag) {
	if(X == 0 && Y == 0) {
		writeln("Yes");
		return;
	}
	if(X > Y) {
		if(X - 3 >= 0 && Y - 1 >= 0) {
			X -= 3;
			Y--;
		} else flag = false;
	} else {
		if(Y - 3 >= 0 && X - 1 >= 0) {
			Y -= 3;
			X--;
		} else flag = false;
	}
}
writeln("No");

感想: 3WA。変に難しいことをしないで、単純に処理を書いたらACできた。

C - Pair Distance

入力:
$N$
$x_1\ x_2\ \cdots\ x_{N-1}\ x_N$
出力: この街の交流コスト

制約:
$2 \le N \le 10^5$
$0 \le |x_i| \le 10^8$
$x_i$ は全て異なる
$N, x_1, x_2, \cdots, x_N \in \mathbb{Z}$

単純に必要なコストを計算すると、 $\displaystyle_{N}{C}_{{2}}=\frac{1}{{2}}\cdot{\left({N}-{1}\right)}\cdot{N}$ となり、最悪の場合に $\displaystyle{\left({10}^{5}\right)}^{2}={10}^{10}$ となってしまい間に合わなくなってしまうかもしれません。
そこで、少し工夫を加えてみます。

まず、与えられたリスト $\displaystyle{\left\lbrace{x}_{{n}}\right\rbrace}$ をソートします。そうすると、 $\displaystyle{\left|{x}-{y}\right|}$ で計算されていたコストを、 $i < j$ として $j-i$ で計算できるようになります。
それと、 $x_i$ は負の値もとりますが、後々の計算で不都合が生じるので、リスト $\displaystyle{\left\lbrace{x}_{{n}}\right\rbrace}$ の最小値をリスト $\displaystyle{\left\lbrace{x}_{{n}}\right\rbrace}$ のそれぞれの要素から引いておきます(そうすると最小値が0に揃い、計算するときに負の値を考慮しなくてよくなります)。
また、愚直に計算をするとTLEするので、累積和を使います。

$\displaystyle{S}_{{n}}={x}_{{1}}+{x}_{{2}}+\ldots+{x}_{{n}}$ とすると、交流コストは $N=3$ のとき
$\displaystyle{\left({x}_{{3}}-{x}_{{1}}\right)}+{\left({x}_{{3}}-{x}_{{2}}\right)}+{\left({x}_{{2}}-{x}_{{1}}\right)}={\left({2}{x}_{{3}}-{S}_{{2}}\right)}+{\left({x}_{{2}}-{S}_{{1}}\right)}$ のようになります。
一般化すると、
$\displaystyle{\left\lbrace{\left({n}-{1}\right)}{x}_{{n}}-{S}_{{{n}-{1}}}\right\rbrace}+{\left\lbrace{\left({n}-{2}\right)}{x}_{{{n}-{1}}}-{S}_{{{n}-{2}}}\right\rbrace}+\ldots+{\left({1}\cdot{x}_{{2}}-{S}_{{1}}\right)}$
のようになります。
これによって、 $\displaystyle\text{O}{\left({n}\right)}$ で計算することができました。

auto N = readln.chomp.to!int;
auto x = readln.split.to!(long[]).sort().array;
auto m = x.reduce!min;
x = x.map!(i => i - m).array;
long[] arr = new long[](N);
arr[0] = x[0];
foreach(i; 1..N) {
	arr[i] = arr[i-1] + x[i];
}
ulong res;
foreach_reverse(i; 1..N) {
	res += i*x[i] - arr[i-1];
}
res.writeln;

感想: ちょっと難しい問題だった。

D - Concatenation

入力: $S$
出力: 連結して $S$ になるような題意の文字列の個数の最小値
制約:
$1 \le |S| \le 10^5$
$S$ は英小文字からなる

「連結」とは、今ある文字列の末尾に新たに文字列をつなげることです。
与えられた文字列 $S$ を先頭から一つずつ見ていきます。
元となるそれぞれの文字列には、先頭と同じ文字が複数含まれていない、とのことであるから、これと「先頭の文字がその文字列においてアルファベット順で最小」より「先頭の文字と同じまたはアルファベット順でそれより小さい文字」があった場合には新たな文字列を繋げる必要があります。

dchar now = S[0];
ulong cnt = 1;
foreach(i; S[1..$]) {
	if(now >= i) {
		cnt++;
		now = i;
	}
}
cnt.writeln;

感想: これ絶対Cより簡単だった。200点で出てもおかしくなさそう。

E 〜H

感想: 全然わからん。

A: Submission #3664315 - CODE THANKS FESTIVAL 2018(Parallel)
B: Submission #3664516 - CODE THANKS FESTIVAL 2018(Parallel)
C: Submission #3666265 - CODE THANKS FESTIVAL 2018(Parallel)
D: Submission #3664994 - CODE THANKS FESTIVAL 2018(Parallel)