問題
タイトル通りわらしべ長者。わらしべ有向グラフを渡り歩いて到達可能な頂点を数え上げる。
解説
グラフ理論を用いた探索。これを表現する実装が分かれば苦労しない。
……分かれば、苦労しないはずなんだ……。（ｎ敗）
隣接リストを用意する。このリストにある頂点にしかいけないよ、を表すリスト。グラフ理論の○ikipediaには隣接行列がでかでかと載っているので勘違いしやすい（１敗）が、基本はジャグ配列となるはず。
この問題の場合、N種類あるアイテムは重複がないので頂点（ノード）の集合を表し、M人いる友達はそれぞれアイテムの取引によって頂点から頂点への辺の向きを表す。
探索する際は未探索の領域かどうかを把握したい。まあQueueとbool型配列は木構造の探索でもよく使うし、そこまで実装に苦戦することはないはず。
グラフ探索に使う変数の宣言は大体こんな感じのコードを書く（サンプル）
var graph = new List<int>[n]; // List型の配列。
for (var i = 0; i < n; i++) abgraph[i] = []; // List型の既定値はnullなので充填する。
for (var i = 0; i < m; i++) graph[a].Add(b); // 各頂点への辺を表す。
// で、このgraphをベースにアイテム1から探索を始める。感想
出力する値を微妙に勘違いしていた。到達する頂点の数を最大化する探索ではなく、到達する可能性のある頂点の数を答えればいい。それに気付かず「うおお、どうすれば綺麗に探索できるのか……！？」などと考えていた。
あとグラフ理論に苦手意識あり過ぎてどんなデータ構造を使えばいいかすら分からなかった。……最大で30万×30万の隣接行列なんてのァなァ……デカすぎんだよォ！（MLE）
だから、グラフ探索は頂点の集合であることと、各頂点から頂点への隣接が表現できればいいから、必然的にList型というかジャグ配列になるわけだ。よし、もう間違えない。
これを拡張すると例の隣接行列になる……と思うんだけど、こっちをプログラムで表現すると0を表すデータが多くなりがちで計算資源がもったいない。
ただまあ、重み付きグラフになるとまた話が変わってくるし、データ構造とか解き方を工夫しないといけない。この問題ではグラフの経路はさほど重要ではなく、どちらかと言えば各頂点への適切な探索とその到達した頂点の数を数えることに重きを置かれていたわけだし。
コメント