はじめに
AtCoder Beginner Contest 278の復習記事です。
記事におけるScannerクラスは、自作の入力クラスです。
コンテスト
https://atcoder.jp/contests/abc278
問題A
0で初期化した長さNの配列に先頭からA[i+K]の値をN-K回代入することで、答えを求めることができます。
public static void Solve()
{
var (N, K) = Scanner.Scan<int, int>();
var A = Scanner.ScanEnumerable<int>().ToArray();
var B = new int[N];
for (var i = 0; i < N - K; i++)
{
B[i] = A[i + K];
}
Console.WriteLine(string.Join(" ", B));
}
問題B
見間違えやすい時刻は、元の時刻のAB:CDとなる時刻であり、ABは時の10の位と分の10の位の値、CDは時の1の位と分の1の位の値になり、0<=AB<24かつ0<=AB<60であることが必要です。
順に時刻をみていき、条件を満たす時刻が答えとなります。
h=23, m=59のときなど、00 00が答えとなることに注意が必要です。
public static void Solve()
{
var (H, M) = Scanner.Scan<int, int>();
for (var h = H; h < 24; h++)
{
for (var m = 0; m < 60; m++)
{
if (h == H && m < M) continue;
var ab = h / 10 * 10 + m / 10;
var cd = h % 10 * 10 + m % 10;
if (ab < 24 && cd < 60)
{
Console.WriteLine($"{h} {m}");
return;
}
}
}
Console.WriteLine("0 0");
}
問題C
ユーザがフォローしている人の集合を辞書で管理し、t==1,2のときは集合を更新、t==3のときはそれぞれのユーザがフォローしている人の集合に存在しているかを判定します。
public static void Solve()
{
var (N, Q) = Scanner.Scan<int, int>();
var dict = new Dictionary<int, HashSet<int>>();
while (Q-- > 0)
{
var (t, a, b) = Scanner.Scan<int, int, int>();
if (!dict.ContainsKey(a)) dict[a] = new HashSet<int>();
if (!dict.ContainsKey(b)) dict[b] = new HashSet<int>();
if (t == 1)
{
dict[a].Add(b);
}
else if (t == 2)
{
dict[a].Remove(b);
}
else
{
var answer = dict[a].Contains(b) && dict[b].Contains(a);
Console.WriteLine(answer ? "Yes" : "No");
}
}
}
問題D
クエリごとに配列のすべての値を更新してしまうと、時間計算量がO(N^2)になり、実行時間制限に間に合いません。
クエリの形式が1における最新の全体更新の時間と値、数列Aのi番目の値が最後に更新された時間を管理し、クエリの形式が2か3のときにi番目の更新された時間が最新の全体更新の時間よりも前ならば、i番目の値を最新の全体更新の値に変更してから処理を行うことで、時間計算量O(N+Q)で答えを求めることができます。
区間変更区間更新が可能な遅延セグメント木などのデータ構造を用いてクエリごとに値を更新することでも、時間計算量O(NlogN)で答えを求めることができます。
public static void Solve()
{
var N = Scanner.Scan<int>();
var A = Scanner.ScanEnumerable<long>().ToArray();
var Q = Scanner.Scan<int>();
var latest = (T: -1, X: 0);
var updated = new int[N];
Array.Fill(updated, -1);
void Update(int i, int x)
{
if (updated[i] < latest.T) A[i] = latest.X;
}
for (var t = 0; t < Q; t++)
{
var query = Scanner.ScanEnumerable<int>().ToArray();
var q = query[0];
if (q == 1)
{
var x = query[1];
latest = (t, x);
}
else if (q == 2)
{
var (i, x) = (query[1] - 1, query[2]);
Update(i);
A[i] += x;
updated[i] = t;
}
else
{
var i = query[1] - 1;
Update(i);
Console.WriteLine(A[i]);
}
}
}
問題E
愚直に範囲にある数を計算してしまうと、時間計算量がO(H^2W^2)となり実行時間制限に間に合いません。
そこで、マスに書かれている値cごとの二次元累積和を求めておくと、マス目全体のcの数と黒く塗りつぶした部分のcの数を引くことで、塗りつぶされていないマスに書かれているcの数を数え上げることができます。
これにより、二次元累積和の構築には時間計算量O(HW)がかかり、cの数え上げには時間計算量O(1)で求めることができます。
そして、各(k,l)ごとにN種類のcの数を求めることになるので、全体計算量O(HW+HWN)で求めることができます。
public static void Solve()
{
var (H, W, N, h, w) = Scanner.Scan<int, int, int, int, int>();
var A = new int[H][];
for (var i = 0; i < H; i++)
{
A[i] = Scanner.ScanEnumerable<int>().ToArray();
}
var cum = new CumulativeSum2D[N].Select(_ => new CumulativeSum2D(H, W)).ToArray();
for (var i = 0; i < H; i++)
{
for (var j = 0; j < W; j++)
{
var a = A[i][j] - 1;
cum[a].Add(i, j, 1);
}
}
var answer = new int[H - h + 1].Select(_ => new int[W - w + 1]).ToArray();
for (var i = 0; i < H - h + 1; i++)
{
for (var j = 0; j < W - w + 1; j++)
{
var sum = 0;
for (var k = 0; k < N; k++)
{
var all = cum[k].Sum(H, W);
var blak = cum[k].Sum(i, j, i + h, j + w);
if (all - blak > 0) sum++;
}
answer[i][j] = sum;
}
}
Printer.Print2D(answer, " ");
}
public class CumulativeSum2D
{
public int Height { get; }
public int Width { get; }
private readonly long[] _data;
private readonly long[] _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 long[height * width];
_sum = new long[(height + 1) * (width + 1)];
}
public void Add(int height, int width, long value)
{
if (height < 0 || Height <= height) throw new ArgumentOutOfRangeException(nameof(height));
if (width < 0 || Width <= width) throw new ArgumentOutOfRangeException(nameof(width));
_isUpdated = false;
_data[height * Width + width] += value;
}
public void Set(int height, int width, long value)
{
if (height < 0 || Height <= height) throw new ArgumentOutOfRangeException(nameof(height));
if (width < 0 || Width <= width) throw new ArgumentOutOfRangeException(nameof(width));
_isUpdated = false;
_data[height * Width + width] = value;
}
public long Get(int height, int width)
{
if (height < 0 || Height <= height) throw new ArgumentOutOfRangeException(nameof(height));
if (width < 0 || Width <= width) throw new ArgumentOutOfRangeException(nameof(width));
return _data[height * Width + width];
}
public long Sum(int height, int width)
{
if (height < 0 || Height < height) throw new ArgumentOutOfRangeException(nameof(height));
if (width < 0 || Width < width) throw new ArgumentOutOfRangeException(nameof(width));
if (!_isUpdated) Build();
return _sum[height * (Width + 1) + width];
}
public long Sum(int height1, int width1, int height2, int width2)
{
if (height1 < 0 || Height < height1) throw new ArgumentOutOfRangeException(nameof(height1));
if (width1 < 0 || Width < width1) throw new ArgumentOutOfRangeException(nameof(width1));
if (height2 < 0 || Height < height2) throw new ArgumentOutOfRangeException(nameof(height2));
if (width2 < 0 || Width < width2) throw new ArgumentOutOfRangeException(nameof(width2));
if (!_isUpdated) Build();
var w1 = Width + 1;
return _sum[height1 * w1 + width1]
+ _sum[height2 * w1 + width2]
- _sum[height2 * w1 + width1]
- _sum[height1 * w1 + width2];
}
private void Build()
{
_isUpdated = true;
var w1 = Width + 1;
_sum[0] = _sum[w1] = _sum[1] = 0;
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)];
}
}