はじめに
「最強最速アルゴリズマー」の「最速」とは、こういう意味ではありません。
基本
AtCoderで実行時間0msを狙うにはどうすればよいのか？Pascalを使用すればよいです。
Pascalは小規模なプログラムの実行がやたらと速いです。C言語を使用し、入出力をreadとwriteで行っていても0msはなかなか出ませんが、Pascalならほとんど一発で出ます。標準の入出力が爆速なのと、（多分）起動時のオーバーヘッドが極小なんだと思います。
しかし、C言語と比較すると他の点で少し遅いのは事実です。$10^5$回ループするだけでもうC言語より遅くなったりします。
経験的に、Pascalでは実行時間0msの範囲内で
- 数千から一万回のループ
- 数百回の入出力
を行えます。ですから、ABC-A問題レベルならば、何も考えずに書いてACするだけで0msがポコポコ出ることになります。
そんなのをわざわざ記事にする意味はないです。よって以下では、普通に書いたら出ないような0msをどうにかこうにか捻り出すテクを具体例とともに書いていくことにします。
どんどん追記していくかもしれませんし、そうでないかもしれません。
コードを改善する前に
Pascalプログラムを提出しても0msが出なかった場合、まず詳細なジャッジ結果を確認します。1ケースだけ数msかかってしまうことがよくありますが、このような場合は全く同じプログラムを再度提出することでめでたく0msを出せることがあります。実行時間は毎回ぶれるからです。
コード長を見て察しがつくかもしれませんが、この3回の提出でコードは1文字も書き換わっていないです。時間がかかってしまった1ケースも別々です。
実例
問題名には、その問題へではなく、実際に0msを出した提出へのリンクを貼っています。
工夫して計算量を落とす
ACできるほど計算量の少ないコードを、さらに考察したり場合分けすることで0msが出せるほどまで持っていきます。
解説では値を一つ全探索していますが、これは場合分けすることで$O(1)$で回答できます。
AtCoder Beginners Selectionに選出されて有名になりました。$O(1)$で解けるのも有名です。5000円札の枚数を9通り探索すればよいです。
……ふと気になってAtCoder Beginners Selectionの方の提出を確認したら、僕より先に提出された複数の0msが存在しました。まあProblemsでは僕が最速コード保持者になっているのでヘーキヘーキ
解説では秒ごとに処理して$O(N \sum t_i)$ですが、区間ごとに$v-t$グラフの形を場合分けして面積を求めることで$O(N^2)$で解けます。
$a=pb+r$と表し、$r$の分布を考えて解いていますが、このとき$p$、つまり商の値は$O(\sqrt{N})$種類しかないのでそれでまとめることができます。
サイコロを振ってからコインを振るゲームですが、コインを振ってからサイコロでつじつまを合わせるようにすると状態がまとめられます。
解説にもありますが、$\mathbb{Z}/2\mathbb{Z}$上で行列のランクを求めればよいです。$O(N^2M)$になります。
3つの区間の重なり具合を頑張って場合分けすれば$O(1)$になります。
解を埋め込む
埋め込めば速いです。それはそう。C++のconstexprを使って頑張ってみたこともあるのですが、結局0msを出すには至りませんでした。
- ABC127-E Cell Distance（コードが長くページが重いので、リンクを踏むときは注意してください）
$2 \times 10^5$までの値の階乗を求める必要がありますが、100個刻みで埋め込んでおくことで実行中の前計算すらせずそれなりに高速に得ることができます。
こういうコードはプログラムで生成しています。10000個刻みですが、途中の計算は何とか0msで回りました。
- ARC099-D Snuke Numbers（コードが長くページが重いので、リンクを踏むときは注意してください）
テストケースが2個しか入ってないやんけ！どうしてくれんのこれ
- Japan Alumni Group Summer Camp 2015 Day 2-A 幾何問題を解こう（コードが長くページが重いので、リンクを踏むときは注意してください）
$10^9$未満の数を素因数分解する必要があります。$1$から$\sqrt{N}$までいちいち調べていては間に合わないのですが、$\sqrt{10^9}$未満の素数は3401個しかないので、すべて埋め込んでそれだけ調べればよいです。
嘘解法
ここでいう嘘解法とは、制約内の入力に対して正しくない答えを出力しうるもの、というくらいの意味です。
どうしても1ケースだけ1msかかってしまう……せや！テストケース特定したろ！→0ms
ちょっとくらい……探索サボってもバレへんか（for j:=1 to 50のあたりのことです）
進む方向を定めるのに、ベクトル$(;\sin(r),;\cos(r);)\quad(r=0,\ldots,99)$を使っています。根拠はないです。
前から順に、矛盾しない限り人を正直者としていく貪欲が通りました。
（これは僕のコードではないですが、経緯がかなり面白いので……）
構築問題ですが、ジャッジ解がバグっているため構築する代わりに0または-2以下の数を出力しても通ります。-1を出力するケースだけはしっかりジャッジしているようなのでそこを判別する必要がありますが、普通にやると$O(N+M)$に加えて入力が数千個あり、0msは狙えません。
MMNMMさんはsleep関数を駆使したテストケースハックによって、数個入力を読むだけで-1を出力すべきケースとそうでないケースを区別することに成功しました。
その他
Bool値のDPをするのですが、bitsetを自前で実装することで64倍高速化に成功しています。
これは入力が2000個あるのですが、必要なのは最初と最後の数個だけです。なので、入力を文字列で受け取って必要な部分だけ自前でパースすることで、0msを出すことができました。
ちなみに、最初はC言語で0msを出しました。strlenは$O(N)$なので、一見文字列の末尾にアクセスするのが大変かのように思えますが、実はread関数が読み込んだバイト数を返すので、これを利用し文字列の末尾のインデックスを得ました。しかしPascalでは文字列のlength取得が$O(1)$なので、素直な方法で同じことができてしまってちょっと残念です。結局最速コードはPascalの独擅場でした……。
最大2600個弱の数値を出力する必要があります。普通に書くと間に合いませんでした。いつもC言語でやるようにループを使って数値を文字列に変換しても間に合いませんでしたが、出力する数値は最大2桁なので、ループを使わずとも場合分けでたやすく文字列に変換することができ、速いです。この改善を入れると0msが出ました。
これも最初はC言語で0msを出しました。Pascalの入出力は元から速いという認識があって、これまで入出力高速化はしてこなかったのですが、C言語で出せるようならPascalでも出せるんだろうなあ……と試しに書いてみると、意外と効いてびっくりしました。
おわりに
いかがでしたか？
実装がクソ面倒な問題を頑張ってPascalで解いて単独0msを出すと……気持ちがいい！