「みんなのプロコン 2019」の解説

A - Anti-Adjacency

入力: $N\ K$
出力: $1$ 以上 $N$ 以下の異なる整数を、差が $1$ の整数をともに選ばないように $K$ 個選ぶことができるなら'YES'、そうでないなら'NO'
制約:

$1 \le N, K \le 100$
$N, K \in \mathbb{Z}$

この問題の一番難しいところは、'Yes'ではなくて'YES'と出力するところです(間違いないね)

… 差が1の整数を選んではいけないので、間をはさみながら整数を選んでいくイメージです。
入力例1では、1以上3以下の異なる整数を、差が1の整数をともに選ばないように選べるか(つまり1,2とか2,3ではなく、1,3のように選べるか)と聞いていますが、これは可能です。

しかしながら、入力例2では不可能になります(どうあがいても、1,2,3,4,5の並びしかない)

$1,2,3,\cdots,N$ と続くなかでこの条件を満たして選べる整数の数の限界は $\displaystyle{\left\lfloor{\frac{{{N}+{1}}}{{2}}}\right\rfloor}$ です。

writeln((N + 1) / 2 >= K ? "YES" : "NO");

感想: 'Yes'と'YES'の統一を、どうかお願いします、AtCoder様…(1WA)

B - Path

入力:
$a_1\ b_1$
$a_2\ b_2$
$a_3\ b_3$
出力: すべての道をちょうど1回ずつ通ることですべての街を訪れることが可能ならば'YES'、そうでないなら'NO'
制約:

$1 \le a_i, b_i \le 4(1 \le i \le 3)$
$a_i \ne b_i(1 \le i \le 3)$
同じ街の対の間を結ぶ道は複数存在しない
どの2つの街の間も、道を何本か通ることで行き来することができる

3つの道の様子を追ってみると、始点と終点の番号が1回、それ以外の点は2回だけ出力に現れればよいことがわかります。
これを満たすかどうかを判定すればよいです。

int[] arr;
foreach(_; 0..3) {
	auto ip = readAs!(int[]), a = ip[0], b = ip[1];
	arr ~= a; arr ~= b;
}
arr.sort();
auto a = arr.group();
auto b = a.map!(i => i[1]);
if(b.count(2) == 2 && b.count(1) == 2) {
	writeln("YES");
} else writeln("NO");

感想: 割と面倒なコードを書いてしまった

C - When I hit my pocket...

入力: $K\ A\ B$
出力: $K$ 回の操作の後、すぬけ君が持っているビスケットの枚数の最大値
制約:

$1 \le K, A, B \le 10^9$
$K, A, B \in \mathbb{Z}$

まず、操作の中で「1枚増やす」というものがあります。
また、「A枚のビスケットを1円に交換する」「1円をB枚のビスケットに交換する」という操作もあります。

ここで、 $K+1 < A$ のとき、下二つの操作には関与できないので、すぬけ君はビスケットを叩き続けることしかできません。よって、出力は $K+1$ となります。
そうでないとき、まずポケットを $A-1$ 回叩いてビスケットを $A$ 枚にし、次にビスケット $A$ 枚を $1$ 円に交換し、 $1$ 円をビスケット $B$ 枚に交換することを考えます。

この「ビスケット $A$ 枚から $1円$ $\rightarrow$ $1$ 円からビスケット $B$ 枚」という交換術は、2回の操作が必要です。したがって、この交換術での増分が2以下のとき、わざわざこんなことをする必要もなく、またしてもすぬけ君はビスケットを叩き続けるほうが良いことがわかります。よって出力は $K+1$ になります。
そうでないとき、この交換術では $B-A$ 枚ずつ増えていくので、残りの操作回数の偶奇に注意してコードを書きます。(2回ずつの操作をセットとして考えるので、1回あまったらビスケットを最後に叩く)

auto ip = readAs!(long[]), K = ip[0], A = ip[1], B = ip[2];
// ulongだとB-Aでオーバーフローすることがあるので注意
if(K+1 < A || B - A <= 2) {
	writeln(K+1);
	return;
}
K -= A-1;
writeln((B-A) * (K/2) + K%2 + A);

感想: コンテスト中はもっと無駄にwhile使ったりして頑張ってた $\displaystyle{O}{\left( \log{{K}}\right)}$ 的解法だったけど、実際数学なので $O(1)$ で解けたなあというお気持ち

D - Ears

入力:
$L$
$A_1$
$\vdots$
$A_L$
出力: 必要な操作の回数の最小値
制約:

$1 \le L \le 2 \times 10^5$
$0 \le A_i \le 10^9(1 \le i \le L)$
$L, A_1, \cdots, A_L \in \mathbb{Z}$

コンテスト中に解けなかったので、公式解説の解法を書きます。
数直線上を散歩することについて考えます。
座標 $S$ で散歩を開始し、座標 $T$ で終了したとし、また散歩中に訪れた左端の座標を $D$ 、右端を $U$ とすると、

$i \le D$ 散歩にこない
$D < i \le S$ 散歩にくる。偶数個の石を得る(0でない)
$S < i \le T$ 散歩にくる。奇数個の石を得る
$T < i \le U$ 散歩にくる。偶数個の石を得る(0でない)
$U < i$ 散歩にこない

の5つの区間が考えられます。(0でない、とするところが0だったら前後との区間の区別ができないので、こういう制約をつけます)

ここで、いい感じにそれぞれの区間の切れ目を全探索すればいけそうって感じますが、それをすると制約からしてTLEは不可避です。したがってDPすることを考えます(DはDPのD)

dp[i][j] を、「マス $i$ 以前まで考えた状態で、マス $i$ を含む区間が $j$ になっているときの操作回数の最小値」とします。

また、cost(i, j)を「マス $i$ が区間 $j$ に含まれると考えたときにプラスされる操作回数」とします。

そうすると、
$j \le k$ として
dp[i+1][k] = min(dp[i+1][k], dp[i][j] + calc(i, k))
という遷移を考えることができます。

最後のマス $L$ は区間0〜4のいずれかに含まれるので、出力はdp[L].reduce!minです。

ulong[] A;

ulong cost(ulong i, ulong j) {
	switch(j) {
		case 0, 4:
			return A[i];
		case 1, 3:
			return A[i] == 0 ? 2 : A[i] % 2;
		case 2:
			return (A[i] + 1) % 2;
		default: return 0;
	}
}

void main() {
	auto L = ri;
	A = L.iota.map!(i => readAs!ulong).array;
	auto dp = new ulong[][](L+1, 5);
	foreach(ref v; dp) v[] = INF;
	dp[0][0] = 0;
	foreach(i; 0..L) foreach(j; 0..5) foreach(k; j..5) {
		dp[i+1][k] = min(dp[i+1][k], dp[i][j] + cost(i, k));
	}
	dp[L].reduce!min.writeln;
}

感想: DP難しいけど、理解した後ならよくわかった。

A: Submission #4204208 - Yahoo Programming Contest 2019
B: Submission #4206354 - Yahoo Programming Contest 2019
C: Submission #4251750 - Yahoo Programming Contest 2019
C(コンテスト中): Submission #4212040 - Yahoo Programming Contest 2019
D: Submission #4251409 - Yahoo Programming Contest 2019