はじめに
AtCoder Beginner Contest 341の復習記事です。
記事における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/abc341
問題A
最初に1から始めて、N個の01を繋げた文字列が答えになります。
例
public static void Solve()
{
var N = Scanner.Scan<int>();
var builder = new StringBuilder();
builder.Append('1');
for (var i = 0; i < N; i++)
{
builder.Append("01");
}
var answer = builder.ToString();
Console.WriteLine(answer);
}
問題B
iが小さい順にS[i]をT[i]にする行動を可能な限り行い、最終的なNの通貨の単位が答えになります。
つまり、N未満の各iにおいて、i+1の通貨をA[i]/S*T増やすという作業を順に行うことで達成できます。
例
public static void Solve()
{
var N = Scanner.Scan<int>();
var A = Scanner.ScanEnumerable<long>().ToArray();
for (var i = 0; i < N - 1; i++)
{
var (s, t) = Scanner.Scan<long, long>();
A[i + 1] += t * (A[i] / s);
}
var answer = A[^1];
Console.WriteLine(answer);
}
問題C
全ての陸の座標から移動を行い、文字列が示す順に移動を行い、経路上が全て陸の経路の数を数え上げます。
例
public static void Solve()
{
var (H, W, N) = Scanner.Scan<int, int, int>();
var T = Scanner.Scan<string>();
var G = new char[H][];
for (var i = 0; i < H; i++)
{
G[i] = Scanner.Scan<string>().ToCharArray();
}
(int dh, int dw) Delta(char d)
{
return d switch
{
'L' => (0, -1),
'R' => (0, 1),
'U' => (-1, 0),
'D' => (1, 0),
_ => (0, 0)
};
}
(int h, int w) F(int ch, int cw)
{
foreach (var d in T)
{
var (dh, dw) = Delta(d);
var (nh, nw) = (ch + dh, cw + dw);
if (nh < 0 || H <= nh || nw < 0 || W <= nw) return (-1, -1);
if (G[nh][nw] == '#') return (-1, -1);
ch = nh;
cw = nw;
}
return (ch, cw);
}
var ok = new bool[H, W];
for (var i = 0; i < H; i++)
{
for (var j = 0; j < W; j++)
{
if (G[i][j] == '#') continue;
var (ch, cw) = F(i, j);
if (ch < 0 || cw < 0) continue;
ok[ch, cw] = true;
}
}
var answer = 0;
for (var i = 0; i < H; i++)
{
for (var j = 0; j < W; j++)
{
if (ok[i, j]) answer++;
}
}
Console.WriteLine(answer);
}
問題D
x以下のNの倍数またはMの倍数の個数は、Nの倍数の個数とMの倍数の個数からLCM(N,M)の倍数の個数を引いたものとなります。
また、ちょうど一方のみで割り切れる数は、x以下のNの倍数またはMの倍数の個数からさらにLCM(N,M)の倍数の個数を引いたものとなります。
よって、x/N + x/M - x/LCM(N,M)*2 >= Kとなるxを二部探索することで答えを求めることができます。
例
public static void Solve()
{
var (N, M, K) = Scanner.Scan<long, long, long>();
var lcm = Lcm(N, M);
bool F(long x)
{
return (x / N) + (x / M) - ((x / lcm) * 2) >= K;
}
const long Inf = 1L << 60;
var answer = BinarySearch(0, Inf, F);
Console.WriteLine(answer);
}
public static long Gcd(long a, long b) => b == 0 ? a : Gcd(b, a % b);
public static long Lcm(long a, long b) => a / Gcd(a, b) * b;
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;
}
問題E
隣り合う数字の変化量に注目します。
隣り合う数字が異なる場合、その変化量を1とすると、L文字目からR文字目が良い文字列になる条件は、L文字目からR文字目までの変化量の総和がその文字列の長さ-1であることになります。
例えば、6文字の良い文字列の010101の変化量は5となり、6文字の良い文字列ではない011010の変化量は4となります。
ある範囲を反転させるということは、L-1文字目とL文字目の変化量が1-元の変化量になり、L文字目からR文字目の変化量は変わらず、R文字目からR+1文字目の変化量が1-元の変化量になります。
よって、一点更新区間和のSegmentTreeを使って変化量を管理することで、クエリ当たり時間計算量O(logN)で答えを求めることができます。
例
public static void Solve()
{
var (N, Q) = Scanner.Scan<int, int>();
var S = Scanner.Scan<string>().ToArray();
var A = new int[N - 1];
var st = new SegmentTree<int>(N + 1, new Oracle());
for (var i = 0; i + 1 < N; i++)
{
st.Set(i + 1, S[i] == S[i + 1] ? 0 : 1);
}
while (Q-- > 0)
{
var (t, l, r) = Scanner.Scan<int, int, int>();
if (t == 1)
{
st.Set(l - 1, 1 - st.Get(l - 1));
st.Set(r, 1 - st.Get(r));
}
else
{
var answer = st.Query(l, r) == r - l;
Console.WriteLine(answer ? "Yes" : "No");
}
}
}
public class Oracle : IOracle<int>
{
public int IdentityElement => 0;
public int Operate(int a, int b)
{
return 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]);
}