はじめに

「最強最速アルゴリズマー」の「最速」とは、こういう意味ではありません。

基本

AtCoderで実行時間0msを狙うにはどうすればよいのか？Pascalを使用すればよいです。

Pascalは小規模なプログラムの実行がやたらと速いです。C言語を使用し、入出力をreadとwriteで行っていても0msはなかなか出ませんが、Pascalならほとんど一発で出ます。標準の入出力が爆速なのと、（多分）起動時のオーバーヘッドが極小なんだと思います。

しかし、C言語と比較すると他の点で少し遅いのは事実です。105${10}^5$回ループするだけでもうC言語より遅くなったりします。

経験的に、Pascalでは実行時間0msの範囲内で

• 数千から一万回のループ
• 数百回の入出力

を行えます。ですから、ABC-A問題レベルならば、何も考えずに書いてACするだけで0msがポコポコ出ることになります。

そんなのをわざわざ記事にする意味はないです。よって以下では、普通に書いたら出ないような0msをどうにかこうにか捻り出すテクを具体例とともに書いていくことにします。

どんどん追記していくかもしれませんし、そうでないかもしれません。

コードを改善する前に

Pascalプログラムを提出しても0msが出なかった場合、まず詳細なジャッジ結果を確認します。1ケースだけ数msかかってしまうことがよくありますが、このような場合は全く同じプログラムを再度提出することでめでたく0msを出せることがあります。実行時間は毎回ぶれるからです。

こんな感じ

コード長を見て察しがつくかもしれませんが、この3回の提出でコードは1文字も書き換わっていないです。時間がかかってしまった1ケースも別々です。

実例

問題名には、その問題へではなく、実際に0msを出した提出へのリンクを貼っています。

工夫して計算量を落とす

ACできるほど計算量の少ないコードを、さらに考察したり場合分けすることで0msが出せるほどまで持っていきます。

• ARC074-C Chocolate Bar

解説では値を一つ全探索していますが、これは場合分けすることでO(1)$O(1)$で回答できます。

• ABC085-C Otoshidama

AtCoder Beginners Selectionに選出されて有名になりました。O(1)$O(1)$で解けるのも有名です。5000円札の枚数を9通り探索すればよいです。

……ふと気になってAtCoder Beginners Selectionの方の提出を確認したら、僕より先に提出された複数の0msが存在しました。まあProblemsでは僕が最速コード保持者になっているのでヘーキヘーキ

• ABC076-D AtCoder Express

解説では秒ごとに処理してO(N∑ti)$O(N\sum t_i)$ですが、区間ごとにv−t$v-t$グラフの形を場合分けして面積を求めることでO(N2)$O(N^2)$で解けます。

• ARC091-D Remainder Reminder

a=pb+r$a=pb+r$と表し、r$r$の分布を考えて解いていますが、このときp$p$、つまり商の値はO(N−−√)$O(\sqrt{N})$種類しかないのでそれでまとめることができます。

• ABC126-C Dice and Coin

サイコロを振ってからコインを振るゲームですが、コインを振ってからサイコロでつじつまを合わせるようにすると状態がまとめられます。

• ABC128-C Switches

解説にもありますが、Z/2Z$\mathbb{Z}/2\mathbb{Z}$上で行列のランクを求めればよいです。O(N2M)$O(N^{2}M)$になります。

• パ研合宿2019　第4日「Teamwork」-C 罰ゲーム

3つの区間の重なり具合を頑張って場合分けすればO(1)$O(1)$になります。

解を埋め込む

埋め込めば速いです。それはそう。C++のconstexprを使って頑張ってみたこともあるのですが、結局0msを出すには至りませんでした。

• ABC127-E Cell Distance（コードが長くページが重いので、リンクを踏むときは注意してください）

2×105$2\times {10}^5$までの値の階乗を求める必要がありますが、100個刻みで埋め込んでおくことで実行中の前計算すらせずそれなりに高速に得ることができます。

• ABC006-B トリボナッチ数列

こういうコードはプログラムで生成しています。10000個刻みですが、途中の計算は何とか0msで回りました。

• ARC099-D Snuke Numbers（コードが長くページが重いので、リンクを踏むときは注意してください）

テストケースが2個しか入ってないやんけ！どうしてくれんのこれ

嘘解法

ここでいう嘘解法とは、制約内の入力に対して正しくない答えを出力しうるもの、というくらいの意味です。

• ABC020-C 壁抜け

どうしても1ケースだけ1msかかってしまう……せや！テストケース特定したろ！→0ms

• ABC133-C Remainder Minimization 2019

ちょっとくらい……探索サボってもバレへんか（for j:=1 to 50のあたりのことです）

• ABC139-F Engines

進む方向を定めるのに、ベクトル(sin(r),cos(r))(r=0,…,99)$(\sin (r),\cos (r))(r=0,\dots ,99)$を使っています。根拠はないです。

• ABC147-C HonestOrUnkind2

前から順に、矛盾しない限り人を正直者としていく貪欲が通りました。

• ABC142-F Pure

（これは僕のコードではないですが、経緯がかなり面白いので……）

構築問題ですが、ジャッジ解がバグっているため構築する代わりに0または-2以下の数を出力しても通ります。-1を出力するケースだけはしっかりジャッジしているようなのでそこを判別する必要がありますが、普通にやるとO(N+M)$O(N+M)$に加えて入力が数千個あり、0msは狙えません。

MMNMMさんはsleep関数を駆使したテストケースハックによって、数個入力を読むだけで-1を出力すべきケースとそうでないケースを区別することに成功しました。

その他

• CODE FESTIVAL 2014チーム対抗早解きリレー-G haruki の覚醒め

Bool値のDPをするのですが、bitsetを自前で実装することで64倍高速化に成功しています。

• ARC085-D ABS

これは入力が2000個あるのですが、必要なのは最初と最後の数個だけです。なので、入力を文字列で受け取って必要な部分だけ自前でパースすることで、0msを出すことができました。

ちなみに、最初はC言語で0msを出しました。strlenはO(N)$O(N)$なので、一見文字列の末尾にアクセスするのが大変かのように思えますが、実はread関数が読み込んだバイト数を返すので、これを利用し文字列の末尾のインデックスを得ました。しかしPascalでは文字列のlength取得がO(1)$O(1)$なので、素直な方法で同じことができてしまってちょっと残念です。結局最速コードはPascalの独擅場でした……

おわりに

いかがでしたか？

実装がクソ面倒な問題を頑張ってPascalで解いて単独0msを出すと……気持ちがいい！