はじめに
AtCoder Beginner Contest 321の復習記事です。
記事における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/abc321
問題A
Nを文字列としてみたとき、全ての1<=i<=N-1においてN[i]>N[i+1]が成り立つものが321-like Numberになります。
public static void Solve()
{
var N = Scanner.Scan<string>();
var answer = true;
for (var i = 0; i + 1 < N.Length; i++)
{
answer &= N[i] > N[i + 1];
}
Console.WriteLine(answer ? "Yes" : "No");
}
問題B
最後にk点取ると固定したときの最終結果がX以上になるkを全探索します。
あらかじめ、N-1試合の合計スコア(sum)、最低スコア(min)、最高スコア(max)を計算しておくと、最終試験でk点とった場合、最終結果はsum + k - Min(min,k) - Max(max,k)で求めることができます。
public static void Solve()
{
var (N, X) = Scanner.Scan<int, int>();
var A = Scanner.ScanEnumerable<int>().ToArray();
var min = A.Min();
var max = A.Max();
var sum = A.Sum();
const int Inf = 1 << 30;
var answer = Inf;
for (var k = 0; k <= 100; k++)
{
var mmin = Math.Min(min, k);
var mmax = Math.Max(max, k);
var x = sum + k - mmin - mmax;
if (x >= X)
{
answer = Math.Min(answer, k);
}
}
if (answer == Inf) answer = -1;
Console.WriteLine(answer);
}
問題C
321-like Numberの各桁に同じ数字が現れることはないため、0から9の数字をそれぞれ使う/使わないとしたときに、使う数字のみを降順に並べたものが321-like Numberになり得ます。
このことから、それぞれの数字を使う/使わないとする組み合わせ2^10-1通りをbit全探索し、全ての321-like Numberを列挙してソートすることで、K番目の値を得ることができます。
public static void Solve()
{
var K = Scanner.Scan<int>();
var S = new List<long>();
for (var s = 1; s < 1 << 10; s++)
{
var list = new List<int>();
for (var i = 0; i < 10; i++)
{
if ((s >> i & 1) == 1) list.Add(i);
}
list.Sort();
list.Reverse();
S.Add(long.Parse(string.Join("", list)));
}
S.Sort();
var answer = S[K];
Console.WriteLine(answer);
}
問題D
ある主菜A[i]を固定したとき、副菜Bのうち価格がP-A[i]以上のものは価格がPとなることから、BのうちP-A[i]以上のものとP-A[i]より小さいもので分けて考えることができます。
P-A[i]以上のものの個数をXとしたとき、P-A[i]以上のものの価格の総和はM*Pになります。
P-A[i]より小さいものの個数はM-Xとなり、P-A[i]より小さいものの価格和をSとすると、P-A[i]より小さいものの価格の総和はA[i]*(M-X)+Sとなります。
Bをあらかじめソートしておき、累積和を求めておくことで、各A[i]ごとにBのうちP-A[i]以上の個数を時間計算量O(logM)で求めることができ、累積和からP-A[i]より小さいものの価格和を時間計算量O(1)で求めることができます。
よって、全体時間計算量O(MlogM + NlogM)で答えを求めることができます。
public static void Solve()
{
var (N, M, P) = Scanner.Scan<int, int, long>();
var A = Scanner.ScanEnumerable<long>().ToArray();
var B = Scanner.ScanEnumerable<long>().ToArray();
Array.Sort(B);
var cumB = new long[M + 1];
for (var i = 0; i < M; i++)
{
cumB[i + 1] = cumB[i] + B[i];
}
long answer = 0;
for (var i = 0; i < N; i++)
{
var lb = LowerBound(B, Math.Max(0, P - A[i]));
var x = A[i] * lb + cumB[lb];
var y = (M - lb) * P;
answer += x + y;
}
Console.WriteLine(answer);
}
public static int LowerBound<T>(List<T> source, T key) where T : IComparable<T>
=> LowerBound(System.Runtime.InteropServices.CollectionsMarshal.AsSpan(source), key);
public static int LowerBound<T>(ReadOnlySpan<T> source, T key) where T : IComparable<T>
{
var (l, r) = (-1, source.Length);
while (r - l > 1)
{
var m = l + (r - l) / 2;
if (source[m].CompareTo(key) >= 0) r = m;
else l = m;
}
return r;
}
問題E
まだ解けていません。
問題F
次のような動的計画法を解きます。
dp[s] := 現在のクエリまでみたとき、総和がsとなる組み合わせの個数
遷移は次のようになります。
if op == '+'
dp[j] += dp[i][j-x] (j=K,K-1,..,x+1,x)
if op == '-'
dp[j] -= dp[i][j-x] (j=x,x+1,..,K-1,K)
public static void Solve()
{
var (Q, K) = Scanner.Scan<int, int>();
var dp = new mint[K + 1];
dp[0] = 1;
for (var i = 0; i < Q; i++)
{
var (op, x) = Scanner.Scan<char, int>();
if (op == '+')
{
for (var j = K; j >= x; j--)
{
dp[j] += dp[j - x];
}
}
else
{
for (var j = x; j <= K; j++)
{
dp[j] -= dp[j - x];
}
}
var answer = dp[K];
Console.WriteLine(answer);
}
}