トップ > AtCoder ABC199

AtCoder ABC199

ABC199参加しました。

atcoder.jp

 

A - Square Inequality

与えられた通り計算し、ifで分岐しましょう。

解説 - AtCoder Beginner Contest 199

B - Intersection

$[1, 1000]$まで入れたリストを作って、A[i], B[i]と比較して重なっていた数字は除外することで結果が出ます。

解説 - AtCoder Beginner Contest 199

C - IPFL

正直なところ、以下と全く同じ解法になりました。
IPFL [AtCoder Beginner Contest 199（Sponsored by Panasonic） C] - はまやんはまやんはまやん

そのまままともにやるとTLEになりそうですね。 T=2のときに、N回ループを回し、クエリがQ個なので、$O(QN)$だけかかることになるため、Q,Nが最大値を取ると間に合いません。

T=1のときは、$O(1)$なので、どうしようもないです。 T=2がネックなので、ここだけなんとかしてみます。

言語の特性(C#)を生かして解いてみました。C#の文字列は参照型なので、予め文字列の前半、後半を分解して持ち、T=2のときは、その参照を入れ替えれば$O(1)$で入れ替えが行われます。これで、ネックだった部分が解消できました。

解説 - AtCoder Beginner Contest 199

D - RGB Coloring 2

DFS! DFS!

与えられたグラフのすべての点が連結しているわけではないので、まずUnion-Findして、グループを作ります。

作られたグループごとに色塗り総数を求めれば、後は各グループの色塗り総数の積が答えです。よって、グループごとの色塗りの方法を考えます。

各グループで以下のステップを取ります。

  1. 同じ頂点を二度訪れないように、DFSで頂点間を移動して、移動履歴を求める。このときはまだ色塗りはしません。
  2. 上の移動履歴順に頂点を辿って、DFSで色塗りをする

色塗りする際は、グループ内のどの頂点から開始してもいいです。 また、開始点はどの色で塗ってもいいです。なぜなら、どの色から塗り始めても、パターン数は変わらないので、適当な色で塗って求めたパターン数を(R,G,B3色なので)3倍してあげれば、グループの総色塗り数が計算できます。

あとはひたすらDFSで塗っていきます。 塗るときは、隣接頂点と同じ色で塗らないようにしましょう。 擬似コードは以下。

    public long countColor()
    {
        //UnionFindしてできたグループのrootを求める
        var roots = ...
        long ans = 1;
        foreach (var root in roots)
        {
            //<1>の部分。DFSで移動履歴を計算(visitedに貯める)
            List<int> visited = //

            long count = 0;

            //<2>の部分。最初のノードをRで塗ると仮定してDFS
            DFSPaint(0, Color.R, ref visited, ref count);

            //最初のノードをどの色で塗っても同じパターン数になるのでx3倍
            ans *= (count * 3);
        }
        return ans;
    }

    public void DFSPaint(int currIdx(visitedの添字), Color currColor(今いる頂点の色), ref List<int> visited, ref long ans)
    {
        //今訪れたノードを塗る
        NodeColors[currNode] = currColor;

        //次のノードを調べる
        int nextIdx = currIdx + 1;
        if (visited.Count <= nextIdx)//全部塗ったら答えの組み合わせが一つ増える
        {
            ++ans;
            return;
        }
        var nextNode = visited[nextIdx];

        //次の頂点の隣接ノードを獲得
        var adjacents = //

        //次の頂点で塗れる色を調べる
        var used = new Dictionary<Color, bool>(3) {
                {R, false },//falseならまだ使ってないので、色が塗れる
                {G, false },//trueならもう隣接頂点で使っているので、色が塗れない
                {B, false },
         };
        //隣接している頂点(今いる頂点も含める)で使っている色は除外
        foreach (int ad in adjacents){
            used[NodeColors[ad]] = true;
        }

        //塗れる色が確定した
        foreach (var c in used)
        {
            if (c.Value == true) { continue; }//使っている色は除外
            //使われていない色を次の頂点で塗る
            DFSPaint(nextIdx, c.Key, ref visited, ref ans);
            //DFSするため、一旦塗り色を消す
            NodeColors[nextNode] = 無色
        }

    }

解説 - AtCoder Beginner Contest 199

まとめ

C問題はちょっとおもしろかった。あとABCでは久々にグラフが出てきた気がする。