ABC287

Published on Saturday, 28 January 2023

Updated on Saturday, 28 January 2023

atcoder csharp

はじめに

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

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

コンテスト

https://atcoder.jp/contests/abc287

問題A

コンテスト提出

入力からForの個数を数え上げ、その個数の2倍がNより大きければ過半数が提案に賛成しています。

public static void Solve()
{
    var N = Scanner.Scan<int>();
    var f = 0;
    for (var i = 0; i < N; i++)
    {
        var S = Scanner.Scan<string>();
        if (S == "For") f++;
    }

    var answer = f * 2 > N ? "Yes" : "No";
    Console.WriteLine(answer);
}

各Sの末尾3文字がTのいずれかと一致しているかを各Sと各Tの組み合わせを全探索することで、時間計算量O(NM)で答えを求めることができます。
また、Tの集合をSetやHashSetなどのデータ構造で管理することで、時間計算量をO(NlogM)、O(N)にすることもできます。
ほかにも、入力が数値のみであることから、大きさが1000以上の配列を用意してTを配列のインデックスとして存在判定し、S%1000でその配列にアクセスすることで、時間計算量O(N+M)で解くこともできます。

public static void Solve()
{
    var (N, M) = Scanner.Scan<int, int>();
    var S = new string[N];
    for (var i = 0; i < N; i++)
    {
        var s = Scanner.Scan<string>();
        S[i] = s[3..];
    }

    var T = new HashSet<string>();
    for (var i = 0; i < M; i++)
    {
        var t = Scanner.Scan<string>();
        T.Add(t);
    }

    var answer = 0;
    foreach (var s in S)
    {
        if (T.Contains(s)) answer++;
    }

    Console.WriteLine(answer);
}

問題C

コンテスト提出

直線になるようなグラフがパスグラフになります。これは、グラフを構成する辺がN-1本であり、端点となる2つの頂点は次数が1、それ以外は次数が2であり、連結であるグラフです。グラフが連結であるかどうかは幅/深さ優先探索やDisjointSetUnionで調べることができます。

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);
    }

    if (M != N - 1 || G.Any(x => x.Count > 2))
    {
        Console.WriteLine("No");
        return;
    }

    var used = new bool[N];
    var queue = new Queue<int>();
    queue.Enqueue(0);
    used[0] = true;
    while (queue.Count > 0)
    {
        var u = queue.Dequeue();
        foreach (var v in G[u].Where(x => !used[x]))
        {
            used[v] = true;
            queue.Enqueue(v);
        }
    }

    var answer = used.All(x => x);
    Console.WriteLine(answer ? "Yes" : "No");
}

問題D

コンテスト提出

SとTの先頭からi文字が一致しているかをfirst[i]としたとき、

i==0のとき、
first[0] = true

i>=1のとき、
f1 = S[i] == T[i]
f2 = S[i] == '?'
f3 = T[i] == '?'
first[i] = first[i - 1] && (f1 || f2 || f3)

同様に末尾からi文字が一致しているかをlast[i]とすると、各xに対する答えをf(x)とすると次のようになります。

f(x) == first[x] && last[|T| - x]`

事前にfirstとlastを時間計算量O(|T|)で求めておくことで、f(x)は時間計算量O(1)で求めることができ、全体計算量はO(|T|)となります。

public static void Solve()
{
    var S = Scanner.Scan<string>();
    var T = Scanner.Scan<string>();
    var N = T.Length;
    var first = new bool[N + 1];
    var last = new bool[N + 1];
    first[0] = last[0] = true;
    for (var i = 0; i < N; i++)
    {
        var sj = S.Length - 1 - i;
        var tj = T.Length - 1 - i;
        var ff = S[i] == '?' || T[i] == '?' || S[i] == T[i];
        var fl = S[sj] == '?' || T[tj] == '?' || S[sj] == T[tj];
        first[i + 1] = first[i] && ff;
        last[i + 1] = last[i] && fl;
    }

    for (var x = 0; x <= N; x++)
    {
        var y = N - x;
        var answer = first[x] && last[y];
        Console.WriteLine(answer ? "Yes" : "No");
    }
}

問題E

コンテスト提出

全ての文字列において、長さ0<=k<=|S|の連続部分文字列Tとなる個数をあらかじめ求めておき、各iにおける長さkのTの個数が2個以上存在する場合、LCP(i,?)==kが成立するため、そのkの最大がiに対する答えとなります。連続部分文字列の管理にRollingHashなどを使うことで、連続部分列の計算を時間計算量O(1)で求めることができ、全体時間計算量O(NlogN)で答えを求めることができます。

public static void Solve()
{
    var N = Scanner.Scan<int>();
    var S = new string[N];
    var dict = new Dictionary<ulong, Dictionary<int, int>>();
    var rhs = new RollingHash[N];
    for (var i = 0; i < N; i++)
    {
        var s = Scanner.Scan<string>();
        S[i] = s;
        var rh = new RollingHash(s);
        rhs[i] = rh;
        for (var j = 0; j <= s.Length; j++)
        {
            var h = rh.SlicedHash(0, j);
            if (!dict.ContainsKey(h)) dict[h] = new Dictionary<int, int>();
            if (!dict[h].ContainsKey(j)) dict[h][j] = 0;
            dict[h][j]++;
        }
    }

    for (var i = 0; i < N; i++)
    {
        var answer = 0;
        for (var j = 0; j <= S[i].Length; j++)
        {
            var h = rhs[i].SlicedHash(0, j);
            if (dict[h].ContainsKey(j) && dict[h][j] >= 2) answer = j;
        }

        Console.WriteLine(answer);
    }
}

RollingHashについて、keymoonさんの安全で爆速なRollingHashの話を参考にしました。

public class RollingHash
{
    private const ulong Mask30 = (1UL << 30) - 1;
    private const ulong Mask31 = (1UL << 31) - 1;
    private const ulong Modulo = (1UL << 61) - 1;
    private const ulong Positivizer = Modulo * ((1UL << 3) - 1);
    public static readonly ulong Base;
    static RollingHash()
    {
        Base = (ulong)new Random().Next(1 << 8, int.MaxValue);
    }
    private readonly ulong[] _powers;
    private readonly ulong[] _hash;
    public RollingHash(ReadOnlySpan<char> s)
    {
        _powers = new ulong[s.Length + 1];
        _powers[0] = 1;
        _hash = new ulong[s.Length + 1];
        for (var i = 0; i < s.Length; i++)
        {
            _powers[i + 1] = CalcModulo(Multiply(_powers[i], Base));
            _hash[i + 1] = CalcModulo(Multiply(_hash[i], Base) + s[i]);
        }
    }
    public ulong SlicedHash(int start, int length)
    {
        return CalcModulo(_hash[start + length] + Positivizer - Multiply(_hash[start], _powers[length]));
    }
    private static ulong Multiply(ulong a, ulong b)
    {
        var au = a >> 31;
        var ad = a & Mask31;
        var bu = b >> 31;
        var bd = b & Mask31;
        var m = ad * bu + au * bd;
        var mu = m >> 30;
        var md = m & Mask30;
        return ((au * bu) << 1) + mu + (md << 31) + ad * bd;
    }
    private static ulong CalcModulo(ulong v)
    {
        var vu = v >> 61;
        var vd = v & Modulo;
        var x = vu + vd;
        return x < Modulo ? x : x - Modulo;
    }
}

はじめに

コンテスト

問題A

問題B

問題C

問題D

問題E