はじめに
AtCoder Beginner Contest 339の復習記事です。
記事における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/abc339
問題A
Sを末尾から見ていき、.が出現した次の文字以降の文字列を出力します。
例
public static void Solve()
{
var S = Scanner.Scan<string>();
var i = S.Length - 1;
while (S[i] != '.') i--;
var answer = S[(i + 1)..];
Console.WriteLine(answer);
}
問題B
上下左右の移動方向の差分(dh,dw)をそれぞれU=(-1,0), D=(1,0), R=(0,1), L=(0,-1)とし、現在位置に向いている方向の差分を足した位置に移動させます。
このとき、URDLの順に配列として並べてインデックスで参照し、時計回りに90度の回転をインデックスを+1する、反時計回りに90度の回転をインデックスを-1することに対応づけることで、楽に管理することができます。
例
public static void Solve()
{
var (H, W, N) = Scanner.Scan<int, int, int>();
var G = new char[H, W];
for (var i = 0; i < H; i++)
{
for (var j = 0; j < W; j++)
{
G[i, j] = '.';
}
}
var (ch, cw) = (0, 0);
var delta = new[] { (-1, 0), (0, 1), (1, 0), (0, -1) };
var dir = 0;
for (var i = 0; i < N; i++)
{
if (G[ch, cw] == '.')
{
G[ch, cw] = '#';
dir = (dir + 1) % 4;
}
else
{
G[ch, cw] = '.';
dir = (dir - 1 + 4) % 4;
}
var (dh, dw) = delta[dir];
(ch, cw) = ((ch + dh + H) % H, (cw + dw + W) % W);
}
Printer.Print2D(G);
}
問題C
答えを二部探索します。
バスの乗客数xが与えられた情報に矛盾しないかの判定は、A[i]を逆順でxから引いていき、一度もx<0にならない場合は矛盾しない乗客数となります。
例
public static void Solve()
{
var N = Scanner.Scan<int>();
var A = Scanner.ScanEnumerable<long>().ToArray();
bool F(long x)
{
for (var i = N - 1; i >= 0; i--)
{
x -= A[i];
if (x < 0) return false;
}
return true;
}
const long Inf = 1L << 60;
var answer = BinarySearch(-1, Inf, 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
次のような動的計画法を解きます。
dp[ch1][cw1][ch2][cw2] := プレイヤー1が(ch1,cw1)、プレイヤー1が(ch2,cw2)にいるときの最小移動回数。
これは、各プレイヤーの現在位置を幅優先探索で最小移動回数を計算することで、答えを求めることができます。
例
public static void Solve()
{
var N = Scanner.Scan<int>();
var S = new char[N][];
var p = new List<(int H, int W)>();
for (var i = 0; i < N; i++)
{
S[i] = Scanner.Scan<string>().ToCharArray();
for (var j = 0; j < N; j++)
{
if (S[i][j] == 'P')
{
p.Add((i, j));
}
}
}
const int Inf = 1 << 30;
var D4 = new[] { (1, 0), (-1, 0), (0, 1), (0, -1) };
var queue = new Queue<Data>();
var first = new Data(p[0].H, p[0].W, p[1].H, p[1].W);
queue.Enqueue(first);
var dp = new int[N, N, N, N];
for (var h1 = 0; h1 < N; h1++)
{
for (var w1 = 0; w1 < N; w1++)
{
for (var h2 = 0; h2 < N; h2++)
{
for (var w2 = 0; w2 < N; w2++)
{
dp[h1, w1, h2, w2] = Inf;
}
}
}
}
dp[p[0].H, p[0].W, p[1].H, p[1].W] = 0;
bool CanMove(int ch, int cw, int nh, int nw)
{
return 0 <= nh && nh < N && 0 <= nw && nw < N && S[nh][nw] != '#';
}
var answer = Inf;
while (queue.Count > 0)
{
var curr = queue.Dequeue();
var (ch1, cw1, ch2, cw2) = curr;
foreach (var (dh, dw) in D4)
{
var (nh1, nw1) = (ch1 + dh, cw1 + dw);
var (nh2, nw2) = (ch2 + dh, cw2 + dw);
if (!CanMove(ch1, cw1, nh1, nw1)) (nh1, nw1) = (ch1, cw1);
if (!CanMove(ch2, cw2, nh2, nw2)) (nh2, nw2) = (ch2, cw2);
var next = new Data(nh1, nw1, nh2, nw2);
if (dp[ch1, cw1, ch2, cw2] + 1 < dp[nh1, nw1, nh2, nw2])
{
dp[nh1, nw1, nh2, nw2] = dp[ch1, cw1, ch2, cw2] + 1;
if (nh1 == nh2 && nw1 == nw2)
{
answer = Math.Min(answer, dp[nh1, nw1, nh2, nw2]);
}
else
{
queue.Enqueue(next);
}
}
}
}
if (answer == Inf) answer = -1;
Console.WriteLine(answer);
}
public readonly record struct Data(int H1, int W1, int H2, int W2);
問題E
A[i]を末尾とするときの部分列の最大の長さは、部分列の末尾がx (A[i]-D<=x<=A[i]+D)のときの部分列の最大の長さ+1で求めることができます。
これは、区間の最大を求めるのSegmentTreeで時間計算量O(logN)で求めることができ、全体計算量O(NlogN)で答えを求めることができます。
例
public static void Solve()
{
var (N, D) = Scanner.Scan<int, int>();
var A = Scanner.ScanEnumerable<int>().ToArray();
var max = A.Max() + 10;
var st = new SegmentTree<int>(max, new Oracle());
for (var i = 0; i < N; i++)
{
var l = Math.Max(0, A[i] - D);
var r = Math.Min(A[i] + D + 1, max);
var v = st.Query(l, r);
st.Set(A[i], v + 1);
}
var answer = st.QueryToAll();
Console.WriteLine(answer);
}
public class Oracle : IOracle<int>
{
public int IdentityElement => 0;
public int Operate(int a, int b)
{
return Math.Max(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]);
}