AtCoderの少し変わった遊び方

高一 S.K

はじめに

今年はこれで許されましたが、来年こそはちゃんと入青記事が書けるようにしたいですね。
最後までご覧いただきありがとうございました。

高1のkino0402です。2026/04/18のABC454にて遂に入青しました！なので今年こそは入青記事を書こうと思ったのですが、AtCoderにはレートを最大化する他にも様々な楽しみ方があることに気付いたので、今回はこれらを紹介していきます。

目次

  • Shortestを狙う
  • Fastestを狙う

Shortestを狙う

俗に言うコードゴルフというやつです。
AtCoder Problemsでは、問題ごとの最短ACコードを見ることができ、最短ACコードの所持数ランキングも見ることができます。私はAtCoder上の約1.3%の問題（125/9430）でShortestを獲得しています。
Shortestを取る方法はいくつかあります。

短く書ける言語を使う

競プロで最も使われているC++はコードゴルフでは弱いです。例えば直近のABC-AのShortestコードは、A言語、dc、Uiua、Bash、AWKなど、あまり聞き馴染みのない言語に埋め尽くされています。
様々な言語がありそれぞれに強みや弱みもあり、強い言語を全て使えるようになるのが理想ではありますが、現実的ではありません。（Shortest取得数1位の方などは例外です）
私はcLayという言語をオススメします。ABC-AなどでShortestを取れる言語ではありませんが、基本的な文法はC++を元にしているため書きやすく、ライブラリが豊富なので一部の問題は瞬殺することもできます。
例えば、この順列の転倒数を求める問題では、ライブラリを使うことで30byteでACすることができます。
https://atcoder.jp/contests/tessoku-book/tasks/tessoku_book_ef

1

ll@A,@B[A];wt(inversion(A,B));

マイナーな問題を狙う

ABC,ARC,AGC,AHCなどのコンテスト以外の問題（大学コン、パ研合宿、PAST、AWCなど）であれば、簡単なのにAC者数が少ないことがあります。こういった問題は狙いやすいです。

細かいテクニックなど、書きたいことはたくさんありますが、余白が狭すぎるのでやめておきます。

Fastestを狙う

ここからが本題です。Shortest狙いと比べてわざわざ狙う人が少なく、時間をかければ比較的簡単にランキング上位になれます。私はAtCoder上の約2.6%（246/9430）の問題でFastestを獲得しています。

ここから先に書くことは全て、C++を使うことを想定しています。

計算量を減らす

場合分けをするなどの方法で、計算量を減らすことができる場合があります。 https://atcoder.jp/contests/math-and-algorithm/tasks/math_and_algorithm_bn
例えば、この問題は典型的な区間スケジューリング問題なのでO(NlogN)で解くことができますが、R_i<=86400という制約になっているので、O(N+max(R_i))でも解くことができます。
これにより、Fastestが18msだったところを3msまで縮めることができました。

コンパイルオプションの指定

1
2
3

#pragma GCC target("avx2")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")

を書くだけでかなり速くなります。TopCoderでは使えないらしいですが、AtCoderで使えればOKです。

入出力の高速化

標準のcinやcoutはかなり遅いです。

1
2

ios::sync_with_stdio(false);
std::cin.tie(nullptr);

を書くだけでかなりの高速化になります。

もっと入出力を高速化

普段のコンテストであればこれで十分です。しかし、ここまでの内容はFastestを狙っていない人でも書いていることが多く、これだけで差をつけるのは難しいです。
getchar_unlocked()やputchar_unlocked()といった、1文字ずつ高速に入力や出力を行う関数を使い、入出力関数を作ると更に速くなります。これらはインタラクティブ問題では基本的に使うことができないので気をつけましょう。

もっともっと入出力を高速化

mmapやfwriteを使うことで更に高速化できます。ここまですれば、マイナーな問題であれば雑にコードを書くだけでFastestが取れることがあります。

ちなみに、1文字ずつ高速に入力や出力を行う関数を使うことによるメリットとして、「必要のない文字を飛ばすことができる」というものがあります。 https://atcoder.jp/contests/math-and-algorithm/tasks/math_and_algorithm_r
この問題では、A_iの値が100、200、300、400のいずれかで確定しているので、百の位を受け取ったらその後の00の部分を飛ばすことができます。これにより、N<=200000の制約でも0msを出すことができました。

入出力の比較

https://atcoder.jp/contests/chokudai_S002/tasks/chokudai_S002_a
この問題での実行時間を比較してみます。

通常のcin,cout : 198ms
高速化したcin,cout : 92ms
getchar_unlocked(),putchar_unlocked() : 24ms
ぼくのかんがえたさいきょうのライブラリ : 10ms

ちなみに、ぼくのかんがえたという表現は嘘です。様々なサイトを参考にしたりChatGPTに書かせたりしました。

GCC,Clangを使い分ける

Clangはmmap,fwriteを使うことができず、標準の入出力も遅いですが、シンプルな処理には強い印象です。入出力が少ない問題ではClangも試してみる価値があると思います。

longlong型を使わない

int型で十分な所ではint型を使いましょう。int型よりも短いshort型(-32768~32767)もありますが、CPUが演算を行う際にint型に変換する分遅くなるので、メモリは節約できますが、速くなるとは限らず、遅くなることもあります。

vectorを使わない

生配列で書けるのであれば、生配列を使ったほうが速いです。

配列を減らす

二次元DPなどでは、配列を上手く使い回すことで空間計算量を減らすことができる場合があります。また、DPの典型問題である二つ先か一つ先の足場に飛ぶような問題は、直前の3つを変数で持っておくことにより配列を持つ必要がなくなります。

割り算を減らす

