はじめに
AtCoder Beginner Contest 348の復習記事です。
記事における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/abc348
問題A
i番目の文字をiが3の倍数ならx、それ以外ならoにした文字列を出力します。
例
public static void Solve()
{
var N = Scanner.Scan<int>();
var answer = new string(Enumerable.Range(1, N).Select(x => x % 3 == 0 ? 'x' : 'o').ToArray());
Console.WriteLine(answer);
}
問題B
各iについて、距離が最大となるjを全探索します。
距離の2乗を計算することで、整数で計算することができます。
例
public static void Solve()
{
var N = Scanner.Scan<int>();
var P = new Point[N];
for (var i = 0; i < N; i++)
{
var (x, y) = Scanner.Scan<int, int>();
P[i] = new Point(x, y);
}
for (var i = 0; i < N; i++)
{
var (x1, y1) = P[i];
var answer = 0;
var max = 0;
for (var j = 0; j < N; j++)
{
var (x2, y2) = P[j];
var dx = x1 - x2;
var dy = y1 - y2;
var d = dx * dx + dy * dy;
if (d > max)
{
max = d;
answer = j + 1;
}
}
Console.WriteLine(answer);
}
}
public readonly record struct Point(int X, int Y);
問題C
辞書などのデータ構造を使って色に対して美味しさが最も小さい値を管理し、その最大値が答えになります。
例
public static void Solve()
{
var N = Scanner.Scan<int>();
var dict = new Dictionary<int, int>();
const int Inf = 1 << 30;
for (var i = 0; i < N; i++)
{
var (a, c) = Scanner.Scan<int, int>();
if (!dict.ContainsKey(c)) dict[c] = Inf;
dict[c] = Math.Min(dict[c], a);
}
var answer = dict.Values.Max();
Console.WriteLine(answer);
}
問題D
現在の場所を(ch,cw)とエネルギー量をceしたとき、(ch,cw)に薬(エネルギーE)がある場合は、ceの値をMax(ce,E)に更新しながら、Dijkstra法で探索を行います。
例
public static void Solve()
{
var (H, W) = Scanner.Scan<int, int>();
var A = new char[H][];
var (sh, sw) = (-1, -1);
var (th, tw) = (-1, -1);
for (var i = 0; i < H; i++)
{
A[i] = Scanner.Scan<string>().ToCharArray();
for (var j = 0; j < W; j++)
{
if (A[i][j] == 'S')
{
(sh, sw) = (i, j);
}
if (A[i][j] == 'T')
{
(th, tw) = (i, j);
}
}
}
var N = Scanner.Scan<int>();
var E = new Dictionary<(int, int), int>();
for (var i = 0; i < N; i++)
{
var (r, c, e) = Scanner.Scan<int, int, int>();
E[(r - 1, c - 1)] = e;
}
const int Inf = 1 << 30;
var dp = new int[H][];
for (var i = 0; i < H; i++)
{
dp[i] = new int[W];
Array.Fill(dp[i], -Inf);
}
dp[sh][sw] = 0;
var queue = new PriorityQueue<(int H, int W, int E), long>();
queue.Enqueue((sh, sw, 0), 0);
var D4 = new[] { (1, 0), (-1, 0), (0, 1), (0, -1) };
while (queue.TryDequeue(out var top, out _))
{
var (ch, cw, ce) = top;
if (dp[ch][cw] > ce) continue;
if (E.ContainsKey((ch, cw)))
{
ce = Math.Max(ce, E[(ch, cw)]);
}
if (ce == 0) continue;
foreach (var (dh, dw) in D4)
{
var (nh, nw) = (ch + dh, cw + dw);
if (nh < 0 || H <= nh || nw < 0 || W <= nw) continue;
if (A[nh][nw] == '#') continue;
var ne = ce - 1;
if (dp[nh][nw] >= ne) continue;
dp[nh][nw] = ne;
queue.Enqueue((nh, nw, ne), -ne);
}
}
var answer = dp[th][tw] >= 0;
Console.WriteLine(answer ? "Yes" : "No");
}
問題E
ある木のfの値を求めるには、その部分木fの和と、その部分木の重みの和を足したものになります。
(long F, long W) Dfs(int u, int p)
{
long f = 0;
long w = 0;
foreach(var v in T[u])
{
if (v == p) continue;
var (cf, cw) = Dfs(v, u);
f += cf;
w += cw;
}
return (f + w, w + C[u]);
}
しかし、各iについて愚直に計算してしまうと時間計算量がO(N^2)となってしまうので、部分木の和と部分木の重みの和を保持しながら全方位木DPを行うことで時間計算量O(N)で答えを求めることができます。
例
public static void Solve()
{
var N = Scanner.Scan<int>();
var E = new (int A, int B)[N - 1];
for (var i = 0; i < N - 1; i++)
{
var (a, b) = Scanner.Scan<int, int>();
a--; b--;
E[i] = (a, b);
}
var C = Scanner.ScanEnumerable<long>().ToArray();
var dp = new ReRooting<Data>(N, new Operation(C));
foreach (var (a, b) in E)
{
dp.AddEdge(a, b);
}
var result = dp.Calculate();
var answer = result.Select(x => x.S).Min();
Console.WriteLine(answer);
}
public class Operation : ReRooting<Data>.IOperation
{
public Data Identity => new Data(0, 0);
private readonly long[] C;
public Operation(long[] c) => C = c;
public Data AddRoot(int i, Data value)
{
return new Data(value.S + value.C, value.C + C[i]);
}
public Data Merge(Data left, Data right)
{
return new Data(left.S + right.S, left.C + right.C);
}
}
public readonly record struct Data(long S, long C);
public class ReRooting<T>
{
public int Size { get; init; }
private readonly List<int>[] _edges;
private readonly IOperation _operation;
public ReRooting(int size, IOperation operation)
{
Size = size;
_operation = operation;
_edges = new List<int>[Size];
for (var i = 0; i < Size; i++) _edges[i] = new List<int>();
}
public void AddEdge(int u, int v)
{
_edges[u].Add(v);
_edges[v].Add(u);
}
public T[] Calculate()
{
var result = new T[Size];
Array.Fill(result, _operation.Identity);
var dp = new T[Size][];
Dfs(0);
Bfs(0, _operation.Identity);
return result;
T Dfs(int u, int p = -1)
{
dp[u] = new T[_edges[u].Count];
var cum = _operation.Identity;
for (var i = 0; i < _edges[u].Count; i++)
{
var v = _edges[u][i];
if (v == p) continue;
dp[u][i] = Dfs(v, u);
cum = _operation.Merge(cum, dp[u][i]);
}
return _operation.AddRoot(u, cum);
}
void Bfs(int u, T value, int p = -1)
{
var n = _edges[u].Count;
for (var i = 0; i < n; i++)
{
if (_edges[u][i] == p) dp[u][i] = value;
}
var cumL = new T[n + 1];
var cumR = new T[n + 1];
Array.Fill(cumL, _operation.Identity);
Array.Fill(cumR, _operation.Identity);
for (var i = 0; i < n; i++)
{
var j = n - 1 - i;
cumL[i + 1] = _operation.Merge(cumL[i], dp[u][i]);
cumR[j] = _operation.Merge(cumR[j + 1], dp[u][j]);
}
result[u] = _operation.AddRoot(u, cumL[n]);
for (var i = 0; i < n; i++)
{
var v = _edges[u][i];
if (v != p) Bfs(v, _operation.AddRoot(u, _operation.Merge(cumL[i], cumR[i + 1])), u);
}
}
}
public interface IOperation
{
public T Identity { get; }
public T Merge(T left, T right);
public T AddRoot(int i, T value);
}
}