はじめに
AtCoder Beginner Contest 327の復習記事です。
記事における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/abc327
問題A
aとbが隣接するということは、S[i]がaかつS[i+1]がbとなる箇所がある、または、S[i]がbかつS[i+1]がaとなる箇所がある必要があるため、そのようなiを全探索します。
例
public static void Solve()
{
var N = Scanner.Scan<int>();
var S = Scanner.Scan<string>();
var answer = false;
for (var i = 0; i + 1 < N; i++)
{
answer |= S[i] == 'a' && S[i + 1] == 'b';
answer |= S[i] == 'b' && S[i + 1] == 'a';
}
Console.WriteLine(answer ? "Yes" : "No");
}
問題B
Aを全探索します。
符号なし64bit整数型で表現できる最大の数は、2^64==2^(4*16)==2^4*2^16==16^16であり、これはBの上限となる10^18未満となります。
よってAの上限を15として探索することで、オーバーフローを考えずに答えを求めることができます。
また、x^xは1にxをx回掛けることで求めることができ、xをx回掛けるまでにBを超える場合は、そのx以上の数値はBを超えるため答えが存在しません。
つまり、x^y<=B (0<=y<x)のとき、x^(y+1)<=Bであるためには、x^y<=B/xである必要があります。
よって、x^y>B/xの場合は、x以上の値にはx^x==Bとなるxは存在しないことが分かります。
このことから、探索の上限が思いつかなくても、計算途中でBを超える場合に探索を打ち切ることで、符号付き64bit整数型を使った探索を行ったとしてもオーバーフローを起こさずに答えを求めることができます。
例
public static void Solve()
{
var B = Scanner.Scan<long>();
for (long i = 1; i <= 20; i++)
{
long v = 1;
for (var j = 0; j < i; j++)
{
if (v <= B / i)
{
v *= i;
}
else
{
Console.WriteLine(-1);
return;
}
}
if (v == B)
{
Console.WriteLine(i);
return;
}
}
Console.WriteLine(-1);
}
問題C
愚直に3つの条件を判定します。
3*3のマス目の判定は、a*3+i行b*3+j列(0<=a,b<3、0<=i,j<3)とすることで、3*3のマス目を1つの大きなマス目としたとき、a行b列の大きなマス目とし、大きなマス目の中のi行j列の小さなマス目として見ることができるようになります。
例
public static void Solve()
{
const int N = 9;
var A = new int[N][];
for (var i = 0; i < N; i++)
{
A[i] = Scanner.ScanEnumerable<int>().Select(x => x - 1).ToArray();
}
var answer = true;
var mask = (1 << 9) - 1; // マス目の数字の存在判定をbit maskで管理
for (var i = 0; i < N; i++)
{
var v = 0;
for (var j = 0; j < N; j++)
{
v |= 1 << A[i][j];
}
answer &= v == mask;
}
for (var j = 0; j < N; j++)
{
var v = 0;
for (var i = 0; i < N; i++)
{
v |= 1 << A[i][j];
}
answer &= v == mask;
}
for (var a = 0; a < 3; a++)
{
for (var b = 0; b < 3; b++)
{
var v = 0;
for (var i = 0; i < 3; i++)
{
for (var j = 0; j < 3; j++)
{
v |= 1 << A[a * 3 + i][b * 3 + j];
}
}
answer &= v == mask;
}
}
Console.WriteLine(answer ? "Yes" : "No");
}
問題D
長さNの数列Xを、頂点A[i]と頂点B[i]間に辺があるN頂点M辺のグラフとして考えます。
このとき、数列Xが良い数列の組であるためには、全てのiについてX[A[i]]!=X[B[i]]が成立する必要があります。
よって、隣り合う頂点には異なる数字を割り当てる必要があることから、このグラフが二部グラフであることが良い数列である条件であることがわかります。
したがって、全ての連結成分において二部グラフが成り立つかを判定することで、答えを求めることができます。
例
public static void Solve()
{
var (N, M) = Scanner.Scan<int, int>();
var A = Scanner.ScanEnumerable<int>().Select(x => x - 1).ToArray();
var B = Scanner.ScanEnumerable<int>().Select(x => x - 1).ToArray();
var G = new HashSet<int>[N].Select(x => new HashSet<int>()).ToArray();
for (var i = 0; i < M; i++)
{
G[A[i]].Add(B[i]);
G[B[i]].Add(A[i]);
}
var colors = new int[N];
Array.Fill(colors, -1);
var queue = new Queue<int>();
for (var i = 0; i < N; i++)
{
if (colors[i] != -1) continue;
colors[i] = 0;
queue.Enqueue(i);
while (queue.TryDequeue(out var u))
{
foreach (var v in G[u])
{
if (colors[u] == colors[v])
{
Console.WriteLine("No");
return;
}
if (colors[v] != -1) continue;
colors[v] = colors[u] ^ 1;
queue.Enqueue(v);
}
}
}
Console.WriteLine("Yes");
}
問題E
選んだコンテストによる変動する、Sum((0.9)^(k-i)*Q[i])の部分について、次のような動的計画法を解きます。
dp[i][j] := i個目のコンテストまで見たとき、参加したコンテストがj個のときの最大値。
あるコンテストがx個目の選んだコンテストであった場合のパフォーマンスの重みをw[x]とします。
また、Pを逆順にすることで、逆順にしたPのi番目のコンテストのパフォーマンス重みをw[j] (j<=i)とすることができます。
このとき、遷移は次のようになります。
// i番目のコンテストを選ばないとき、
dp[i+1][j] = Max(dp[i+1][j], dp[i][j])
// i番目のコンテストを選ぶとき、
dp[i+1][j+1] = Max(dp[i+1][j+1], dp[i][j]+w[j+1]*P[i])
cumW[x]を選んだコンテストの数がx個の時の重みの累積和とします。
N番目のコンテストまで見たとき、dp[N][j]/cumW[j] - 1200/sqrt[j]の最大値が答えとなります。
例
public static void Solve()
{
var N = Scanner.Scan<int>();
var P = Scanner.ScanEnumerable<int>().ToArray();
var sqrt = new double[N + 1];
var w = new double[N + 1];
var cumW = new double[N + 1];
sqrt[1] = w[1] = cumW[1] = 1;
for (var i = 2; i <= N; i++)
{
sqrt[i] = Math.Sqrt(i);
w[i] = w[i - 1] * 0.9;
cumW[i] = cumW[i - 1] + w[i];
}
Array.Reverse(P);
var dp = new double[N + 1, N + 1];
for (var i = 0; i < N; i++)
{
for (var j = 0; j <= i; j++)
{
// i番目のコンテストを選ばないとき
dp[i + 1, j] = Math.Max(dp[i + 1, j], dp[i, j]);
// i番目のコンテストを選ぶとき
dp[i + 1, j + 1] = Math.Max(dp[i + 1, j + 1], dp[i, j] + w[j + 1] * P[i]);
}
}
const double Inf = 1e18;
var answer = -Inf;
for (var j = 1; j <= N; j++)
{
var r = dp[N, j] / cumW[j] - 1200 / sqrt[j];
answer = Math.Max(answer, r);
}
Console.WriteLine(answer);
}