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

A - Coffee

入力: $S$
出力: $S$ がcoffeeに似ている場合は 'Yes' を、そうでない場合は 'No' を
制約: $S$ は長さ $6$ の英小文字からなる文字列

素直に実装。

auto S = readln.chomp;
if(S[2] == S[3] && S[4] == S[5]) writeln("Yes");
else writeln("No");

感想: かんたん

B - Golden Coins

入力: $X$
出力: 嬉しさの最大値
制約:

$0 \le X \le 10^9$
$X$ は整数

できるだけ500円玉に両替し、余ったお金をできるだけ5円玉に両替します。

auto X = readln.chomp.to!int;
ulong res;
while(X >= 500) {
	res += 1000;
	X -= 500;
}
res += (X / 5) * 5;
res.writeln;

感想: 割り算と余りをうまく使えば一行でも解けますね。

C - Traveling Salesman around Lake

入力:
$K\ N$
$A_1\ A_2\ \dots\ A_N$
出力: $N$ 軒すべての家を訪ねるための最短移動距離
制約:

$2 \le K \le 10^6$
$2 \le N \le 2 \times 10^5$
$0 \le A_1 \le \dots \le A_N \le K$
入力中のすべての値は整数である。

一度訪ねた家に再度戻るようなルートは明らかに最短ではありません。したがって、一筆書きできるようなルートについて着目します。すると、家同士の間の長さが最長である部分だけ通らないようにすると最適となります。

auto ip = readln.split.to!(int[]), K = ip[0], N = ip[1];
auto A = readln.split.to!(int[]);
int[] arr;
foreach(i; 0..N-1) arr ~= A[i+1] - A[i];
arr ~= (K - A[$-1]) + (A[0]);
(K - arr.reduce!max).writeln;

感想: 頭がおかしくなって20分溶かしました……。

D - Line++

入力: $N\ X\ Y$
出力: $k = 1,2,\dots,N-1$ に対する問題の答えを、順番に一行ずつ
制約:

$3 \le N \le 2\times 10^3$
$1 \le X,Y \le N$
$X+1 < Y$
入力は全て整数である。

ある2頂点 $i, j\ (i < j)$ について、これらの最短距離を $d_{i,j}$ とおくと、

$\displaystyle{d}_{{{i},{j}}}=\min{\left\lbrace{j}-{i},{\left|{{i}-{X}}\right|}+{1}+{\left|{{j}-{Y}}\right|}\right\rbrace}$

です。ちなみに、今は無向グラフを扱っているので $d_{i,j} = d_{j,i}$ です。
$j - i$ は、単純に頂点 $i$ から頂点 $j$ へとまっすぐ向かうときの距離です。
$\displaystyle{\left|{{i}-{X}}\right|}+{1}+{\left|{{j}-{Y}}\right|}$ は、2頂点 $X, Y$ を経由して向かうときの距離です。
これで全通りの向いかたを検証できていることになりますから、どちらか短い方を取ればよいです。

auto ip = readln.split.to!(long[]), N = ip[0], X = ip[1], Y = ip[2];
X--; Y--;
auto darr = new long[][](N, N);
foreach(ref v; darr) v[] = -1;
foreach(i; 0..N) {
	foreach(j; i+1..N) {
		auto tmp = j - i;
		tmp = min(tmp, abs(i - X) + 1 + abs(j - Y));
		darr[i][j] = tmp;
	}
}
auto res = new int[](N);
foreach(i; 0..N) foreach(j; i+1..N) {
	res[darr[i][j]]++;
}
res[1..$].each!writeln;

感想: BFSしたほうが数式を考えるよりも幾分も楽だったのかな〜と後悔しています。

E - Red and Green Apples

入力:
$X\ Y\ A\ B\ C$
$p_1\ p_2\ \dots\ p_A$
$q_1\ q_2\ \dots\ q_A$
$r_1\ r_2\ \dots\ r_A$
出力: リンゴの美味しさの総和の最大値

赤色のリンゴを $X$ 個より多く食べることはできませんから、赤色のリンゴについては美味しさが大きい順に $X$ 個のみ取り出します。
同様に、緑色のリンゴを $Y$ 個より多く食べることはできませんから、緑色のリンゴについては美味しさが大きい順に $Y$ 個のみ取り出します。
無色のリンゴをこれらの取り出した集まりの中に加えて、大きい順に $X + Y$ 個取り出すことでリンゴの美味しさの総和の最大値を求めることができました。

auto ip = readln.split.to!(long[]), X = ip[0], Y = ip[1], A = ip[2], B = ip[3], C = ip[4];
auto p = readln.split.to!(long[]);
auto q = readln.split.to!(long[]);
auto r = readln.split.to!(long[]);
p.sort!"a > b"(); q.sort!"a > b"(); r.sort!"a > b"();
p = p[0..X]; q = q[0..Y];
long[] arr = r ~ p ~ q;
arr.sort!"a > b"();
arr[0..X+Y].sum.writeln;

感想: 気づくと簡単ですが、気づくのが難しいです。

A: Submission #11264409 - AtCoder Beginner Contest 160
B: Submission #11267808 - AtCoder Beginner Contest 160
C: Submission #11290765 - AtCoder Beginner Contest 160
D: Submission #11301894 - AtCoder Beginner Contest 160
E: Submission #11310513 - AtCoder Beginner Contest 160