はじめに
AtCoder Beginner Contest 281の復習記事です。
記事におけるScannerクラスは、自作の入力クラスです。
コンテスト
https://atcoder.jp/contests/abc281
問題A
生成すべき非負整数は、0,1,2,...,NのN+1個の整数を逆順に表示したものとなります。
やりやすい方法で解きましょう。
for文でNから0まで逆順に表示する方法
public static void Solve()
{
var N = Scanner.Scan<int>();
for (var i = N; i >= 0; i--)
{
Console.WriteLine(i);
}
}
Enumerable.Rangeで数列を生成して逆順に表示する方法
public static void Solve()
{
var N = Scanner.Scan<int>();
var answer = Enumerable.Range(0, N + 1).Reverse();
Console.WriteLine(string.Join(Environment.NewLine, answer));
}
問題B
文字列Sが条件を満たすかどうか、問題文に与えられた条件を詳細に分割して一つずつ判定していきます。
Sの長さは英大文字+6桁の整数+英大文字の8であるか。Sの先頭の文字は英文字であり、大文字であるか。Sの末尾の文字は英文字であり、大文字であるか。- 英大文字に囲まれた文字列は数値に変換でき、
100000以上999999以下であるか。
全ての条件を満たす場合、答えはYesとなります。
public static void Solve()
{
var S = Scanner.Scan<string>();
var answer = S.Length == 1 + 6 + 1;
answer &= char.IsLetter(S[0]) && char.IsUpper(S[0]);
answer &= char.IsLetter(S[^1]) && char.IsUpper(S[^1]);
if (answer)
{
answer &= int.TryParse(S[1..7], out var val);
answer &= 100000 <= val && val <= 999999;
}
Console.WriteLine(answer ? "Yes" : "No");
}
問題C
i番目の曲までの時間の累積和をとり、i番目にT秒を超えた曲が答えとなる曲であり、Tからi-1番目の曲が終わった時間を引いた秒数が答えとなる時点となります。
public static void Solve()
{
var (N, T) = Scanner.Scan<int, long>();
var A = Scanner.ScanEnumerable<long>().ToArray();
var cum = new long[N + 1];
for (var i = 0; i < N; i++)
{
cum[i + 1] = cum[i] + A[i];
}
T %= cum[N];
var num = LowerBound(cum, T);
var time = T - cum[Math.Max(0, num - 1)];
Console.WriteLine($"{num} {time}");
}
問題D
dp[i][k][d]:=i番目の項までみたときにk項使い、和の余りがdのときの最大値とした動的計画法を解きます。
遷移として、uを遷移前の和の余り、v=(u+A[i])%Dを遷移後の和の余りとしたとき、
i番目の項を使わない場合:dp[i+1][k][u] := Max(dp[i+1][k][u], dp[i][k][u])i番目の項を使う場合 (k<K):dp[i+1][k][v] := Max(dp[i+1][k+1][v], dp[i][k][u]+A[i])
N番目の項まで見たときにK項使い、和の余りが0の時の最大値が答えとなります。
public static void Solve()
{
var (N, K, D) = Scanner.Scan<int, int, int>();
var A = Scanner.ScanEnumerable<long>().ToArray();
var dp = new long[N + 1, K + 1, D];
const long inf = (long)1e18;
for (var i = 0; i <= N; i++)
{
for (var k = 0; k <= K; k++)
{
for (var d = 0; d < D; d++)
{
dp[i, k, d] = -inf;
}
}
}
dp[0, 0, 0] = 0;
for (var i = 0; i < N; i++)
{
for (var k = 0; k <= K; k++)
{
for (var u = 0; u < D; u++)
{
var v = (u + A[i]) % D;
dp[i + 1, k, u] = Math.Max(dp[i + 1, k, u], dp[i, k, u]);
if (k + 1 <= K)
{
dp[i + 1, k + 1, v] = Math.Max(dp[i + 1, k + 1, v], dp[i, k, u] + A[i]);
}
}
}
}
var answer = dp[N, K, 0] < 0 ? -1 : dp[N, K, 0];
Console.WriteLine(answer);
}
問題E
各iについて、毎回配列をソートしてしまうと、全体の時間計算量がO((N-M+1)(NlogN+K))となり実行時間制限に間に合いません。
そこで、順序付けできる多重集合のデータ構造を使い、各iにおける値の集合を管理しながら昇順K個の総和を計算していきます。
i==1について、集合にはM項目までの値があり、総和はM項までの昇順K個の総和となります。
i==2について、i==1の総和からA[1]または集合のうちK番目の値を引き、集合からA[1]を削除します。
また、A[2+M]を集合に追加し、A[2+M]または集合のうちK番目の値を総和に足します。
i>2についても同様の操作を行うことで、各iについての総和を時間計算量O(logM)で求めることができ、全体の時間計算量O((N-M+1)logM)で求めることができます。
C#の標準ライブラリでは、多重集合を扱うクラスが存在しないため、多重集合のデータ構造は自前の実装が必要です。
public static void Solve()
{
var (N, M, K) = Scanner.Scan<int, int, int>();
var A = Scanner.ScanEnumerable<long>().ToArray();
var set = new Set<long>(true);
for (var i = 0; i < M; i++)
{
set.Add(A[i]);
}
long sum = 0;
for (var i = 0; i < K; i++)
{
sum += set.ElementAt(i);
}
var answer = new List<long>(N - M + 1) { sum };
for (var i = M; i < N; i++)
{
var x = A[i - M];
sum -= Math.Min(x, set.ElementAt(K - 1));
set.Remove(x);
set.Add(A[i]);
sum += Math.Min(A[i], set.ElementAt(K - 1));
answer.Add(sum);
}
Console.WriteLine(string.Join(" ", answer));
}