はじめに
AtCoder Beginner Contest 274の復習記事です。
記事におけるScannerクラスは、自作の入力クラスです。
コンテスト
https://atcoder.jp/contests/abc274
問題A
double型でB/Aをとり、カスタム数値形式文字列の0カスタム指定子で桁数を指定します。
public static void Solve()
{
var (A, B) = Scanner.Scan<double, double>();
var answer = B / A;
Console.WriteLine($"{answer:0.000}");
}
問題B
二次元配列の入力を受け取り、列ごとにその行にある#の数を数え上げます。
public static void Solve()
{
var (H, W) = Scanner.Scan<int, int>();
var G = new char[H][];
for (var i = 0; i < H; i++)
{
G[i] = Scanner.Scan<string>().ToArray();
}
var X = new int[W];
for (var j = 0; j < W; j++)
{
for (var i = 0; i < H; i++)
{
X[j] += G[i][j] == '#' ? 1 : 0;
}
}
Console.WriteLine(string.Join(" ", X));
}
問題C
辞書型などで番号kの親の数を管理します。
初期値である番号1のアメーバが0であり、1が分裂すると1*2=2番目と1*3番目のアメーバは1番目のアメーバの数+1されたものがたどることができる親の数となります。
そのため、dict[i*2] = dict[i*2+1] = dict[A[i]]+1のように順番にそのアメーバのたどることができる親の数を数え上げることができます。
public static void Solve()
{
var N = Scanner.Scan<int>();
var A = Scanner.ScanEnumerable<int>().ToArray();
var dict = new Dictionary<int, int>();
dict[1] = 0;
for (var i = 1; i <= N; i++)
{
dict[i * 2] = dict[i * 2 + 1] = dict[A[i - 1]] + 1;
}
for (var i = 1; i <= N * 2 + 1; i++)
{
Console.WriteLine(dict[k]);
}
}
問題D
移動について、iが奇数番目の時はXの移動、偶数の時はYの移動であることに注目し、Xの移動とYの移動それぞれについてi回目の移動で座標P行くことができるか、という動的計画法をとき、最終的にxとyにたどり着くことができるかを判定します。
初期値dpX{A[0]}, dpY{0}とし、iが奇数番目の時はdpXの集合であり、ある頂点pxがpx+A[i]とpx-A[i]に遷移します。
同様にiが偶数番目の時はdpYの集合である頂点pyがpy+A[i]とpy-A[i]に遷移します。
public static void Solve()
{
var (N, x, y) = Scanner.Scan<int, int, int>();
var A = Scanner.ScanEnumerable<int>().ToArray();
var dpX = new HashSet<int>();
var dpY = new HashSet<int>();
dpX.Add(A[0]);
dpY.Add(0);
for (var i = 1; i < N; i++)
{
var tmp = new HashSet<int>();
var target = i % 2 == 0 ? dpX : dpY;
foreach (var p in target)
{
tmp.Add(p + A[i]);
tmp.Add(p - A[i]);
}
if (i % 2 == 0) dpX = tmp;
else dpY = tmp;
}
var answer = dpX.Contains(x) && dpY.Contains(y);
Console.WriteLine(answer ? "Yes" : "No");
}
問題E
全ての組み合わせを愚直に探索してしまうと、時間計算量がO((N+M)!)となり実行時間制限に間に合いません。
そこで、原点と町と宝箱を頂点とした集合について、dp[s][u]:=既に訪れている頂点集合sで現在地がuのときの距離の最小値としたbitDPを行うことで、時間計算量O(2^(N+M)*(N+M)^2)で求めることができます。
bitDPをおこない、すべての町を訪れている集合s、現在地がu、訪れた宝箱の数がk、Boostを単位時間に対する倍率としたとき、Min(dp[s,u]+D[u,0]*Boost[k])が答えとなります。
public static void Solve()
{
var (N, M) = Scanner.Scan<int, int>();
var S = N + M + 1;
var P = new (int X, int Y)[S];
P[0] = (0, 0);
for (var i = 1; i < S; i++)
{
var (x, y) = Scanner.Scan<int, int>();
P[i] = (x, y);
}
double Distance(double x1, double y1, double x2, double y2)
{
var dx = x1 - x2;
var dy = y1 - y2;
return Math.Sqrt(dx * dx + dy * dy);
}
var D = new double[S, S];
for (var i = 0; i < S; i++)
{
for (var j = 0; j < S; j++)
{
D[i, j] = Distance(P[i].X, P[i].Y, P[j].X, P[j].Y);
}
}
const double inf = 7e18;
var p2 = new double[M + 1];
p2[0] = 1;
for (var i = 1; i <= M; i++)
{
p2[i] = p2[i - 1] / 2.0;
}
var dp = new double[1 << S, S];
for (var s = 0; s < 1 << S; s++)
{
for (var u = 0; u < S; u++)
{
dp[s, u] = inf;
}
}
dp[1, 0] = 0;
int CountM(int s)
{
var k = 0;
for (var i = 0; i < M; i++)
{
k += (s >> (N + 1 + i)) & 1;
}
return k;
}
for (var s = 0; s < 1 << S; s++)
{
var k = CountM(s);
for (var u = 0; u < S; u++)
{
for (var v = 0; v < S; v++)
{
var t = s | (1 << v);
dp[t, v] = Math.Min(dp[t, v], dp[s, u] + D[u, v] * p2[k]);
}
}
}
var answer = inf;
var mask = 0;
for (var i = 0; i < N; i++)
{
mask |= 1 << (1 + i);
}
for (var s = 0; s < 1 << S; s++)
{
if ((s & mask) != mask) continue;
var k = CountM(s);
for (var u = 0; u < S; u++)
{
answer = Math.Min(answer, dp[s, u] + D[u, 0] * p2[k]);
}
}
Console.WriteLine(answer);
}