ABC279

はじめに

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

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

コンテスト

https://atcoder.jp/contests/abc279

問題A

コンテスト提出

文字列Sを順にみていき、文字S[i]がvなら1、wなら2を足した総和が答えとなります。

public static void Solve()
{
    var S = Scanner.Scan<string>();

    int F(char c)
    {
        return c switch
        {
            'v' => 1,
            'w' => 2,
            _ => 0,
        };
    }

    var answer = 0;
    foreach (var c in S)
    {
        answer += F(c);
    }

    Console.WriteLine(answer);
}

問題B

コンテスト提出

文字列Sに文字列Tが含まれているかを調べます。 方法としては以下のようなものがあります。

• stringのContainsメソッド(計算量O(S))
• Sの始点を固定しTと比較する(計算量O(ST))
• ボイヤームーア法で探索する(計算量O(S))

public static void Solve()
{
    var S = Scanner.Scan<string>();
    var T = Scanner.Scan<string>();
    var answer = S.Contains(T);
    Console.WriteLine(answer ? "Yes" : "No");
}

問題C

コンテスト提出

Sの列を並べ替えてTと等しくできるかどうかは、Sの列の集合とTの列の集合が一致しているか確認できればいいので、``Sの列とT`の列をそれぞれ文字列として辞書などのデータ構造などで個数を管理することで、集合が一致しているかを比較できます。

public static void Solve()
{
    var (H, W) = Scanner.Scan<int, int>();
    var S = new char[H][];
    var T = new char[H][];
    for (var k = 0; k < 2; k++)
    {
        for (var i = 0; i < H; i++)
        {
            (k == 0 ? S : T)[i] = Scanner.Scan<string>().ToCharArray();
        }
    }

    var dictS = new Dictionary<string, int>();
    var dictT = new Dictionary<string, int>();
    for (var j = 0; j < W; j++)
    {
        var builderS = new StringBuilder();
        var builderT = new StringBuilder();
        for (var i = 0; i < H; i++)
        {
            builderS.Append(S[i][j]);
            builderT.Append(T[i][j]);
        }

        var s = builderS.ToString();
        var t = builderT.ToString();
        if (!dictS.ContainsKey(s)) dictS[s] = 0;
        dictS[s]++;
        if (!dictT.ContainsKey(t)) dictT[t] = 0;
        dictT[t]++;
    }

    var answer = true;
    foreach (var (s, c) in dictS)
    {
        answer &= dictT.ContainsKey(s) && dictT[s] == c;
    }

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

問題D

コンテスト提出

公式解説にもあるように、F(g)=B(g-1)+A/Sqrt(g)は下に凸な関数であるため、gに対する三部探索を行い、最小となるgを求めます。 このgは浮動小数点のため、その付近の整数値のうち、F(g)が最小となる値が答えとなります。 また、三部探索を行う際の範囲として、F(g)<F(1)=A以下であればいいので、1<=g<=A/Bであれば十分であることがわかります。

public static void Solve()
{
    var (A, B) = Scanner.Scan<long, long>();

    double F(double g)
    {
        return B * (g - 1) + A / Math.Sqrt(g);
    }

    var r = (A + B - 1) / B;
    var g = (long)TernarySearch(0, r, F, 1e-2);
    var answer = new[] { Math.Max(g - 1, 1), g, g + 1 }.Select(x => F(x)).Min();
    Console.WriteLine(answer);
}

public static double TernarySearch(double l, double r, Func<double, double> func, double eps = 1e-9)
{
    while (r - l > eps)
    {
        var d = (r - l) / 3;
        var (ml, mr) = (l + d, r - d);
        if (func(ml) < func(mr)) r = mr;
        else l = ml;
    }
    return (l + r) / 2;
}

問題E

コンテスト提出

愚直にシミュレーションしてしまうと、時間計算量がO(M^2)となり実行時間制限に間に合いません。
求めるものはB[j]==1となるjの位置Sであるため、位置Sのiの集合を辞書などのデータ構造で管理します。 x=A[k],y=A[k]+1としたとき、B[x]とB[y]を入れ替えるということは、位置xと位置yにあるそれぞれのiの集合を入れ替えることになります。 また、i==kのときは操作しないということは、入れ替えの操作時にxのiの集合にkが含まれていれば、i以外をyに移動することになります。 このとき、一つずつ移動をしてしまうと時間計算量がO(M)になってしまいますが、xとyの集合の参照を入れ替えた後に、yの集合からkを削除し、xの集合にkを追加することで、時間計算量O(logN)で操作を行うことができます。 全体の時間計算量はO(N+MlogN)となります。

public static void Solve()
{
    var (N, M) = Scanner.Scan<int, int>();
    var A = Scanner.ScanEnumerable<int>().Select(x => x - 1).ToArray();

    var dict = new Dictionary<int, HashSet<int>>();
    for (var i = 0; i < N; i++)
    {
        dict[i] = new HashSet<int>();
    }

    for (var i = 0; i < M; i++)
    {
        dict[0].Add(i);
    }

    for (var k = 0; k < M; k++)
    {
        var i = k;
        var x = A[k];
        var y = A[k] + 1;
        (dict[x], dict[y]) = (dict[y], dict[x]);
        if (dict[x].Contains(i))
        {
            dict[x].Remove(i);
            dict[y].Add(i);
        }
        else if (dict[y].Contains(i))
        {
            dict[y].Remove(i);
            dict[x].Add(i);
        }
    }

    var answer = new int[M];
    foreach (var (s, set) in dict)
    {
        foreach (var i in set)
        {
            answer[i] = s + 1;
        }
    }

    Console.WriteLine(string.Join(Environment.NewLine, answer));
}