はじめに
AtCoder Beginner Contest 241の復習記事です。
記事におけるScannerクラスは、自作の入力クラスです。
コンテスト
https://atcoder.jp/contests/abc241
問題A
現在の値をcurrとし、現在の値をA[curr]で更新します。
public static void Solve()
{
var A = Scanner.ScanEnumerable<int>().ToArray();
var curr = 0;
for (var i = 0; i < 3; i++)
{
curr = A[curr];
}
Console.WriteLine(curr);
}
問題B
あらかじめ麵の長さAの個数を辞書に持ち、Bを順番に見たときに、1個以上ある場合は辞書のBの値をデクリメントし、0個または辞書に存在しない場合は答えはNoになります。最終的にすべてを見ることができれば、答えはYesとなります。
public static void Solve()
{
var (N, M) = Scanner.Scan<int, int>();
var A = Scanner.ScanEnumerable<int>().ToArray();
var B = Scanner.ScanEnumerable<int>().ToArray();
var dict = new Dictionary<int, int>();
foreach (var a in A)
{
if (!dict.ContainsKey(a))
{
dict[a] = 0;
}
dict[a]++;
}
foreach (var b in B)
{
if (!dict.ContainsKey(b) || dict[b] == 0)
{
Console.WriteLine("No");
return;
}
dict[b]--;
}
Console.WriteLine("Yes");
}
問題C
マスを順にみて、端を(i,j)に固定したときに連続した区間のうち4つ以上#が存在すれば、答えはYesとなります。
縦の場合は(i,j)から(i+5,j)まで、横の場合は(i,j)から(i,j+5)まで、斜めの場合は(i,j)から(i+5,j+5)と(i+5,j-5)を確かめます。
検査時に範囲外に出ないように注意します。
public static void Solve()
{
var N = Scanner.Scan<int>();
var G = new string[N];
for (var i = 0; i < N; i++)
{
G[i] = Scanner.ScanLine();
}
for (var i = 0; i < N; i++)
{
for (var j = 0; j < N; j++)
{
var ok = false;
if (i + 5 < N)
{
var count = 0;
for (var k = 0; k <= 5; k++)
{
if (G[i + k][j] == '#') count++;
}
ok |= count >= 4;
}
if (j + 5 < N)
{
var count = 0;
for (var k = 0; k <= 5; k++)
{
if (G[i][j + k] == '#') count++;
}
ok |= count >= 4;
}
if (i + 5 < N && j + 5 < N)
{
var count = 0;
for (var k = 0; k <= 5; k++)
{
if (G[i + k][j + k] == '#') count++;
}
ok |= count >= 4;
}
if (i + 5 < N && j - 5 >= 0)
{
var count = 0;
for (var k = 0; k <= 5; k++)
{
if (G[i + k][j - k] == '#') count++;
}
ok |= count >= 4;
}
if (ok)
{
Console.WriteLine("Yes");
return;
}
}
}
Console.WriteLine("No");
}
問題D
復習提出 (FenwickTree) 復習提出 (平衡二分探索木)
FenwickTreeを使った場合の解き方です。
xの値が大きいので、あらかじめクエリを先読みし、出現する座標を圧縮します。
圧縮したxの値をcxとしたとき、
tの値が1であれば、FenwickTreeのcxに1を追加します。tの値が2であれば、FenwickTreeの区間[idx, cx]の値がk以上の場所を二部探索し、存在するならばその時のidxの対応する値が答えとなります。tの値が2であれば、FenwickTreeの区間[cx, idx]の値がk以上の場所を二部探索し、存在するならばその時のidxの対応する値が答えとなります。
public static void Solve()
{
var Q = Scanner.Scan<int>();
var query = new (int, long, int)[Q];
var set = new HashSet<long>();
for (var i = 0; i < Q; i++)
{
var line = Scanner.ScanEnumerable<long>().ToArray();
var (t, x) = ((int)line[0], line[1]);
var k = t == 1 ? -1 : (int)line[2];
query[i] = (t, x, k);
set.Add(x);
}
var (map, remap) = Compress(set);
var N = map.Count;
var ft = new FenwickTree(N);
foreach (var (t, x, k) in query)
{
if (t == 1)
{
ft.Add(map[x], 1);
}
else if (t == 2)
{
bool F(int idx) => ft.Sum(idx, map[x] + 1) >= k;
var idx = BinarySearch(map[x] + 1, 0, F);
var answer = F(idx) ? remap[idx] : -1;
Console.WriteLine(answer);
}
else
{
bool F(int idx) => ft.Sum(map[x], idx + 1) >= k;
var idx = BinarySearch(map[x] - 1, N - 1, F);
var answer = F(idx) ? remap[idx] : -1;
Console.WriteLine(answer);
}
}
}
public static int BinarySearch(int ng, int ok, Func<int, bool> func)
{
while (Math.Abs(ok - ng) > 1)
{
var m = (ok + ng) / 2;
if (func(m)) ok = m;
else ng = m;
}
return ok;
}
public static (Dictionary<T, int> Map, Dictionary<int, T> ReMap) Compress<T>(IEnumerable<T> source)
{
var distinct = source.Distinct().ToArray();
Array.Sort(distinct);
var map = new Dictionary<T, int>();
var remap = new Dictionary<int, T>();
foreach (var (x, i) in distinct.Select((x, i) => (x, i)))
{
map[x] = i;
remap[i] = x;
}
return (map, remap);
}
public class FenwickTree
{
private readonly long[] _data;
private readonly int _length;
public FenwickTree(int length)
{
if (length < 0) throw new ArgumentOutOfRangeException(nameof(length));
_length = length;
_data = new long[length];
}
public void Add(int index, long item)
{
if (index < 0 || _length <= index) throw new ArgumentOutOfRangeException(nameof(index));
index++;
while (index <= _length)
{
_data[index - 1] += item;
index += index & -index;
}
}
public long Sum(int length)
{
if (length < 0 || _length < length) throw new ArgumentOutOfRangeException(nameof(length));
var s = 0L;
while (length > 0)
{
s += _data[length - 1];
length -= length & -length;
}
return s;
}
public long Sum(int left, int right)
{
if (left < 0 || right < left || _length < right) throw new ArgumentOutOfRangeException();
return Sum(right) - Sum(left);
}
public int LowerBound(long item) => CommonBound(item, LessThanOrEqual);
public int UpperBound(long item) => CommonBound(item, LessThan);
private int CommonBound(long item, Func<long, long, bool> compare)
{
if (compare(item, _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(item, _data[x + k - 1])) continue;
item -= _data[x + k - 1];
x += k;
}
return x;
}
private static bool LessThanOrEqual(long x, long y) => x <= y;
private static bool LessThan(long x, long y) => x < y;
}
平衡二分探索木を使った時の解き方です。
C#ではMultiSetが存在しないので、平衡二分探索木を自作する必要があります。
降順、昇順の平衡二分探索木を用意し、
tの値が1であれば、両方の平衡二分探索木にxを追加します。tの値が2であれば、降順の平衡二分探索木においてx以上になるインデックス(idx)を取得し、idx+k-1となる値が存在するならば、その値が答えとなります。tの値が3であれば、昇順の平衡二分探索木において、x以下になるインデックス(idx)を取得し、idx+k-1となる値が存在するならば、その値が答えとなります。
public static void Solve()
{
var Q = Scanner.Scan<int>();
var asc = new RandomizedBinarySearchTree<long>();
var desc = new RandomizedBinarySearchTree<long>((x, y) => y.CompareTo(x));
while (Q-- > 0)
{
var line = Scanner.ScanEnumerable<long>().ToArray();
var (t, x) = (line[0], line[1]);
if (t == 1)
{
asc.Insert(x);
desc.Insert(x);
}
else
{
var k = (int)line[2] - 1;
var set = t == 2 ? desc : asc;
if (set.Count() == 0)
{
Console.WriteLine(-1);
continue;
}
var lb = set.LowerBound(x);
var answer = lb + k < set.Count() ? set.ElementAt(lb + k) : -1;
Console.WriteLine(answer);
}
}
}
次のような平衡二分探索木を使用しました。
public class RandomizedBinarySearchTree<T> : IEnumerable<T>
{
private readonly Comparison<T> _comparison;
private readonly Compare _lowerBound;
private readonly Compare _upperBound;
private readonly Random _random;
private Node _root;
private int _count;
public RandomizedBinarySearchTree(int seed = 0) : this(comparer: null, seed) { }
public RandomizedBinarySearchTree(Comparer<T> comparer, int seed = 0) : this(
(comparer ?? Comparer<T>.Default).Compare, seed)
{
}
public RandomizedBinarySearchTree(Comparison<T> comparison, int seed = 0)
{
_comparison = comparison;
_lowerBound = (x, y) => _comparison(x, y) >= 0;
_upperBound = (x, y) => _comparison(x, y) > 0;
_random = new Random(seed);
}
public delegate bool Compare(T x, T y);
public void Insert(T value)
{
if (_root is null) _root = new Node(value);
else InsertAt(LowerBound(value), value);
}
public void InsertAt(int index, T value)
{
var (l, r) = Split(_root, index);
_root = Merge(Merge(l, new Node(value)), r);
}
public void Erase(T value)
{
EraseAt(LowerBound(value));
}
public void EraseAt(int index)
{
var (l, r1) = Split(_root, index);
var (_, r2) = Split(r1, 1);
_root = Merge(l, r2);
}
public T ElementAt(int index)
{
if (index < 0 || Count(_root) <= index) throw new ArgumentNullException(nameof(index));
var node = _root;
var idx = Count(node) - Count(node.R) - 1;
while (node is { })
{
if (idx == index) return node.Value;
if (idx > index)
{
node = node.L;
idx -= Count(node?.R) + 1;
}
else
{
node = node.R;
idx += Count(node?.L) + 1;
}
}
throw new ArgumentOutOfRangeException(nameof(index));
}
public bool Contains(T value)
{
return Find(value) is { };
}
public int Count() => Count(_root);
public IEnumerator<T> GetEnumerator() => Enumerate(_root).GetEnumerator();
IEnumerator IEnumerable.GetEnumerator() => GetEnumerator();
public int UpperBound(T value) => CommonBound(value, _upperBound);
public int LowerBound(T value) => CommonBound(value, _lowerBound);
public int CommonBound(T value, Compare compare)
{
var node = _root;
if (node is null) return -1;
var bound = Count(node);
var idx = bound - Count(node.R) - 1;
while (node is { })
{
if (compare(node.Value, value))
{
node = node.L;
bound = Math.Min(bound, idx);
idx -= Count(node?.R) + 1;
}
else
{
node = node.R;
idx += Count(node?.L) + 1;
}
}
return bound;
}
private double GetProbability() => _random.NextDouble();
private Node Merge(Node l, Node r)
{
if (l is null || r is null) return l ?? r;
var (n, m) = (Count(l), Count(r));
if ((double)n / (n + m) > GetProbability())
{
l.R = Merge(l.R, r);
return l;
}
else
{
r.L = Merge(l, r.L);
return r;
}
}
private (Node, Node) Split(Node node, int k)
{
if (node is null) return (null, null);
if (k <= Count(node.L))
{
var (l, r) = Split(node.L, k);
node.L = r;
return (l, node);
}
else
{
var (l, r) = Split(node.R, k - Count(node.L) - 1);
node.R = l;
return (node, r);
}
}
private Node Find(T value)
{
var node = _root;
while (node is { })
{
var cmp = _comparison(node.Value, value);
if (cmp > 0) node = node.L;
else if (cmp < 0) node = node.R;
else break;
}
return node;
}
private static int Count(Node node) => node?.Count ?? 0;
private static IEnumerable<T> Enumerate(Node node = null)
{
if (node is null) yield break;
foreach (var value in Enumerate(node.L)) yield return value;
yield return node.Value;
foreach (var value in Enumerate(node.R)) yield return value;
}
private class Node
{
public T Value { get; }
public Node L
{
get => _l;
set
{
_l = value;
UpdateCount();
}
}
public Node R
{
get => _r;
set
{
_r = value;
UpdateCount();
}
}
public int Count { get; private set; }
private Node _l;
private Node _r;
public Node(T value)
{
Value = value;
Count = 1;
}
private void UpdateCount()
{
Count = (L?.Count ?? 0) + (R?.Count ?? 0) + 1;
}
}
}
問題E
modの性質上、最大でもN回でループすることがわかります。
そのため、答えは(1回のループ中の和 * ループ回数) + (ループに入るまでの和 + ループの端数の和)で求めることができます。
実装としては、idxのときの合計値と、idxの時にAの値を参照したことを保持しながら順にみていきます。
一度見たことがあるAを参照する場合、現在の合計値 - 1度目のidxの合計値から1回のループ中の和がわかり、2度目のidx - 1度目のidxからループの長さが求まり、(K - 1度目のidx) / ループの長さでループの回数がわかるので、(1回のループ中の和 * ループ回数)を求めることができます。
また、(K - 1度目のidx) % ループの長さでループの端数となる残りのidxを求めることができ、一度目のidx + 残りのidxのときの合計値をみることで、(ループに入るまでの和 + ループの端数の和)を求めることができます。
public static void Solve()
{
var (N, K) = Scanner.Scan<int, long>();
var A = Scanner.ScanEnumerable<long>().ToArray();
var dict = new Dictionary<int, int>();
var steps = new List<long>();
int F(long x) => (int)(x % N);
var current = 0L;
for (var i = 0; i < K; i++)
{
var x = F(current);
if (dict.ContainsKey(x))
{
var noloop = dict[x];
var loop = i - dict[x];
var div = (K - noloop) / loop;
current = (current - steps[noloop]) * div;
var mod = (int)((K - noloop) % loop);
if (mod < 0) mod += loop;
current += steps[noloop + mod];
break;
}
dict[x] = i;
steps.Add(current);
current += A[x];
}
Console.WriteLine(current);
}