【競プロ】グラフ問題の苦手克服がしたい
スポンサードリンク
こんにちは。ふぁんたです。
競技プログラミングのスキルを上げたい。
急に思い立ったので、一問手を出しました。
Atcoder Regular Contest 034?C - One-stroke Path
問題文概要
無向グラフの頂点数N、辺の数Mが最初に与えられる。
その後、M個のノードの情報が与えられる。
1番の頂点から始めて、全部の頂点を通るルートはなんパターンあるか出力せよ。
結構時間がかかりましたが、実装できました。
それでは、解説を見ていきます。
解説を見ると、深さ優先探索の再帰関数で解いています。
探索し終わったノードに関しては9行目、深さ優先探索後に一つ上のノードに抜けています。こんなにきれいに書けるんですね。
日本語が混ざっていますが、12行で簡潔に書けるというのは想像していませんでした。
自分の実装について。
…自分が「グラフ問題が苦手だから」なのか、「DFS(=深さ優先探索)になれていないから」なのか、「クラスの実装、コンストラクタの作成を覚えて使いたいだけだから」なのかわからないのですが、めっっっっっっちゃ長くなりました。
考え方としては、
「ノードの通し番号と、次のノードのリストを保持するクラス Nodes」と
「今どこのノードにいて、今までどのノードを通ってきたかという履歴情報を持つ、ノード間を移動する人を生成するクラス Person」を使って、
1のノードにPersonを一人置いて、人の列を作ります。
この人の列がなくなるまで、
・人を一人取り出して、それが全ノード制覇済みの履歴を持っていたら出力する数字を＋１します。
・そういう履歴を持っていなかったら、繋がっているノードのうち、訪問していないノードのリストを作ります。
・リストの中のノードの数だけ人間を複製し、
・分岐先に訪問した情報を各人の履歴情報に書き込んで移動させる
ということを繰り返します。
ACしました。
ACはできたんですが、こう書いてしまうのを治していきたいんです。
まず、C#にグラフを扱う方法はないのか？ という疑問があります。
配列とか、Dictionary(連想配列)とかListとか、大事だなあ、便利だなあと思うデータの扱い方があるんですが、グラフはどう扱えばいいんでしょう。
今回はnodesクラスを実装してやりきりましたが、時間がかかるんです。
次に、クラス使うべきか？というのも思うところではあります。
模範解答のPDFに、こんなに長いコードは見たことがありません。
しかも、思いついて書いてACするまでに1時間弱ほどかかっているんです。
速さ、正確さを競いたいコンテストで、走るフォームがきれいとかそういうことを言っても仕方がないので治したいなあと思うんです。
ときどき、300点400点ぐらいの問題を解いてみるってのはいいですね。優先探索とか、再帰とか、忘れかけそうなものを思い出せますし、自分で反省するべき材料がこんな感じに見つかることにもなります。
またやります。
競技プログラミングのスキルを上げたい。
急に思い立ったので、一問手を出しました。
Atcoder Regular Contest 034?C - One-stroke Path
問題文概要
無向グラフの頂点数N、辺の数Mが最初に与えられる。
その後、M個のノードの情報が与えられる。
1番の頂点から始めて、全部の頂点を通るルートはなんパターンあるか出力せよ。
結構時間がかかりましたが、実装できました。
それでは、解説を見ていきます。
解説を見ると、深さ優先探索の再帰関数で解いています。
1: procedure DFS(現在の頂点 v)
2: if 全ての頂点を訪問済み then
3: 答えを 1 増やす。
4: return
5: end if
6: for 頂点 i: 頂点 v に隣接しているかつ未訪問 do
7: 頂点 i を訪問済みとする。
8: DFS(i)
9: 頂点 i を未訪問とする。
10: end for
11: return
12: end procedure
ABC054の解説PDFより引用
探索し終わったノードに関しては9行目、深さ優先探索後に一つ上のノードに抜けています。こんなにきれいに書けるんですね。
日本語が混ざっていますが、12行で簡潔に書けるというのは想像していませんでした。
自分の実装について。
…自分が「グラフ問題が苦手だから」なのか、「DFS(=深さ優先探索)になれていないから」なのか、「クラスの実装、コンストラクタの作成を覚えて使いたいだけだから」なのかわからないのですが、めっっっっっっちゃ長くなりました。
考え方としては、
「ノードの通し番号と、次のノードのリストを保持するクラス Nodes」と
「今どこのノードにいて、今までどのノードを通ってきたかという履歴情報を持つ、ノード間を移動する人を生成するクラス Person」を使って、
1のノードにPersonを一人置いて、人の列を作ります。
この人の列がなくなるまで、
・人を一人取り出して、それが全ノード制覇済みの履歴を持っていたら出力する数字を＋１します。
・そういう履歴を持っていなかったら、繋がっているノードのうち、訪問していないノードのリストを作ります。
・リストの中のノードの数だけ人間を複製し、
・分岐先に訪問した情報を各人の履歴情報に書き込んで移動させる
ということを繰り返します。
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace Atcoder
{
class Program
{
static void Main(string[] args)
{
int[] NM = Console.ReadLine().Split(' ').Select(int.Parse).ToArray();
Node[] nodes = new Node[NM[0]];
for (int i = 0; i < NM[0]; i++)
{
nodes[i] = new Node();
}
for (int i = 0; i < NM[1]; i++)
{
int[] edge = Console.ReadLine().Split(' ').Select(int.Parse).Select(x=>x-1).ToArray();
nodes[edge[0]].number = edge[0];
nodes[edge[0]].next.Add(edge[1]);
nodes[edge[1]].number = edge[1];
nodes[edge[1]].next.Add(edge[0]);
}
Person person = new Person(0, NM[0]);
person.history[0] = true;
Queue<Person> people = new Queue<Person>();
people.Enqueue(person);
int output = 0;
while (people.Count > 0)
{
Person tuginokata = people.Dequeue();
bool isFinished = true;
for (int i = 0; i < tuginokata.history.Length; i++)
{
isFinished = isFinished && tuginokata.history[i];
}
if (isFinished) output++;
else
{
List<int> next_choice = nodes[tuginokata.You_are_here].next;
for (int i = 0; i < next_choice.Count; i++)
{
Person next_generation = tuginokata.Clone();
if (next_generation.history[next_choice[i]] == false)
{
//行ったことがなければ
next_generation.history[next_choice[i]] = true;
//次行くところに足跡をつけて
next_generation.You_are_here = next_choice[i];
//移動して
people.Enqueue(next_generation);
//後ろに並ぶ
}
}
}
}
;
Console.WriteLine(output);
}
}
class Node
{
public int number;
public List<int> next;
public Node(int number)
{
this.number = number;
this.next = new List<int>();
}
public Node()
{
this.number = 0;
this.next = new List<int>();
}
}
class Person
{
public int You_are_here;
public bool[] history;
public Person(int place, int N)
{
this.You_are_here = place;
this.history = new bool[N];
}
public Person Clone()
{
Person output = new Person(0,this.history.Length);
output.You_are_here = this.You_are_here;
output.history = (bool[])this.history.Clone();
return output;
}
}
}
ACしました。
ACはできたんですが、こう書いてしまうのを治していきたいんです。
まず、C#にグラフを扱う方法はないのか？ という疑問があります。
配列とか、Dictionary(連想配列)とかListとか、大事だなあ、便利だなあと思うデータの扱い方があるんですが、グラフはどう扱えばいいんでしょう。
今回はnodesクラスを実装してやりきりましたが、時間がかかるんです。
次に、クラス使うべきか？というのも思うところではあります。
模範解答のPDFに、こんなに長いコードは見たことがありません。
しかも、思いついて書いてACするまでに1時間弱ほどかかっているんです。
速さ、正確さを競いたいコンテストで、走るフォームがきれいとかそういうことを言っても仕方がないので治したいなあと思うんです。
ときどき、300点400点ぐらいの問題を解いてみるってのはいいですね。優先探索とか、再帰とか、忘れかけそうなものを思い出せますし、自分で反省するべき材料がこんな感じに見つかることにもなります。
またやります。
スポンサードリンク