プロコン勉強会1004_01

私の研究室では、週に一度、プログラミングコンテスト勉強会というものがあります。
任意参加で、毎回テーマに沿った問題を解きます。（判定はpkuのonlinejudge）
テーマは、DFS（深さ優先探索）だったり、ダイクストラだったり、DP（動的計画法）だったり、アルゴリズムが主。
というのも、ここでのプログラミングコンテストとは、icpcのものを指しています。

今日は模擬戦だったわけで、3時間で6問用意されていたのですが、受理されたのはたったの1問でした。
ただ約数を求めて、組み合わせ最適化しただけ。
受理されなかったけど解いたのがあと2問。終わった後の解説と反省タイムにて検討。
一つは、ループの終了条件が悪かった。whileをforにしてループの上限を設定することにより回避。
もう一つは、for文の繰り返しが10億回行われていた。これは無理ですね。というのも、onlinejudgeの制限的な意味で。
ワーシャル-フロイドを使ってしまっていたのですが、実際にはダイクストラに一手間加えるだけでした。
他の問題は、バックトラックとか、ダイクストラの応用とかでした。

アルゴリズムを知っているだけでなく、使いこなせないと意味がないですね。