この記事は新歓ブログリレー2026 48日目の記事です。

ちなみに、$48^2=2304$ です。覚えておくと便利かもしれません。

自己紹介

ブログを書くのは(個人では)初めてなので、簡単な自己紹介をしておきます。初めまして、@2251799813685248です。別の表記でいえば $2^{51}$ です。

高校の時に少しだけ(Pythonで多重ループ全探索が書ける程度で、BFS,DFS等の探索アルゴリズムなどは知らない)プログラミングを、大学から競技プログラミングを始めて、今は主にアルゴリズム班で活動しています。
AtCoderはユーザーネームa1073741824として2025/4/27に(本格的に)始めて、今(2026/4/22)はレート1642です。

今までのレート変動について

印象に残った回を紹介しておきます。

ABC403...初参加です。パフォーマンスは402で、ギリギリ灰色回避でした。これによってレート20を得ることができました。

ABC411...初めてパフォーマンスが緑色相当になりました。ちなみに、この回は春ハッカソンの帰りの電車の中で参加しました。

ABC416...初めてパフォーマンスが水色相当になりました。D問題で直感に頼った未証明の貪欲法が刺さって開始から37分で解くことができました。

ABC418...D問題で $4$ 元の連立漸化式を解くという変なことをしましたが、一応解けて、無事緑色になることができました。

ABC420...D問題のToggle Mazeで変なバグを引き起こしてWAが連続し、残り4分でギリギリ通せたものの、E問題がUnionFindコピペで終わるような簡単な問題なのもあって、パフォーマンスは低く、茶色に帰ってきてしまいました。

ABC421...D問題がRLE Movingという超重実装問題でした。高橋君と青木君の衝突判定の実装に困り、特に賢い実装が思いつかなかったのでif文を24個書きました。約79分間の実装を終えたあと、絶対どこかバグってると思いながら提出してみたところ、無事通りました。パフォーマンスは1305であり、この時は「水色相当ってこんなに難しいんだ～」と思いました。(絶対問題が悪い)

ABC425,426...ともにE問題が数学系の問題であり、すぐに方針を思いつくことができました。425の方は「同じものを含む順列」、426の方は「点と直線の距離公式, 二次関数の最小値」の問題でした。

ABC432...D問題がSuddenly, A Tempestという見た目地雷系問題でした。入力例 $1$ の図解の時点で一旦飛ばしてE問題に行きました。E問題がセグメント木の練習問題だったため、これを先に解くことで高いパフォーマンスを出すことができ、水色になることができました。ちなみに、このD問題はかなり印象が強かったので、パズルゲームのアイデアとして採用しました。(ゲームのリンクはこれ→Suddenly, A Tempest)

ABC433...E問題がよく分からなかったのでF問題に行きました。すると、F問題は二項係数の畳み込みであるヴァンデルモンドの畳み込みを使う問題であったため、解くことができました。そして、初めて青色相当パフォーマンスを出すことができました。

ABC448...E問題が、等比数列の和と剰余に関する等式を利用する問題であり、F問題がMo's Algorithmの中身をコピペするだけの問題でした。Mo's Algorithmは対策済みのため、解くことができ、初めて黄色相当パフォーマンスを出して、青色になることができました。

茶色相当以上のパフォーマンスを安定して出すためにしたこと

初回のABC403はGoogle検索でなんとかC問題を解けましたが、これでは安定しませんでした。そのため、まずはAtCoder ProblemsでC問題を集中的に色々解いていきました。それにより、二分探索, 順序付き集合, 連想配列, 全探索の基本(bit全探索, 多重ループなど)の基礎を身に着けることができました。
ただし、Snake Numbersだけはあまり推奨できません。
以下のように周囲と比べて目立つ色をしていますが、かなり難易度が高いので、まだやらない方がいいと思います。変なアルゴリズムの知識はいらないので、数学に自信があるならやってみてもいいかもしれません。