四則演算の中では割り算が突出して遅いです。x/2の代わりにx»1を使ったり、x%2の代わりにx&1を使うなどの方法で高速化することもできます。
他にも、modを取る問題では、y<modであれば

1

x = (x + y) % mod;

の代わりに

1
2

x += y;
if(x >= mod) x -= mod;

を使うことで割り算を無くすことができますし、modを取らなくてもオーバーフローしないのであれば、最後の最後に一回割るだけで済みます。

グラフを生配列で管理するテクニック

隣接リスト形式のグラフを、連結リストで管理します。

変数の定義＋初期化は

1
2
3

int MAX_N = 頂点数, MAX_M = 辺数;
int head[MAX_N], to[MAX_M], next[MAX_M];
memset(head, -1, sizeof(head));//-1の初期化はこれが速い

辺の追加は

1
2
3
4
5
6

void add_edge(int u, int v) {
    to[idx] = v;
    next[idx] = head[u];
    head[u] = idx;
    idx++;
}

隣接頂点の列挙は

1
2
3

for (int t = head[pos]; t != -1; t = next[t]) {
    int nex = to[t];
}

でできます。
headは各頂点の最初の辺、toは辺の行き先、nextは始点が同じ次の辺を管理しています。
https://atcoder.jp/contests/math-and-algorithm/tasks/math_and_algorithm_an
この問題で試したところ、vector<vector<int>>で管理した時は21msだったのに対し、連結リストで管理した時は7msでした。

メモリアクセスを考える

正直あまり意識できていませんが、代表的な物を紹介します。これは行列の積を求めるコードの一部です。

1
2
3
4
5
6
7

for (int i = 0; i < x; ++i) {
    for (int j = 0; j < y; ++j) {
        for (int k = 0; k < z; ++k) {
            C[i][j] += A[i][k] * B[k][j];
        }
    }
}

これだと配列Bへのアクセスが、メモリの順番と異なるため、キャッシュ効率が悪いです。

1
2
3
4
5
6
7

for (int i = 0; i < x; ++i) {
    for (int k = 0; k < z; ++k) {
        for (int j = 0; j < y; ++j) {
            C[i][j] += A[i][k] * B[k][j];
        }
    }
}

とすることで、メモリの順番通りにアクセスするようになり、かなり高速になります。
実際、x=y=z=1000で実験したところ、一つ目のコードは758ms、二つ目のコードは126msとかなり差が出ました。

ソート関数の自作

std::sort()では計算量がO(NlogN)のイントロソートが使われています。計算量がO(kN)（k=ソートする要素の桁数）である、基数ソートを使うことで高速化できることがあります。

コラム:C++以外の言語

最近ではRustがFastestを取っていることも多いです。あまり詳しくはないですが、標準の入出力やソート関数がとても速いらしいです。
また、Shortestの時に話したcLayという言語も強いです（使っている人はあまりいませんが…）。先程書いた基数ソートなどもライブラリとして用意されています。

最適化以外の方法

ここまではただの最適化です。ここからは「AtCoderでFastestを取る」ことに特化していきます。

同じコードを何度も提出する

AtCoderのジャッジシステムは実行時間にブレがあります。 https://atcoder.jp/contests/arc184/tasks/arc184_a
この問題はインタラクティブ問題で、ジャッジシステムとの通信時間が実行時間の大部分を占めるため、なかなか実行時間を縮められません。
しかし、同じコードを80回ほど提出したところ、緑コーダー時代に書いたほとんど高速化していないコードでFastestを取ることができました。（36ms~44ms程度のブレがありました）

嘘解法

https://atcoder.jp/contests/joig2026final/tasks/joig2026final_a
この問題を正攻法で解くとK<=N<=500000のO(N+K)になり、10msほどかかってしまいます。しかし、テストケースの内訳を見ると大きく時間がかかっているテストケース、すなわちN+Kが大きいケースは03-14.txtの一つだけだと分かります。
この問題では、K*2>Nの時には答えを0か1の二択に絞り込むことができます。どちらも試したところ、0を出力したときに03-14.txtがACになりました。
よってN+Kが大きいかどうかを判定し、答えを埋め込むことにより4msまで縮めることができました。(N+K>=900000で判定したらACになりました)

マイナーな問題を探す

ABC,ARC,AGC,AHCなどのコンテスト以外の問題であれば、簡単なのにAC者数が少ないことがあります。こういった問題は狙いやすいです。

Fastestが旧ジャッジの問題を探す

2020年のジャッジシステム更新の前と後では、かなり実行時間に差が出る気がしています。（旧ジャッジ時代にはAtCoderをやっていなかったため比較はできませんが…）
Fastestガチ勢の旧ジャッジの提出vs少し高速化した新ジャッジの提出だと後者が勝つこともあります。

コラム:0ms狙いの際の注意

通常のC++では0msを出すのが難しいので、C++ IOI-Styleを使います。ACLが使えなくなるので注意してください。
AtCoderの環境では長さ200000の文字列の入力、長さ100000の文字列の出力などであれば試行回数次第では0msを出すことができます。

また、0ms特化の言語としてPascalというものがあります。AtCoderの環境では長さ30000の文字列の入力や出力などが0msでできます。わざわざPascalを使うメリットは無いように見えますが、ジャッジが最新になっていないためC++ IOI-Styleを使うことができない、一部の古い問題を解く時には重宝します。

おわりに

Fastestは狙っている人が少なく、入出力ライブラリさえ作れば狙うことができるため、敷居が低いです。みなさんもFastestを狙ってみてください！最後までご覧いただきありがとうございました！

次へ初代ポケモンでプログラミング＞
前へゲームを作ろう＞