はじめに
AtCoder Beginner Contest 317の復習記事です。
記事におけるScannerクラスは、自作の入力クラスです。
Scannerクラス
public static class Scanner
{
public static T Scan<T>() where T : IConvertible => Convert<T>(ScanStringArray()[0]);
public static (T1, T2) Scan<T1, T2>() where T1 : IConvertible where T2 : IConvertible
{
var input = ScanStringArray();
return (Convert<T1>(input[0]), Convert<T2>(input[1]));
}
public static (T1, T2, T3) Scan<T1, T2, T3>() where T1 : IConvertible where T2 : IConvertible where T3 : IConvertible
{
var input = ScanStringArray();
return (Convert<T1>(input[0]), Convert<T2>(input[1]), Convert<T3>(input[2]));
}
public static (T1, T2, T3, T4) Scan<T1, T2, T3, T4>() where T1 : IConvertible where T2 : IConvertible where T3 : IConvertible where T4 : IConvertible
{
var input = ScanStringArray();
return (Convert<T1>(input[0]), Convert<T2>(input[1]), Convert<T3>(input[2]), Convert<T4>(input[3]));
}
public static (T1, T2, T3, T4, T5) Scan<T1, T2, T3, T4, T5>() where T1 : IConvertible where T2 : IConvertible where T3 : IConvertible where T4 : IConvertible where T5 : IConvertible
{
var input = ScanStringArray();
return (Convert<T1>(input[0]), Convert<T2>(input[1]), Convert<T3>(input[2]), Convert<T4>(input[3]), Convert<T5>(input[4]));
}
public static (T1, T2, T3, T4, T5, T6) Scan<T1, T2, T3, T4, T5, T6>() where T1 : IConvertible where T2 : IConvertible where T3 : IConvertible where T4 : IConvertible where T5 : IConvertible where T6 : IConvertible
{
var input = ScanStringArray();
return (Convert<T1>(input[0]), Convert<T2>(input[1]), Convert<T3>(input[2]), Convert<T4>(input[3]), Convert<T5>(input[4]), Convert<T6>(input[5]));
}
public static IEnumerable<T> ScanEnumerable<T>() where T : IConvertible => ScanStringArray().Select(Convert<T>);
private static string[] ScanStringArray()
{
var line = Console.ReadLine()?.Trim() ?? string.Empty;
return string.IsNullOrEmpty(line) ? Array.Empty<string>() : line.Split(' ');
}
private static T Convert<T>(string value) where T : IConvertible => (T)System.Convert.ChangeType(value, typeof(T));
}
コンテスト
https://atcoder.jp/contests/abc317
問題A
H+P[i]>=Xとなる最初のiを出力します。
public static void Solve()
{
var (N, H, X) = Scanner.Scan<int, int, int>();
var P = Scanner.ScanEnumerable<int>().ToArray();
for (var i = 0; i < N; i++)
{
if (H + P[i] >= X)
{
Console.WriteLine(i + 1);
return;
}
}
}
問題B
Aをソートし、A[i-1]+1==A[i]ならば、それらの整数は連続しています。
そのため、A[i-1]+1!=A[i]ならばそれらの整数が連続しておらず、A[i-1]+1がなくした整数になります。
public static void Solve()
{
var N = Scanner.Scan<int>();
var A = Scanner.ScanEnumerable<int>().ToArray();
Array.Sort(A);
for (var i = 1; i < N; i++)
{
if (A[i - 1] + 1 != A[i])
{
Console.WriteLine(A[i - 1] + 1);
return;
}
}
}
問題C
既に訪れた町と、現在通った道路の長さの和を管理しながら深さ優先探索を行います。
時間計算量O(N!)で答えを求めることができます。
public static void Solve()
{
var (N, M) = Scanner.Scan<int, int>();
var G = new List<(int, long)>[N].Select(x => new List<(int, long)>()).ToArray();
for (var i = 0; i < M; i++)
{
var (a, b, c) = Scanner.Scan<int, int, long>();
a--; b--;
G[a].Add((b, c));
G[b].Add((a, c));
}
long answer = 0;
var used = new bool[N];
void Dfs(int u, long s)
{
answer = Math.Max(answer, s);
used[v] = true;
foreach (var (v, c) in G[u])
{
if (used[v]) continue;
Dfs(v, s + c);
}
used[v] = false;
}
for (var i = 0; i < N; i++)
{
Dfs(i, 0);
}
Console.WriteLine(answer);
}
問題D
次のような動的計画法を解きます。
dp[i][s] := i番目の選挙区までみたとき、s議席獲得するために必要な鞍替えさせる必要がある人数の最小値
遷移としては次のようになります。
v = (Max(0, Y[i]-X[i]) + 1) / 2; // i番目の選挙区において高橋派が過半数を得るために必要な、鞍替えさせる必要がある人数
dp[i+1][s] = Min(dp[i+1][s], dp[i][s-Z[i]] + v);
そして、N個の選挙区全体として過半数の議席を獲得するには、全ての議席の数をzsとしたとき、必要な議席reqは(zs+1)/2以上であるため、dp[req]からdp[zs]までの最小値が答えとなります。
public static void Solve()
{
var N = Scanner.Scan<int>();
var V = new (long X, long Y, long Z)[N];
long zs = 0;
for (var i = 0; i < N; i++)
{
var (x, y, z) = Scanner.Scan<long, long, long>();
V[i] = (x, y, z);
zs += z;
}
const long Inf = (long)1e18;
var dp = new long[zs + 1];
Array.Fill(dp, Inf);
dp[0] = 0;
for (var i = 0; i < N; i++)
{
var (x, y, z) = V[i];
var v = (Math.Max(0, y - x) + 1) / 2;
for (var s = zs; s >= z; s--)
{
dp[s] = Math.Min(dp[s], dp[s - z] + v);
}
}
var req = (zs + 1) / 2;
var answer = Inf;
for (var s = req; s <= zs; s++)
{
answer = Math.Min(answer, dp[s]);
}
Console.WriteLine(answer);
}
問題E
各人の視線をあらかじめ計算しておき、幅優先探索を行うことで答えを求めることができます。
グリッド内のマスのうち、侵入可能な.、S、Gのマスを侵入可能マス、人や障害物の侵入不可能マスをとしたとき、各人の視線は、各人のマスから各方向に対して侵入不可能マスまでの侵入可能マスを侵入不可能にします。
このことからX[i][j]をi行j列目のマスを侵入可能かとしたとき、侵入不可能マスに加えて、侵入可能マスを侵入不可能にしたものに対して、SのマスからGのマスまでの最短距離を、グリッド上における4方向の幅優先探索で求めることができるようになります。
public static void Solve()
{
var (H, W) = Scanner.Scan<int, int>();
var G = new char[H][];
var (sh, sw) = (-1, -1);
var (gh, gw) = (-1, -1);
for (var i = 0; i < H; i++)
{
G[i] = Scanner.Scan<string>().ToCharArray();
for (var j = 0; j < W; j++)
{
if (G[i][j] == 'S') (sh, sw) = (i, j);
if (G[i][j] == 'G') (gh, gw) = (i, j);
}
}
bool IsPossible(int h, int w)
{
return 0 <= h && h < H && 0 <= w && w < W && (G[h][w] == '.' || G[h][w] == 'S' || G[h][w] == 'G');
}
var X = new bool[H, W];
X[sh, sw] = X[gh, gw] = true;
for (var i = 0; i < H; i++)
{
for (var j = 0; j < W; j++)
{
if (IsPossible(i, j)) X[i, j] = true;
}
}
void F(char c)
{
var (dh, dw) = (0, 0);
if (c == '>') dw = 1;
if (c == 'v') dh = 1;
if (c == '<') dw = -1;
if (c == '^') dh = -1;
for (var i = 0; i < H; i++)
{
for (var j = 0; j < W; j++)
{
if (G[i][j] == c)
{
var k = 1;
while (IsPossible(i + dh * k, j + dw * k))
{
var ni = i + dh * k;
var nj = j + dw * k;
X[ni, nj] = false;
k++;
}
}
}
}
}
F('>');
F('v');
F('<');
F('^');
var dp = new int[H, W];
const int Inf = (int)1e9;
for (var i = 0; i < H; i++)
{
for (var j = 0; j < W; j++)
{
dp[i, j] = Inf;
}
}
dp[sh, sw] = 0;
var D4 = new[] { (1, 0), (-1, 0), (0, 1), (0, -1) };
var queue = new Queue<(int, int, int)>();
queue.Enqueue((sh, sw, 0));
while (queue.TryDequeue(out var top))
{
var (ch, cw, cc) = top;
foreach (var (dh, dw) in D4)
{
var (nh, nw) = (ch + dh, cw + dw);
if (nh < 0 || H <= nh || nw < 0 || W <= nw) continue;
if (!X[nh, nw] || dp[nh, nw] <= cc + 1) continue;
dp[nh, nw] = cc + 1;
queue.Enqueue((nh, nw, cc + 1));
}
}
var answer = dp[gh, gw];
if (answer == Inf) answer = -1;
Console.WriteLine(answer);
}