擬似コードの薦め
IOI世界大会2007年の問題を解いていました。洪水があって、壁が決壊して、残った壁を求めよ、という問題です。(詳しくは問題文を読んでください)
アルゴリズムは簡単です。
まだたどっていない壁があるなら、左上の頂点から順番に壁をたどり、1度しか通らなかったら決壊、2度通ったら残す
これだけです。おそらく、世界大会参加者の多くの人がここまではわかっていたのではないかと思います。しかし、実は、本問題での課題はこれをコンテストの制限時間内にコードまで落とせるかという点にあります。僕のコードでは150行ほどになりました。頂点の数が100k個あるので、ちゃんとした実装にしないと、プログラム自体の制限時間をクリアできません。そのため、コードを書くのは少々複雑で、やっかいです。
実は、僕は、上記のアルゴリズムがわかったので、よっしゃ、と思って、すぐにコードを書き始めたら、失敗しました。(1度失敗したから、ブログの記事になっているんですw)。2回目、擬似コードを書いてからプログラムを書き始めたら1時間半ほどで書けました。
擬似コードはこんな感じ。
{まだたどっていない壁}がある [全ての壁|座標でソート済み]in{まだたどっていない壁}から最初の壁をとる。次はこの配列番号から。 左手に水:int=頂点から右方向に壁 なら 1 下方向なら -1 最初の壁に戻ってくるまで、壁をたどる (do-while) {たどった壁}に入っている => {たどった壁}から{両方水の壁}へ移動 else {まだたどっていない壁}から{たどった壁}へ移動 次の壁の始点=前の壁の終点 {次の壁の始点 -> つながっている壁|not in 両方水の壁 && 崩壊壁}から「角度」の小さい順にたどる 角度=外積(前の壁、次の壁)×左手に水(正負)-> 90〜360 {たどった壁}から{崩壊壁}へ移動 {両方水の壁}を表示
つまり、3つ書いたんです。
この3つを書くことによって成功しました。1/10サイズの疑似コードを書いたとしても、記述する総コード量は11%しか増えないんですが、総コーディング時間は激減します。擬似コードをうまく活用するのは効果的だと思います。