はじめに
AtCoder Beginner Contest 314の復習記事です。
記事における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/abc314
問題A
円周率を文字列Sとしたとき、3.と小数N文字が答えとなるので、Sの先頭N+2文字が答えとなります。
public static void Solve()
{
const string PI = "3.1415926535897932384626433832795028841971693993751058209749445923078164062862089986280348253421170679";
var N = Scanner.Scan<int>();
var answer = PI[..(N + 2)];
Console.WriteLine(answer);
}
問題B
S[a,c]をaに掛けた人のうち、掛けた個数がcの人の番号の集合としたとき、空集合ではないS[X,c]が答えとなり、そのようなcが存在しなければ、答えは0になります。
public static void Solve()
{
const int M = 37;
var N = Scanner.Scan<int>();
var S = new List<int>[M + 1, M + 1];
for (var i = 0; i <= M; i++)
{
for (var j = 0; j <= M; j++)
{
S[i, j] = new List<int>();
}
}
for (var i = 1; i <= N; i++)
{
var c = Scanner.Scan<int>();
var A = Scanner.ScanEnumerable<int>().ToArray();
foreach (var a in A)
{
S[a, c].Add(i);
}
}
var X = Scanner.Scan<int>();
for (var i = 0; i <= M; i++)
{
if (S[X, i].Count == 0) continue;
Console.WriteLine(S[X, i].Count);
Console.WriteLine(string.Join(" ", S[X, i]));
return;
}
Console.WriteLine(0);
Console.WriteLine();
}
問題C
各色ごとに出現位置を管理し、各文字を右シフトします。
現在の文字と同じ色の左の文字(一番左の場合は最後の文字)をprevとしたとき、現在の文字とprevをスワップしていくことで、右シフトを実現できます。
public static void Solve()
{
var (N, M) = Scanner.Scan<int, int>();
var S = Scanner.Scan<string>();
var C = Scanner.ScanEnumerable<int>().ToArray();
var ID = new List<int>[M + 1].Select(_ => new List<int>()).ToArray();
for (var i = 0; i < N; i++)
{
ID[C[i]].Add(i);
}
var T = S.ToCharArray();
for (var i = 1; i <= M; i++)
{
if (ID[i].Count <= 1) continue;
var idx = ID[i];
var prev = T[idx[^1]];
for (var j = 0; j < idx.Count; j++)
{
(T[idx[j]], prev) = (prev, T[idx[j]]);
}
}
var answer = new string(T);
Console.WriteLine(answer);
}
問題D
各クエリを愚直に操作してしまうと、クエリがt==2またはt==3のときごとにSを全て見る必要があるため、全体時間計算量がO(QN)になってしまい、実行時間制限に間に合いません。
t==2のときとt==3のときの操作を考えたとき、クエリがt==2のとき、Sは全て小文字になり、t==3のとき、Sは全て大文字になります。
このことから、t==2またはt==3を大小の変更操作としたとき、クエリ全体の最後に出現する大小の変更操作より前の大小の変更操作は上書きされることがわかります。
あらかじめ、大小の変更操作の最終位置をクエリ先読みしておき、t==1となるクエリを順に操作しつつ、大小の変更操作の最終位置でのみSの大小の変更操作を行うことで、Sを全てを操作することは1回で済むため、全体時間計算量O(Q+N)で答えを求めることができるようになります。
public static void Solve()
{
var N = Scanner.Scan<int>();
var S = Scanner.Scan<string>();
var Q = Scanner.Scan<int>();
var state = 0;
var changed = -1;
var T = S.ToCharArray();
var queries = new (int T, int X, char C)[Q];
for (var i = 0; i < Q; i++)
{
var (t, x, c) = Scanner.Scan<int, int, char>();
x--;
queries[i] = (t, x, c);
if (t != 1)
{
state = t;
changed = i;
}
}
for (var i = 0; i < Q; i++)
{
var (t, x, c) = queries[i];
if (i == changed && state != 1)
{
for (var j = 0; j < N; j++)
{
T[j] = state == 2 ? char.ToLower(T[j]) : char.ToUpper(T[j]);
}
}
if (t == 1)
{
T[x] = c;
}
}
var answer = new string(T);
Console.WriteLine(answer);
}