ABC276

Published on Saturday, 05 November 2022

Updated on Saturday, 05 November 2022

atcoder csharp

はじめに

AtCoder Beginner Contest 276の復習記事です。

記事におけるScannerクラスは、自作の入力クラスです。

コンテスト

https://atcoder.jp/contests/abc276

問題A

コンテスト提出

文字列Sを左から順番に調べて、aが出現した場所を更新し、最後に更新された場所が答えとなります。

public static void Solve()
{
    var S = Scanner.Scan<string>();
    var answer = -1;
    for (var i = 0; i < S.Length; i++)
    {
        if (S[i] == 'a') answer = i + 1;
    }

    Console.WriteLine(answer);
}

G[u][v]のように二次元配列で頂点uが頂点vと接続しているかを持ってしまうと、空間計算量がO(N^2)となってしまいます。
Nが最大で10^5なので、二乗の10^10の空間計算量が必要となってしまい、実行時間制限に間に合いません。そこで、頂点ごとにリストを持ち、接続されている頂点を追加していくことで、空間計算量が最大でも10^5*2に収まり、ソートの計算量とあわせて全体でO(logN+N)で答えを求めることができます。

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 (a, b) = Scanner.Scan<int, int>();
        a--;
        b--;
        G[a].Add(b);
        G[b].Add(a);
    }

    for (var i = 0; i < N; i++)
    {
        G[i].Sort();
        var c = G[i].Count;
        if (c == 0) Console.WriteLine(0);
        else Console.WriteLine($"{c} {string.Join(" ", G[i].Select(x => x + 1))}");
    }
}

問題C

コンテスト提出復習提出

例を見てみると、Pの末尾が単調増加している部分の一つ手前(位置i)から右側が変化していることがわかります。
また、変化後のP[i]は、もとのP[i]より小さいものと入れ替わっており、iより右側が逆順にソートされていることがわかります。
ここで、P[i]と入れ替える値は、P[i]より小さいもので最大の値であり、Pの末尾は単調増加していることから、末尾から見てP[i]より小さくなった値と入れ替えることで、辞書順の直前にすることができます。

Rustなどではprev_permutation()メソッドを使って求めることもできます。

public static void Solve()
{
    var N = Scanner.Scan<int>();
    var P = Scanner.ScanEnumerable<int>().ToArray();
    var j = N - 2;
    var k = N - 1;
    while (P[j] < P[j + 1]) j--;
    while (P[j] < P[k]) k--;
    (P[j], P[k]) = (P[k], P[j]);
    Array.Sort(P, j + 1, N - (j + 1));
    for (var (l, r) = (j + 1, N - 1); l < r; l++, r--)
    {
        (P[l], P[r]) = (P[r], P[l]);
    }

    Console.WriteLine(string.Join(" ", P));
}

問題D

コンテスト提出

Aが操作後に全て一致するには、A[i] = 2^x * 3^y * V[i]で表すことができ、かつV[i]==V[j]である必要があります。そして、Aにおける最大公約数をgとすると、A[i] = 2^x * 3^y * gで表すことができます。このことから、A[i]/g == 2^x * 3^yが成り立つかどうかを判定しつつ、全てのAにおけるxとyの総和が答えとなります。

public static void Solve()
{
    var N = Scanner.Scan<int>();
    var A = Scanner.ScanEnumerable<long>().ToArray();

    var g = A.Aggregate(0L, Gcd);
    var answer = 0;
    for (var i = 0; i < N; i++)
    {
        var k = A[i] / g;

        while (k % 2 == 0)
        {
            k /= 2;
            answer++;
        }

        while (k % 3 == 0)
        {
            k /= 3;
            answer++;
        }

        if (k != 1)
        {
            Console.WriteLine(-1);
            return;
        }
    }

    Console.WriteLine(answer);
}

public static long Gcd(long a, long b) => b == 0 ? a : Gcd(b, a % b);

問題E

コンテスト提出

4方向のみ移動可能であるため、直前にいたマスに戻らずに同じマスに訪れることができた場合は、n>=4であることが確定します。そのため、直前に訪れたマスをメモしながら深さ優先探索を行い、開始始点にたどり着くことができるかを判定することで答えを求めることができます。

public static void Solve()
{
    var (H, W) = Scanner.Scan<int, int>();
    var G = new char[H][];
    var (sh, sw) = (0, 0);
    for (var i = 0; i < H; i++)
    {
        G[i] = Scanner.Scan<string>().ToCharArray();
        for (var j = 0; j < W; j++)
        {
            if (G[i][j] == 'S') (sh, sw) = (i, j);
        }
    }

    var D4 = new[] { (1, 0), (-1, 0), (0, 1), (0, -1) };

    var used = new bool[H * W];
    var prev = new int[H * W];
    var s = sh * W + sw;

    bool Dfs(int ch, int cw)
    {
        var u = ch * W + cw;
        used[u] = true;
        var result = false;

        foreach (var (dh, dw) in D4)
        {
            var (nh, nw) = (ch + dh, cw + dw);
            var v = nh * W + nw;
            if (nh < 0 || H <= nh || nw < 0 || W <= nw) continue;
            if (G[nh][nw] == '#') continue;
            if (v == s && v != prev[u]) result |= true;
            if (used[v]) continue;
            prev[v] = u;

            result |= Dfs(nh, nw);
        }

        return result;
    }

    var answer = Dfs(sh, sw);

    Console.WriteLine(answer ? "Yes" : "No");
}

