IOI世界大会2007年の問題を解いていました。洪水があって、壁が決壊して、残った壁を求めよ、という問題です。(詳しくは問題文を読んでください) アルゴリズムは簡単です。 まだたどっていない壁があるなら、左上の頂点から順番に壁をたどり、1度しか通らなかったら決壊、2度通ったら残す これだけです。おそらく、世界大会参加者の多くの人がここまではわかっていたのではないかと思います。しかし、実は、本問題での課題はこれをコンテストの制限時間内にコードまで落とせるかという点にあります。僕のコードでは150行ほどになりました。頂点の数が100k個あるので、ちゃんとした実装にしないと、プログラム自体の制限時間をクリアできません。そのため、コードを書くのは少々複雑で、やっかいです。 実は、僕は、上記のアルゴリズムがわかったので、よっしゃ、と思って、すぐにコードを書き始めたら、失敗しました。(1度失敗したから