はじめに
AtCoder Beginner Contest 318の復習記事です。
記事における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/abc318
問題A
N日間のうちM日目以降の期間はN-M日間であり、この期間にFloor(N-M)/P回満月を見ることができます。
これにM日目を加えた、Floor(N-M)/P+1が答えとなります。
N-Mが負数になることがあるので注意が必要です。
public static void Solve()
{
var (N, M, P) = Scanner.Scan<int, int, int>();
var answer = (N - M + P) / P;
Console.WriteLine(answer);
}
問題B
シートは最大でも0<=x<=100かつ0<=y<=100なので、100*100のグリッドを用意し、その領域がシートで覆われているかを判定します。
public static void Solve()
{
var N = Scanner.Scan<int>();
var H = 100;
var W = 100;
var G = new bool[H + 1, W + 1];
for (var i = 0; i < N; i++)
{
var (a, b, c, d) = Scanner.Scan<int, int, int, int>();
for (var x = a; x < b; x++)
{
for (var y = c; y < d; y++)
{
G[x, y] = true;
}
}
}
var answer = 0;
for (var i = 0; i <= H; i++)
{
for (var j = 0; j <= W; j++)
{
if (G[i, j]) answer++;
}
}
Console.WriteLine(answer);
}
問題C
周遊パスは好きな日に使うことができるので、Fをソートしても問題ありません。
次のような動的計画法を解きます。
dp[i] := i日間の旅行でかかる最小金額
遷移は次のようになります。
// i日目の運賃を通常料金で払うとき
dp[i+1] = Min(dp[i+1], dp[i]+F[i])
// i日目の運賃を周遊パスで払うとき
dp[i+D] = Min(dp[i+D], dp[i]+P)
i+DがNより大きい場合はNにまとめることができ、dp[N]が答えとなります。
public static void Solve()
{
var (N, D, P) = Scanner.Scan<int, int, long>();
var F = Scanner.ScanEnumerable<long>().ToArray();
Array.Sort(F);
var cum = new long[N + 1];
const long Inf = (long)1e18;
Array.Fill(cum, Inf);
cum[0] = 0;
for (var i = 0; i < N; i++)
{
cum[i + 1] = Math.Min(cum[i + 1], cum[i] + F[i]);
var x = Math.Min(i + D, N);
cum[x] = Math.Min(cum[x], cum[i] + P);
}
var answer = cum[N];
Console.WriteLine(answer);
}
問題D
次のような動的計画法を解きます。
dp[s] := 既に選んだ頂点集合がsのときの選んだ重みの総和の最大値
遷移は次のようになります。
i番目の頂点とj番目の頂点がsに含まれていないとき、sにiとjを含んだ頂点集合をtとする。
dp[t] = Max(dp[t], dp[s]+D[i][j])
全ての頂点集合のうち、総和の最大値が答えとなります。
public static void Solve()
{
var N = Scanner.Scan<int>();
var D = new long[N, N];
for (var i = 0; i < N - 1; i++)
{
var d = Scanner.ScanEnumerable<int>().ToArray();
for (var j = 0; j < d.Length; j++)
{
D[i, i + j + 1] = d[j];
}
}
var dp = new long[1 << N];
dp[0] = 0;
for (var s = 0; s < 1 << N; s++)
{
for (var i = 0; i < N; i++)
{
for (var j = i + 1; j < N; j++)
{
if ((s >> i & 1) == 1 || (s >> j & 1) == 1) continue;
var t = s | (1 << i) | (1 << j);
dp[t] = Math.Max(dp[t], dp[s] + D[i, j]);
}
}
}
long answer = 0;
for (var s = 0; s < 1 << N; s++)
{
answer = Math.Max(answer, dp[s]);
}
Console.WriteLine(answer);
}
問題E
L[x]を現在左側にあるxの個数、R[x]を現在右側にあるxの個数とします。
jを固定したとき、jに対して条件を満たすi,kの組み合わせの個数は、1<=y<=Nかつy!=A[j]のL[y]*R[y]の総和になります。
これにより、各jに対して時間計算量O(N)で組み合わせの個数を求めることができますが、全体時間計算量がO(N^2)になり、実行時間制限に間に合いません。
そこで、jを1つずらしたとき、L[A[j]]が1つ増え、R[A[j]]が1つ減ることから、組み合わせの個数を累積和として管理し、各jにおける差分のみを計算することで、各jに対して時間計算量O(1)で組み合わせの個数を求めることができるようになり、全体時間計算量O(N)で答えを求めることができます。
public static void Solve()
{
var N = Scanner.Scan<int>();
var A = Scanner.ScanEnumerable<int>().ToArray();
var L = new long[N + 1];
var R = new long[N + 1];
foreach (var a in A) R[a]++;
long answer = 0;
long cum = 0;
foreach (var a in A)
{
cum -= L[a] * R[a];
answer += cum;
R[a]--;
L[a]++;
cum += L[a] * R[a];
}
Console.WriteLine(answer);
}