はじめに
AtCoder Beginner Contest 263の復習記事です。
記事におけるScannerクラスは、自作の入力クラスです。
コンテスト
https://atcoder.jp/contests/abc263
問題A
数字ごとの枚数を数え上げ、数値iの枚数が3と数値jの枚数が2となるiとjが存在するかを全探索します。
public static void Solve()
{
var A = Scanner.ScanEnumerable<int>().ToArray();
var count = new int[14];
foreach (var a in A) count[a]++;
for (var i = 1; i <= 13; i++)
{
for (var j = 1; j <= 13; j++)
{
if (count[i] == 3 && count[j] == 2)
{
Console.WriteLine("Yes");
return;
}
}
}
Console.WriteLine("No");
}
数字をソートして、A[0]==A[2] && A[3]==A[4] || A[0]==A[1] && A[2]==A[4]で求める方法もあります。
問題B
現在の値が1になるまで、現在の値を更新しながら回数を数え上げます。
public static void Solve()
{
var N = Scanner.Scan<int>();
var P = Scanner.ScanEnumerable<int>().ToArray();
var curr = N;
var answer = 0;
while (curr != 1)
{
curr = P[curr - 2];
answer++;
}
Console.WriteLine(answer);
}
問題C
現在の配列、深さ、ひとつ前の値を保持して深さ優先探索を行います。
public static void Solve()
{
var (N, M) = Scanner.Scan<int, int>();
void Dfs(int[] buffer, int idx, int prev)
{
if (idx == N)
{
Console.WriteLine(string.Join(" ", buffer));
return;
}
for (var i = prev + 1; i <= M; i++)
{
buffer[idx] = i;
Dfs(buffer, idx + 1, i);
}
}
var buffer = new int[N];
Dfs(buffer, 0, 0);
}
問題D
xとyを全探索してしまうと、時間計算量がO(N^2)となってしまい、実行時間制限内に答えを求めることができません。
数列を二つに分けたとき、数列の左側の合計と右側の合計は数列全体の合計になることに注目します。
そこで、左からx番目までの累積和を考えたとき、x番目の累積和になりえるものはx-1番目までの累積和+A[x]またはL*xであり、それらの最小値を左から順に調べることで、x番目までの累積和の最小値を求めることができます。
同様に、右からy番目までの累積和の最小値を求め、左からi番目までの累積和と右からN-i番目の累積和の和の最小を求めることで、時間計算量O(N)で答えを求めることができます。
public static void Solve()
{
var (N, L, R) = Scanner.Scan<int, long, long>();
var A = Scanner.ScanEnumerable<long>().ToArray();
const long inf = (long)1e18;
var cumL = new long[N + 1];
var cumR = new long[N + 1];
for (var i = 0; i < N; i++)
{
cumL[i + 1] = Math.Min(cumL[i] + A[i], L * (i + 1));
cumR[N - 1 - i] = Math.Min(cumR[N - i] + A[N - 1 - i], R * (i + 1));
}
var answer = inf;
for (var i = 0; i <= N; i++)
{
answer = Math.Min(answer, cumL[i] + cumR[i]);
}
Console.WriteLine(answer);
}
問題E
dp[i]:=マスiからマスNにたどり着くまでにサイコロを振る回数の期待値とした動的計画法を行います。
dp[i] = (dp[i..i+A[i]] + 1) / (A[i] + 1) #(次の状態の期待値+1回)/種類数
=> dp[i] = dp[i] / (A[i] + 1) + (dp[(i+1)..(i+A[i])] + 1) / (A[i] + 1) #右辺に左辺が入っているので式変形
=> dp[i] * A[i] / (A[i] + 1) = (dp[(i+1)..(i+A[i])] + 1) / (A[i] + 1)
=> dp[i] = (dp[(i+1)..(i+A[i])] + A[i] + 1) / A[i]
i+1からi+A[i]の累積和をSegmentTreeのようなデータ構造で管理し、クエリ当たりO(logN)で累積和を求めることで、全体でO(NlogN)で答えを求めることができます。
public static void Solve()
{
var N = Scanner.Scan<int>();
var A = Scanner.ScanEnumerable<int>().ToArray();
var dp = new SegmentTree<ModuloInteger>(N + 1, new Oracle());
for (var i = N - 1; i > 0; i--)
{
var sum = dp.Query(i, i + A[i - 1] + 1);
sum += A[i - 1] + 1;
sum /= A[i - 1];
dp.Set(i, sum);
}
var answer = dp.Get(1);
Console.WriteLine(answer);
}
SegmentTreeは以下のようなものを使いました。
public class Oracle : IOracle<ModuloInteger>
{
public ModuloInteger MonoidIdentity => (ModuloInteger)0;
public ModuloInteger Operate(ModuloInteger a, ModuloInteger b)
{
return a + b;
}
}
public interface IOracle<TMonoid>
{
TMonoid MonoidIdentity { 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.MonoidIdentity);
}
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.MonoidIdentity, _oracle.MonoidIdentity);
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.MonoidIdentity)) throw new ArgumentException(nameof(predicate));
if (left == Length) return Length;
left += _dataSize;
var sm = _oracle.MonoidIdentity;
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.MonoidIdentity)) throw new ArgumentException(nameof(predicate));
if (right == 0) return 0;
right += _dataSize;
var sm = _oracle.MonoidIdentity;
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]);
}