はじめに
AtCoder Beginner Contest 299の復習記事です。
記事におけるScannerクラスは、自作の入力クラスです。
コンテスト
https://atcoder.jp/contests/abc299
問題A
左側の|と右側の|のインデックスを検索した後、その間に*が存在するかを判定します。
public static void Solve()
{
var N = Scanner.Scan<int>();
var S = Scanner.Scan<string>();
var l = 0;
var r = N - 1;
while (l < N && S[l] != '|') l++;
while (r >= 0 && S[r] != '|') r--;
for (var i = l; i <= r; i++)
{
if (S[i] == '*')
{
Console.WriteLine("in");
return;
}
}
Console.WriteLine("out");
}
問題B
辞書などのデータ構造を使い、Cをキーとした最大のRとそのプレイヤーiを管理します。
public static void Solve()
{
var (N, T) = Scanner.Scan<int, int>();
var C = Scanner.ScanEnumerable<int>().ToArray();
var R = Scanner.ScanEnumerable<int>().ToArray();
var dict = new Dictionary<int, (int R, int I)>();
for (var i = 0; i < N; i++)
{
var c = C[i];
var r = R[i];
if (!dict.ContainsKey(c)) dict[c] = (r, i);
else if (r > dict[c].R) dict[c] = (r, i);
}
var t = dict.ContainsKey(T) ? T : C[0];
var answer = dict[t].I + 1;
Console.WriteLine(answer);
}
問題C
尺取り法で文字列を順にみていき、連続したoの後に-が続くダンゴ文字列のレベルの最大値を更新します。
文字列を反転させたものを再び判定することで、-の後にoが連続するダンゴ文字列のレベルを判定することができます。
public static void Solve()
{
var N = Scanner.Scan<int>();
var S = Scanner.Scan<string>().ToCharArray();
int F(char[] s)
{
var l = 0;
var result = -1;
while (l < s.Length)
{
if (s[l] == '-')
{
l++;
continue;
}
var r = l;
while (r < s.Length && s[r] == 'o') r++;
if (r < s.Length && s[r] == '-')
{
result = Math.Max(result, r - l);
}
l = r;
}
return result;
}
var answer = F(S);
Array.Reverse(S);
answer = Math.Max(answer, F(S));
Console.WriteLine(answer);
}
問題D
連続した0と連続した1が繋がった文字列のうち、0と1の境目の番号を求める問題です。
0と1の境目を二部探索することでCeil(logN)回(最大でも18回)の質問で、答えを求めることができます。
public static void Solve()
{
var N = Scanner.Scan<int>();
bool F(int x)
{
Console.WriteLine($"?{x + 1}");
var v = Scanner.Scan<int>();
return v == 1;
}
var answer = BinarySearch(0, N, F);
Console.WriteLine($"!{answer}");
}
public static int BinarySearch(int ng, int ok, Func<int, bool> func)
{
while (Math.Abs(ok - ng) > 1)
{
var m = (ok + ng) / 2;
if (func(m)) ok = m;
else ng = m;
}
return ok;
}
問題E
Kが0のとき、黒を1つ以上含むグラフであれば条件を満たします。
それ以外のときを考えます。
「黒で塗られた頂点のうち頂点p[i]からの距離が最小であるもの」の距離がちょうどdとなるものであることから、頂点p[i]から距離d未満の頂点に黒で塗られた頂点が存在してはいけません。
そのため、はじめに全ての頂点を黒で塗り、各p[i]から1<=u<=Nの頂点について、距離がd未満の頂点を白で塗ったものが、条件を満たす可能性のある塗る方法になります。
このうち、1つ以上の頂点が黒で塗られているかつ、全てのp[i]において、黒で塗られている頂点との距離がdのものが1つ以上存在する場合、その頂点の塗り方が答えとなります。
public static void Solve()
{
var (N, M) = Scanner.Scan<int, int>();
var G = new List<int>[N].Select(x => new List<int>()).ToArray();
for (var i = 0; i < M; i++)
{
var (u, v) = Scanner.Scan<int, int>();
u--; v--;
G[u].Add(v);
G[v].Add(u);
}
var K = Scanner.Scan<int>();
if (K == 0)
{
Console.WriteLine("Yes");
Console.WriteLine(new string('1', N));
return;
}
var D = new int[N][];
var queue = new Queue<int>();
for (var i = 0; i < N; i++)
{
var dist = new int[N];
Array.Fill(dist, -1);
queue.Enqueue(i);
dist[i] = 0;
while (queue.Count > 0)
{
var u = queue.Dequeue();
foreach (var v in G[u])
{
if (dist[v] != -1) continue;
dist[v] = dist[u] + 1;
queue.Enqueue(v);
}
}
D[i] = dist;
}
var minD = new int[N];
const int Inf = (int)1e9;
Array.Fill(minD, Inf);
var PD = new (int P, int D)[K];
for (var i = 0; i < K; i++)
{
var (p, d) = Scanner.Scan<int, int>();
p--;
PD[i] = (p, d);
}
var C = new int[N];
Array.Fill(C, 1);
foreach (var (p, d) in PD)
{
for (var j = 0; j < N; j++)
{
if (D[p][j] < d) C[j] = 0;
}
}
foreach (var (p, d) in PD)
{
var ok = false;
for (var v = 0; v < N; v++)
{
ok |= C[v] == 1 && D[p][v] == d;
}
if (!ok)
{
Console.WriteLine("No");
return;
}
}
if (!C.Contains(1))
{
Console.WriteLine("No");
return;
}
Console.WriteLine("Yes");
Console.WriteLine(string.Join("", C));
}