はじめに
AtCoder Beginner Contest 286の復習記事です。
記事におけるScannerクラスは、自作の入力クラスです。
コンテスト
https://atcoder.jp/contests/abc286
問題A
入れ替える数列の個数はM=Q-P(==S-R)個であり、0<=i<MのA[P+i]とA[R+i]を入れ替えたものがBとなります。
public static void Solve()
{
var (N, P, Q, R, S) = Scanner.Scan<int, int, int, int, int>();
P--; R--;
var A = Scanner.ScanEnumerable<int>().ToArray();
var M = Q - P;
for (var i = 0; i < M; i++)
{
(A[P + i], A[R + i]) = (A[R + i], A[P + i]);
}
Console.WriteLine(string.Join(" ", A));
}
問題B
文字列Sのうち、naをnyaに置き換えたものが答えとなるので、stringのReplaceメソッドや、文字を順にみていきnの次にaがある場合、yを追加するといったアルゴリズムで解くことができます。
public static void Solve()
{
var N = Scanner.Scan<int>();
var S = Scanner.Scan<string>();
var T = S.Replace("na", "nya");
Console.WriteLine(T);
}
public static void Solve()
{
var N = Scanner.Scan<int>();
var S = Scanner.Scan<string>();
var builder = new StringBuilder();
for (var i = 0; i < N; i++)
{
builder.Append(S[i]);
if(i + 1 < N && S[i] == 'n' && S[i + 1] == 'a')
{
builder.Append('y');
}
}
var T = builder.ToString();
Console.WriteLine(T);
}
問題C
愚直に文字列をシフトして、シフトした文字列が回文かどうかを判定することで、時間計算量O(N^2)で答えを求めることができます。
public static void Solve()
{
var (N, A, B) = Scanner.Scan<int, long, long>();
var S = Scanner.Scan<string>();
const long inf = (long)1e18;
var answer = inf;
for (var i = 0; i < N; i++)
{
if (A * i >= answer) continue;
var sum = A * i;
var T = Shift<char>(S, -i);
for (var j = 0; j * 2 < N; j++)
{
if (T[j] == T[N - 1 - j]) continue;
sum += B;
}
answer = Math.Min(answer, sum);
}
Console.WriteLine(answer);
}
public static T[] Shift<T>(ReadOnlySpan<T> source, int shift)
{
shift = (shift + source.Length) % source.Length;
if (shift == 0) return source.ToArray();
var result = new T[source.Length];
source[^shift..].CopyTo(result.AsSpan(..shift));
source[..^shift].CopyTo(result.AsSpan(shift..));
return result;
}
問題D
次のような動的計画法を解きます。
dp[i][j] := i番目まで見たときちょうどj円にする組み合わせを作ることができるか
そして、状態は次のような遷移が可能です。
dp[i+1][j+a*k] |= dp[i][j] (0<=j<=X, 0<=k<=b)
時間計算量はO(NX^2)で求めることができます。
public static void Solve()
{
var (N, X) = Scanner.Scan<int, int>();
var dp = new bool[N + 1, X + 1];
dp[0, 0] = true;
for (var i = 0; i < N; i++)
{
var (a, b) = Scanner.Scan<int, int>();
for (var j = 0; j <= X; j++)
{
if (!dp[i, j]) continue;
for (var k = 0; k <= b && j + a * k <= X; k++)
{
dp[i + 1, j + a * k] |= dp[i, j];
}
}
}
var answer = dp[N, X];
Console.WriteLine(answer ? "Yes" : "No");
}
問題E
都市uから都市vに移動すると、お土産の価値の合計はA[u]+A[v]になります。
また、都市uから都市kを経由して都市vに移動すると、お土産の価値の合計は、A[u]+A[k]+A[v]ですが、これは都市uから都市kに移動したときのお土産の価値(A[u]+A[k])と都市kから都市vに移動したときのお土産の価値(A[k]+A[v])から、A[k]を引いたもの、つまり(A[u]+A[k])+(A[k]+A[v])-A[k]として求めることができます。
この法則を利用し、ワーシャルフロイド法で使う直行便の数が最小となる時のお土産の価値の総和を時間計算量O(N^3)であらかじめ求めておくことで、クエリ当たり時間計算量O(1)で答えることができるようになります。
C[i][j]をiからjに移動するときに使う直行便の数、V[i][j]をiからjに移動するときのお土産の価値としたとき、kを経由したC[i][j]とV[i][j]の更新は、c=C[i][k]+C[k][j]、v=V[i][k]+V[k][j]-A[k]としたとき、次のようになります。
c == C[i][j]のとき、V[i][j]=Max(V[i][j], v)c < C[i][j]のとき、C[i][j]=c、V[i][j]=v
public static void Solve()
{
var N = Scanner.Scan<int>();
var A = Scanner.ScanEnumerable<long>().ToArray();
var G = new bool[N][];
for (var i = 0; i < N; i++)
{
var S = Scanner.Scan<string>();
G[i] = S.Select(x => x == 'Y').ToArray();
}
const long inf = (long)1e18;
var values = new long[N, N];
var counts = new long[N, N];
for (var i = 0; i < N; i++)
{
for (var j = 0; j < N; j++)
{
values[i, j] = G[i][j] ? A[i] + A[j] : -inf;
counts[i, j] = G[i][j] ? 1 : inf;
}
values[i, i] = 0;
counts[i, i] = 0;
}
for (var k = 0; k < N; k++)
{
for (var i = 0; i < N; i++)
{
for (var j = 0; j < N; j++)
{
var count = counts[i, k] + counts[k, j];
var value = values[i, k] + values[k, j] - A[k];
if (count == counts[i, j])
{
values[i, j] = Math.Max(values[i, j], value);
}
else if (count < counts[i, j])
{
counts[i, j] = count;
values[i, j] = value;
}
}
}
}
var Q = Scanner.Scan<int>();
while (Q-- > 0)
{
var (u, v) = Scanner.Scan<int, int>();
u--; v--;
var count = counts[u, v];
var value = values[u, v];
if (count == inf)
{
Console.WriteLine("Impossible");
}
else
{
Console.WriteLine($"{count} {value}");
}
}
}