ABC269

はじめに

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

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

コンテスト

https://atcoder.jp/contests/abc269

問題A

コンテスト提出

入出力の問題です。 C#では、コンソールからの文字列の入力をConsole.ReadLine()メソッド、コンソールへの文字列の出力をConsole.WriteLine()メソッドで行うことができます。

public static void Solve()
{
    var values = Console.ReadLine().Split(' ');
    var (a, b, c, d) = (long.Parse(values[0]), long.Parse(values[1]), long.Parse(values[2]), long.Parse(values[3]));
    var answer = (a + b) * (c - d);
    Console.WriteLine(answer);
    Console.WriteLine("Takahashi");
}

問題B

コンテスト提出

(A,B)は#が出現する最小の行と最大の行になり、(C,D)は、#が出現する最小の列と最大の列になります。

public static void Solve()
{
    var N = 10;
    var G = new string[N];
    for (var i = 0; i < N; i++)
    {
        G[i] = Scanner.Scan<string>();
    }

    const int inf = (int)1e9;
    var (a, b, c, d) = (inf, 0, inf, 0);
    for (var i = 0; i < N; i++)
    {
        for (var j = 0; j < N; j++)
        {
            if (G[i][j] == '#')
            {
                a = Math.Min(a, i);
                b = Math.Max(b, i);
                c = Math.Min(c, j);
                d = Math.Max(d, j);
            }
        }
    }

    Console.WriteLine($"{a + 1} {b + 1}");
    Console.WriteLine($"{c + 1} {d + 1}");
}

問題C

コンテスト提出

求めたい集合は、|をビット論理和としたとき、x | N == Nとなるxの集合です。 Nがとても大きいので、xを全探索してしまうと実行時間制限に間に合いません。 そこで、Nのビットが立っている位置をビット全探索して論理和を求めることで、集合を求めることができます。 制約によりNのビットが立っている個数は最大でも15なので、答えとなる個数は最大でも2^15なので、実行時間制限に十分間に合います。

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

    var list = new List<int>();
    for (var i = 0; i <= 60; i++)
    {
        if ((N >> i & 1) == 1) list.Add(i);
    }

    var answer = new List<long>();
    var M = list.Count;
    for (var i = 0; i < 1 << M; i++)
    {
        var v = 0L;
        for (var j = 0; j < M; j++)
        {
            if ((i >> j & 1) == 1)
            {
                v |= 1L << list[j];
            }
        }

        answer.Add(v);
    }

    answer.Sort();
    Console.WriteLine(string.Join("\n", answer));
}

問題D

コンテスト提出

N個のマスのペアが隣接する6マスにあるかを探索し、マスの番号を頂点としたDisjointSetUnion (DSU, aka UnionFind)等を使って、連結成分の個数を数え上げます。

public static void Solve()
{
    var N = Scanner.Scan<int>();
    var XY = new (int X, int Y)[N];
    var dict = new Dictionary<(int X, int Y), int>();
    for (var i = 0; i < N; i++)
    {
        var p = Scanner.Scan<int, int>();
        XY[i] = p;
        dict[p] = i;
    }

    var D6 = new (int X, int Y)[6] { (-1, -1), (-1, 0), (0, -1), (0, 1), (1, 0), (1, 1) };
    var dsu = new DisjointSetUnion(N);
    for (var i = 0; i < N; i++)
    {
        foreach (var (dx, dy) in D6)
        {
            var np = (XY[i].X + dx, XY[i].Y + dy);
            if (dict.ContainsKey(np))
            {
                var j = dict[np];
                dsu.Merge(i, j);
            }
        }
    }

    var answer = dsu.GetGroups().Count();
    Console.WriteLine(answer);
}

問題E

コンテスト提出

行と列はそれぞれ独立しているため、行と列を別に考えます。
ある行mまでに含まれるルークの数を質問したとき(! 1 m 1 N)、質問への答えがmの場合、1行からm行までには既にルークが全て置かれており、m+1行目からN行目までに答えとなる行が存在することがわかり、m以外の場合は1からm行までの中に答えとなる行が存在することがわかります。 また、制約が2<=N<=1000であり、N<=2^10であることから、答えとなる行mの二部探索を行うことで、10回程度の質問で答えとなる行mを求められることがわかります。
同様に列に対しても二部探索で答えを求めることで、行と列合わせて20回程度の質問で答えを求めることができます。

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

    bool AskI(long m)
    {
        Console.WriteLine($"? 1 {m} 1 {N}");
        var c = Scanner.Scan<int>();
        return c != m;
    }

    bool AskJ(long m)
    {
        Console.WriteLine($"? 1 {N} 1 {m}");
        var c = Scanner.Scan<int>();
        return c != m;
    }

    var i = BinarySearch(0, N, AskI);
    var j = BinarySearch(0, N, AskJ);
    Console.WriteLine($"! {i} {j}");
}

public static long BinarySearch(long l, long r, Func<long, bool> func)
{
    while (Math.Abs(r - l) > 1)
    {
        var m = (r + l) / 2;
        if (func(m)) r = m;
        else l = m;
    }

    return r;
}