はじめに
AtCoder Beginner Contest 296の復習記事です。
記事におけるScannerクラスは、自作の入力クラスです。
コンテスト
https://atcoder.jp/contests/abc296
問題A
1<=i<Nにおいて、S[i]とS[i+1]がすべて異なっている場合、答えはYesになります。
public static void Solve()
{
var N = Scanner.Scan<int>();
var S = Scanner.Scan<string>();
var answer = true;
for (var i = 0; i + 1 < N; i++)
{
answer &= S[i] != S[i + 1];
}
Console.WriteLine(answer ? "Yes" : "No");
}
問題B
S[r][c]が*のとなるrとcを求め、rとcを指定されたフォーマット文字列に変換します。
フォーマット文字列は、{行}{列}ではなく、{列+'a'}{8-行}であることに注意します。
public static void Solve()
{
const int H = 8;
const int W = 8;
var S = new char[H][];
for (var i = 0; i < H; i++)
{
S[i] = Scanner.Scan<string>().ToCharArray();
}
string F(int r, int c) => $"{(char)(c + 'a')}{8 - r}"
for (var i = 0; i < H; i++)
{
for (var j = 0; j < W; j++)
{
if (S[i][j] == '*')
{
Console.WriteLine(F(i, j));
return;
}
}
}
}
問題C
Aをソートし、尺取り法でA[r]-A[l]==Xとなるlとrを探索することで、時間計算量O(NlogN+N)で答えを求めることができます。
public static void Solve()
{
var (N, X) = Scanner.Scan<int, long>();
var A = Scanner.ScanEnumerable<long>().ToArray();
Array.Sort(A);
var r = 0;
for (var l = 0; l < N; l++)
{
while (r < N && A[r] - A[l] < X) r++;
if (r < N && A[r] - A[l] == X)
{
Console.WriteLine("Yes");
return;
}
}
Console.WriteLine("No");
}
A[i]-A[j]==Xを式変形するとA[i]==A[j]+Xであることから、Aからなる集合Sを用意し、A[i]+XがSに含まれているかどうかを判定することでも、答えを求めることができます。
public static void Solve()
{
var (N, X) = Scanner.Scan<int, long>();
var A = Scanner.ScanEnumerable<long>().ToArray();
var set = new HashSet<long>(A);
var answer = set.Any(a => set.Contains(a + X));
Console.WriteLine(answer ? "Yes" : "No");
}
問題D
a<=bとしaを固定して考えると、M<=a*bよりb>=M/a、Floor(M/a)<=M/a<=Ceil(M/a)より、b=Ceil(M/a)とすることができ、1<=b<=Nであることから、c=a*Min(b,N)になり、c>=Mのときの最小値が答えとなります。
時間計算量はO(Min(N,Sqrt(M)))程度となり、最大でも1e6回程度の計算で答えを求めることができます。
public static void Solve()
{
var (N, M) = Scanner.Scan<long, long>();
const long Inf = (long)1e18;
long CalcB(long a) => Math.Min(N, (M + a - 1) / a);
var answer = Inf;
for (long a = 1; a <= CalcB(a); a++)
{
var b = CalcB(a);
var c = a * b;
if (c >= M) answer = Math.Min(answer, c);
}
if (answer == Inf) answer = -1;
Console.WriteLine(answer);
}
問題E
1<=i<=Nを頂点としたグラフとし、黒板にxが書かれているとき、それを消し、A[x]を新しく書くという操作をxからA[x]に対する有向辺とすると、
サイクルを構築する頂点の集合(強連結成分)に含まれる頂点には、正整数K[i]がどのような値であっても、始点となる頂点を任意に決めることができるので、たどり着くことができます。
このことから、iからA[i]に対する有効辺を構築したグラフに対して強連結成分分解を行い、各強連結成分を構成する頂点の総和が答えとなります。
このとき、自己辺が存在する場合に注意が必要です。
public static void Solve()
{
var N = Scanner.Scan<int>();
var A = Scanner.ScanEnumerable<int>().Select(x => x - 1).ToArray();
var isSelf = new bool[N];
var scc = new StronglyConnectedComponent(N);
for (var i = 0; i < N; i++)
{
scc.AddEdge(i, A[i]);
if (i == A[i]) isSelf[i] = true;
}
var answer = 0;
foreach (var graph in scc.GetGraph())
{
if (graph.Count == 1 && !isSelf[graph[0]]) continue;
answer += graph.Count;
}
Console.WriteLine(answer);
}
強連結成分に関しては以下のクラスを使いました。
public class StronglyConnectedComponent
{
public int Length { get; }
private readonly List<(int, Edge)> _edges;
public StronglyConnectedComponent(int length)
{
if (length < 0) throw new ArgumentOutOfRangeException(nameof(length));
Length = length;
_edges = new List<(int, Edge)>();
}
public void AddEdge(int from, int to)
{
if (from < 0 || Length <= from) throw new ArgumentOutOfRangeException(nameof(from));
if (to < 0 || Length <= to) throw new ArgumentOutOfRangeException(nameof(to));
_edges.Add((from, new Edge(to)));
}
public (int GroupCount, int[] IDs) GetIDs()
{
var g = new CompressedSparseRow<Edge>(Length, _edges);
var (nowOrd, groupCount) = (0, 0);
var visited = new Stack<int>(Length);
var low = new int[Length];
var ord = new int[Length];
Array.Fill(ord, -1);
var ids = new int[Length];
void Dfs(int v)
{
low[v] = ord[v] = nowOrd++;
visited.Push(v);
for (var i = g.Start[v]; i < g.Start[v + 1]; i++)
{
var to = g.Edges[i].To;
if (ord[to] == -1)
{
Dfs(to);
low[v] = Math.Min(low[v], low[to]);
}
else
{
low[v] = Math.Min(low[v], ord[to]);
}
}
if (low[v] != ord[v]) return;
while (true)
{
var u = visited.Pop();
ord[u] = Length;
ids[u] = groupCount;
if (u == v) break;
}
groupCount++;
}
for (var i = 0; i < Length; i++)
{
if (ord[i] == -1)
Dfs(i);
}
for (var i = 0; i < Length; i++)
{
ids[i] = groupCount - 1 - ids[i];
}
return (groupCount, ids);
}
public IReadOnlyList<IReadOnlyList<int>> GetGraph()
{
var (groupCount, ids) = GetIDs();
var groups = new List<int>[groupCount];
for (var i = 0; i < groups.Length; i++)
{
groups[i] = new List<int>();
}
foreach (var (id, index) in ids.Select((x, i) => (x, i)))
{
groups[id].Add(index);
}
return groups;
}
private readonly struct Edge
{
public readonly int To;
public Edge(int to) => To = to;
}
}
public class CompressedSparseRow<T>
{
public CompressedSparseRow(int length, IEnumerable<(int ID, T)> edges)
{
Start = new int[length + 1];
var es = edges.ToArray();
Edges = new T[es.Length];
foreach (var e in es) Start[e.ID + 1]++;
for (var i = 0; i < length; i++) Start[i + 1] += Start[i];
var counter = new int[length + 1];
Start.AsSpan().CopyTo(counter.AsSpan());
foreach (var (i, t) in es) Edges[counter[i]++] = t;
}
public int[] Start { get; }
public T[] Edges { get; }
}