はじめに
AtCoder Beginner Contest 330の復習記事です。
記事における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/abc330
問題A
A内の条件を満たす個数を数え上げます。
また、C#ではIEnumerable<T>を実装するシーケンスに対して、Count()の引数に条件判定を行うラムダ式を渡すことで、シーケンス内で与えられた条件を満たすものの個数を得ることができます。
例
public static void Solve()
{
var (N, L) = Scanner.Scan<int, int>();
var A = Scanner.ScanEnumerable<int>().ToArray();
var answer = A.Count(x => x >= L);
Console.WriteLine(answer);
}
問題B
L<=x<=Rのうち、A[i]に最も近いxを求めます。
L<=A[i]<=Rであるとき、xはA[i]です。
A[i]<Lであるとき、xはLです。
A[i]>Rであるとき、xはRです。
例
public static void Solve()
{
var (N, L, R) = Scanner.Scan<int, long, long>();
var A = Scanner.ScanEnumerable<long>().ToArray();
var answers = A.Select(x => Math.Min(Math.Max(L, x), R));
Console.WriteLine(string.Join(" ", answers));
}
問題C
xを固定して考えると、xが取りうる範囲は0<=x<=Sqrt(D)になります。
これにより、x^2-Dをcとすると、c>=0のときy==0で最小値を取り、c<0のとき、y==Floor(Sqrt(-c))またはy==Ceil(Sqrt(-c))で最小値を取ります。
例
public static void Solve()
{
var D = Scanner.Scan<long>();
const long Inf = 1L << 60;
var answer = Inf;
for (long x = 0; x * x <= D; x++)
{
var xx = x * x;
var c = xx - D;
var y = c >= 0 ? 0 : (long)Math.Sqrt(-c);
for (var k = 0; k < 2; k++)
{
var yy = (y + k) * (y + k);
var v = Math.Abs(xx + yy - D);
answer = Math.Min(answer, v);
}
}
Console.WriteLine(answer);
}
問題D
i行目のoの個数をcH[i]、j行目のoの個数をcW[j]とします。
i行目j列のマスがoのとき、そのマスと同じ行にあるoのマスを選ぶ組み合わせはch[i]-1個、そのマスと同じ列にあるoのマスを選ぶ組み合わせはcw[j]-1個なので、このマスを3マスのうちの1つとしたとき、このマスを含む組み合わせは(ch[i]-1)*(cw[j]-1)個になります。
よって、すべてのoのマスを固定したときの組み合わせの総和が答えになります。
例
public static void Solve()
{
var N = Scanner.Scan<int>();
var G = new char[N][];
for (var i = 0; i < N; i++)
{
G[i] = Scanner.Scan<string>().ToCharArray();
}
var cH = new long[N + 1];
var cW = new long[N + 1];
for (var i = 0; i < N; i++)
{
for (var j = 0; j < N; j++)
{
if (G[i][j] == 'x') continue;
cH[i]++;
cW[j]++;
}
}
long answer = 0;
for (var i = 0; i < N; i++)
{
for (var j = 0; j < N; j++)
{
if (G[i][j] == 'x') continue;
answer += (cH[i] - 1) * (cW[j] - 1);
}
}
Console.WriteLine(answer);
}
問題E
長さNの数列において取りうるmexの値は、0<=mex<=Nになります。
よって、A[i]がNより大きい場合は、その値に対する処理を無視することができます。
また、数列Xにおいて、A[i]に存在する値はX[A[i]]=inf、存在しない値はX[i]=iとすることで、Xにおける最小値をmexとして求めることができます。
よって、N以下の値がそれぞれ何個あるかを管理しながら、SegmentTreeなどのデータ構造を使い区間内における最小値を高速で求められるようにすることで、クエリ当たり時間計算量O(logN)、全体時間計算量O(QlogN)で答えを求めることができます。
例
public static void Solve()
{
var (N, Q) = Scanner.Scan<int, int>();
var A = Scanner.ScanEnumerable<int>().ToArray();
var count = new int[N + 1];
var st = new SegmentTree<int>(N + 1, new Oracle());
const int Inf = 1 << 30;
for (var i = 0; i <= N; i++)
{
st.Set(i, i);
}
foreach (var a in A)
{
if (a <= N)
{
count[a]++;
st.Set(a, Inf);
}
}
for (var q = 0; q < Q; q++)
{
var (i, x) = Scanner.Scan<int, int>();
i--;
if (A[i] <= N)
{
count[A[i]]--;
if (count[A[i]] == 0) st.Set(A[i], A[i]);
}
A[i] = x;
if (x <= N)
{
count[x]++;
st.Set(x, Inf);
}
var mex = Math.Min(st.QueryToAll(), N);
Console.WriteLine(mex);
}
}
public class Oracle : IOracle<int>
{
public int IdentityElement => 1 << 30;
public int Operate(int a, int b)
{
return Math.Min(a, b);
}
}
public interface IOracle<TMonoid>
{
TMonoid IdentityElement { get; }
TMonoid Operate(TMonoid a, TMonoid b);
}
public class SegmentTree<TMonoid>
{
public int Length { get; }
private readonly IOracle<TMonoid> _oracle;
private readonly TMonoid[] _data;
private readonly int _log;
private readonly int _dataSize;
public SegmentTree(IReadOnlyCollection<TMonoid> source, IOracle<TMonoid> oracle) : this(source.Count, oracle)
{
var idx = _dataSize;
foreach (var value in source) _data[idx++] = value;
for (var i = _dataSize - 1; i >= 1; i--) Update(i);
}
public SegmentTree(int length, IOracle<TMonoid> oracle)
{
if (length < 0) throw new ArgumentOutOfRangeException(nameof(length));
Length = length;
_oracle = oracle;
while (1 << _log < Length) _log++;
_dataSize = 1 << _log;
_data = new TMonoid[_dataSize << 1];
Array.Fill(_data, oracle.IdentityElement);
}
public void Set(int index, TMonoid value)
{
if (index < 0 || Length <= index) throw new ArgumentOutOfRangeException(nameof(index));
index += _dataSize;
_data[index] = value;
for (var i = 1; i <= _log; i++) Update(index >> i);
}
public TMonoid Get(int index)
{
if (index < 0 || Length <= index) throw new ArgumentOutOfRangeException(nameof(index));
return _data[index + _dataSize];
}
public TMonoid Query(int left, int right)
{
if (left < 0 || right < left || Length < right) throw new ArgumentOutOfRangeException();
var (sml, smr) = (_oracle.IdentityElement, _oracle.IdentityElement);
left += _dataSize;
right += _dataSize;
while (left < right)
{
if ((left & 1) == 1) sml = _oracle.Operate(sml, _data[left++]);
if ((right & 1) == 1) smr = _oracle.Operate(_data[--right], smr);
left >>= 1;
right >>= 1;
}
return _oracle.Operate(sml, smr);
}
public TMonoid QueryToAll() => _data[1];
public int MaxRight(int left, Func<TMonoid, bool> predicate)
{
if (left < 0 || Length < left) throw new ArgumentOutOfRangeException(nameof(left));
if (predicate is null) throw new ArgumentNullException(nameof(predicate));
if (!predicate(_oracle.IdentityElement)) throw new ArgumentException(nameof(predicate));
if (left == Length) return Length;
left += _dataSize;
var sm = _oracle.IdentityElement;
do
{
while ((left & 1) == 0) left >>= 1;
if (!predicate(_oracle.Operate(sm, _data[left])))
{
while (left < _dataSize)
{
left <<= 1;
var tmp = _oracle.Operate(sm, _data[left]);
if (!predicate(tmp)) continue;
sm = tmp;
left++;
}
return left - _dataSize;
}
sm = _oracle.Operate(sm, _data[left]);
left++;
} while ((left & -left) != left);
return Length;
}
public int MinLeft(int right, Func<TMonoid, bool> predicate)
{
if (right < 0 || Length < right) throw new ArgumentOutOfRangeException(nameof(right));
if (predicate is null) throw new ArgumentNullException(nameof(predicate));
if (!predicate(_oracle.IdentityElement)) throw new ArgumentException(nameof(predicate));
if (right == 0) return 0;
right += _dataSize;
var sm = _oracle.IdentityElement;
do
{
right--;
while (right > 1 && (right & 1) == 1) right >>= 1;
if (!predicate(_oracle.Operate(_data[right], sm)))
{
while (right < _dataSize)
{
right = (right << 1) + 1;
var tmp = _oracle.Operate(_data[right], sm);
if (!predicate(tmp)) continue;
sm = tmp;
right--;
}
return right + 1 - _dataSize;
}
sm = _oracle.Operate(_data[right], sm);
} while ((right & -right) != right);
return 0;
}
private void Update(int k) => _data[k] = _oracle.Operate(_data[k << 1], _data[(k << 1) + 1]);
}