はじめに
AtCoder Beginner Contest 285の復習記事です。
記事におけるScannerクラスは、自作の入力クラスです。
コンテスト
https://atcoder.jp/contests/abc285
問題A
図を見て全てのaとbの組み合わせを判定することもできますが、もっと簡単な方法はないか考えます。
図は完全二分木であり、親xは、子x*2と子x*2+1につながっていることがわかります。
そして、直接結ばれているかどうかは、親子が直接的につながっている必要があることから、a*2==bまたはa*2+1==bであることが判定の条件となります。
また、Floor(b/2)==aも成り立ちます。
public static void Solve()
{
var (a, b) = Scanner.Scan<int, int>();
var answer = b / 2 == a ? "Yes" : "No";
Console.WriteLine(answer);
}
問題B
問題文が複雑ですが、lはS[k]!=S[k+i]がk=0から何回続けることができるかを表します。
そのため、各i(1<=i<=N-1)において、S[k]!=S[k+i] (0<=k<N-i)が何回成り立つかを数え上げることで、答えを求めることができます。
public static void Solve()
{
var N = Scanner.Scan<int>();
var S = Scanner.Scan<string>();
for (var i = 1; i <= N - 1; i++)
{
var l = 0;
for (var k = 0; k + i < N; k++)
{
if (S[k] != S[k + i]) l++;
else break;
}
Console.WriteLine(l);
}
}
問題C
A==1,B==2,...,Z==26,AA==27,...であることから、Sの値を26進数+1としたとき、10進数でSの値はいくらかという問題になります。
S=ABCの場合は1(A)*26^2 + 2(B)*26^1 + 3(C)*26^0のようになり、各桁の値に26のべき乗を掛けたものとなります。
public static void Solve()
{
var S = Scanner.Scan<string>();
long b = 1;
long answer = 0;
foreach (var c in S.Select(x => x - 'A' + 1).Reverse())
{
answer += c * b;
b *= 26;
}
Console.WriteLine(answer);
}
問題D
ユーザ名を頂点とし、ユーザ名の変更を頂点sから頂点tへの有効辺としたグラフとして考えたとき、グラフに閉路がある場合は変更することができません。(a->b->c->aとしたとき、bの変更はaが必要だが、aの変更はcが必要であり、cの変更はbが必要となる。)
そのため、構築したグラフに閉路があるか判定することで、答えを求めることができます。
閉路の判定は、深さ優先探索やDisjointSetUnion、トポロジカルソートなどで求めることができます。
public static void Solve()
{
var N = Scanner.Scan<int>();
var dict = new Dictionary<string, int>();
var M = N * 2;
var G = new List<int>[M].Select(x => new List<int>()).ToArray();
var inDeg = new int[M];
var idx = 0;
for (var i = 0; i < N; i++)
{
var (s, t) = Scanner.Scan<string, string>();
if (!dict.ContainsKey(s)) dict[s] = idx++;
if (!dict.ContainsKey(t)) dict[t] = idx++;
var (u, v) = (dict[s], dict[t]);
inDeg[v]++;
G[u].Add(v);
}
var queue = new Queue<int>();
for (var i = 0; i < M; i++)
{
if (inDeg[i] == 0) queue.Enqueue(i);
}
var sorted = new int[M];
var curr = 0;
while (queue.TryDequeue(out var u))
{
foreach (var v in G[u])
{
inDeg[v]--;
if (inDeg[v] == 0) queue.Enqueue(v);
}
sorted[curr++] = u;
}
var answer = curr == M;
Console.WriteLine(answer ? "Yes" : "No");
}
問題E
まだ解けていません。
問題F
S[l..r]がTの部分文字列であるには、Tが昇順であることから、S[l..r]も昇順である必要があります。
S[l..r]が昇順であるかの判定について、S[l..r]に含まれる文字ごとの個数を順にみていき、ll=l+既にみた文字の個数、cc=現在の文字の個数、rr=ll+cc-1としたとき、S[ll..rr]に含まれる現在の文字の個数がccと等しくなる必要があります。
例えば、S==aaabcba、l==3、r==6としたとき、T==aaaabbc、S[l..r]==abcbになります。
文字aについて考えると、ll=l、cc=1、rr=llとなり、S[ll..rr]==aであり、ccと等しくなります。
文字bについて考えると、ll=l+1、cc=2、rr=ll+1となり、S[ll..rr]=bcであり、ccと異なるので、S[l..r]は昇順ではありません。
S[l..r]が昇順であるとき、S[l..r]がTの部分文字列であるかの判定について、S[l..r]に含まれる最も小さい文字a、最も大きい文字zとしたとき、a<c<zとなるcの個数は、Tに含まれるcの個数と一致する必要があります。
例えば、S==aabccde、l==2、r==6としたとき、T==aabccde、S[l..r]==abccdになり、S[l..r]に含まれる最も小さい文字はa、最も大きい文字はdなので、b==1とc==2となりTに含まれるbとcの数に一致するので、部分文字列となります。
一方、S==aabccdc、l==2、r==6としたとき、T==aabcccd、S[l..r]==abccdになり、S[l..r]に含まれる最も小さい文字はa、最も大きい文字はdなので、b==1とc==2になりますが、Tに含まれるbとcの数に一致しないので、部分文字列にはなりません。
これらのことから、現在の各文字の個数と現在の各文字の指定した範囲にある個数を求められるデータ構造が必要となります。
前者は配列、後者はFenwickTreeなどのデータ構造を使うことで求めることができ、クエリ当たりの時間計算量はO(logN)となり、全体時間計算量はO(N+QlogN)となります。
public static void Solve()
{
var N = Scanner.Scan<int>();
var S = Scanner.Scan<string>().Select(x => x - 'a').ToArray();
var Q = Scanner.Scan<int>();
var fts = new FenwickTree[26].Select(_ => new FenwickTree(N)).ToArray();
var sc = new int[26];
for (var i = 0; i < N; i++)
{
var c = S[i];
sc[c]++;
fts[c].Add(i, 1);
}
while (Q-- > 0)
{
var query = Scanner.ScanEnumerable<string>().ToArray();
if (query[0] == "1")
{
var (x, c) = (int.Parse(query[1]) - 1, query[2][0] - 'a');
var p = S[x];
S[x] = c;
fts[p].Add(x, -1);
fts[c].Add(x, 1);
sc[p]--;
sc[c]++;
}
else
{
var (l, r) = (int.Parse(query[1]) - 1, int.Parse(query[2]));
var tc = new int[26];
for (var i = 0; i < 26; i++)
{
tc[i] = (int)fts[i].Sum(l, r);
}
var alpha = 0;
var ll = l;
var answer = true;
while (alpha < 26 && tc[alpha] == 0) alpha++;
if (alpha < 26)
{
ll += tc[alpha];
alpha++;
}
while (answer && alpha < 26 && ll + tc[alpha] <= r)
{
var rr = ll + tc[alpha];
if (rr < r)
{
answer &= sc[alpha] == tc[alpha];
}
else
{
answer &= sc[alpha] >= tc[alpha];
}
answer &= tc[alpha] == fts[alpha].Sum(ll, rr);
ll = rr;
alpha++;
}
Console.WriteLine(answer ? "Yes" : "No");
}
}
}