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

A - ABD

入力: $N\quad(N \in \mathbb{Z}; 1 \le N \le 1998)$
出力: $N \le 999$ なら "ABC"、 $1000 \le N$ なら "ABD" と出力

auto N = readln.chomp.to!int;
if(N <= 999) {
	"ABC".writeln;
} else {
	"ABD".writeln;
}

感想: はい

B - Stone Monument

入力: $a \, b\quad (a, b \in \mathbb{Z}; 1 \le a < b < 499550(= 1+2+3+\ldots + 999))$
出力: 積もっている雪の高さ $x$

まず、 $1, 3, 6, 10, 15, \ldots, (1+2+3+\ldots+999)$ という数列を用意する。

int[] arr = new int[](999);
arr[0] = 1;
foreach(i; 1..999) arr[i] = arr[i-1] + i+1;

そして、 $b-a$ の値 $d$ を求めて、 $arr_{i+1} - arr_i = d$ ならば、 $arr_i - a$ を出力すればよいです。

int d = b - a;
foreach(i; 0..998) {
	if(arr[i+1] - arr[i] == d) {
		writeln(arr[i] - a);
	}
}

感想: ちょっとだけ考察が難しいかもしれないけど、問題文から「隣り合った柱について、雪に埋もれてない部分の長さがそれぞれ与えられる」ので、これらの差をとれば何番目の柱なのかがわかって、同時に積雪量も求められるとわかります。

C - Strange Bank

入力: $N\quad (N \in \mathbb{Z}; 1 \le N \le 100000)$
出力: この銀行からちょうどN円を引き出すのに必要な操作回数の最小値

僕はDPでときました。漸化式は
$dp[0] = 0$
$dp[i] = min(dp[i-1] + 1, dp[i-6] + 1, dp[i-9] + 1, dp[i-6^2] + 1, \ldots)$
という感じで表せます。具体的に、 $dp[i - x] + 1$ に入る $x$ の値は
${1, 6, 9, 36, 81, 216, 729, 1296, 6561, 7776, 46656, 59049}$ が考えられます。 $(x \le N \le 100000)$
あとはDPするだけです。

int[] dp;
int[] arr = [1, 6, 9, 36, 81, 216, 729, 1296, 6561, 7776, 46656, 59049];
int solve(int i) {
	if(dp[i] >= 0) return dp[i];
	int tmp = int.max;
	foreach(k; arr) {
		if(i < k) break;
		tmp = min(solve(i-k)+1, tmp);
	}
	return dp[i] = tmp;
}
void main() {
	auto N = readln.chomp.to!int;
	dp = new int[](N+1);
	dp[] = -1;
	dp[0] = 0;
	solve(N).writeln;
}

感想: 入力例3で「これ貪欲法じゃ解けねぇ…！ならばDPしかない！！」となり、DPで解きました。

D - Good Grid

入力:
$N \, C\quad (1 \le N \le 500; 3 \le C \le 30)$
$D_{1,1} \, \cdots \, D_{1,C}$
$\vdots$
$D_{C,1} \, \cdots \, D_{C,C}$
$c_{1,1} \, \cdots \, c_{1,N}$
$\vdots$
$c_{N,1} \, \cdots \, c_{N,N}$
出力: すべてのマスに対して感じる違和感の和のとりうる最小値

下の文章の添字は問題文と異なります。 $(i, j) \to (x, y)$
素直に全探索を考えます。そうすると、まずはcの(x, y)成分で $(x+y)\%3$ について、3色を色 $1$ から色 $C$ までで考える必要があるので、それぞれの色を $i, j, k$ とおき、各マスについて条件を満たしているかどうかを調べ、それぞれについて適切な処理を行おうとすると、計算量が $O(C^3 \times N^2)$ となり、これは間に合いません。
そこで、まず前処理として色 $a$ を一つ決め、 $x, y$ についてループを回し、先に違和感をそれぞれ $(x+y)\%3=0, (x+y)\%3=1, (x+y)\%3=2$ の場合について計算しておきます。

auto arr = new int[][](3, C);
foreach(a; 0..C) foreach(x; 0..N) foreach(y; 0..N) {
	arr[(x+y)%3][a] += D[c[x][y]-1][a];
}

次に、実際に3色 $i, j, k$ を三重ループで回し、 $i=j \lor j=k \lor k = i$ の場合に注意して違和感の最小値を取得します。

foreach(i; 0..C) foreach(j; 0..C) foreach(k; 0..C) {
	if(i==j||j==k||k==i) continue;
	res = min(res, arr[0][i]+arr[1][j]+arr[2][k]);
}

そして、 $res$ を出力すればよいです。
感想: コンテスト中は前者の超愚直方式で解こうとしてTLE。終了後にこの方法を知る。まだまだ競プロはわからないことだらけ。

A: Submission #2643843 - AtCoder Beginner Contest 099
B: Submission #2645854 - AtCoder Beginner Contest 099
C: Submission #2649430 - AtCoder Beginner Contest 099
D: Submission #2652709 - AtCoder Beginner Contest 099