はじめに
AtCoder Beginner Contest 325の復習記事です。
記事における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/abc325
問題A
SとTの入力をとり、S sanを出力します。
例
public static void Solve()
{
var (S, _) = Scanner.Scan<string, string>();
Console.WriteLine($"{S} san");
}
問題B
cum[x]を世界標準時のx時に会議に参加できる人の数とします。
拠点の時刻がt時で時差がd時間の場合、世界標準時ではt-d時になります。
このことから各拠点の9時から18時までを世界標準時に変換した時間帯にw人を追加する累積和を求め、世界標準時で何時に一番参加できる人が多いかを判定します。
このとき、2日分の累積和を求めることに注意が必要です。
例
public static void Solve()
{
var N = Scanner.Scan<int>();
var cum = new long[100];
for (var i = 0; i < N; i++)
{
var (w, x) = Scanner.Scan<int, int>();
cum[24 + 9 - x] += w;
cum[24 + 18 - x] -= w;
cum[48 + 9 - x] += w;
cum[48 + 18 - x] -= w;
}
for (var i = 0; i + 1 < cum.Length; i++)
{
cum[i + 1] += cum[i];
}
long answer = 0;
for (var i = 24; i <= 48; i++)
{
answer = Math.Max(answer, cum[i]);
}
Console.WriteLine(answer);
}
問題C
連動するセンサの個数は、各センサを頂点としたグラフの連結成分の個数と一致します。
これは、各センサに番号を与え、8方向に別のセンサが存在する場合、そのセンサどうしの連結する操作をDFSを行ったり、DSUなどのデータ構造を使うことで求めることができます。
summary
public static void Solve()
{
var (H, W) = Scanner.Scan<int, int>();
var M = 0;
var S = new char[H][];
var dict = new Dictionary<(int H, int W), int>();
for (var i = 0; i < H; i++)
{
S[i] = Scanner.Scan<string>().ToCharArray();
for (var j = 0; j < W; j++)
{
if (S[i][j] == '#')
{
dict[(i, j)] = M++;
}
}
}
var dsu = new DisjointSetUnion(M);
var D8 = new[] { (1, 0), (-1, 0), (0, 1), (0, -1), (1, 1), (1, -1), (-1, 1), (-1, -1) };
for (var i = 0; i < H; i++)
{
for (var j = 0; j < W; j++)
{
if (S[i][j] != '#') continue;
foreach (var (dh, dw) in D8)
{
var (nh, nw) = (i + dh, j + dw);
if (nh < 0 || H <= nh || nw < 0 || W <= nw) continue;
if (S[nh][nw] == '#')
{
dsu.Merge(dict[(i, j)], dict[(nh, nw)]);
}
}
}
}
var answer = dsu.GetGroups().Count();
Console.WriteLine(answer);
}
問題D
ある時間tに印字機の範囲内にある商品のうち、範囲から出る時間が早いものから順に印字することで答えを求めることができます。
印字機の範囲から出る時間が早い順に管理するデータ構造を使い、時刻tにおける印字機の範囲内にある商品を管理しながら、時刻tを更新していきます。
時刻tを全探索してしまうと、tが最大で10^18になり実行時間制限に間に合わなくなるため、印字機に商品がない場合はまだ印字機に入っていない商品が印字機に入る時刻tまでスキップすることで、全体時間計算量O(NlogN)で答えを求めることができます。
例
public static void Solve()
{
var N = Scanner.Scan<int>();
var T = new Timeline[N];
for (var i = 0; i < N; i++)
{
var (t, d) = Scanner.Scan<long, long>();
T[i] = new Timeline(t, t + d);
}
Array.Sort(T, (x, y) => x.In.CompareTo(y.In));
var idx = 0;
var queue = new PriorityQueue<Timeline>((x, y) => x.Out.CompareTo(y.Out));
long curr = 0;
var answer = 0;
while (true)
{
if (queue.Count == 0)
{
if (idx == N) break;
curr = T[idx].In;
}
while (idx < N && T[idx].In <= curr)
{
queue.Enqueue(T[idx++]);
}
while (queue.TryPeek(out var t) && t.Out < curr)
{
queue.Dequeue();
}
if (queue.TryDequeue(out _))
{
answer++;
}
curr++;
}
Console.WriteLine(answer);
}
public record struct Timeline(long In, long Out);
問題E
各都市について、電車を使わないときの最短の時間と、電車を一度以上使うときの最短の時間を管理することで、電車から社用車に乗り換えることはできないという制約に対応することができます。
これは、各都市につき電車を使わない|使うとした頂点を用意し、電車を使わない頂点からは電車を使わない頂点と電車を使う頂点への辺を張り、電車を使う頂点からは電車を使う頂点への辺のみを張ったグラフを作成することで、Djikstra法を使って最短時間を求めることができるようになります。
例
public static void Solve()
{
var (N, A, B, C) = Scanner.Scan<int, long, long, long>();
var D = new long[N][];
for (var i = 0; i < N; i++)
{
D[i] = Scanner.ScanEnumerable<long>().ToArray();
}
var G = new List<(int, long)>[N * 2].Select(x => new List<(int, long)>()).ToArray();
for (var i = 0; i < N; i++)
{
for (var j = 0; j < N; j++)
{
G[i].Add((j, D[i][j] * A));
G[j].Add((i, D[j][i] * A));
G[i].Add((N + j, D[i][j] * B + C));
G[j].Add((N + i, D[j][i] * B + C));
G[N + i].Add((N + j, D[i][j] * B + C));
G[N + j].Add((N + i, D[j][i] * B + C));
}
}
var costs = new long[N * 2];
Array.Fill(costs, 1L << 60);
costs[0] = 0;
costs[N] = 0;
var queue = new PriorityQueue<(int U, long C), long>();
queue.Enqueue((0, 0), 0);
queue.Enqueue((N, 0), 0);
while (queue.TryDequeue(out var top, out _))
{
var (u, uc) = top;
if (costs[u] < uc) continue;
foreach (var (v, vc) in G[u])
{
var nc = costs[u] + vc;
if (costs[v] <= nc) continue;
costs[v] = nc;
queue.Enqueue((v, nc), nc);
}
}
var answer = Math.Min(costs[N - 1], costs[N + N - 1]);
Console.WriteLine(answer);
}