はじめに
AtCoder Beginner Contest 336の復習記事です。
記事における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/abc336
問題A
Lとngの間にoをN個連続させた文字列を出力します。
例
public static void Solve()
{
var N = Scanner.Scan<int>();
var answer = "L" + new string('o', N) + "ng";
Console.WriteLine(answer);
}
問題B
Nの下位ビットから0が何個続くかを求めます。
Nと1の論理和N&1を取ることで、下位1ビットの値が0|1を判別することができ、Nをビットシフトしていくことで、答えを求めることができます。
例
public static void Solve()
{
var N = Scanner.Scan<int>();
var answer = 0;
while ((N & 1) == 0)
{
answer++;
N >>= 1;
}
Console.WriteLine(answer);
}
問題C
5進数で考えたときのN番目の整数を求めます。
N-1を5進数変換し、各桁を0,2,4,6,8に変換したものが答えになります。
例
public static void Solve()
{
var N = Scanner.Scan<long>();
N--;
var builder = new StringBuilder();
var list = new List<long>();
while (N > 0)
{
list.Add(N % 5);
N /= 5;
}
list.Reverse();
foreach (var v in list)
{
builder.Append((char)(v * 2 + '0'));
}
var answer = list.Count == 0 ? "0" : builder.ToString();
Console.WriteLine(answer);
}
問題D
maxL[i]をAを左から見たときにi項目が取りうる最大値とし、maxR[i]をAを右から見たときにi項目が取りうる最大値とします。
maxL[0]=0としたとき、maxL[i]はMin(maxL[i-1]+1, A[i])となります。
同様に、maxR[N+1]=0として各maxR[i]を求めます。
そして、i項目をピラミッドの頂点として固定したとき、Min(maxL[i], maxR[i])の最大値が答えとなります。
例
public static void Solve()
{
var N = Scanner.Scan<int>();
var A = Scanner.ScanEnumerable<int>().ToArray();
var maxL = new int[N + 2];
var maxR = new int[N + 2];
for (var i = 0; i < N; i++)
{
maxL[i + 1] = Math.Min(maxL[i] + 1, A[i]);
}
Array.Reverse(A);
for (var i = 0; i < N; i++)
{
maxR[i + 1] = Math.Min(maxR[i] + 1, A[i]);
}
Array.Reverse(maxR);
var answer = 0;
for (var i = 0; i < N + 2; i++)
{
answer = Math.Max(answer, Math.Min(maxL[i], maxR[i]));
}
Console.WriteLine(answer);
}
問題E
まだ解けていません。
問題F
各状態を深さ優先探索で半分全探索します。
初期状態から10回の操作で遷移できる状態と最終状態から10回の操作で遷移できる状態を列挙しておき、両方の状態から遷移できる状態があるとき、初期状態からの操作回数+最終状態からの操作回数の最小値が答えとなります。
例
public static void Solve()
{
var (H, W) = Scanner.Scan<int, int>();
var G = new int[H][];
for (var i = 0; i < H; i++)
{
G[i] = Scanner.ScanEnumerable<int>().ToArray();
}
string ToString(int[][] g)
{
var buffer = new int[H * W];
for (var i = 0; i < H; i++)
{
for (var j = 0; j < W; j++)
{
buffer[i * W + j] = g[i][j];
}
}
return string.Join(" ", buffer);
}
void Rotate(int[][] g, int x, int y)
{
for (var i = x; i < H - (1 - x); i++)
{
var a = H - 1 - (1 - x) - i + x;
if (i > a) break;
for (var j = y; j < W - (1 - y); j++)
{
var b = W - 1 - (1 - y) - j + y;
if (i == a && j >= b) break;
(g[i][j], g[a][b]) = (g[a][b], g[i][j]);
}
}
}
var E = new int[H][];
for (var i = 0; i < H; i++)
{
E[i] = new int[W];
for (var j = 0; j < W; j++)
{
E[i][j] = i * W + j + 1;
}
}
const int Inf = 1 << 30;
void Dfs(int[][] g, string s, int c, Dictionary<string, int> dp)
{
if (c >= 10) return;
var u = ToString(g);
if (dp[u] > dp[s]) return;
for (var i = 0; i < 2; i++)
{
for (var j = 0; j < 2; j++)
{
for (var k = 0; k < 2; k++)
{
var v = ToString(g);
if (!dp.ContainsKey(v)) dp[v] = Inf;
if (dp[u] + 1 < dp[v])
{
dp[v] = dp[u] + 1;
Dfs(g, s, c + k, dp);
}
Rotate(g, i, j);
}
}
}
}
var dp1 = new Dictionary<string, int>();
var dp2 = new Dictionary<string, int>();
var S = ToString(G);
var T = ToString(E);
dp1[T] = Inf;
dp1[S] = 0;
Dfs(G, T, 0, dp1);
dp2[S] = Inf;
dp2[T] = 0;
Dfs(E, S, 0, dp2);
var answer = dp1[T];
foreach (var k in dp1.Keys)
{
if (dp2.ContainsKey(k))
{
answer = Math.Min(answer, dp1[k] + dp2[k]);
}
}
if (answer > 20) answer = -1;
Console.WriteLine(answer);
}