はじめに
AtCoder Beginner Contest 256の復習記事です。
記事におけるScannerクラスは、自作の入力クラスです。
コンテスト
https://atcoder.jp/contests/abc256
問題A
Math.Pow(2, N)や1をNビットシフトした値が答えとなります。
public static void Solve()
{
var N = Scanner.Scan<int>();
var answer = 1L << N;
Console.WriteLine(answer);
}
問題B
各ターンの初めに位置0に1を足し、位置3,2,1,0の順でMin(現在の位置+a,4)に移動させるシミュレーションを行います。
位置の操作を0,1,2,3ではなく逆順で処理することで、移動した後の現在の位置を0にすることができるので、何個移動させたかを記録せずに操作できるようになります。
public static void Solve()
{
var N = Scanner.Scan<int>();
var A = Scanner.ScanEnumerable<int>().ToArray();
var g = new int[5];
foreach (var a in A)
{
g[0]++;
for (var i = 3; i >= 0; i--)
{
g[Math.Min(i + a, 4)] += g[i];
g[i] = 0;
}
}
var answer = g[4];
Console.WriteLine(answer);
}
問題C
全てのマスを全探索してしまうと30^9通りとなり、実行時間制限に間に合いません。
しかし、左上の2x2マスさえわかれば、3行目と3列目の数字が固定されるので、30^4の全探索で済むようになります。
public static void Solve()
{
var (H1, H2, H3, W1, W2, W3) = Scanner.Scan<int, int, int, int, int, int>();
var answer = 0;
for (var h1w1 = 1; h1w1 < Math.Min(H1, W1); h1w1++)
{
for (var h2w1 = 1; h1w1 + h2w1 < W1; h2w1++)
{
for (var h1w2 = 1; h1w1 + h1w2 < H1; h1w2++)
{
for (var h2w2 = 1; h1w2 + h2w2 < W2 && h2w1 + h2w2 < H2; h2w2++)
{
var h3w1 = W1 - h1w1 - h2w1;
var h3w2 = W2 - h1w2 - h2w2;
var h1w3 = H1 - h1w1 - h1w2;
var h2w3 = H2 - h2w1 - h2w2;
if (H3 - h3w1 - h3w2 == W3 - h1w3 - h2w3 && W3 - h1w3 - h2w3 > 0)
{
answer++;
}
}
}
}
}
Console.WriteLine(answer);
}
問題D
区間の左側を昇順で並べたときに、ある区間の左側よりもその直前区間の右側が大きい場合、その二つの区間をマージすることができます。
public static void Solve()
{
var N = Scanner.Scan<int>();
var range = new (int L, int R)[N];
for (var i = 0; i < N; i++)
{
range[i] = Scanner.Scan<int, int>();
}
Array.Sort(range, (x, y) => x.L.CompareTo(y.L));
var answer = new List<(int L, int R)>();
answer.Add(range[0]);
foreach (var (l, r) in range.Skip(1))
{
if (answer[^1].R >= l)
{
answer[^1] = (Math.Min(answer[^1].L, l), Math.Max(answer[^1].R, r));
}
else
{
answer.Add((l, r));
}
}
answer.Sort((x, y) => x.L.CompareTo(y.L));
foreach (var (l, r) in answer)
{
Console.WriteLine($"{l} {r}");
}
}
問題E
嫌いな人との関係を有効辺として考えることで、グラフとして考えることができるようになります。
N頂点N辺のグラフであることから、連結成分ごとにサイクルは多くても1個であることがわかります。
そこで、グラフを強連結成分ごとに分解し、サイクル内の最小の不満を受け入れることで、サイクルごとの不満度を最小にすることができます。
そして、サイクルごとの不満度の総和が答えとなります。
public static void Solve()
{
var N = Scanner.Scan<int>();
var X = Scanner.ScanEnumerable<int>().Select(x => x - 1).ToArray();
var C = Scanner.ScanEnumerable<long>().ToArray();
var scc = new StronglyConnectedComponent(N);
for (var i = 0; i < N; i++)
{
scc.AddEdge(i, X[i]);
}
const long inf = (long)1e18;
var answer = 0L;
foreach (var graph in scc.GetGraph())
{
if (graph.Count == 1) continue;
var min = inf;
foreach (var u in graph)
{
min = Math.Min(min, C[u]);
}
answer += min;
}
Console.WriteLine(answer);
}
強連結成分はACLのscc等で求めることができます。
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; }
}