ac-library-csharpを使ってみるの続きです。ac-library-csharpだけでなく自作のライブラリをひとつのファイルに統合する方法を解説します。
SourceExpanderとSourceExpander.Embedder
競技プログラミングをやっていると自作ライブラリを使えないか考えたくなるものです。自作ライブラリもSourceExpanderを使えばひとつの提出用のファイルにまとめることができます。
ただし、SourceExpanderの仕様上の制約からライブラリは実行プロジェクトと別でなければなりません。そこでソリューションエクスプローラーでソリューションを右クリックして、「追加」→「新しいプロジェクト」でライブラリ用のプロジェクトを作成しましょう。そしてプロジェクト参照の追加からこのライブラリ用のプロジェクトを追加しておきます。
そのあと追加したライブラリ用のプロジェクトを右クリックして「NuGetパッケージの管理」でNuGet管理画面を開き、SourceExpander.Embedder をインストールします。またライブラリ側でもac-library-csharpを使いたい場合はこれもインストールしておきます。
自作ライブラリを提出用コードに変換してみる
ためしにこの問題を解いてみることにします。
これは k = 1, 2, …, N それぞれについて、（頂点 1 から頂点 k までの距離）+ （頂点 k から頂点 N までの距離）の合計を求めよという問題です。ダイクストラ法を用いれば（頂点 1 から頂点 k までの距離）はわかります。またスタート地点を頂点 N とすれば（頂点 k から頂点 N までの距離）もわかります。あとはそれらを足し合わせた値を出力するだけです。
最短経路問題はよく出題されるのでダイクストラ法で最短距離を求めるライブラリを自作します。
普通のダイクストラ法を実装しているだけなんの変哲もないコードです。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 |
namespace HatoLibrary { public class Dijkstra { public class Edge { public Edge(int next, long cost) { Next = next; Cost = cost; } public int Next = 0; public long Cost = 0; } int N = 0; List<Edge>[] Edges; public Dijkstra(int n) { N = n; Edges = new List<Edge>[N]; for (int i = 0; i < N; i++) Edges[i] = new List<Edge>(); } public void AddEdge(int from, int next, int cost) { Edges[from].Add(new Edge(next, cost)); } public long[] Solve(int start) { long[] costs = new long[N]; bool[] seen = new bool[N]; for (int i = 0; i < N; i++) costs[i] = long.MaxValue; PriorityQueue<int, long> pq = new PriorityQueue<int, long>(); pq.Enqueue(start, 0); costs[start] = 0; while (pq.Count > 0) { int cur = pq.Dequeue(); if (seen[cur]) continue; seen[cur] = true; foreach (Edge edge in Edges[cur]) { int next = edge.Next; long ncost = costs[cur] + edge.Cost; if (costs[next] > ncost) { costs[next] = ncost; pq.Enqueue(next, ncost); } } } return costs; } } } |
事前にこのようなライブラリを準備しておけば、あとはこれを利用してコードを書くだけなのでかなりの時間短縮につながると思います。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 |
class Program { static void Main() { SourceExpander.Expander.Expand(); int N, M; { int[] vs = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); N = vs[0]; M = vs[1]; } var d = new HatoLibrary.Dijkstra(N); for (int i = 0; i < M; i++) { int[] vs = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); int a = vs[0] - 1; // 1-indexed -> 0-indexed int b = vs[1] - 1; int c = vs[2]; d.AddEdge(a, b, c); d.AddEdge(b, a, c); } long[] rets1 = d.Solve(0); long[] rets2 = d.Solve(N - 1); for (int i = 0; i < N; i++) Console.WriteLine(rets1[i] + rets2[i]); } } |
では、よき競技プログラミングライフを。
