はじめに
AtCoder Beginner Contest 331の復習記事です。
記事における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/abc331
問題A
次の日を求めるので、dを+1します。
このとき、d>Dならば、次の月になるので、mを+1してdが1になります。
このとき、m>Mならば、次の年になるので、yを+1してmが1になります。
例
public static void Solve()
{
var (M, D) = Scanner.Scan<int, int>();
var (y, m, d) = Scanner.Scan<int, int, int>();
d++;
if (d > D)
{
d = 1;
m++;
}
if (m > M)
{
m = 1;
y++;
}
Console.WriteLine($"{y} {m} {d}");
}
問題B
サイズごとの卵のパックを全探索します。
例
public static void Solve()
{
var (N, S, M, L) = Scanner.Scan<int, int, int, int>();
const long Inf = 1 << 60;
var answer = Inf;
for (var s = 0; s <= (100 + 5) / 6; s++)
{
for (var m = 0; m <= (100 + 7) / 8; m++)
{
for (var l = 0; l <= (100 + 11) / 12; l++)
{
if (s * 6 + m * 8 + l * 12 >= N)
{
answer = Math.Min(answer, s * S + m * M + l * L);
}
}
}
}
Console.WriteLine(answer);
}
次のような動的計画法で解くこともできます。
dp[i] := i個の卵を買うときの最小の金額
dp[i+6] = Min(dp[i+6], dp[i]+S);
dp[i+8] = Min(dp[i+8], dp[i]+M);
dp[i+12] = Min(dp[i+12], dp[i]+L);
例
public static void Solve()
{
var (N, S, M, L) = Scanner.Scan<int, int, int, int>();
const int Inf = 1 << 30;
var dp = new long[N + 1];
Array.Fill(dp, Inf);
dp[0] = 0;
var X = new (int, long)[] { (6, S), (8, M), (12, L) };
for (var i = 0; i < N; i++)
{
foreach (var (c, v) in X)
{
var nc = Math.Min(N, i + c);
dp[nc] = Math.Min(dp[nc], dp[i] + v);
}
}
var answer = dp[N];
Console.WriteLine(answer);
}
問題C
各A[i]についてA[i]より大きな要素全ての和を愚直に探索してしまうと、A[i]ごとに時間計算量O(N)、全体で時間計算量O(N^2)になり、実行時間制限に間に合いません。
そこで、各A[i]に対して高速に答えを求められるようにする必要があります。
Aを昇順ソートしたものをB、数列Bのi番目までの累積和をcum[i]、BにおけるA[i]が出現する最も右側の位置をpos[A[i]]とします。
A[i]より大きい要素全ての和は、数列全体の和-A[i]以下の要素全ての和で求めることができることから、cum[N]-cum[pos[A[i]]]で求めることができるようになります。
あらかじめcum[i]を時間計算量O(N)で求めておくことで、以降各iに対して時間計算量O(1)で求めることができるようにします。
また、辞書などのデータ構造やBに対する二部探索を行うことで、pos[A[i]]を時間計算量O(logN)で求めることができるようにします。
そして、各A[i]に対してcum[N]-cum[pos[A[i]]]を求めていくことで、全体時間計算量O(NlogN)で答えを求めることができるようになります。
例
public static void Solve()
{
var N = Scanner.Scan<int>();
var A = Scanner.ScanEnumerable<long>().ToArray();
var B = A.ToArray();
Array.Sort(B);
var pos = new Dictionary<long, int>();
for (var i = 0; i < N; i++)
{
pos[B[i]] = i;
}
var cum = new long[N + 1];
for (var i = 0; i < N; i++)
{
cum[i + 1] = cum[i] + B[i];
}
var answers = new long[N];
for (var i = 0; i < N; i++)
{
answers[i] = cum[N] - cum[pos[A[i]] + 1];
}
Console.WriteLine(string.Join(" ", answers));
}
問題D
N*NマスのパターンをPとします。
Pのi行j列目までのにおける黒の個数を二次元累積和をS[i][j]は次のように求められます。
S[i][j] = S[i-1][j] + S[i][j-1] - S[i-1][j-1] + (P[i][j]が黒?1:0)
S[i][j]を時間計算量O(N^2)で求めておき、各クエリ当たり時間計算量O(1)で答えられるようにしておきます。
クエリa,b,c,dは閉区間H:[a,c], W:[b,d]ですが、計算の都合として半開区間H:[a,c), W:[b,d)とします。
また、a,b,c,dをNで割った余りをam,bm,cm,dmとします。
クエリの長方形領域を3*3の領域に分割すると、領域の{左上|右上|左下|右下}はPの一部を覆い、{左中|右中}はPの行の全てと列の一部を覆い、{上中|下中}はPの行の一部と列の全てを覆い、真中がPの行と列の全てを覆います。
また、｛左|右|上|下|真｝中の領域は、0以上個のPを繰り返します。
行を全て使うものは、縦にhc=((c-a)-(N-am+cm))/N個のPを並べます。
同様に、列を全て使うものは、横にwc=((d-b)-(N-bm+dm))/N個のPを並べます。
よって、各領域は次の範囲を覆います。
| 領域 | 行 | 列 | Pの個数 |
|---|---|---|---|
| 左上 | [am,N) | [bm,N) | 1 |
| 右上 | [am,N) | [0,dm) | 1 |
| 左下 | [0,bm) | [cm,N) | 1 |
| 右下 | [0,0) | [cm,dm) | 1 |
| 左中 | [0,N) | [bm,N) | hc |
| 右中 | [0,N) | [0,dm) | hc |
| 上中 | [am,N) | [0,N) | wc |
| 下中 | [0,cm) | [0,N) | wc |
| 真中 | [0,N) | [0,N) | hc*wc |
よって、各領域のPを覆う範囲にある黒の個数に繰り返すPの個数を掛けたものの総和が答えになります。
例
public static void Solve()
{
var (N, Q) = Scanner.Scan<int, int>();
var P = new char[N][];
for (var i = 0; i < N; i++)
{
P[i] = Scanner.Scan<string>().ToCharArray();
}
var cum = new CumulativeSum2D<long>(N + 10, N + 10);
for (var i = 0; i < N; i++)
{
for (var j = 0; j < N; j++)
{
if (P[i][j] == 'B')
{
cum.Add(i, j, 1);
}
}
}
while (Q-- > 0)
{
var (a, b, c, d) = Scanner.Scan<int, int, int, int>();
c++; d++;
long answer = 0;
var (am, bm, cm, dm) = (a % N, b % N, c % N, d % N);
long hc = ((c - a) - (N - am + cm)) / N;
long wc = ((d - b) - (N - bm + dm)) / N;
answer += cum.Sum(am, bm, N, N); // 左上
answer += cum.Sum(am, 0, N, dm); // 右上
answer += cum.Sum(0, bm, cm, N); // 左下
answer += cum.Sum(0, 0, cm, dm); // 右下
answer += cum.Sum(0, bm, N, N) * hc; // 左中
answer += cum.Sum(0, 0, N, dm) * hc; // 右中
answer += cum.Sum(am, 0, N, N) * wc; // 上中
answer += cum.Sum(0, 0, cm, N) * wc; // 下中
answer += cum.Sum(N, N) * (hc * wc); // 中中
Console.WriteLine(answer);
}
}
public class CumulativeSum2D<T> where T : INumber<T>
{
public int Height { get; }
public int Width { get; }
private readonly T[] _data;
private readonly T[] _sum;
private bool _isUpdated;
public CumulativeSum2D(int height, int width)
{
if (height <= 0) throw new ArgumentOutOfRangeException(nameof(height));
if (width <= 0) throw new ArgumentOutOfRangeException(nameof(width));
Height = height;
Width = width;
_data = new T[height * width];
_sum = new T[(height + 1) * (width + 1)];
}
public void Add(int height, int width, T value)
{
ThrowIfNegative(height);
ThrowIfGreaterThanOrEqual(height, Height);
ThrowIfNegative(width);
ThrowIfGreaterThanOrEqual(width, Width);
_isUpdated = false;
_data[height * Width + width] += value;
}
public void Set(int height, int width, T value)
{
ThrowIfNegative(height);
ThrowIfGreaterThanOrEqual(height, Height);
ThrowIfNegative(width);
ThrowIfGreaterThanOrEqual(width, Width);
_isUpdated = false;
_data[height * Width + width] = value;
}
public T Get(int height, int width)
{
ThrowIfNegative(height);
ThrowIfGreaterThanOrEqual(height, Height);
ThrowIfNegative(width);
ThrowIfGreaterThanOrEqual(width, Width);
return _data[height * Width + width];
}
/// <summary>
/// Calculate a two-dimensional cumulative sum of [0, height), [0, width).
/// </summary>
public T Sum(int height, int width)
{
ThrowIfNegative(height);
ThrowIfGreaterThan(height, Height);
ThrowIfNegative(width);
ThrowIfGreaterThan(width, Width);
if (!_isUpdated) Build();
return _sum[height * (Width + 1) + width];
}
/// <summary>
/// Calculate a two-dimensional cumulative sum of [height1, height2), [width1, width2).
/// </summary>
public T Sum(int height1, int width1, int height2, int width2)
{
ThrowIfGreaterThan(height1, height2);
ThrowIfGreaterThan(width1, width2);
return Sum(height1, width1) + Sum(height2, width2) - Sum(height2, width1) - Sum(height1, width2);
}
private void Build()
{
_isUpdated = true;
var w1 = Width + 1;
_sum[0] = _sum[w1] = _sum[1] = T.Zero;
for (var i = 1; i <= Height; i++)
{
for (var j = 1; j <= Width; j++)
{
_sum[i * w1 + j] =
_sum[i * w1 + (j - 1)]
+ _sum[(i - 1) * w1 + j]
- _sum[(i - 1) * w1 + (j - 1)]
+ _data[(i - 1) * Width + (j - 1)];
}
}
}
private static void ThrowIfNegative(int value)
{
if (value < 0) throw new ArgumentOutOfRangeException(nameof(value));
}
private static void ThrowIfGreaterThan(int value, int other)
{
if (value > other) throw new ArgumentOutOfRangeException(nameof(value));
}
private static void ThrowIfGreaterThanOrEqual(int value, int other)
{
if (value >= other) throw new ArgumentOutOfRangeException(nameof(value));
}
}
問題E
主菜のを固定したとき、その主菜との食べ合わせが悪くない最も価格の高い副菜が、その主菜に対する最も価格が高い定食の組み合わせになります。
その主菜との食べ合わせが悪くない副菜のうち、最も価格が高い副菜以外を組み合わせたところで、最も高い副菜との組み合わせのほうが定食価格が高いので、最も高い副菜以外の走査を打ち切ることができます。
これにより、N種類の主菜と、食べ合わせが悪いL種類の食べ合わせを判定することで答えを求めることができます。
したがって、食べ合わせが悪い主菜と副菜の組み合わせのペアを集合で管理し、Bの価格と番号をペアにしたものを、価格の降順に並べ替え、各Aに対して食べ合わせの判定を行うことで、時間計算量O(MlogM+N+L)で答えを求めることができます。
例
public static void Solve()
{
var (N, M, L) = Scanner.Scan<int, int, int>();
var A = Scanner.ScanEnumerable<long>().ToArray();
var B = Scanner.ScanEnumerable<long>().ToArray();
var set = new HashSet<(int C, int D)>();
for (var i = 0; i < L; i++)
{
var (c, d) = Scanner.Scan<int, int>();
c--; d--;
set.Add((c, d));
}
var C = B.Select((x, i) => (V: x, I: i)).OrderByDescending(x => x.V).ToArray();
long answer = 0;
for (var i = 0; i < N; i++)
{
var (a, ai) = (A[i], i);
for (var j = 0; j < M; j++)
{
var (b, bi) = C[j];
if (set.Contains((ai, bi))) continue;
answer = Math.Max(answer, a + b);
break;
}
}
Console.WriteLine(answer);
}