AtCoder Grand Contest 043 に参加した記録
AGC043 に参加しました。問題はA問題400点、B問題700点… みたいな難しい問題のコンテストです。
実力レート的に1問解けたら御の字みたいなコンテストでした。予定通りA問題(400点)だけACしたので一応振り返りだけしておきます。
レートは微増しました。
A – Range Flip Find Route
H 行 W 列のマス目を考えます。上から r 番目、左から c 番目のマスを (r,c) と表すことにします。 全てのマスはそれぞれ白か黒のどちらかの色に塗られています。
次のような経路が存在するとき、このマス目を"良い"状態と呼びます。
- 常に白いマスの上にいながら、(1,1) から、一つ 右か下 のマスに移動することを繰り返し、 (H,W) へ移動する。
ここで、"良い"状態ならば (1,1) や (H,W) が必ず白いことに注意してください。
あなたの仕事は、以下の操作を繰り返し、マス目を"良い"状態にすることです。最小で何回操作を行う必要があるか求めてください。なお、有限回の操作で必ず"良い"状態に出来ることが証明可能です。
4 つの整数 r0,c0,r1,c1(1≤r0≤r1≤H,1≤c0≤c1≤W) を選ぶ。r0≤r≤r1,c0≤c≤c1 を満たす全ての r,c について、(r,c) の色を変更する。つまり、白色ならば黒色にし、黒色ならば白色にする。
制約
- 2≤H,W≤100
操作自体が何回必要かということを考えたときに、黒が連続している経路は1回の操作ですべて白にできることに気が付きました。
例えば
###
..#
..#みたいな経路だと左上から右下までの全区間を反転すると
...
##.
##.みたいに連続する黒は1回ですべて白にできます。
ということで実装としてはBFSで白から黒に変わったときにコストを増加させて、それ以外はコスト0として計算しました。
var q = new Queue<Tuple<int, int, int, bool>>();
q.Enqueue(Tuple.Create(0, 0, S[0][0] == '#' ? 1 : 0, S[0][0] == '#'));
var cost = new int[H, W];
for (int i = 0; i < H; i++)
{
for (int j = 0; j < W; j++)
{
cost[i, j] = int.MaxValue;
}
}
while (q.Count > 0)
{
var t = q.Dequeue();
var h = t.Item1;
var w = t.Item2;
var c = t.Item3;
var flag = t.Item4;
if (cost[h, w] < c) continue;
cost[h, w] = c;
var dh = new int[] { 1, 0 };
var dw = new int[] { 0, 1 };
for (int d = 0; d < 2; d++)
{
var nh = h + dh[d];
var nw = w + dw[d];
if (0 <= nh && nh < H && 0 <= nw && nw < W)
{
var nextCost = c;
if (S[nh][nw] == '#' && flag == false)
{
nextCost++;
}
var nextFlag = S[nh][nw] == '#';
if (cost[nh, nw] > nextCost)
{
cost[nh, nw] = nextCost;
q.Enqueue(Tuple.Create(nh, nw, nextCost, nextFlag));
}
}
}
}一度バグらせてWAしましたが、一応解けました。計算量的にも右か下しか進まないので問題ないっぽいです。
解説PDF によると、白から黒に移動する時に操作が1回必要とあります。それを考慮してDPするみたいですが、BFSでも解けました。
一応必要な操作回数の考え方はあってたのでよしとします。
