はじめに
AtCoder Beginner Contest 305の復習記事です。
記事における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/abc305
問題A
Nの付近にある給水所は、Floor(N/5)*5もしくはCeil(N/5)*5kmの地点になり、より近い方が答えとなります。
public static void Solve()
{
var N = Scanner.Scan<int>();
var L = N / 5 * 5;
var R = (N + 4) / 5 * 5;
var Answer = L;
if (N - L > R - N) answer = R;
Console.WriteLine(answer);
}
問題B
頂点A-Gをそれぞれ配列の添え字に対応させたとき、AB間の距離は3、BC間の距離は1、...と添え字の点からその次の点までの距離に対応させることができます。
このことから、与えられた2点の左右を区別し、左の点から右の点の手前の点までの距離の和を取ることで、答えを求めることができます。
public static void Solve()
{
var (p, q) = Scanner.Scan<char, char>();
var D = new int[] { 3, 1, 4, 1, 5, 9 };
var L = p - 'A';
var R = q - 'A';
if (L > R) (L, R) = (R, L);
var answer = 0;
for (var k = L; k < R; k++)
{
answer += D[k];
}
Console.WriteLine(answer);
}
問題C
グリッドを走査し、次の値を求めます。
a: クッキーがある行の最小値b: クッキーがある行の最大値c: クッキーがある列の最小値d: クッキーがある列の最大値
そして、a<=i<=b, c<=j<=dにおいて、クッキーが置かれていないマスが答えとなります。
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>().ToCharArray();
}
const int Inf = (int)1e9;
var (a, b, c, d) = (Inf, 0, Inf, 0);
for (var i = 0; i < H; i++)
{
for (var j = 0; j < W; j++)
{
if (G[i][j] == '#')
{
a = Math.Min(a, i);
b = Math.Max(b, i);
c = Math.Min(c, j);
d = Math.Max(d, j);
}
}
}
for (var i = a; i <= b; i++)
{
for (var j = c; j <= d; j++)
{
if (G[i][j] == '.')
{
Console.WriteLine($"{i + 1} {j + 1}");
return;
}
}
}
}
問題D
寝ている時間の累積和をとり、各クエリに対して時間計算量O(1)で答えられるようにします。
1秒ごとの累積和を取ってしまうと、最大で1e9となってしまうため、クエリを先読みして必要なタイムスタンプだけを使えるように圧縮します。
定義より、Aの偶数番目のタイムスタンプから、奇数番目のタイムスタンプまでが睡眠期間なので、この間にある全てのタイムスタンプは全て睡眠期間となります。
t番目のタイムスタンプまでの累積睡眠時間をCum[t]とすると、l番目のタイムスタンプとr番目のタイムスタンプ間の睡眠時間はCum[r]-cum[l]で求めることができるようになります。
public static void Solve()
{
var N = Scanner.Scan<int>();
var A = Scanner.ScanEnumerable<int>().ToArray();
var Q = Scanner.Scan<int>();
var query = new (int L, int R)[Q];
var timeline = new HashSet<int>(A);
for (var i = 0; i < Q; i++)
{
var (l, r) = Scanner.Scan<int, int>();
query[i] = (l, r);
timeline.Add(l);
timeline.Add(r);
}
var (map, remap) = Compress(timeline);
var cum = new long[map.Count + 1];
for (var i = 1; i < N; i += 2)
{
var ml = map[A[i]];
var mr = map[A[i + 1]];
for (var j = ml; j < mr; j++)
{
cum[j + 1] += remap[j + 1] - remap[j];
}
}
for (var i = 0; i + 1 < cum.Length; i++)
{
cum[i + 1] += cum[i];
}
foreach (var (l, r) in query)
{
var ml = map[l];
var mr = map[r];
var answer = cum[mr] - cum[ml];
Console.WriteLine(answer);
}
}
public static (Dictionary<T, int> Map, Dictionary<int, T> ReMap) Compress<T>(IEnumerable<T> source)
{
var distinct = source.Distinct().ToArray();
Array.Sort(distinct);
var map = new Dictionary<T, int>();
var remap = new Dictionary<int, T>();
foreach (var (x, i) in distinct.Select((x, i) => (x, i)))
{
map[x] = i;
remap[i] = x;
}
return (map, remap);
}
問題E
hp[u]を頂点uにおける警備員の最大の体力としたとき、hp[u]>=0となる頂点uは、警備されている頂点とすることができます。
探索できる頂点のうち警備員の体力が最大となる頂点を優先して探索するダイクストラ法を行うことで、各頂点の警備員の最大の体力を時間計算量O((N+M)log(N+M))で求めることができます。
public static void Solve()
{
var (N, M, K) = Scanner.Scan<int, int, int>();
var G = new List<int>[N].Select(x => new List<int>()).ToArray();
for (var i = 0; i < M; i++)
{
var (a, b) = Scanner.Scan<int, int>();
a--; b--;
G[a].Add(b);
G[b].Add(a);
}
var guards = new (int P, int H)[K];
for (var i = 0; i < K; i++)
{
var (p, h) = Scanner.Scan<int, int>();
p--;
guards[i] = (p, h);
}
var hp = new int[N];
Array.Fill(hp, -1);
var queue = new PriorityQueue<(int U, int H)>((x, y) => y.H.CompareTo(x.H));
foreach (var (p, h) in guards)
{
hp[p] = h;
queue.Enqueue((p, h));
}
while (queue.Count > 0)
{
var (u, h) = queue.Dequeue();
if (hp[u] > h) continue;
foreach (var v in G[u])
{
if (h - 1 > hp[v])
{
hp[v] = h - 1;
queue.Enqueue((v, h - 1));
}
}
}
var answer = new List<int>();
for (var i = 0; i < N; i++)
{
if (hp[i] >= 0) answer.Add(i + 1);
}
Console.WriteLine(answer.Count);
if (answer.Count > 0) Console.WriteLine(string.Join(" ", answer));
}