はじめに
AtCoder Beginner Contest 332の復習記事です。
記事における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/abc332
問題A
P[i]*Q[i]の総和を求め、総和がS未満であれば送料のKを足したものが答えになります。
例
public static void Solve()
{
var (N, S, K) = Scanner.Scan<int, int, int>();
long answer = 0;
for (var i = 0; i < N; i++)
{
var (P, Q) = Scanner.Scan<long, long>();
answer += P * Q;
}
if (answer < S) answer += K;
Console.WriteLine(answer);
}
問題B
手順を愚直にシミュレートします。
現在のグラスの水の量をcg、現在のマグカップの水の量をcmとしたとき、cg==Gならばcg=0、そうでなくcm==0ならばcm=M、それ以外のときd=Min(G-cg,cm)としたとき、cg+=dかつcm-=dになります。
例
public static void Solve()
{
var (K, G, M) = Scanner.Scan<int, long, long>();
long cg = 0;
long cm = 0;
while (K-- > 0)
{
if (cg == G) cg = 0;
else if (cm == 0) cm = M;
else
{
var d = Math.Min(G - cg, cm);
cg += d;
cm -= d;
}
}
Console.WriteLine($"{cg} {cm}");
}
問題C
次のような小問題を定義したとき、新しく購入するTシャツの数xを二部探索します。
x枚のロゴ入りのTシャツを買うことでN日間過ごすことができるか。
無地のTシャツの枚数をa、ロゴ入りのTシャツの枚数をbとする。
初期値a=M、b=xとする。
各iについて次を判定する。
- S[i]が0のとき、a=M、b=xにする。
- S[i]が1のとき、a>0ならばa-=1する。そうでないとき、b>0ならばb-=1する。それ以外のときはTシャツがないので、x枚ではN日間過ごすことができない。
- S[i]が2のとき、b>0ならばb-=1する。それ以外のときはTシャツがないので、x枚ではN日間過ごすことができない。
1<=i<=Nにおいてa>=0かつb>=0を満たすことができれば、x枚でN日間過ごすことができる。
例
public static void Solve()
{
var (N, M) = Scanner.Scan<int, int>();
var S = Scanner.Scan<string>();
bool F(int x)
{
var a = M;
var b = x;
for (var i = 0; i < N; i++)
{
if (S[i] == '0')
{
a = M;
b = x;
}
else if (S[i] == '1')
{
if (a > 0) a--;
else if (b > 0) b--;
else return false;
}
else
{
if (b > 0) b--;
else return false;
}
}
return true;
}
var answer = BinarySearch<int>(-1, N, F);
Console.WriteLine(answer);
}
public static T BinarySearch<T>(T ng, T ok, Func<T, bool> f) where T : INumber<T> => BinarySearch(ng, ok, f, T.One);
public static T BinarySearch<T>(T ng, T ok, Func<T, bool> f, T eps) where T : INumber<T>
{
var one = T.One;
var two = one + one;
while (T.Abs(ok - ng) > eps)
{
var m = ng + (ok - ng) / two;
if (f(m)) ok = m;
else ng = m;
}
return ok;
}
問題D
行xと行yを入れ替えたとき、各列における要素の順番が変わるだけで、要素の集合が変わることはありません。
同様に、列xと列yを入れ替えたとき、各行における要素の順番が変わるだけで、要素の集合が変わることはありません。
このことから、行を入れ替える操作と列を入れ替える操作は、それぞれ独立していることがわかります。
よって、Aの行を並べ替える順列と、Aの列の並べ替えの順列を全探索し、行と列を並べ替えたものがBと一致しているかを判定します。
ある数列をバブルソートしたとき、隣り合う2項の交換回数はその数列の転倒数と一致するので、Bと一致するようなAの行番号の順列の転倒数と、列番号の順列の転倒数の和が、その並べ替えにおけるAをBに一致させる交換回数になります。
例
public static void Solve()
{
var (H, W) = Scanner.Scan<int, int>();
var A = new int[H][].Select(_ => Scanner.ScanEnumerable<int>().ToArray()).ToArray();
var B = new int[H][].Select(_ => Scanner.ScanEnumerable<int>().ToArray()).ToArray();
const int Inf = 1 << 30;
var answer = Inf;
foreach (var oAH in Permutation.Generate(H))
{
foreach (var oAW in Permutation.Generate(W))
{
var ok = true;
for (var i = 0; i < H && ok; i++)
{
for (var j = 0; j < W && ok; j++)
{
ok &= A[oAH[i]][oAW[j]] == B[i][j];
}
}
if (!ok) continue;
var inv = 0;
var ftH = new FenwickTree<int>(H);
var ftW = new FenwickTree<int>(W);
for (var i = 0; i < H; i++)
{
inv += i - ftH.Sum(oAH[i] + 1);
ftH.Add(oAH[i], 1);
}
for (var j = 0; j < W; j++)
{
inv += j - ftW.Sum(oAW[j] + 1);
ftW.Add(oAW[j], 1);
}
answer = Math.Min(answer, inv);
}
}
if (answer == Inf) answer = -1;
Console.WriteLine(answer);
}
public class FenwickTree<T>
where T : struct, IAdditionOperators<T, T, T>, ISubtractionOperators<T, T, T>, IComparisonOperators<T, T, bool>
{
public int Length { get; }
private readonly T[] _data;
public FenwickTree(int length)
{
if (length < 0) throw new ArgumentOutOfRangeException(nameof(length));
Length = length;
_data = new T[length];
}
public void Add(int index, T value)
{
if (index < 0 || Length <= index) throw new ArgumentOutOfRangeException(nameof(index));
index++;
while (index <= Length)
{
_data[index - 1] += value;
index += index & -index;
}
}
public T Sum(int length)
{
if (length < 0 || Length < length) throw new ArgumentOutOfRangeException(nameof(length));
T s = default;
while (length > 0)
{
s += _data[length - 1];
length -= length & -length;
}
return s;
}
public T Sum(int left, int right)
{
if (left < 0 || right < left || Length < right) throw new ArgumentOutOfRangeException();
return Sum(right) - Sum(left);
}
public int LowerBound(T value) => Bound(value, (x, y) => x <= y);
public int UpperBound(T value) => Bound(value, (x, y) => x < y);
private int Bound(T value, Func<T, T, bool> compare)
{
if (Length == 0 || compare(value, _data[0])) return 0;
var x = 0;
var r = 1;
while (r < Length) r <<= 1;
for (var k = r; k > 0; k >>= 1)
{
if (x + k - 1 >= Length || compare(value, _data[x + k - 1])) continue;
value -= _data[x + k - 1];
x += k;
}
return x;
}
}
public static class Permutation
{
public static bool NextPermutation(Span<int> indices)
{
var n = indices.Length;
var (i, j) = (n - 2, n - 1);
while (i >= 0 && indices[i] >= indices[i + 1]) i--;
if (i == -1) return false;
while (j > i && indices[j] <= indices[i]) j--;
(indices[i], indices[j]) = (indices[j], indices[i]);
indices[(i + 1)..].Reverse();
return true;
}
public static bool PreviousPermutation(Span<int> indices)
{
var n = indices.Length;
var (i, j) = (n - 2, n - 1);
while (i >= 0 && indices[i] <= indices[i + 1]) i--;
if (i == -1) return false;
indices[(i + 1)..].Reverse();
while (j > i && indices[j - 1] < indices[i]) j--;
(indices[i], indices[j]) = (indices[j], indices[i]);
return true;
}
public static IEnumerable<IReadOnlyList<int>> Generate(int n)
{
return Inner();
IEnumerable<IReadOnlyList<int>> Inner()
{
var indices = new int[n];
for (var i = 0; i < indices.Length; i++) indices[i] = i;
do { yield return indices; } while (NextPermutation(indices));
}
}
public static IEnumerable<IReadOnlyList<int>> GenerateDescending(int n)
{
return Inner();
IEnumerable<IReadOnlyList<int>> Inner()
{
var indices = new int[n];
for (var i = 0; i < indices.Length; i++) indices[i] = n - 1 - i;
do { yield return indices; } while (PreviousPermutation(indices));
}
}
}