AtCoder NoviStepsを埋めてみる(16) 集合（set）

AtCoder NoviStepsを埋めてみる(15) Union-Find 1Qの続きです。今回は集合（set）の問題です。C# の HashSet は「挿入する」「削除する」「検索する」といった処理を高速にこなせるデータ構造です。

Contents

1 027 – Sign Up Requests （★2）
2 C – Σ
3 C – A+B+C
4 C – Max MEX
5 C – Variety Split Easy
6 C – Cards Query Problem
7 D – 星座探し
8 D – Rectangles
9 D – すぬけ君の塗り絵
10 D – Switch Seats
11 D – Bonfire
12 F – Colored Ball
13 E – Isolation
14 E – Tree Game

027 – Sign Up Requests （★2）

問題の概要

文字列が N 回入力される。
これまでに入力された文字列と重複がなければ受理され、そうでなければ無視される。
受理された文字列の番号を答えよ。

解説不要の基本問題です。

class Program
{
    static void Main()
    {
        int N = int.Parse(Console.ReadLine());

        List<int> ans = new List<int>();

        HashSet<string> set = new HashSet<string>();
        for (int i = 0; i < N; i++)
        {
            string s = Console.ReadLine();
            if (!set.Contains(s))
            {
                set.Add(s);
                ans.Add(i + 1);
            }
        }
        foreach (var v in ans)
            Console.WriteLine(v);
    }
}

class Program

