2003/Contest/マニラ大会/Problem B

Problem B : Carbon Copies †

グラフの形で与えられた二つの分子構造式が等しいかどうかを判定する。

頂点 (原子) 一つと、それに隣接する全ての頂点・接続する全ての辺を組にし、その集合が二つの分子構造式で等しいかどうかを調べればいいようだ。泉の仮説による。証明は今度考えてみたいところ。 (三廻部)

それだと [A-A-A=B=A-A-A]と [A-A=B=A-A-A-A] が区別できないような気がする。（谷口）

それじゃ A の手の数が…とも思ったけど、 [H-O-O-N=C=N-O-O-O-O-H]と[H-O-O-O-N=C=N-O-O-O-H]ってのはありか。しまった。でもプログラムは通ったぞ。審判データのミス？（笑）（泉）

実装に当たってのミス :

atomid (分子記号に対する識別番号) を二つの分子で分けて管理してしまい Wrong answer となる。

二者 (以上) の比較を行う際は、何を共有すべきで何を分離すべきなのかを慎重に考えるべし。 (三廻部)

合ってそうなプログラム（グラフを辿っていって一致しているかどうか調べている）を添付(B.java)。

それにしても、このジャッジデータ微妙な気もする。異性体はいくつか入れるべきだろう(谷口)。