AISing Programming Contest 2019の解説 - private-yusuke’s diary

A - Bulletin Board

入力:
$N$
$H$
$W$
出力: 貼り出す場所の選び方の場合の数
制約:
$\displaystyle{H},{W},{N}\in\mathbb{Z}$
$\displaystyle{1}\le{H},{W}\le{N}\le{100}$

f:id:private_yusuke:20190112231330p:plain — Aの絵

writeln(max(0, N - H + 1) * max(0, N - W + 1));

感想: これ最初戸惑った。解説は絵を描きたかっただけ。

B - Contests

入力:
$N$
$A\ B$
$\displaystyle{P}_{{1}}\ {P}_{{2}}\ \ldots\ {P}_{{N}}$
$\displaystyle{N},{A},{B},{P}_{{1}},{P}_{{2}},\ldots,{P}_{{N}}\in\mathbb{Z}$
出力: コンテストを実施できる最大の回数
制約:
$\displaystyle{3}\le{N}\le{100}$
$\displaystyle{1}\le{P}_{{i}}\le{20}\ {\left({1}\le{i}\le{N}\right)}$
$\displaystyle{1}\le{A}<{B}<{20}$

問題文より、与えられた問題は3つのパターンに分類することができます。

$\displaystyle{P}_{{i}}\le{A}$
$\displaystyle{A}+{1}\le{P}_{{i}}\le{B}$
$\displaystyle{B}+{1}\le{P}_{{i}}$

一度のコンテストでは、それぞれの分け方から一問ずつ出題されるため、どんどん消費されていきます。
したがって、一番最初に消費しきってしまうグループの値を出力すればよいです。

ulong a = P.filter!(i => i <= A).array.length;
ulong b = P.filter!(i => A+1 <= i && i <= B).array.length;
ulong c = P.filter!(i => i >= B + 1).array.length;
writeln(min(a, b, c));

感想: なぜか問題を読むのに時間がかかった。風呂上がって髪を乾かした後、もう20秒しかない状態でコンテストに参加したので、10分ぐらい上裸だった。そんな状況でACできたので自分を称えたい(は?)

C - Alternating Path

入力:
$H\ W$
$S_1$
$S_2$
$\vdots$
$S_H$
出力: 条件を満たすものの個数
制約:
$\displaystyle{1}\le{H},{W}\le{400}$
$\displaystyle{\left|{S}_{{i}}\right|}={W}\ {\left({1}\le{i}\le{H}\right)}$
各 $\displaystyle{i}\ {\left({1}\le{i}\le{H}\right)}$ に対して、文字列 $S_i$ は文字'#'と文字'.'だけからなる。

まず、愚直に全探索することを考えてみる( $\displaystyle{\left({a},{b}\right)}\to{\left({c},{d}\right)}$ の移動を、すべての $a,b,c,d$ について考える)と、 $\displaystyle\text{O}{\left({W}^{2}{H}^{2}\right)}$ で $\displaystyle{400}^{4}={25600000000}$ となり、 $\displaystyle{{\log}_{{10}}{\left({25600000000}\right)}}\approx{10.4082399653}$ なので間に合いません。
したがって、どうにか計算量を落としたい気持ちになります。
ここで、入力例 1を画像にしてみると、こんな感じになります。

f:id:private_yusuke:20190112233125p:plain — Bの絵1

それぞれの'#'から、隣りあった'.'に行けることは問題文からわかります。
問われているのは、'#'から'.'に行ける場合の数です。

f:id:private_yusuke:20190112233615p:plain — Bの絵2

例えば、こういうふうに $\displaystyle{\left({1},{2}\right)}\to{\left({3},{3}\right)}$ と行くことができます。

f:id:private_yusuke:20190112235228p:plain — Bの絵3

こうやって見ると、通うことのできる範囲にある'#'と'.'の個数をかけ算すればよくね?ということに気づきます。これは考えてみるとわかります。
よって、まずは'#'のあるところの座標から探索することにします。
そして、それぞれ問題文の条件を満たすようにDFSで探索し、通うことのできる範囲をしらみつぶしに調べます。その間に計算した座標については訪問済みフラグを立てておき、次は計算をしないように管理します(これで計算量が減ります)。
こうすることで、 $\displaystyle\text{O}{\left({H}{W}\right)}$ で計算が終わります。よってTLEを防ぐことができました。

int[] dy = [1, 0, -1, 0], dx = [0, 1, 0, -1];
Pair[] stack;
foreach(i, iv; S) foreach(j, jv; iv) {
	if(jv == '#') stack ~= Pair(i, j);
}
ulong res;
bool[][] done = new bool[][](H, W);

//ulong res2;
while(stack != []) {
	auto p = stack.front;
	stack.popFront;
	if(done[p.y][p.x]) continue; // 計算量が減るポイント
	Pair[] stack2;
	stack2 ~= Pair(p.y, p.x);
	ulong wh, bl;
	
	while(stack2 != []) {
		auto p2 = stack2.front;
		stack2.popFront;

		foreach(k; 0..4) { //周囲4マスを探索します
			auto ry = p2.y + dy[k];
			auto rx = p2.x + dx[k];
			if(0 <= ry && ry < H && 0 <= rx && rx < W && S[ry][rx] != S[p2.y][p2.x] && !done[ry][rx]) {
				if(S[ry][rx] == '.') { res++; wh++; }
				else bl++;
				stack2 ~= Pair(ry, rx);
				done[ry][rx] = true;
			}
		}
		done[p2.y][p2.x] = true;
	}
	res += wh * bl; // 通える範囲にある'#'と'.'の個数の積をとり答に加算する
}
res.writeln;

感想: この発想が出て30分は、結局 $\displaystyle\text{O}{\left({H}^{2}{W}^{2}\right)}$ になってしまう別のコードを書いてしまい、学校の競プロerに抜かされてしまった。悔しい。でも解けたのでオッケーです

D とか

読んでない

A: Submission #3983758 - AISing Programming Contest 2019 / エイシングプログラミングコンテスト 2019
B: Submission #3985570 - AISing Programming Contest 2019 / エイシングプログラミングコンテスト 2019
C: Submission #3990879 - AISing Programming Contest 2019 / エイシングプログラミングコンテスト 2019