はじめに
AtCoder Beginner Contest 335の復習記事です。
記事における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/abc335
問題A
文字列Sをchar型の配列とし、|S|-1番目の値を4にしたものを出力します。
例
public static void Solve()
{
var S = Scanner.Scan<string>().ToCharArray();
S[^1] = '4';
Console.WriteLine(new string(S));
}
問題B
x,y,zの3種が取りうる組み合わせは高々21^3==9261なので、全探索してx+y+z<=Nが成り立つかを判定します。
例
public static void Solve()
{
var N = Scanner.Scan<int>();
for (var x = 0; x <= N; x++)
{
for (var y = 0; y <= N; y++)
{
for (var z = 0; z <= N; z++)
{
var s = x + y + z;
if (s <= N)
{
Console.WriteLine($"{x} {y} {z}");
}
}
}
}
}
問題C
クエリ2を考えます。
pの位置は、それまでに移動した回数がq回である場合、パーツ1が移動した回数がq-p+1回目の位置になります。
q-p+1<0であるとき、(1-(p-q+1),0)の位置になります。
よって、クエリ1のときにq回目の移動回数のときのパーツ1の位置を記録し、クエリ2のときに上記の位置を求めることで、答えを求めることができます。
例
public static void Solve()
{
var (N, Q) = Scanner.Scan<int, int>();
var P = new (int X, int Y)[Q + 1];
P[0] = (1, 0);
var q = 0;
for (var i = 1; i <= Q; i++)
{
var query = Scanner.ScanEnumerable<string>().ToArray();
if (query[0] == "1")
{
var (cx, cy) = P[q];
q++;
var (dx, dy) = (0, 0);
switch (query[1])
{
case "R": dx++; break;
case "L": dx--; break;
case "U": dy++; break;
case "D": dy--; break;
default: break;
}
P[q] = (cx + dx, cy + dy);
}
else
{
var p = int.Parse(query[1]);
var d = q - p + 1;
if (d >= 0)
{
var (x, y) = P[d];
Console.WriteLine($"{x} {y}");
}
else
{
var (x, y) = (1 - d, 0);
Console.WriteLine($"{x} {y}");
}
}
}
}
問題D
左上から時計回りに外周をたどることを考えます。
グリッドGのch行cw列をG[ch][cw]とし、そのマスの値をv、進行方向をd (4方向)とします。
進行方向dの差分をdh行dw列とすると、v+1になるマスはnh=ch+dh行nw=cw+dw列になります。
G[nh][nw]がグリッドの外あるいは既に値が埋められていた場合、進行方向を時計回りに90度回転させます。
この処理をv==N*N-1まで行い、中央のマスをTにしたものを出力することで、答えを求めることができます。
進行方向の差分をD4={(0,1), (1,0), (0,-1), (-1,0)}の4つ管理しておき、進行方向を時計回りに90度回転させる処理をd=(d+1)%4とすることで、dのときの進行方向の差分D4[d]として取得することができます。
例
public static void Solve()
{
var N = Scanner.Scan<int>();
var G = new int[N, N];
for (var i = 0; i < N; i++)
{
for (var j = 0; j < N; j++)
{
G[i, j] = -1;
}
}
var D4 = new[] { (0, 1), (1, 0), (0, -1), (-1, 0) };
void Fill(int ch, int cw, int v, int d)
{
if (v == N * N) return;
G[ch, cw] = v;
var (dh, dw) = D4[d];
var (nh, nw) = (ch + dh, cw + dw);
if (nh < 0 || N <= nh || nw < 0 || N <= nw || G[nh, nw] != -1)
{
d++;
d %= 4;
(dh, dw) = D4[d];
(nh, nw) = (ch + dh, cw + dw);
}
Fill(nh, nw, v + 1, d);
}
Fill(0, 0, 1, 0);
var answer = new string[N, N];
for (var i = 0; i < N; i++)
{
for (var j = 0; j < N; j++)
{
answer[i, j] = G[i, j].ToString();
if (answer[i, j] == "-1") answer[i, j] = "T";
}
}
Printer.Print2D(answer, " ");
}
問題E
M個の辺のうち、A[u|v]<A[1]||A[N]<A[u|v]の場合は、その辺は考える必要はありません。
また、A[u]==A[v]の場合は、uとvを同一頂点としてみなすことができ、これはDisjointSetUnionなどで管理することができます。
そして、A[u]<A[v]の場合は、uからvへの辺のみ考えればよく、A[v]>A[u]の場合は、vからuへの辺のみを考えれば十分です。
dp[x]を頂点xのの最大得点とします。
頂点xの同一頂点をL(x)としたとき、dp[L(1)]=1、それ以外は-Infで初期化します。
頂点uから頂点vへの辺があるとき、A[u]の小さい順からdp[L(v)]=Max(dp[L(v)], dp[L(u)]+1)として更新していき、Max(0, dp[L(N)])が答えとなります。
例
public static void Solve()
{
var (N, M) = Scanner.Scan<int, int>();
var A = Scanner.ScanEnumerable<int>().ToArray();
var G = new List<int>[N].Select(x => new List<int>()).ToArray();
var dsu = new DisjointSetUnion(N);
var E = new Dictionary<int, List<(int U, int V)>>();
for (var i = 0; i < M; i++)
{
var (u, v) = Scanner.Scan<int, int>();
u--; v--;
if (A[u] < A[0] || A[u] > A[^1]) continue;
if (A[v] < A[0] || A[v] > A[^1]) continue;
if (A[u] > A[v]) (u, v) = (v, u);
if (A[u] == A[v])
{
dsu.Merge(u, v);
}
else
{
if (A[u] > A[v]) (u, v) = (v, u);
var a = A[u];
if (!E.ContainsKey(a)) E[a] = new List<(int U, int V)>();
E[a].Add((u, v));
}
}
const int Inf = 1 << 30;
var dp = new int[N];
Array.Fill(dp, -Inf);
dp[dsu.LeaderOf(0)] = 1;
foreach (var (a, edges) in E.OrderBy(x => x.Key))
{
foreach (var (u, v) in edges)
{
var (lu, lv) = (dsu.LeaderOf(u), dsu.LeaderOf(v));
dp[lv] = Math.Max(dp[lv], dp[lu] + 1);
}
}
var answer = Math.Max(0, dp[dsu.LeaderOf(N - 1)]);
Console.WriteLine(answer);
}