AGC002の参加日記

AGC第二回。2完397位/662人で惨敗。

A - Range Product

整数a,bが与えられたとき、a, a+1, ..., bすべての積の符号を求めよ。

aとbが両方負のときは、個数の偶奇で解が変わる。

if (a > 0 && b > 0)
    Console.WriteLine("Positive");
else if ( (a <= 0 && b >= 0) || (a >= 0 && b <= 0))
    Console.WriteLine("Zero");
else
    Console.WriteLine(Math.Abs(a - b) % 2 == 0 ? "Negative" : "Positive");


B - Box and Ball

箱がN個あり、1番目の箱には赤いボールが、それ以外の箱には白いボールが1つずつ入っている。以下のM回の操作を行ったとき、最終的に赤いボールが入っている可能性のある箱は何個か。
・箱xからボールを取り出し、箱yに移す

それぞれの箱に入っているボールの数と、赤いボールが入っているかもしれない箱の集合を保持しながらシミュ―レーションする。ボールの数を管理しないと、箱が空になる場合に対処できない。

var num = new int[n + 1];
for (int i = 1; i < n + 1; i++) num[i] = 1;

var ret = new HashSet<int>() { 1 };
for (int i = 0; i < m; i++)
{
    str = Console.ReadLine().Split();
    var x = Int32.Parse(str[0]);
    var y = Int32.Parse(str[1]);

    if (ret.Contains(x)) ret.Add(y);
    num[x]--;
    num[y]++;
    if (num[x] == 0) ret.Remove(x);
}
Console.WriteLine(ret.Count());


C - Knot Puzzle

長さa[1], a[2], … a[N]のロープがある。1<=i<=N-1について、ロープiの右端とロープi+1の左端が結ばれている。繋がれているロープの長さの合計がL以上なら、どれか一つを解くことができる。すべての結び目を解くことは可能か。可能ならその手順も出力せよ。
2 <= N <= 10^5
1 <= a[i] <= 10^9
1 <= L <= 10^9

最後に残る2つのロープの合計長がL以上なら、そこに至るまでの手順はどのようでもよい。よって、長さがL以上になる2つの連続するロープを探し、そこだけを残して左右から解けばよい。

var tgt = -1;
for (int i = 0; i < n - 1; i++)
{
    if (a[i] + a[i + 1] >= l)
    {
        tgt = i;
        break;
    }
}

if (tgt == -1)
{
    Console.WriteLine("Impossible");
    return;
}

Console.WriteLine("Possible");
for (int i = 0; i < tgt; i++)
    Console.WriteLine(i + 1);
for (int i = n - 1; i > tgt; i--)
    Console.WriteLine(i);

閃けばひどく単純に解けるが、思いつかないとかなり嵌るタイプの問題だった。


D - Stamp Rally

N頂点M辺の無向グラフがある。頂点は1~N、辺は1~Mに番号が振ってある。以下のクエリごとの最小スコアを求めよ。
・頂点xとy、および整数zが与えられる
・xまたはyから任意に頂点を訪れていく
・訪れた頂点数がzになったとき、辺の番号の最大値がスコアとなる
3 <= N <= 10^6
N-1 <= M <= 10^5
1 <= クエリ数(Q) <= 10^5

「クエリjのスコアをk以下にできるか?」という判定で二分探索をする。スコアがk以下になるかどうかは、UnionFindに辺1からkまでの頂点を結合していき、xとyが含まれる集合の頂点数がz以上になっているかで判断できる。
クエリの数が多いので、二分探索は並列に行わないと間に合わない。

class Query
{
    public int X;
    public int Y;
    public int Z;

    //最終解が(left, Right]に存在する
    public int Left;
    public int Right;        
}

こんな風にクエリごとに二分探索のLeftとRightを持ち、エッジ1~Nのループ内で、今のエッジ番号がkに一致するクエリをアップデートしていく。

while (true)
{
    if (queries.Count(v => v.Right - v.Left > 1) == 0) break;

    var tgts = new Dictionary<int, List<Query>>();

    //これだと通らない。まだv.Leftが解答の可能性が残っている
    //foreach (var query in queries.Where(v => v.Right - v.Left > 1))
    foreach(var query in queries)
    {
        var mid = (query.Left + query.Right) / 2;
        if (!tgts.ContainsKey(mid)) tgts.Add(mid, new List<Query>());
        tgts[mid].Add(query);
    }
    if (tgts.Count() == 0) break;
                
    var unionFind = new UnionFind(n);
    for (int e = 0; e < m; e++)
    {
        unionFind.Unite(edges[e].Item1, edges[e].Item2);  //2頂点を結合
        if (tgts.ContainsKey(e))
        {
            foreach (var query in tgts[e])    //どれかのクエリの (Left + Right) / 2 なら該当クエリをアップデート
            {
                var sum = unionFind.Size(query.X);
                if (!unionFind.Same(query.X, query.Y)) sum += unionFind.Size(query.Y);
                if (sum >= query.Z)
                    query.Right = e;
                else
                    query.Left = e;
            }
        }
    }
}

手持ちのUnionFindにSize()を実装していなかったので追加しておいた。