はじめに
AtCoder Beginner Contest 343の復習記事です。
記事における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/abc343
問題A
C=A+Bとし、0から9の間でfor文を回してC以外の値であればそれを出力します。
例
public static void Solve()
{
var (A, B) = Scanner.Scan<int, int>();
var C = A + B;
for (var i = 0; i < 10; i++)
{
if (i != C)
{
Console.WriteLine(i);
return;
}
}
}
問題B
i行目の出力は、A[i][j]==1となるjを全て出力します。
例
public static void Solve()
{
var N = Scanner.Scan<int>();
var A = new int[N][];
for (var i = 0; i < N; i++)
{
A[i] = Scanner.ScanEnumerable<int>().ToArray();
}
for (var i = 0; i < N; i++)
{
var list = new List<int>();
for (var j = 0; j < N; j++)
{
if (A[i][j] == 1)
{
list.Add(j + 1);
}
}
Console.WriteLine(string.Join(" ", list));
}
}
問題C
x*x*x=k<=Nとなるxを走査し、そのkを文字列としてみたときに回文であるかを判定し、回文であるときの最大のkを求めます。
例
public static void Solve()
{
var N = Scanner.Scan<long>();
bool F(long x)
{
var s = x.ToString();
var m = s.Length;
for (int i = 0, j = m - 1; i <= j; i++, j--)
{
if (s[i] != s[j]) return false;
}
return true;
}
long answer = 0;
for (long x = 1; x * x * x <= N; x++)
{
var k = x * x * x;
if (k <= N && F(k))
{
answer = k;
}
}
Console.WriteLine(answer);
}
問題D
得点をKeyとした選手の番号の集合をもつ辞書などを使って現在の状態を管理します。
現在のAの得点がxであるとき、y=x+Bとなる得点yの集合にAを追加し、得点xの集合からAを削除する操作を行います。
このとき、得点xが空集合であれば、xのキーを削除し、辞書に存在するキーの数が答えとなります。
例
public static void Solve()
{
var (N, T) = Scanner.Scan<int, int>();
var dp = new Dictionary<long, HashSet<int>>();
dp[0] = Enumerable.Range(0, N).ToHashSet();
var P = new long[N];
for (var i = 0; i < T; i++)
{
var (A, B) = Scanner.Scan<int, int>();
A--;
var curr = P[A];
var next = curr + B;
if (!dp.ContainsKey(next)) dp[next] = new HashSet<int>();
dp[next].Add(A);
dp[curr].Remove(A);
P[A] = next;
if (dp[curr].Count == 0) dp.Remove(curr);
Console.WriteLine(dp.Count);
}
}
問題E
まだ解けていません。
問題F
1番目に大きい値をX1、X1の個数をC1、2番目に大きい値をX2、X2の個数をC2とし、i番目にX1=A[i], C1=1, X2=0, C2=0の要素をもつSegmentTreeを用意します。
SegmentTreeにおいて、ある値xとその個数cがあるとき、次のような演算をおこないます。
- X1<xならば、X1=x, C1=c, X2=X1, C2=C1
- それ以外かつX1==xならば、C1+=c,
- それ以外かつX2<xならば、X2=x, C2=c
- それ以外かつX2==xならば、C2+=c,
1番目のクエリでは、SegmentTreeのi番目の要素をX1=p, C1=1, X2=0, C2=0で更新します。
2番目のクエリでは、SegmentTreeのlからrについて、上記の演算を行うことで、時間計算量O(logN)で求めることができます。
例
public static void Solve()
{
var (N, Q) = Scanner.Scan<int, int>();
var A = Scanner.ScanEnumerable<int>().ToArray();
var st = new SegmentTree<Data>(N, new Oracle());
for (var i = 0; i < N; i++)
{
st.Set(i, new Data(A[i], 1, 0, 0));
}
while (Q-- > 0)
{
var query = Scanner.ScanEnumerable<int>().ToArray();
if (query[0] == 1)
{
var p = query[1] - 1;
var x = query[2];
var next = new Data(x, 1, 0, 0);
st.Set(p, next);
}
else
{
var l = query[1] - 1;
var r = query[2];
var x = st.Query(l, r);
Console.WriteLine(x.C2);
}
}
}
public readonly record struct Data(int X1, int C1, int X2, int C2);
public class Oracle : IOracle<Data>
{
public Data IdentityElement => new Data(0, 0, 0, 0);
public Data Operate(Data a, Data b)
{
var x1 = 0;
var c1 = 0;
var x2 = 0;
var c2 = 0;
void F(int x, int c)
{
if (x1 < x)
{
x2 = x1;
c2 = c1;
x1 = x;
c1 = c;
}
else if (x1 == x)
{
c1 += c;
}
else if (x2 < x)
{
x2 = x;
c2 = c;
}
else if (x2 == x)
{
c2 += c;
}
}
F(a.X1, a.C1);
F(a.X2, a.C2);
F(b.X1, b.C1);
F(b.X2, b.C2);
return new Data(x1, c1, x2, c2);
}
}
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]);
}