{

static void Main()

{

int N = int.Parse(Console.ReadLine());

List<int> ans = new List<int>();

HashSet<string> set = new HashSet<string>();

for (int i = 0; i < N; i++)

{

string s = Console.ReadLine();

if (!set.Contains(s))

{

set.Add(s);

ans.Add(i + 1);

}

foreach (var v in ans)

Console.WriteLine(v);

}

C – Σ

問題の概要

長さ N の正整数列 A および正整数 K が与えられる。
1 以上 K 以下の整数のうち、A の中に一度も現れないものの総和を求めよ。

K が大きいのでA の中に一度も現れないものの総和ではなく、1 から K までの総和を先に求めておき、ここから K 以下の整数で一度でも現れたものを引くことにします。

class Program
{
    static void Main()
    {
        int[] nk = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray();
        int N = nk[0];
        int K = nk[1];
        int[] A = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray();

        HashSet<int> set = new HashSet<int>();
        foreach (int v in A)
        {
            if(v <= K)
                set.Add(v);
        }

        long ans = 1L * K * (K + 1) / 2;
        foreach (int v in set)
            ans -= v;

        Console.WriteLine(ans);
    }
}

class Program

{

static void Main()

{

int[] nk = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray();

int N = nk[0];

int K = nk[1];

int[] A = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray();

HashSet<int> set = new HashSet<int>();

foreach (int v in A)

{

if(v <= K)

set.Add(v);

}

long ans = 1L * K * (K + 1) / 2;

foreach (int v in set)

ans -= v;

Console.WriteLine(ans);

}

C – A+B+C

問題の概要

3 つの数列 A, B, C と数列 X が与えられる。
A, B, C からそれぞれ 1 個ずつ要素を選び、和を X[i] にすることができるか判定せよ。

先に A, B, C からそれぞれ 1 個ずつ要素を選んで和の集合を作っておき、このなかに X[i] があるかどうかを調べれば高速で判定することができます。

class Program
{
    static void Main()
    {
        int N = int.Parse(Console.ReadLine());
        int[] A = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray();

        int M = int.Parse(Console.ReadLine());
        int[] B = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray();

        int L = int.Parse(Console.ReadLine());
        int[] C = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray();

        int Q = int.Parse(Console.ReadLine());
        int[] X = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray();

        HashSet<int> set = new HashSet<int>();
        for (int a = 0; a < N; a++)
        {
            for (int b = 0; b < M; b++)
            {
                for (int c = 0; c < L; c++)
                    set.Add(A[a] + B[b] + C[c]);
            }
        }

        for (int i = 0; i < Q; i++)
            Console.WriteLine(set.Contains(X[i]) ? "Yes" : "No");
    }
}

class Program

{

static void Main()

{

int N = int.Parse(Console.ReadLine());

int[] A = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray();

int M = int.Parse(Console.ReadLine());

int[] B = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray();

int L = int.Parse(Console.ReadLine());

int[] C = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray();

int Q = int.Parse(Console.ReadLine());

int[] X = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray();

HashSet<int> set = new HashSet<int>();

for (int a = 0; a < N; a++)

{

for (int b = 0; b < M; b++)

{

for (int c = 0; c < L; c++)

set.Add(A[a] + B[b] + C[c]);

}

for (int i = 0; i < Q; i++)

Console.WriteLine(set.Contains(X[i]) ? "Yes" : "No");

}

C – Max MEX

長さ N の非負整数列 A が与えられる。
A から K 要素を選んで順序を保ったまま抜き出した列を B としたとき、MEX(B) としてありえる最大値を求めよ。
ただし、MEX(X) は以下の条件を満たす唯一の非負整数 m として定義される。
(定義) 0 ≦ i < m を満たすすべての整数 i が X に含まれるが、m は X に含まれない。

Set に A の値をすべて格納して 0 から K – 1 までの値で存在しないものを探します。最初にみつかったものが解となります。すべて存在する場合は K が解です。

class Program
{
    static void Main()
    {
        int[] nk = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray();
        int N = nk[0];
        int K = nk[1];

        int[] A = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray();

        HashSet<int> set = new HashSet<int>();
        foreach (var v in A)
            set.Add(v);

        int ans = K;
        for (int i = 0; i < K; i++)
        {
            if (!set.Contains(i))
            {
                ans = i;
                break;
            }
        }
        Console.WriteLine(ans);
    }
}

class Program

{

static void Main()

{

int[] nk = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray();

int N = nk[0];

int K = nk[1];

int[] A = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray();

HashSet<int> set = new HashSet<int>();

foreach (var v in A)

set.Add(v);

int ans = K;

for (int i = 0; i < K; i++)

{

if (!set.Contains(i))

{

ans = i;

break;

}

Console.WriteLine(ans);

}

C – Variety Split Easy

問題の概要

長さ N の整数列 A が与えられる。
A を 1 か所で区切って 2 個の空でない連続する部分列に分割するとき、数列に含まれる数の種類数の和としてありえる最大値を求めよ。

B[i] = (初項から A[i] までの種類数)、C[i] = (A[i] から末項までの種類数) となるような数列を生成し、B[i] + C[i + 1] が最大になるようなものを選べばよいです。

class Program
{
    static void Main()
    {
        int N = int.Parse(Console.ReadLine());
        int[] A = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray();

        HashSet<int> set1 = new HashSet<int>();
        int[] B = new int[N];
        for (int i = 0; i < N; i++)
        {
            set1.Add(A[i]);
            B[i] = set1.Count;
        }

        HashSet<int> set2 = new HashSet<int>();
        int[] C = new int[N];
        for (int i = N - 1; i >= 0; i--)
        {
            set2.Add(A[i]);
            C[i] = set2.Count;
        }

        int ans = 0;
        for (int i = 0; i < N - 1; i++)
            ans = Math.Max(ans, B[i] + C[i + 1]);

        Console.WriteLine(ans);
    }
}

class Program

{

static void Main()

{

int N = int.Parse(Console.ReadLine());

int[] A = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray();

HashSet<int> set1 = new HashSet<int>();

int[] B = new int[N];

for (int i = 0; i < N; i++)

{

set1.Add(A[i]);

B[i] = set1.Count;

}

HashSet<int> set2 = new HashSet<int>();

int[] C = new int[N];

for (int i = N - 1; i >= 0; i--)

{

set2.Add(A[i]);

C[i] = set2.Count;

}

int ans = 0;

for (int i = 0; i < N - 1; i++)

ans = Math.Max(ans, B[i] + C[i + 1]);

Console.WriteLine(ans);

}

C – Cards Query Problem

問題の概要

1 から N までの番号がついた N 個の空の箱と、何も書かれていない無数のカードがある。
Q 個のクエリが与えられる。クエリは次の 3 種類のいずれかである。
種類 1 : カードを 1 枚選んで数 i を書き込み、そのカードを箱 j に入れる。
種類 2 : 箱 i に入っているカードに書かれた数を昇順ですべて答える。
（箱 i の中に同じ数が書かれたカードが複数枚あるときは、入っている枚数と同じ回数だけその数を出力する）
種類 3 : 数 i が書かれたカードが入っている箱の番号を昇順ですべて答える。
（数 i が書かれたカードが同じ箱に複数枚入っている場合でも、その箱の番号は 1 度だけ出力する）

問題文には「昇順でソートして出力せよ」とありますが、制約をみると「出力するべき数は合計で 2 ×10^5 個以下」とあるので出力時にソートすれば充分間に合います。

class Program
{
    static void Main()
    {
        int N = int.Parse(Console.ReadLine());
        int Q = int.Parse(Console.ReadLine());

        List<int>[] B = new List<int>[N];
        for (int i = 0; i < N; i++)
            B[i] = new List<int>();

        int max_value = 20 * 10000;
        HashSet<int>[] V = new HashSet<int>[max_value + 1];
        for (int i = 0; i <= max_value; i++)
            V[i] = new HashSet<int>();

        for (int i = 0; i < Q; i++)
        {
            int[] query = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray();
            int t = query[0];
            if (t == 1)
            {
                int v = query[1];
                int b = query[2];
                B[b - 1].Add(v);
                V[v].Add(b);
            }
            if (t == 2)
            {
                int b = query[1] - 1;
                Console.WriteLine(string.Join(" ", B[b].OrderBy(_ => _)));
            }
            if (t == 3)
            {
                int v = query[1];
                Console.WriteLine(string.Join(" ", V[v].OrderBy(_ => _)));
            }
        }
    }
}

class Program

{

static void Main()

{

int N = int.Parse(Console.ReadLine());

int Q = int.Parse(Console.ReadLine());

List<int>[] B = new List<int>[N];

for (int i = 0; i < N; i++)

B[i] = new List<int>();

int max_value = 20 * 10000;

HashSet<int>[] V = new HashSet<int>[max_value + 1];

for (int i = 0; i <= max_value; i++)

V[i] = new HashSet<int>();

for (int i = 0; i < Q; i++)

{

int[] query = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray();

int t = query[0];

if (t == 1)

{

int v = query[1];

int b = query[2];

B[b - 1].Add(v);

V[v].Add(b);

}

if (t == 2)

{

int b = query[1] - 1;

Console.WriteLine(string.Join(" ", B[b].OrderBy(_ => _)));

}

if (t == 3)

{

int v = query[1];

Console.WriteLine(string.Join(" ", V[v].OrderBy(_ => _)));

}

D – 星座探し

問題の概要

写真には探したい星座と同じ形・向き・大きさの図形がちょうど一つ含まれているが、写真の中には星座を構成する星以外に余分な星が写っている可能性がある。
探したい星座の形と写真に写っている星の位置が与えられたとき、星座の座標を写真の中の座標に変換するために平行移動するべき量を答えるプログラムを書け。

探したい星座の最初の星と写真に写っている星のそれぞれが一致すると仮定して考えます。写真のなかから探したい星座の星をすべて見つけることができたらそのときの平行移動量が解となります。

class Program
{
    static void Main()
    {
        int M = int.Parse(Console.ReadLine());
        List<(int, int)> stars1 = new List<(int, int)>();

        for (int i = 0; i < M; i++)
        {
            int[] xy = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray();
            stars1.Add((xy[0], xy[1]));
        }

        int N = int.Parse(Console.ReadLine());
        List<(int, int)> stars2 = new List<(int, int)>();
        HashSet<string> set = new HashSet<string>();

        for (int i = 0; i < N; i++)
        {
            int[] xy = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray();
            stars2.Add((xy[0], xy[1]));
            set.Add($"{xy[0]},{xy[1]}");
        }

        for (int i = 0; i < N; i++)
        {
            // stars1[0] に対応しているのは stars2[i] と仮定する
            int dx = stars2[i].Item1 - stars1[0].Item1;
            int dy = stars2[i].Item2 - stars1[0].Item2;
            if (stars1.All(_ => set.Contains($"{_.Item1 + dx},{_.Item2 + dy}")))
            {
                Console.WriteLine($"{dx} {dy}");
                return;
            }
        }
    }
}

class Program

{

static void Main()

{

int M = int.Parse(Console.ReadLine());

List<(int, int)> stars1 = new List<(int, int)>();

for (int i = 0; i < M; i++)

{

int[] xy = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray();

stars1.Add((xy[0], xy[1]));

}

int N = int.Parse(Console.ReadLine());

List<(int, int)> stars2 = new List<(int, int)>();

HashSet<string> set = new HashSet<string>();

for (int i = 0; i < N; i++)

{

int[] xy = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray();

stars2.Add((xy[0], xy[1]));

set.Add($"{xy[0]},{xy[1]}");

}

for (int i = 0; i < N; i++)

{

// stars1[0] に対応しているのは stars2[i] と仮定する

int dx = stars2[i].Item1 - stars1[0].Item1;

int dy = stars2[i].Item2 - stars1[0].Item2;

if (stars1.All(_ => set.Contains($"{_.Item1 + dx},{_.Item2 + dy}")))

{

Console.WriteLine($"{dx} {dy}");

return;

}

D – Rectangles

問題の概要

2 次元平面上に N 個の相異なる点がある。
これらの点のうち 4 つを頂点とし、全ての辺が x 軸または y 軸に平行であるような長方形はいくつあるか求めよ。

頂点の個数は最大で 2000 個なのでこれらのなかから 4 つ取り出して長方形になるか調べていては TLE してしまいます。

そこで N 個の頂点のなかから X[a] < X[b], Y[a] < Y[b] となるような 2 つの頂点を取り出します。これが長方形の左上と右下の座標になります。残りの 2 つの頂点が存在するかどうかは Set を使えば簡単に判定できます。

class Program
{
    static void Main()
    {
        int N = int.Parse(Console.ReadLine());

        HashSet<string> set = new HashSet<string>();
        List<(int, int)> V = new List<(int, int)> ();
        for (int i = 0; i < N; i++)
        {
            int[] xy = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray();
            int x = xy[0];
            int y = xy[1];
            V.Add((x, y));
            set.Add($"{x},{y}");
        }

        int ans = 0;
        for (int a = 0; a < N; a++)
        {
            for (int b = 0; b < N; b++)
            {
                if (a == b)
                    continue;

                if (V[a].Item1 < V[b].Item1 && V[a].Item2 < V[b].Item2)
                {
                    // (V[a].Item1, V[b].Item2), (V[b].Item1, V[a].Item2) が存在するか？
                    if (set.Contains($"{V[a].Item1},{V[b].Item2}") && set.Contains($"{V[b].Item1},{V[a].Item2}"))
                        ans++;
                }
            }
        }
        Console.WriteLine(ans);
    }
}

class Program

{

static void Main()

{

int N = int.Parse(Console.ReadLine());

HashSet<string> set = new HashSet<string>();

List<(int, int)> V = new List<(int, int)> ();

for (int i = 0; i < N; i++)

{

int[] xy = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray();

int x = xy[0];

int y = xy[1];

V.Add((x, y));

set.Add($"{x},{y}");

}

int ans = 0;

for (int a = 0; a < N; a++)

{

for (int b = 0; b < N; b++)

{

if (a == b)

continue;

if (V[a].Item1 < V[b].Item1 && V[a].Item2 < V[b].Item2)

{

// (V[a].Item1, V[b].Item2), (V[b].Item1, V[a].Item2) が存在するか？

if (set.Contains($"{V[a].Item1},{V[b].Item2}") && set.Contains($"{V[b].Item1},{V[a].Item2}"))

ans++;

}

Console.WriteLine(ans);

}

D – すぬけ君の塗り絵

問題の概要

縦 H 行、横 W 列のマス目からなる盤がある。
初期状態ではすべての目が白く塗られている。
このうち N マスを黒く塗りつぶした。
各整数 j (0 ≦ j ≦ 9) について、盤の中に完全に含まれるすべての 3 行 3 列の連続するマス目のうち、黒いマスがちょうど j 個あるものの個数をそれぞれ求めよ。

黒く塗りつぶしたマスを含む 3 行 3 列のブロックの個数を数えます。黒いマスを含まないブロックの数は全体の個数である (H – 2) × (W – 2) から黒マスが 1 ～ 9 個あるものの総和を引くことで求めることができます。

class Program
{
    static void Main()
    {
        int[] hwn = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray();
        int H = hwn[0];
        int W = hwn[1];
        int N = hwn[2];

        List<(int, int)> V = new List<(int, int)>();
        for (int i = 0; i < N; i++)
        {
            int[] rc = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray();
            int r = rc[0];
            int c = rc[1];
            V.Add((r, c));
        }

        Dictionary<string, int> dic = new Dictionary<string, int>();
        foreach (var v in V)
        {
            int r = v.Item1;
            int c = v.Item2;
            for (int dr = 0; dr < 3; dr++)
            {
                for (int dc = 0; dc < 3; dc++)
                {
                    // (r - dr, c - dc) を左上とする 3 × 3 ブロックが H × W の盤内に存在するか？
                    if (c - dc <= 0 || c - dc + 2 > W || r - dr <= 0 || r - dr + 2 > H)
                        continue; // 存在しない

                    string key = $"{r - dr},{c - dc}";
                    if(!dic.ContainsKey(key))
                        dic.Add(key, 0);
                    dic[key]++;
                }
            }
        }

        long[] ans = new long[10];
        ans[0] = 1L * (H - 2) * (W - 2);
        for (int i = 1; i <= 9; i++)
        {
            ans[i] = dic.Count(_ => _.Value == i);
            ans[0] -= ans[i];
        }

        foreach (long v in ans)
            Console.WriteLine(v);
    }
}

class Program

{

static void Main()

{

int[] hwn = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray();

int H = hwn[0];

int W = hwn[1];

int N = hwn[2];

List<(int, int)> V = new List<(int, int)>();

for (int i = 0; i < N; i++)

{

int[] rc = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray();

int r = rc[0];

int c = rc[1];

V.Add((r, c));

}

Dictionary<string, int> dic = new Dictionary<string, int>();

foreach (var v in V)

{

int r = v.Item1;

int c = v.Item2;

for (int dr = 0; dr < 3; dr++)

{

for (int dc = 0; dc < 3; dc++)

{

// (r - dr, c - dc) を左上とする 3 × 3 ブロックが H × W の盤内に存在するか？

if (c - dc <= 0 || c - dc + 2 > W || r - dr <= 0 || r - dr + 2 > H)

continue; // 存在しない

string key = $"{r - dr},{c - dc}";

if(!dic.ContainsKey(key))

dic.Add(key, 0);

dic[key]++;

}

long[] ans = new long[10];

ans[0] = 1L * (H - 2) * (W - 2);

for (int i = 1; i <= 9; i++)

{

ans[i] = dic.Count(_ => _.Value == i);

ans[0] -= ans[i];

}

foreach (long v in ans)

Console.WriteLine(v);

}

D – Switch Seats

問題の概要

N 組のカップルが一列に座っている。
2 組のカップルであって、もともと両方のカップルは隣り合わせで座っておらず、かつ 4 人の間で席を交換することで両方のカップルが隣り合わせで座れるようになる組の個数を数えよ。

数えるべき組とは ab…ab, ab…ba, abab の 3 パターンです（abba は不適）。

隣り合わせで座っているカップルは除外します。それ以外で隣り合っている値のペア（ab と ba は同一）の個数を数えて 2 回出てきたペアを数えればいいのですが、注意する点があります。

[1, 2, 1, …] のようなとき、この段階で 1, 2 のペアが 2 回と数えてしまわないようにしなければなりません。同じペアが連続して出現したときは無視してペアがある区間が重複しないようにします。

class Program
{
    static void Main()
    {
        int T = int.Parse(Console.ReadLine());

        for (int i = 0; i < T; i++)
        {
            int ans = Solve();
            Console.WriteLine(ans);
        }

        int Solve()
        {
            int N = int.Parse(Console.ReadLine());
            int[] A = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray();

            int M = N * 2;
            HashSet<int> ng = new HashSet<int>();
            for (int i = 0; i < M - 1; i++)
            {
                if (A[i] == A[i + 1])
                    ng.Add(A[i]);
            }

            Dictionary<string, int> pairCounts = new Dictionary<string, int>();
            Dictionary<string, int> pairIndexes = new Dictionary<string, int>();
            for (int i = 0; i < M - 1; i++)
            {
                if (!ng.Contains(A[i]) && !ng.Contains(A[i + 1]))
                {
                    int x = A[i];
                    int y = A[i + 1];
                    if (A[i] > A[i + 1])
                    {
                        x = A[i + 1];
                        y = A[i];
                    }
                    string key = $"{x},{y}";
                    if (!pairCounts.ContainsKey(key)) // 1 回目
                    {
                        pairCounts.Add(key, 1);
                        pairIndexes.Add(key, i);
                    }
                    else if (pairIndexes[key] != i - 1) // 2 回目 ( [1, 2, 1, ...] のようなときに注意！)
                        pairCounts[key]++;
                }
            }
            return pairCounts.Count(_ => _.Value == 2);
        }
    }
}

class Program

{

static void Main()

{

int T = int.Parse(Console.ReadLine());

for (int i = 0; i < T; i++)

{

int ans = Solve();

Console.WriteLine(ans);

}

int Solve()

{

int N = int.Parse(Console.ReadLine());

int[] A = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray();

int M = N * 2;

HashSet<int> ng = new HashSet<int>();

for (int i = 0; i < M - 1; i++)

{

if (A[i] == A[i + 1])

ng.Add(A[i]);

}

Dictionary<string, int> pairCounts = new Dictionary<string, int>();

Dictionary<string, int> pairIndexes = new Dictionary<string, int>();

for (int i = 0; i < M - 1; i++)

{

if (!ng.Contains(A[i]) && !ng.Contains(A[i + 1]))

{

int x = A[i];

int y = A[i + 1];

if (A[i] > A[i + 1])

{

x = A[i + 1];

y = A[i];

}

string key = $"{x},{y}";

if (!pairCounts.ContainsKey(key)) // 1 回目

{

pairCounts.Add(key, 1);

pairIndexes.Add(key, i);

}

else if (pairIndexes[key] != i - 1) // 2 回目 ( [1, 2, 1, ...] のようなときに注意！)

pairCounts[key]++;

}

return pairCounts.Count(_ => _.Value == 2);

}

D – Bonfire

問題の概要

無限に広い 2 次元グリッドがあり、このグリッドの座標 (0,0) に焚き火がある。
時刻 t = 0 では、マス (0, 0) にのみ煙が存在する。
N, W, S, E からなる長さ N の文字列 S が与えられる。文字は各時刻の風向きを示す。
各時刻においてすべての煙が風の方向に移動し、(0, 0) に煙が存在しない場合、新たな煙がマス (0, 0) に生成される。
各時刻において座標 X (R,C) に煙が存在するか判定せよ。

時間の経過とともに煙が増えていきます。その煙をすべて移動させようとすると TLE するので焚き火と座標 X を風向きとは逆方向に移動させます。焚き火が煙のない位置にある場合はその位置に煙を生成します。

class Program
{
    static void Main()
    {
        int[] nrc = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray();
        int N = nrc[0];
        int R = nrc[1];
        int C = nrc[2];

        string S = Console.ReadLine();

        int r = 0;
        int c = 0;

        HashSet<string> set = new HashSet<string>();
        set.Add($"{r},{c}");

        char[] ans = new char[S.Length];
        for (int i = 0; i < S.Length; i++)
        {
            char ch = S[i];
            if (ch == 'N')
            {
                R++;
                r++;
            }
            if (ch == 'W')
            {
                C++;
                c++;
            }
            if (ch == 'S')
            {
                R--;
                r--;
            }
            if (ch == 'E')
            {
                C--;
                c--;
            }
            set.Add($"{r},{c}");

            ans[i] = set.Contains($"{R},{C}") ? '1' :'0';
        }
        Console.WriteLine(new string(ans));
    }
}

class Program

{

static void Main()

{

int[] nrc = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray();

int N = nrc[0];

int R = nrc[1];

int C = nrc[2];

string S = Console.ReadLine();

int r = 0;

int c = 0;

HashSet<string> set = new HashSet<string>();

set.Add($"{r},{c}");

char[] ans = new char[S.Length];

for (int i = 0; i < S.Length; i++)

{

char ch = S[i];

if (ch == 'N')

{

R++;

r++;

}

if (ch == 'W')

{

C++;

c++;

}

if (ch == 'S')

{

R--;

r--;

}

if (ch == 'E')

{

C--;

c--;

}

set.Add($"{r},{c}");

ans[i] = set.Contains($"{R},{C}") ? '1' :'0';

}

Console.WriteLine(new string(ans));

}

F – Colored Ball

問題の概要

N 個の箱があり、はじめ箱 i には色 C[i] のボールが 1 つ入っている。
箱 a のボールをすべて箱 b に移す操作を Q 回おこなう。
各操作の直後において、箱 b に何種類の色のボールが入っているかを出力せよ。

箱 a のボールをすべて箱 b に移す操作をうまくやらないと TLE してしまいます。TLE するケースとして予想されるのは箱 a に入っているボールの種類 > 箱 b に入っているボールの種類数である移動が何度もおこなわれる場合です。

このようなときはボールの種類が少ないほうから多いほうへ移動させ、箱を入れ替えます。これで TLE は回避できます。

class Program
{
    static void Main()
    {
        int[] nq = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray();
        int N = nq[0];
        int Q = nq[1];

        int[] C = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray();

        HashSet<int>[] sets = new HashSet<int>[N];
        for (int i = 0; i < N; i++)
        {
            sets[i] = new HashSet<int>();
            sets[i].Add(C[i]);
        }

        for (int i = 0; i < Q; i++)
        {
            int[] query = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray();
            int a = query[0] - 1;
            int b = query[1] - 1;

            if (sets[a].Count < sets[b].Count)
            {
                foreach (var item in sets[a])
                    sets[b].Add(item);
                sets[a].Clear();
            }
            else
            {
                foreach (var item in sets[b])
                    sets[a].Add(item);
                sets[b] = sets[a];
                sets[a] = new HashSet<int>();
            }
            Console.WriteLine(sets[b].Count);
        }
    }
}

class Program

{

static void Main()

{

int[] nq = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray();

int N = nq[0];

int Q = nq[1];

int[] C = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray();

HashSet<int>[] sets = new HashSet<int>[N];

for (int i = 0; i < N; i++)

{

sets[i] = new HashSet<int>();

sets[i].Add(C[i]);

}

for (int i = 0; i < Q; i++)

{

int[] query = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray();

int a = query[0] - 1;

int b = query[1] - 1;

if (sets[a].Count < sets[b].Count)

{

foreach (var item in sets[a])

sets[b].Add(item);

sets[a].Clear();

}

else

{

foreach (var item in sets[b])

sets[a].Add(item);

sets[b] = sets[a];

sets[a] = new HashSet<int>();

}

Console.WriteLine(sets[b].Count);

}

E – Isolation

問題の概要

N 頂点 0 辺の無向グラフがある。
Q 個のクエリが与えられるので、各クエリの後における「他のどの頂点とも辺で結ばれていない頂点」の数を出力せよ。
タイプ 1 : 頂点 u と頂点 v を辺で結ぶ。
タイプ 2 : 頂点 v と他の頂点を結ぶ辺をすべて削除する。

ある頂点から辺で結ばれている別の頂点を Set で管理します。

他のどの頂点とも辺で結ばれていない頂点を「孤立した頂点」と呼び、その個数を cnt と表記することにします。孤立した頂点を辺で結ぶと cnt は 1 減ります。頂点 v と他の頂点を結ぶ辺をすべて削除すれば、頂点 v と結ばれている頂点が存在する場合、cnt が 1 増えます。また頂点 v と結ばれている頂点が頂点 v とのみ結ばれていた場合はその個数だけ cnt は増えます。

class Program
{
    static void Main()
    {
        int[] nq = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray();
        int N = nq[0];
        int Q = nq[1];

        HashSet<int>[] nexts = new HashSet<int>[N];
        for (int i = 0; i < N; i++)
            nexts[i] = new HashSet<int>();

        List<int> ans = new List<int>();
        int cnt = N;
        for (int i = 0; i < Q; i++)
        {
            int[] query = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray();
            int t = query[0];

            if (t == 1)
            {
                int u = query[1] - 1;
                int v = query[2] - 1;
                if (nexts[u].Count == 0) // 頂点 u は孤立した頂点から孤立した頂点ではなくなる
                    cnt--;
                if (nexts[v].Count == 0) // 同
                    cnt--;
                nexts[u].Add(v);
                nexts[v].Add(u);
            }
            if (t == 2)
            {
                int u = query[1] - 1;
                if (nexts[u].Count > 0)
                {
                    foreach (var next in nexts[u]) // 頂点 u への辺を削除
                    {
                        nexts[next].Remove(u);
                        if (nexts[next].Count == 0)
                            cnt++;
                    }
                    nexts[u].Clear(); // 頂点 u は孤立した頂点になる
                    cnt++;
                }
            }
            ans.Add(cnt);
        }
        foreach (var v in ans)
            Console.WriteLine(v);
    }
}

class Program

{

static void Main()

{

int[] nq = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray();

int N = nq[0];

int Q = nq[1];

HashSet<int>[] nexts = new HashSet<int>[N];

for (int i = 0; i < N; i++)

nexts[i] = new HashSet<int>();

List<int> ans = new List<int>();

int cnt = N;

for (int i = 0; i < Q; i++)

{

int[] query = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray();

int t = query[0];

if (t == 1)

{

int u = query[1] - 1;

int v = query[2] - 1;

if (nexts[u].Count == 0) // 頂点 u は孤立した頂点から孤立した頂点ではなくなる

cnt--;

if (nexts[v].Count == 0) // 同

cnt--;

nexts[u].Add(v);

nexts[v].Add(u);

}

if (t == 2)

{

int u = query[1] - 1;

if (nexts[u].Count > 0)

{

foreach (var next in nexts[u]) // 頂点 u への辺を削除

{

nexts[next].Remove(u);

if (nexts[next].Count == 0)

cnt++;

}

nexts[u].Clear(); // 頂点 u は孤立した頂点になる

cnt++;

}

ans.Add(cnt);

}

foreach (var v in ans)

Console.WriteLine(v);

}

E – Tree Game

この問題はインタラクティブな問題である。
N 頂点からなる木 G が与えられる。この木 G を使ってゲームをする。
まず先手後手を決め、先手から順に交互に以下の操作をおこなう。
まだ両者のあいだに辺が存在しないふたつの頂点を選ぶ。
ただしこの頂点間に辺を追加することで奇閉路ができる場合、これを選ぶことはできない。
操作を行えなくなった方が負けであり、負けでない方が勝ち。
実際にゲームをして勝つ操作とは？

木は二部グラフですが、彩色したあと同じ色の頂点を辺で繋いでしまうと奇閉路ができてしまいます。なので、異なる色の頂点を辺で繋いでいきます。そのような頂点のペアが奇数個あるのであれば先手を選択し、偶数個なら後手を選択します。

using AtCoder;

class Program
{
    static void Main()
    {
        int N = int.Parse(Console.ReadLine());

        // 入力を受け取り Union-Find で二部グラフを構築する
        Dsu dsu = new Dsu(N * 2);
        HashSet<string> edges = new HashSet<string>(); // すでに辺でつながっているので手としては使えない

        for (int i = 0; i < N - 1; i++)
        {
            int[] uv = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray();
            int u = uv[0] - 1;
            int v = uv[1] - 1;
            dsu.Merge(u, v + N);
            dsu.Merge(u + N, v);

            int min = Math.Min(u, v);
            int max = Math.Max(u, v);
            edges.Add($"{min} {max}");
        }
        List<int> B = new List<int>();
        List<int> W = new List<int>();
        for (int i = 0; i < N; i++)
        {
            if(dsu.Same(0, i)) // 頂点 0 と同じグループなら「黒」、そうでないなら「白」
                B.Add(i);
            else
                W.Add(i);
        }

        HashSet<string> hands = new HashSet<string>(); // 着手の候補
        foreach (var b in B)
        {
            foreach (var w in W)
            {
                int min = Math.Min(b, w);
                int max = Math.Max(b, w);
                if (!edges.Contains($"{min} {max}")) // 色違いで辺で繋がっていないなら着手可能
                    hands.Add($"{min + 1} {max + 1}");
            }
        }

        bool isFirst = hands.Count % 2 == 1 ? true : false; // 着手可能点の偶奇で先手後手を決める
        Console.WriteLine(isFirst ? "First" : "Second");

        if (isFirst)
        {
            string first = hands.First(); // 着手候補のうち、最初にみつけたものを採用する
            hands.Remove(first); // 着手したら候補から取り除く
            Console.WriteLine(first);
        }

        while (true)
        {
            string s = Console.ReadLine(); // 相手の着手
            if (s == "-1 -1") // 相手の負け
                break;

            // 相手の着手を候補から取り除く
            int[] uv = s.Split().Select(_ => int.Parse(_)).ToArray();
            int u = uv[0];
            int v = uv[1];
            int min = Math.Min(u, v);
            int max = Math.Max(u, v);
            hands.Remove($"{min} {max}");

            // 自分の着手。最初に見つけたものを採用し、候補から取り除く
            string hand = hands.First();
            hands.Remove(hand);
            Console.WriteLine(hand);
        }
    }
}

using AtCoder;

class Program

{

static void Main()

{

int N = int.Parse(Console.ReadLine());

// 入力を受け取り Union-Find で二部グラフを構築する

Dsu dsu = new Dsu(N * 2);

HashSet<string> edges = new HashSet<string>(); // すでに辺でつながっているので手としては使えない

for (int i = 0; i < N - 1; i++)

{

int[] uv = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray();

int u = uv[0] - 1;

int v = uv[1] - 1;

dsu.Merge(u, v + N);

dsu.Merge(u + N, v);

int min = Math.Min(u, v);

int max = Math.Max(u, v);

edges.Add($"{min} {max}");

}

List<int> B = new List<int>();

List<int> W = new List<int>();

for (int i = 0; i < N; i++)

{

if(dsu.Same(0, i)) // 頂点 0 と同じグループなら「黒」、そうでないなら「白」

B.Add(i);

else

W.Add(i);

}

HashSet<string> hands = new HashSet<string>(); // 着手の候補

foreach (var b in B)

{

foreach (var w in W)

{

int min = Math.Min(b, w);

int max = Math.Max(b, w);

if (!edges.Contains($"{min} {max}")) // 色違いで辺で繋がっていないなら着手可能

hands.Add($"{min + 1} {max + 1}");

}

bool isFirst = hands.Count % 2 == 1 ? true : false; // 着手可能点の偶奇で先手後手を決める

Console.WriteLine(isFirst ? "First" : "Second");

if (isFirst)

{

string first = hands.First(); // 着手候補のうち、最初にみつけたものを採用する

hands.Remove(first); // 着手したら候補から取り除く

Console.WriteLine(first);

}

while (true)

{

string s = Console.ReadLine(); // 相手の着手

if (s == "-1 -1") // 相手の負け

break;

// 相手の着手を候補から取り除く

int[] uv = s.Split().Select(_ => int.Parse(_)).ToArray();

int u = uv[0];

int v = uv[1];

int min = Math.Min(u, v);

int max = Math.Max(u, v);

hands.Remove($"{min} {max}");

// 自分の着手。最初に見つけたものを採用し、候補から取り除く

string hand = hands.First();

hands.Remove(hand);

Console.WriteLine(hand);

}

AtCoder NoviStepsを埋めてみる(16) 集合（set）

027 – Sign Up Requests （★2）

C – Σ

C – A+B+C

C – Max MEX

C – Variety Split Easy

C – Cards Query Problem

D – 星座探し

D – Rectangles

D – すぬけ君の塗り絵

D – Switch Seats

D – Bonfire

F – Colored Ball

E – Isolation

E – Tree Game

鳩でも分かるC#管理人からのお願い

コメントについて

管理人のモチベーションアップのために

コメントをどうぞ