AtCoder Beginner Contest 099の解説

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