SRM517D1H Colorful Board
考察成分が大きい？
問題概要(原文)
$N \times M$ のマス目がある．最終的に各マスの目標の色が与えられる．達成する最小手数を求めよ．不可能なら $-1$ を返せ．
- 操作1: 列と色を選ぶ．その列に属するマス目のマスを全て選んだ色で塗る
- 操作2: 行と色を選ぶ．その行に属するマス目のマスを全て選んだ色で塗る
考察
少なくとも各列，各行は $1$ 度だけ操作すればよい．つまり，答えの最大値の上限は $N+M$ である．
ここで，使う必要がない列(あるいは行)が必ず存在するはずである．そうでないとすると，最初の $1$ 回目に選んだ操作は全て無駄になってしまう．答えの最大値の上限は $N+M-1$ であることがわかった．
これはかなり嬉しい．なぜなら，操作されない列/行があるとすると，行/列に対する操作が全て分かる．すると，各行，各列にどの色を割り当てたかを求めることができる．割当ができないなら，その列/行を操作しないで達成することは不可能である．
$i$ 行 $j$ 列の色において，行の色を先に塗らないといけないなら $n+j \rightarrow i$ へ，列の色を先に塗らないといけないなら， $i \rightarrow n+j$ へ有向辺を張る．これがDAGになっていないならば，達成不可能である．
最小の手数は，行，列において，塗る色が未確定の頂点の数で定まる．
計算量は $O((N+M)^4)$
ソースコード
using System;
using System.Collections.Generic;
using System.Linq;
using System.Numerics;
using Debug = System.Diagnostics.Debug;
using StringBuilder = System.Text.StringBuilder;
public class ColorfulBoard
{
public int theMin(string[] s)
{
var ans = 100000;
var n = s.Length;
var m = s[0].Length;
for (int k = 0; k < n + m; k++)
{
var ok = true;
var R = Enumerate(n, x => '?');
var C = Enumerate(m, x => '?');
if (k < n) for (int j = 0; j < m; j++) C[j] = s[k][j];
else for (int i = 0; i < n; i++) R[i] = s[i][k - n];
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++)
{
if (s[i][j] == C[j]) continue;
if (s[i][j] == R[i]) continue;
if (R[i] == '?') R[i] = s[i][j];
if (C[j] == '?') C[j] = s[i][j];
}
var g = new bool[n + m, n + m];
for (int i = 0; i < n + m; i++)
g[i, i] = true;
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++)
{
if (s[i][j] != C[j] && s[i][j] != R[i]) ok = false;
if (R[i] == C[j]) continue;
if (s[i][j] == R[i]) g[n + j, i] = true;
else g[i, n + j] = true;
}
for (int kk = 0; kk < n + m; kk++)
for (int i = 0; i < n + m; i++)
for (int j = 0; j < n + m; j++)
g[i, j] |= g[i, kk] & g[kk, j];
for (int i = 0; i < n + m; i++)
for (int j = i + 1; j < n + m; j++)
if (g[i, j] & g[j, i]) ok = false;
if (ok)
ans = Math.Min(ans, R.Count(x => x != '?') + C.Count(x => x != '?'));
}
if (ans > n + m) return -1;
return ans;
}
static public T[] Enumerate<T>(int n, Func<int, T> f) { var a = new T[n]; for (int i = 0; i < n; ++i) a[i] = f(i); return a; }
}
コメント
- 考察を理解してからバグらせまくったのは反省
