はじめに
AtCoder Beginner Contest 342の復習記事です。
記事における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/abc342
問題A
文字を数え上げ、出現数が1の文字の出現位置を出力します。
例
public static void Solve()
{
var S = Scanner.Scan<string>();
var count = new int[26];
foreach (var c in S)
{
count[c - 'a']++;
}
for (var i = 0; i < 26; i++)
{
if (count[i] == 1)
{
var answer = S.IndexOf((char)(i + 'a')) + 1;
Console.WriteLine(answer);
return;
}
}
}
問題B
あらかじめP[i]の位置pos[P[i]]を求めておき、pos[A] < pos[B]ならAを、それ以外ならばBの値を出力します。
例
public static void Solve()
{
var N = Scanner.Scan<int>();
var P = Scanner.ScanEnumerable<int>().ToArray();
var pos = new int[N + 1];
for (var i = 0; i < N; i++)
{
pos[P[i]] = i;
}
var Q = Scanner.Scan<int>();
while (Q-- > 0)
{
var (a, b) = Scanner.Scan<int, int>();
if (pos[a] < pos[b])
{
Console.WriteLine(a);
}
else
{
Console.WriteLine(b);
}
}
}
問題C
変換後の文字dになる文字を集合として管理しながら、クエリごとにcの集合をdの集合にマージし、cの集合を空にするという操作を行います。
例
public static void Solve()
{
var N = Scanner.Scan<int>();
var S = Scanner.Scan<string>().ToCharArray();
var Q = Scanner.Scan<int>();
var dict = new Dictionary<int, HashSet<int>>();
for (var i = 0; i < 26; i++)
{
dict[i] = new HashSet<int> { i };
}
while (Q-- > 0)
{
var (c, d) = Scanner.Scan<char, char>();
if (c == d) continue;
c -= 'a';
d -= 'a';
dict[d].UnionWith(dict[c]);
dict[c].Clear();
}
var to = new int[26];
for (var i = 0; i < 26; i++)
{
foreach (var c in dict[i])
{
to[c] = i;
}
}
var answer = new char[N];
for (var i = 0; i < N; i++)
{
answer[i] = (char)(to[S[i] - 'a'] + 'a');
}
Console.WriteLine(new string(answer));
}
問題D
例
public static void Solve()
{
var N = Scanner.Scan<int>();
const int M = (int)2e5 + 1;
var A = Scanner.ScanEnumerable<long>().ToArray();
for (var i = 0; i < N; i++)
{
for (var j = (int)Math.Sqrt(A[i]); j * j > 0; j--)
{
var sq = j * j;
if (A[i] % sq == 0) A[i] /= sq;
}
}
var count = new long[M];
foreach (var a in A)
{
count[a]++;
}
var answer = count[0] * (count[0] - 1) / 2 + count[0] * (N - count[0]);
for (var i = 1; i < M; i++)
{
answer += count[i] * (count[i] - 1) / 2;
}
Console.WriteLine(answer);
}
問題E
駅を頂点、l,d,k,cの情報を辺をもつ有向グラフとしたとき、頂点Nにつながる頂点xのF(x)は、F(x)=Max(F(x), l+(k-1)*d)として求めることができ、この頂点xを始点とした最短経路問題としてDjikstra法で解くことができます。
頂点uのF(u)が決まっていて、頂点uに繋がる頂点vおよび情報l,d,k,cがあるとき、F(u)-c<lであれば頂点uから頂点vに遷移することができ、F(v)=l+Min(K-1,(F(u)-c-l)/d)*dとして求めることができます。
例
public static void Solve()
{
var (N, M) = Scanner.Scan<int, int>();
var G = new List<Data>[N].Select(x => new List<Data>()).ToArray();
for (var i = 0; i < M; i++)
{
var (l, d, k, c, A, B) = Scanner.Scan<int, int, int, int, int, int>();
A--;
B--;
G[B].Add(new Data(A, l, d, k, c));
}
const long Inf = 1L << 60;
var dp = new long[N];
Array.Fill(dp, -Inf);
var queue = new PriorityQueue<(int U, long C), long>();
foreach (var (v, l, d, k, c) in G[N - 1])
{
var vc = l + (k - 1) * d;
if (dp[v] < vc)
{
dp[v] = vc;
queue.Enqueue((v, dp[v]), -dp[v]);
}
}
while (queue.TryDequeue(out var top, out _))
{
var (u, uc) = top;
if (dp[u] > uc) continue;
foreach (var (v, l, d, k, c) in G[u])
{
if (dp[u] - c < l) continue;
var vk = Math.Min(k - 1, (dp[u] - c - l) / d);
var vc = l + vk * d;
if (dp[v] >= vc) continue;
dp[v] = vc;
queue.Enqueue((v, dp[v]), -dp[v]);
}
}
for (var i = 0; i < N - 1; i++)
{
var answer = dp[i] >= 0 ? dp[i].ToString() : "Unreachable";
Console.WriteLine(answer);
}
}
public readonly record struct Data(int To, long L, long D, long K, long C);