読者です 読者をやめる 読者になる 読者になる

競プロでは特化したアルゴリズムを使わないんですか?

コンテスト

Q: 競プロでは汎用アルゴリズムで満足して問題特有の性質に基づいて平均性能を向上させたアルゴリズムは使わないのですか?

A: 使います。ただし、そういう問題があれば。

競プロでのアルゴリズムの選択基準は、主に実装量最悪計算量です。平均計算量を下げるだけアルゴリズムは実用上重要かもしれませんが、漸近的な最悪計算量が変わらなければ、大抵の場合、実装量を増やすばかりか、最悪計算コストも定数のオーバーヘッドが大きくなるだけになることが大半なので嫌われます。競プロでは広義の heuristics という扱いです。

なお、特化したアルゴリズムを普及させたいなら、そのアルゴリズムの計算量を決める implicit な parameter が自然に出てくるような問題設定を考え、出題してみるとよいでしょう。