AGC第二回。2完397位/662人で惨敗。
整数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");
箱が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());
長さ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);
閃けばひどく単純に解けるが、思いつかないとかなり嵌るタイプの問題だった。
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()を実装していなかったので追加しておいた。