D問題への挑戦

C問題が安定して解けるようになったところで次の課題として、「D問題をどう解くか」があります。D問題以降ではC問題以上に様々な知識が要求され、特に「典型」という「コンテスト中に $0$ から思いつくのが非常に難しく、知らないと使えない」テクニックもよく要求されます。
このような典型テクニックは蟻本などの教材から学ぶというのが一般的ですが、私はそんなものを持っていなかった (この時期にそのような教材の存在を知らなかった) ため、過去問から学ぶという勉強法をとりました。先ほども出したAtCoder Problemsで今度はD問題を集中的に解いていきました。
最初は得意な問題や難易度の低い問題から手を付けていき、分からないところは調べながら少しずつDP(動的計画法)やグラフ系アルゴリズム(幅優先探索, 深さ優先探索, ダイクストラ法など)にも手を付けていくのがいいと思います。

私は数学系,実装系の問題が得意で、そればかり解いていたため、動的計画法やグラフ系アルゴリズムなどはほぼ対策できてなくて3回連続で、C問題が早めに終わったのにD問題が解けなかったことがあります。
これらの経験によって一応典型の勉強にはなりましたが、グラフ系問題は過去問より解説サイトや本から学んだ方がいいということがわかりました。グラフ系問題は色々な捻りを混ぜることのできるジャンルであり、過去問から学ぼうとしても余計な部分が多くなってしまうため、純粋なグラフ問題として予習しておいた方がいいと思いました。

ちなみに、この3連続の後はABC413-D. Make Geometric Sequenceという数学系の問題が来たため、ここで初めてD問題をコンテスト中に解くことができました。

水色になるためにしたこと

水色になるためのキーは、「解く順番」と「データ構造」です。

解く順番について

たいていの場合は問題の難易度はC<D<Eとなりますが、個人の好みによってDよりもCの方が解きやすかったり、難易度自体がD>Eのように逆転したりすることがあります。また、D問題は典型的な問題が多いため、「知ってればただ書くだけ」のようなことも多いです。そのため、C,D,E問題は一通り目を通してからどれを先に解くかを決めた方がいいと思います。

データ構造について

A~D問題は、典型アルゴリズムと実装の組み合わせが多いですが、一部のD問題とE問題以降では大量のデータを効率よく扱う必要のある問題が現れます。D問題に出題されるレベルであればstd::set, std::mapなどをうまく使うことで効率よくデータを処理することができますが、E問題以降ではstd::setよりも機能の多い順序付き集合やセグメント木や遅延伝播セグメント木などのより強いデータ構造が要求されることがあります。このようなデータ構造はコンテスト中に $0$ から作ってると時間が足りなくなってしまうので、事前に作っておくか、AtCoder Libraryと呼ばれる公開されたソースコードを利用するのが主流です。

アルゴリズム班に所属している25Bの人であって、現在水色以上のレートを持っている人の中では自作している人もAtCoder Libraryを利用している人も両方いるので、どちらを選択するかは個人の好みでよいと思います。

私は自作を選んでいます。その理由は、大きく分けて以下の $3$ つです。

• 仕様を自分で設定できる。
• 自分で作ることによって、そのデータ構造がどのようなアルゴリズムを用いて効率よく処理を行っているのかが分かり、他の問題を解くときにも応用できる。(例えば、Union Findで用いられている経路圧縮とよばれる手法があるが、これは配列上の探索の高速化などに使える。)
• 複雑なデータ構造を時間をかけてでも自分で作ることにより、実装力を鍛えることができる。

また、データ構造以外にもよく使うコード群をまとめてライブラリにすることがあり、例えば「エラトステネスのふるい, 二項係数計算, 強連結成分分解」などがあります。これらは必要になったときに作り、そのままライブラリにしてしまうのがいいと思います。

始めてライブラリを作成するのであれば、Union Findがおすすめです。
このリンク先の問題に載っているスライドが分かりやすいです。

