【プログラミングコンテスト】全国統一プログラミング王決定戦予選⑤
朝から環境構築という名の自分の部屋の大掃除をしていました、ねむーです。
今回はAtCoder(https://atcoder.jp/contests/nikkei2019-qual)にて開催されました、全国統一プログラミング王決定戦予選の第五回目です。
今回は、第五問「E - Weights on Vertices and Edges」の問題と僕との戦闘記です。
0.はじめに
1.問題文
N 頂点 M 辺の連結な無向グラフがあります。 頂点には 1 から N までの番号が、辺には 1 から M までの番号がついています。 また、各頂点、各辺にはそれぞれ重みが定められています。 頂点 i の重みは X i です。 辺 i は頂点 A i と B i を結ぶ辺で、その重みは Y i です。
グラフから辺を 0 本以上削除して、次の条件が満たされるようにしたいです。
削除されていない任意の辺について、その辺を含む連結成分の頂点の重みの総和が、その辺の重み以上である。 最小で何本の辺を消す必要があるかを求めてください。
2.入力例
入力
入力は以下の形式で標準入力から与えられる。
N X_(1) X_(2) ... X(N) A_(1) B_(1) Y_(1) .. A_(M) B_(M) Y_(M)
出力
最小で何本の辺を消す必要があるかを出力せよ。
3.コンテスト終わってから見た時の初見の感想(本番は解けなかったので…)
- 入力の分割とパースが必要
- 図は書けて問題の意味は分かった
- グラフが繋がってる判定をどのように調べればよいか？…(圧倒的挫折)
4.入出力例
こればっかりは実際に書いてイメージすることが重要だと思いました。
入力
4 4 2 3 5 7 1 2 7 1 3 9 2 3 12 3 4 18
入力されたグラフは次のようなものです。
出力
2
辺 3 , 4 を削除したとします。 このとき、辺 1 を含む連結成分は、頂点 1 , 2 , 3 からなる連結成分であり、頂点の重みの総和は 2+3+5=10 です。 辺 1 の重みは 7 なので、辺 1 については条件を満たしています。 また同様に、辺 2 についても条件を満たしています。 よって、辺を 2 本削除することで条件を満たすグラフが得られます。
辺を 1 本以下削除することによって条件を満たすことはできないので、答えは 2 になります。
5.他の人のコードを読んだ学び
- そもそも辺はどう表せるか？辺はどういう情報で区別できるか？
→始点と終点の情報と重みの情報で一意に決定できる！
これをクラスにまとめます！
- 端点はどう表せるか？
→番号で区別できる！
さらに、繋がってる辺の情報も呼び出せると便利そうでは？というところに気付くのが重要そうですね…
- 求めたい状態ってどんな状態？
一言でいうと、最もコストが重い辺から順に辺を消していった時に最初に条件を満たした状態です！
この時、辺を消すときに端点が他にどこにもつながってなければ消去する必要がありますね…
ただ、この処理を行うのはナンセンスです！
なぜなら下のように辺の重さ順に木構造を上げる段階で、すでに端点接続状態が現れているからです！
下の図では上から2段階目の時に条件を満たす構造になっています
これを端点接続情報として捉えるのではなく、組み上げるステップとして保存するのが重要なのですね
ここでは例として、一番下から順に見ていきます
一番下の構造は辺の重み18が条件を満たしません…
下から2番目の構造は辺の重み12が条件を満たしません…
下から３番目は条件を満たしてる！！！
といった具合で探索をしていくのが主な方針です
- UnionFindという考え方
詳しくはこちらのスライドを見てもらえると理解できるかと…(僕も理解するのに苦労しました)
今回はグラフを結合する部分に使用しています！
今回もすごく勉強になりました…
5.簡単なコードの解説
- 入力のパース
public int N, M;
public Graph G;
public long[] X;
{
var line = Input.ReadIntArray();
N = line[0];
M = line[1];
}
X = Input.ReadLongArray();
- 端点(Node)と辺(Edge)のクラス作成
internal class Node
{
public List<Edge> Edges;
public int Dist;
public int No;
public Node(int no)
{
this.No = no;
Dist = int.MaxValue;
Edges = new List<Edge>();
}
}
internal class Edge
{
public int From;
public int To;
public long Cost;
public Edge Rev;
public Edge(int fr, int to, long cost = 0)
{
From = fr;
To = to;
Cost = cost;
}
public bool IsRev(Edge e)
{
return Rev != null && (e == Rev);
}
}
- 辺を重み順にソートし、辺の重みが小さい順にくみ上げます
// 小さい方からソート
Edges.Sort((e1, e2) => e1.Cost.CompareTo(e2.Cost));
// UnionFindを作りながら、情報を整理
var isNG = new bool[M];
var prev1 = new int[M];
var prev2 = new int[M];
var uf = new UnionFind(N, X);
for (int i = 0; i < M; i++)
{
var e = Edges[i];
var tpl = uf.Unite(e.From, e.To, i);
// uniteした重みと、以前Uniteした場所を保持する
long weight = tpl.Item1;
if (weight < e.Cost) isNG[i] = true;
Console.WriteLine(weight);
Console.WriteLine(e.Cost);
prev1[i] = tpl.Item2;
prev2[i] = tpl.Item3;
}
- 辺の重みが大きい順に条件を満たしているかチェックし、何個辺を消去したところで条件を満たしたかを出力
// 上から順に見ていく
int ret = 0;
bool[] flags = new bool[M];
if (M > 0) flags[M - 1] = true;
for (int i = M - 1; i >= 0; i--)
{
if (flags[i] && isNG[i])
{
ret++;
if (prev1[i] != -1) flags[prev1[i]] = true;
if (prev2[i] != -1) flags[prev2[i]] = true;
}
}
Console.WriteLine(ret);
6.全コード
internal class Solution
{
public int N, M;
public Graph G;
public long[] X;
public void Run()
{
// Input
{
var line = Input.ReadIntArray();
N = line[0];
M = line[1];
}
X = Input.ReadLongArray();
var Edges = new List<Edge>();
for (int i = 0; i < M; i++)
{
var line = Input.ReadIntArray();
int u = line[0] - 1;
int v = line[1] - 1;
long y = line[2];
var e1 = new Edge(u, v, y);
Edges.Add(e1);
}
// 小さい方からソート
Edges.Sort((e1, e2) => e1.Cost.CompareTo(e2.Cost));
// UnionFindを作りながら、情報を整理
var isNG = new bool[M];
var prev1 = new int[M];
var prev2 = new int[M];
var uf = new UnionFind(N, X);
for (int i = 0; i < M; i++)
{
var e = Edges[i];
var tpl = uf.Unite(e.From, e.To, i);
// uniteした重みと、以前Uniteした場所を保持する
long weight = tpl.Item1;
if (weight < e.Cost) isNG[i] = true;
prev1[i] = tpl.Item2;
prev2[i] = tpl.Item3;
}
// 上から順に見ていく
int ret = 0;
bool[] flags = new bool[M];
if (M > 0) flags[M - 1] = true;
for (int i = M - 1; i >= 0; i--)
{
if (flags[i] && isNG[i])
{
ret++;
if (prev1[i] != -1) flags[prev1[i]] = true;
if (prev2[i] != -1) flags[prev2[i]] = true;
}
}
Console.WriteLine(ret);
}
}
internal class Graph
{
public List<Node> Nodes;
public Node this[int i]
{
set { Nodes[i] = value; }
get { return Nodes[i]; }
}
public Graph(int N)
{
Nodes = new List<Node>();
for (int i = 0; i < N; i++)
{
Nodes.Add(new Node(i));
}
}
}
internal class Node
{
public List<Edge> Edges;
public int Dist;
public int No;
public Node(int no)
{
this.No = no;
Dist = int.MaxValue;
Edges = new List<Edge>();
}
}
internal class Edge
{
public int From;
public int To;
public long Cost;
public Edge Rev;
public Edge(int fr, int to, long cost = 0)
{
From = fr;
To = to;
Cost = cost;
}
public bool IsRev(Edge e)
{
return Rev != null && (e == Rev);
}
}
// libs ----------
class UnionFind
{
public List<int> Par;
public List<int> Sizes;
public List<int> PrevMerged;
public List<long> Weight;
public UnionFind(int n, long[] X)
{
Par = new List<int>();
Sizes = new List<int>();
PrevMerged = new List<int>();
Weight = new List<long>();
for (int i = 0; i < n; i++)
{
Par.Add(i);
Sizes.Add(1);
PrevMerged.Add(-1);
Weight.Add(X[i]);
}
}
public int Find(int x)
{
if (x == Par[x]) return x;
Par[x] = Find(Par[x]);
return Par[x];
}
public Tuple<long, int, int> Unite(int x, int y, int i)
{
x = Find(x);
y = Find(y);
if (x == y)
{
var tpl0 = Tuple.Create(Weight[x], PrevMerged[x], -1);
PrevMerged[x] = i;
return tpl0;
}
if (Sizes[x] < Sizes[y])
{
// swap
int temp = x;
x = y;
y = temp;
}
var tpl = Tuple.Create(Weight[x] + Weight[y], PrevMerged[x], PrevMerged[y]);
Par[y] = x;
Sizes[x] += Sizes[y];
Sizes[y] = 0;
Weight[x] += Weight[y];
Weight[y] = 0;
PrevMerged[x] = i;
PrevMerged[y] = -1;
return tpl;
}
public bool Same(int x, int y)
{
return Find(x) == Find(y);
}
public int Size(int x)
{
return Sizes[Find(x)];
}
}
// common ----------
internal static class Input
{
public static string ReadString()
{
string line = Console.ReadLine();
return line;
}
public static int ReadInt()
{
string line = Console.ReadLine();
return int.Parse(line);
}
public static int[] ReadIntArray()
{
string line = Console.ReadLine();
return line.Split(' ').Select(int.Parse).ToArray();
}
public static long ReadLong()
{
string line = Console.ReadLine();
return long.Parse(line);
}
public static long[] ReadLongArray()
{
string line = Console.ReadLine();
return line.Split(' ').Select(long.Parse).ToArray();
}
public static double[] ReadDoubleArray()
{
string line = Console.ReadLine();
return line.Split(' ').Select(double.Parse).ToArray();
}
}
internal class Program
{
public static void Main(string[] args)
{
var s = new Solution();
s.Run();
}
}
7.最後に
この問題の解き方を理解するのに、時間がかかったので更新が少しく遅くなってました(汗)
最近スターを押してくれる方がいらっしゃって嬉しいです！(スターを押してくれた方のブログもみて勉強してたり…)
元々は自分の勉強ノート代わりにしているので、できるだけわかりやすく書いてるつもりですが…わからないことなどあればコメント頂ければ一緒に考えます…(必ず解決できるとは言ってない)
Youtuberみたいな言い回しで恥ずかしいですが…スター押してもらえると喜びます！
