はじめに
AtCoder Beginner Contest 334の復習記事です。
記事における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/abc334
問題A
B>GならばBat、それ以外ならばGloveが答えになります。
例
public static void Solve()
{
var (B, G) = Scanner.Scan<int, int>();
var answer = B > G ? "Bat" : "Glove";
Console.WriteLine(answer);
}
問題B
Lを原点として考えると、R-=L,A-=L,L-=L(0)になります。
また、AからMごとにツリーがあることから、0以上で最小のツリーの位置Bは(A%M+M)%Mになります。
これにより、L(0)<=RかつL(0)<=Bとすることができます。
よって、R<Bのときはツリーはありません。
一方、B<=RのときはBを原点としたときのRまでにあるツリーの数になるので、(R-B)/M+1になります。
例
public static void Solve()
{
var (A, M, L, R) = Scanner.Scan<long, long, long, long>();
R -= L;
A -= L;
var B = (A % M + M) % M;
var answer = R < B ? 0 : (R - B) / M + 1;
Console.WriteLine(answer);
}
問題C
偶数のとき、Aのうち奇数番目と偶数番目をペアとしたK/2組を作ることが最適です。
これは、i,jをなくした色、なくしていない色をkとし、x=|i-k|,y=|j-k|,z=|i-j|,w=|k-k|すると、三角不等式より|z|+|w|=|z|<|x|+|y|になることから、なくした色のみ考えればいいからです。
奇数のとき、K個のうちの一つを除外して(K-1)/2組を作ることが最適になります。
よって、除外するものを固定したとき、それより左側にあるペアの累積和と右側にあるペアの累積和の総和の最小が答えになります。
例
public static void Solve()
{
var (N, K) = Scanner.Scan<int, int>();
var A = Scanner.ScanEnumerable<int>().ToArray();
var D = new long[K - 1];
for (var i = 0; i + 1 < K; i++)
{
D[i] = A[i + 1] - A[i];
}
var M = K / 2;
var cumL = new long[M + 1];
var cumR = new long[M + 1];
for (var i = 0; i < M; i++)
{
cumL[i + 1] = cumL[i] + D[i * 2];
}
Array.Reverse(D);
for (var i = 0; i < M; i++)
{
cumR[i + 1] = cumR[i] + D[i * 2];
}
Array.Reverse(cumR);
const long Inf = 1L << 60;
var answer = Inf;
for (var i = 0; i <= M; i++)
{
answer = Math.Min(answer, cumL[i] + cumR[i]);
}
Console.WriteLine(answer);
}
問題D
X匹以下で引くことができるソリをRが小さい方から順に選択することが、X匹以下で引くことができる最大のソリの数になります。
あらかじめRを昇順に並べ替えたものの累積和を計算しておき、クエリごとに累積和のX以下となるソリの数を二部探索することで、全体時間計算量O(NlogN)で答えを求めることができます。
例
public static void Solve()
{
var (N, Q) = Scanner.Scan<int, int>();
var R = Scanner.ScanEnumerable<long>().ToArray();
Array.Sort(R);
var cum = new long[N + 1];
for (var i = 0; i < N; i++)
{
cum[i + 1] = cum[i] + R[i];
}
while (Q-- > 0)
{
var X = Scanner.Scan<long>();
var answer = UpperBound(cum, X) - 1;
Console.WriteLine(answer);
}
}
public static int UpperBound<T>(List<T> source, T key, IComparer<T>? comparer = null)
=> UpperBound(System.Runtime.InteropServices.CollectionsMarshal.AsSpan(source), key, comparer);
public static int UpperBound<T>(ReadOnlySpan<T> source, T key, IComparer<T>? comparer = null)
{
comparer ??= Comparer<T>.Default;
var (lo, hi) = (-1, source.Length);
while (hi - lo > 1)
{
var mi = lo + ((hi - lo) >> 1);
if (comparer.Compare(source[mi], key) > 0) hi = mi;
else lo = mi;
}
return hi;
}
問題E
各赤色のマスごとに塗り替えた後の連結成分数の総和を、赤色のマスの数で割ったものが期待値になります。
初期状態の連結成分数をxとします。
ある赤色のマスから上下左右にある緑色のマス含む連結成分数をyとしたとき、その赤色のマスを緑色に塗り替えた後の連結成分数はx-y+1になります。
よって、初期状態の連結成分数をあらかじめ計算し、赤マスごとにの上下左右にある緑マスを含む連結成分数を求めていくことで、時間計算量O(HW)で答えを求めることができます。
例
public static void Solve()
{
var (H, W) = Scanner.Scan<int, int>();
var G = new char[H][];
for (var i = 0; i < H; i++)
{
G[i] = Scanner.Scan<string>().ToCharArray();
}
var dsu = new DisjointSetUnion(H * W);
int F(int h, int w) => h * W + w;
var D4 = new[] { (1, 0), (-1, 0), (0, 1), (0, -1) };
var red = 0;
for (var ch = 0; ch < H; ch++)
{
for (var cw = 0; cw < W; cw++)
{
if (G[ch][cw] == '.')
{
red++;
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 (G[nh][nw] == '#')
{
dsu.Merge(F(ch, cw), F(nh, nw));
}
}
}
}
var max = dsu.GetGroups().Count() - red;
var buffer = new List<int>(4);
var used = new bool[4];
mint answer = 0;
for (var ch = 0; ch < H; ch++)
{
for (var cw = 0; cw < W; cw++)
{
if (G[ch][cw] == '#') continue;
buffer.Clear();
Array.Fill(used, false);
foreach (var (dh, dw) in D4)
{
var (nh, nw) = (ch + dh, cw + dw);
if (nh < 0 || H <= nh || nw < 0 || W <= nw) continue;
if (G[nh][nw] == '#') buffer.Add(F(nh, nw));
}
var c = 0;
for (var i = 0; i < buffer.Count; i++)
{
if (used[i]) continue;
c++;
for (var j = i + 1; j < buffer.Count; j++)
{
if (dsu.IsSame(buffer[i], buffer[j]))
{
used[j] = true;
}
}
}
answer += max - c + 1;
}
}
answer /= red;
Console.WriteLine(answer);
}