はじめに
AtCoder Beginner Contest 267の復習記事です。
記事におけるScannerクラスは、自作の入力クラスです。
コンテスト
https://atcoder.jp/contests/abc267
問題A
与えられる文字列は5通りしかないため、それぞれに対しての答えを求めます。
public static void Solve()
{
var S = Scanner.Scan<string>();
var answer = 0;
if (S == "Monday") answer = 5;
if (S == "Tuesday") answer = 4;
if (S == "Wednesday") answer = 3;
if (S == "Thursday") answer = 2;
if (S == "Friday") answer = 1;
Console.WriteLine(answer);
}
問題B
列ごとの処理を行うため、あらかじめ列ごとにピンが1本でも立っているかをboolで管理できるようにします。
1番ピンがfalseかつ、列Lがtrueかつと列Rがtrueかつ、列Lと列Rの間の列Mがfalseであるときにスプリットになります。
public static void Solve()
{
var S = Scanner.Scan<string>();
var T = new bool[11];
for (var i = 0; i < S.Length; i++)
{
T[i + 1] = S[i] == '1';
}
var col = new bool[7];
col[0] |= T[7];
col[1] |= T[4];
col[2] |= T[8] || T[2];
col[3] |= T[5] || T[1];
col[4] |= T[9] || T[3];
col[5] |= T[6];
col[6] |= T[10];
if (!T[1])
{
for (var l = 0; l < col.Length; l++)
{
for (var r = l + 2; r < col.Length; r++)
{
for (var m = l + 1; m < r; m++)
{
if (col[l] && col[r] && !col[m])
{
Console.WriteLine("Yes");
return;
}
}
}
}
}
Console.WriteLine("No");
}
問題C
長さMの連続部分列の右側の位置Rから位置R+1にずれたとき、求める総和はA[R-M+1..R]の区間和が引かれてA[R]*Mが足されます。
そのため、位置をずらして総和を更新していったときの最大値が答えとなります。
累積和を用いることで時間計算量O(1)で区間和を求めることができ、全体の計算量O(N)で答えを求めることができます。
public static void Solve()
{
var (N, M) = Scanner.Scan<int, int>();
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];
}
var sum = 0L;
for (var i = 0; i < M; i++)
{
sum += (i + 1) * A[i];
}
var answer = sum;
for (var i = 1; i + M <= N; i++)
{
sum -= cum[i + M - 1] - cum[i - 1];
sum += M * A[i + M - 1];
answer = Math.Max(answer, sum);
}
Console.WriteLine(answer);
}
問題D
dp[i][j]:=i番目までみたときにBの要素をj個決めたときの求める和の最大値とした動的計画法を解きます。
これは、i番目の要素を選ばなかったときはMax(dp[i+1][j], dp[i][j])であり、選んだ時はMax(dp[i+1][j+1], dp[i][j]+A[i]*(j+1))の遷移が成り立ちます。
総和が負になることもあるため、dpテーブルを-infのような値で初期化する必要があることに注意が必要です。
public static void Solve()
{
var (N, M) = Scanner.Scan<int, int>();
var A = Scanner.ScanEnumerable<long>().ToArray();
const long inf = (long)1e18;
var dp = new long[N + 1, M + 1];
for (var i = 0; i <= N; i++)
{
for (var j = 0; j <= M; j++)
{
dp[i, j] = -inf;
}
}
dp[0, 0] = 0;
for (var i = 0; i < N; i++)
{
for (var j = 0; j <= M; j++)
{
dp[i + 1, j] = Math.Max(dp[i + 1, j], dp[i, j]);
if (j + 1 <= M) dp[i + 1, j + 1] = Math.Max(dp[i + 1, j + 1], dp[i, j] + A[i] * (j + 1));
}
}
var answer = dp[N, M];
Console.WriteLine(answer);
}
問題E
ある時点で頂点uを消すと、頂点uに接続している頂点vのコストはA[u]減ることになり、その時点での頂点vとコストのペアをPriorityQueueに追加していくことで、頂点xを消すときに必要なコストの最小値を求めることができ、全ての頂点におけるコストの最小値の最大値が答えとなります。
public static void Solve()
{
var (N, M) = Scanner.Scan<int, int>();
var A = Scanner.ScanEnumerable<long>().ToArray();
var G = new List<int>[N].Select(x => new List<int>()).ToArray();
var costs = new long[N];
for (var i = 0; i < M; i++)
{
var (u, v) = Scanner.Scan<int, int>();
u--; v--;
costs[u] += A[v];
costs[v] += A[u];
G[u].Add(v);
G[v].Add(u);
}
var answer = 0L;
var queue = new PriorityQueue<(int U, long C)>((x, y) => x.C.CompareTo(y.C));
for (var i = 0; i < N; i++)
{
queue.Enqueue((i, costs[i]));
}
var used = new bool[N];
while (queue.Count > 0)
{
var (u, c) = queue.Dequeue();
if (used[u]) continue;
used[u] = true;
answer = Math.Max(answer, c);
foreach (var v in G[u])
{
if (used[v]) continue;
costs[v] -= A[u];
queue.Enqueue((v, costs[v]));
}
}
Console.WriteLine(answer);
}