ライブラリを色々持っていると、その知識を使うだけの問題やライブラリコピペで解けるような問題が増えるため、考察でミスをしてD問題を落としてしまってもF問題を通して逆転勝ちということも起こりえます。また、実装が面倒なC問題を瞬殺し、後の問題のために時間を稼ぐということもできます。

青色になるためにしたこと

水色から青色になるためには、安定して水色相当パフォーマンスを出し、時々青色相当のパフォーマンスを出さなければなりません。したがって、ほとんどの場合において(A,B,C,D,E), (A,B,C,D,F), (A,B,C,E,F)などの5完が必須になります。E問題以降のデータ構造の問題も解かなければならないため、最低でもセグメント木を使えるようになっておきましょう。

それに加え、この段階になってくると問題を解く速度が重要になってきます。例として、ABC444を出します。

この回はE問題の難易度が1107と、少し簡単になっています。しかし、その次のF問題の難易度が2654と非常に高くなっているため、基本的にABCにRatedで参加する人にとってはほぼ解けない問題となっています。そのため、この回は実質的にはA,B,C,D,Eの5問から構成されており、いかに早くE問題を解いたかによってコンテスト結果が決まります。
このように、難易度の大きな差が生じる回は解く速度によって結果が大きく変わってしまうため、典型問題を素早く実装する力が必要になります。ABCの多くの問題において、解く速度は知識量と類題の経験によって決まるため、過去問を色々解くことが重要だと思います。

知識と経験を身に付けるいい手段として、「他の人と一緒に考える」があります。traPではほぼ毎日、進捗部屋という部屋が用意されていて、この部屋の中で過去のコンテストの問題の解法について議論したり、データ構造に関する話を行ったりすることができます。実際、今持っているデータ構造(セグメント木, 両端優先度付きキュー, Wavelet Matrixなど)は、ほとんどが@n3と色々話して作ったり、作り始めたりしたものです。データ構造以外にも、自分の知らない典型を学んだり、賢い実装方法について学んだりすることができるため、競プロ仲間を作り、議論をするのは上達するうえでかなりよい手段だと思います。
一人で競技プログラミングを継続するのはかなり難しいと思うので、まずはtraQ上でもいいので、いろいろな競プロ仲間を作っておくのがいいと思います。特に土曜日の22:40の直後に「ABC」というキーワードで検索をすると必ずどこかのチャンネルで問題に関する議論が行われてるので、ここに突撃してみてもいいかもしれません。

最後に

特に書くことがなかったので、私が持っているライブラリを紹介しておきます。

• 平衡二分探索木(AVL木)による順序付き集合, 順序付き連想配列
• 繰り返し二乗法、有理数用floor, ceil、isqrtなどの基本的な関数
• 線形篩, 約数列挙などの素数,約数関連
• $\mathrm{mod}M$ 上での逆元を求めるアルゴリズム(拡張ユークリッドの互除法)
• modint構造体
• 二項係数計算(階乗式, 表計算式)
• 行列計算
• ガウスの消去法
• floor_sum, floor_max(この関数に関しては後から別のブログで詳細を解説します。)
• 配列の添え字の和に関する畳み込み計算の関数
• Bostan-Mori法
• 抽象化セグメント木
• 抽象化遅延伝播セグメント木
• 抽象化動的遅延伝播セグメント木
• 両端優先度付きキュー
• 完全永続配列
• Wavelet Matrix
• 双方向連結リスト
• LCAや木の直径が求まる木のライブラリ
• KMP法
• ローリングハッシュ
• ランレングス圧縮
• 最長増加部分列の長さやその部分列自体を求める関数
• 全方位木DPに関する関数

$1$ 年あればこれらを理解できるようになるはずです。特にセグメント木やWavelet Matrixはとても上手くデータを管理する構造なので、一度は自分で作ってみるといいかもしれません。

明日の投稿者は @n3 さんと @blueberry1001 さんです。