問題F

復習提出

G[i][j]:=Max(1回目のカードA[i], 2回目のカードA[j])とすると、k番目の期待値はG[i][j] {i,j=1..k}の和をk*kで割ったものとなります。 k番目の試行を考えたとき、

1回目にk-1番目までのカードがでて、2回目にk番目のカードがでるとすると、G[i][k]=Max(A[i],A[k])になる。
1回目にk番目のカードがでて、2回目にk-1番目までのカードがでるとすると、G[k][i]=Max(A[k],A[i])になる。
1回目にk番目のカードがでて、2回目にk番目のカードがでるとすると、G[k][k]=A[k]になる。

k-1番目のG[i][j] {i,j=1..(k-1)}の総和をprevとすると、k番目のG[i][j] {i,j=1..k}の総和は、prev + G[i][k]{i..(k-1)} + G[k][i] {i..(k-1)} + G[k][k]となります。このとき、G[i][k]{i..(k-1)}は、k-1番目までのA[k]より小さい数*A[k]をsumS、k-1番目までのA[k]より大きい数の和をsumLとし、G[i][k]{i..(k-1)}==G[k][i] {i..(k-1)}であることから、k-1からkの総和の増分は(sumS + sumL)*2 + A[k]であることがわかります。
このことから、FenwickTree等を使ってk番目までのA[k]より小さい数の個数とA[k]より大きな数の和を管理しながらk番目における合計S[k]=S[k-1]+(sumS+sumL)*2+A[k]を計算していくことで、k番目における期待値S[k]/(k*k)を求めることができます。

public static void Solve()
{
    var N = Scanner.Scan<int>();
    var A = Scanner.ScanEnumerable<int>().ToArray();
    var (map, _) = Compress(A);
    var ft1 = new FenwickTree(N);
    var ft2 = new FenwickTree(N);
    var dp = new mint[N];
    dp[0] = A[0];
    ft1.Add(map[A[0]], 1);
    ft2.Add(map[A[0]], A[0]);

    for (var i = 1; i < N; i++)
    {
        var sumS = ft1.Sum(map[A[i]] + 1) * A[i];
        var sumL = ft2.Sum(map[A[i]] + 1, N);
        dp[i] = dp[i - 1] + (sumS + sumL) * 2 + A[i];

        ft1.Add(map[A[i]], 1);
        ft2.Add(map[A[i]], A[i]);
    }

    for (var i = 0; i < N; i++)
    {
        var curr = (mint)(i + 1) * (i + 1);
        Console.WriteLine(dp[i] / curr);
    }
}

public static (Dictionary<T, int> Map, Dictionary<int, T> ReMap) Compress<T>(IEnumerable<T> source)
{
    var distinct = source.Distinct().ToArray();
    Array.Sort(distinct);
    var map = new Dictionary<T, int>();
    var remap = new Dictionary<int, T>();
    foreach (var (x, i) in distinct.Select((x, i) => (x, i)))
    {
        map[x] = i;
        remap[i] = x;
    }

    return (map, remap);
}

public class FenwickTree
{
    public int Length { get; }
    private readonly mint[] _data;

    public FenwickTree(int length)
    {
        if (length < 0) throw new ArgumentOutOfRangeException(nameof(length));
        Length = length;
        _data = new mint[length];
    }

    public void Add(int index, long value)
    {
        if (index < 0 || Length <= index) throw new ArgumentOutOfRangeException(nameof(index));
        index++;
        while (index <= Length)
        {
            _data[index - 1] += value;
            index += index & -index;
        }
    }

    public mint Sum(int length)
    {
        if (length < 0 || Length < length) throw new ArgumentOutOfRangeException(nameof(length));
        mint s = 0;
        while (length > 0)
        {
            s += _data[length - 1];
            length -= length & -length;
        }

        return s;
    }

    public mint Sum(int left, int right)
    {
        if (left < 0 || right < left || Length < right) throw new ArgumentOutOfRangeException();
        return Sum(right) - Sum(left);
    }

    public int LowerBound(long value) => Bound(value, (x, y) => x <= y);
    public int UpperBound(long value) => Bound(value, (x, y) => x < y);

    private int Bound(long value, Func<long, long, bool> compare)
    {
        if (Length == 0 || compare(value, _data[0])) return 0;
        var x = 0;
        var r = 1;
        while (r < Length) r <<= 1;
        for (var k = r; k > 0; k >>= 1)
        {
            if (x + k - 1 >= Length || compare(value, _data[x + k - 1])) continue;
            value -= _data[x + k - 1];
            x += k;
        }

        return x;
    }
}

はじめに

コンテスト

問題A

問題B

問題C

問題D

問題E

問題F