AtCoder水色になるまで #C++

周りの東大生が数カ月で水色なり青色突破している中でお恥ずかしい限りですが、3年かけて水色になりました。

感想としては、競技プログラミングをするとしても、もう正直AtCoderはやりたくないです。
(Beginner Contestという名目で、プログラミング以外の数学知識（用語、公式など）の暗黙的な要求など、公的な競技というよりかは一部の高学歴の嗜みと化しているところがあまり気に食わないからですね。

環境構築

まとめると、WSLでC++を動かし、VSCodeで書いています。

言語について

Pythonが書きやすいのは僕も認めるところではありますが、Pythonだと記述の仕方だとかどのコンパイラーが都合がいいのかとかの非本質的な微調整で時間を無駄にしてしまいます。
ツイッターで「Pyhton TLE」と検索するとそのようなツイートがたくさん見られるかと思います。あるいは「ChatGPTでC++に翻訳してもらったら合格した」とも。

ただただ本質的なロジック面に集中するために C++ が推奨されうると思っています。

（だいぶ以前に、想定解をPythonで書いてもTLEするのでPython正解者が一人もいなかった問題がABCに出題されたというのが話題になっていた記憶がありますが、ソースが見つからないため噂程度に）

VSCodeを動かす

VSCodeだけでデバックできる環境を目指します。

Windows使いなので、この記事に従いました
VSCode+WSL2でAtCoderコンテスト用C++環境を構築してみる&おまけ【サマーブログリレー2021 7日目】

デバッガを使えるようにするには以下の通り。
【VScode＋WSLで始める】競プロ用C++デバッグ環境構築

ただ、この記事に関してコピペではうまくいかなかったので（コメント参照）、とりあえず僕のVSCode設定を転載しておきます。詳しくないから頑張って。

.vscode/launch.json

{
    "version": "0.2.0",
    "configurations": [
        {
            "name": "(gdb) Bash on Windows Launch",
            "type": "cppdbg",
            "request": "launch",
            // "program": "${command:extension.vscode-wsl-workspaceFolder}/problem.exe",
            "program": "${workspaceFolder}/problem.exe",
            "args": [
                "<",
                // "${command:extension.vscode-wsl-workspaceFolder}/problem.in"
                "${workspaceFolder}/problem.in"
            ],
            "stopAtEntry": false,
            // "cwd": "${command:extension.vscode-wsl-workspaceFolder}",
            "cwd": "${workspaceFolder}",
            "environment": [],
            "externalConsole": true,
            "pipeTransport": {
                "debuggerPath": "/usr/bin/gdb",
                // "pipeProgram": "${env:windir}\\system32\\bash.exe",
                "pipeProgram": "/bin/bash",
                "pipeArgs": [
                    "-c"
                ],
                "pipeCwd": "/"
            },
            "setupCommands": [
                {
                    "description": "Enable pretty-printing for gdb",
                    "text": "-enable-pretty-printing",
                    "ignoreFailures": true
                }
            ],
            // "sourceFileMap": {
            // "${command:extension.vscode-wsl-workspaceFolder}": "${workspaceFolder}"
            // },
        }
    ]
}

.vscode/settings.json

{
    "files.associations": {
        "iostream": "cpp",
        "ostream": "cpp",
        "any": "cpp",
        "array": "cpp",
        "atomic": "cpp",
        "bit": "cpp",
        "*.tcc": "cpp",
        "bitset": "cpp",
        "cctype": "cpp",
        "cfenv": "cpp",
        "charconv": "cpp",
        "chrono": "cpp",
        "cinttypes": "cpp",
        "clocale": "cpp",
        "cmath": "cpp",
        "codecvt": "cpp",
        "complex": "cpp",
        "condition_variable": "cpp",
        "csetjmp": "cpp",
        "csignal": "cpp",
        "cstdarg": "cpp",
        "cstddef": "cpp",
        "cstdint": "cpp",
        "cstdio": "cpp",
        "cstdlib": "cpp",
        "cstring": "cpp",
        "ctime": "cpp",
        "cuchar": "cpp",
        "cwchar": "cpp",
        "cwctype": "cpp",
        "deque": "cpp",
        "forward_list": "cpp",
        "list": "cpp",
        "map": "cpp",
        "set": "cpp",
        "unordered_map": "cpp",
        "unordered_set": "cpp",
        "vector": "cpp",
        "exception": "cpp",
        "algorithm": "cpp",
        "functional": "cpp",
        "iterator": "cpp",
        "memory": "cpp",
        "memory_resource": "cpp",
        "numeric": "cpp",
        "optional": "cpp",
        "random": "cpp",
        "ratio": "cpp",
        "regex": "cpp",
        "string": "cpp",
        "string_view": "cpp",
        "system_error": "cpp",
        "tuple": "cpp",
        "type_traits": "cpp",
        "utility": "cpp",
        "fstream": "cpp",
        "future": "cpp",
        "initializer_list": "cpp",
        "iomanip": "cpp",
        "iosfwd": "cpp",
        "istream": "cpp",
        "limits": "cpp",
        "mutex": "cpp",
        "new": "cpp",
        "scoped_allocator": "cpp",
        "shared_mutex": "cpp",
        "sstream": "cpp",
        "stdexcept": "cpp",
        "streambuf": "cpp",
        "thread": "cpp",
        "typeindex": "cpp",
        "typeinfo": "cpp",
        "valarray": "cpp",
        "variant": "cpp",
        "barrier": "cpp",
        "compare": "cpp",
        "concepts": "cpp",
        "coroutine": "cpp",
        "source_location": "cpp",
        "latch": "cpp",
        "numbers": "cpp",
        "ranges": "cpp",
        "semaphore": "cpp",
        "span": "cpp",
        "stop_token": "cpp",
        "syncstream": "cpp"
    }
}

.vscode/tasks.json

{
    "version": "2.0.0",
    "tasks": [
        {
            "label": "build",
            "type": "shell",
            // "options": {
            //     "shell": {
            //         // "executable": "C:\\Windows\\System32\\wsl.exe",
            //         "executable": "/bin/bash",
            //     }
            // },
            "command": "g++",
            "args": [
                "-std=gnu++1y",
                "-g",
                "-O0",
                "-I/opt/boost/gcc/include",
                "-L/opt/boost/gcc/lib",
                "-o",
                // "`wslpath",
                // "'${workspaceFolder}/problem.exe'`",
                "'${workspaceFolder}/problem.exe'",
                // "`wslpath",
                // "'${file}'`",
                "'${file}'",
            ],
            "group": {
                "kind": "build",
                "isDefault": true
            }
        }
    ]
}

テンプレートの用意

上記手順に従えばテンプレートを作れますが、僕はこんな感じでよく使うものを関数として用意しています。

それと、いつでもコピペできるようにコピペ用コードをストックしています。

中身はいろいろなサイトのコピペの寄せ集めなので著作権的に公開できないです。

前提知識面

アルゴリズム理解に必要な数学

数学センスを前提知識にするのは嫌だな～と書きつつ、さすがにこれは知っておかないとAtCoderどころかアルゴリズムできないなあと素直に認めざるを得ない数学知識はあります:

対数

$\log$とかいうやつですね。
これは二部探索などの計算量で出てきますね。
こればかりはさすがに知っておかないと解説が読めないっす。

対数自体の説明は高校数学の記事に任せるとして (難しくないよ！)、アルゴリズムの文脈で重要なのは 「対数はザコ」というお気持ちです

計算機に入れたら分かりますが、

$\log_2{10^5} \simeq 17\ $
$\log_2{10^{19}} \simeq 63\ $

というように、$log{(n)}$の中にデカい数字を入れても、出てくる数字はめっちゃ小さいです

AtCoderで出てくるようなデカ数字は高々$10^{19}$なので、$log$はザコ認識することが重要です。

調和級数は$log$扱い

たまに、計算量が
$1 + \frac{1}{2} + \frac{1}{3} + \frac{1}{4} + ...$
のようになることがあります、あるんです。
これは$O(\log{(n)})$になって、またもやザコになります。

調和級数が log(n) で押さえられることの証明

指数爆発

指数爆発とかいうのは聞いたことがあります。
ドラえもんのバイバイんが有名ですね。

$2^n$は 死ぬほどデカいという認識が重要です。
たとえば100入れるだけで

$2^{100} \simeq 1.2676 × 10^{30}$
ですからね。死ぬほどデカい。

問題を理解・回答するのに必要な数学

知っている限り書きます。

合同式

「割り算のあまり」に関するお話です。教科書の「発展的学習」の欄に記載されているため、高校によってはやっていないところも全然あると思います。

合同式(mod)の意味とよく使う６つの性質

分数の合同式

正直なんでこれをBeginner Contestに出題するのか理解できないです。

この記事は実装面だけ書いてくれてるのでいいですね。
「確率 mod 998244353」とか「期待値 mod 998244353」って何なの？という話

要するに
$\frac{A}{B}$を、$A \times Inv(B)$という一つの整数で計算してやれというルールで、$Inv(x)$の計算についてはネットからコピペしてくればいい、というお話です。

数列の公式すべて

数学Ｂ：数列公式集

とりわけ「等比数列の和の公式」を知っておかないと解答不可能な問題はちょくちょく出題されます。

グラフ

用語が説明無しで問題文に出てきます。

基本的なグラフアルゴリズムの解説とPython実装【グラフ入門】

アルゴリズム知識

無料の情報源だと、東大工学部EEICの矢谷さんの授業資料が網羅的で推奨できます
アルゴリズム（2022年度）

E問題まで、ここの知識 + 整数問題知識でだいたい解けるというイメージがあります。

現状のAtCoder ABC

ABCに傾向がないように見えて、実は変わるときがあるので（一時期はDP知ってるだけでD問題まで解けた）、ここの記述は一時的なものだと思ってください。
2024/6/20

水色に辿り着くには

まず、水色に達するためには、コンスタントにだいたい2050位以内に入らないといけません。（現在のような参加者1万人の場合）

感覚的な目安ですが、

E問題が難しい（正解者1000人程度まで）日は、D問題まで30分以内 (スピード勝負）
E問題がまあまあ解ける（正解者1000～1500人いく）日は E問題までを時間終了までに (解けるかどうか勝負）
E問題がめっちゃ解かれる（正解者1500人以上）日は E問題まで70分以内 （スピード勝負）

の3パターンがあると感じています。

各問題の位置づけ

A問題

プログラミング入門。3分で解かねばならない。
計算量を意識しなくとも解ける

B問題

制作や業務でいつも書いているレベル感。3分で解かねばならない。
計算量を意識しなくとも解ける

C問題

計算量を意識して解いてほしがっている問題
一工夫するか、あるいは基本的なアルゴリズム（尺取りや二部探索レベル）あるいはデータ構造（配列か集合か）が期待されている。

D問題

入門書レベルのアルゴリズム・データ構造を適用する問題
尺取り、深さ/幅優先探索、動的計画法、BIT、合同式問題（これは入門レベルではない）などが多いですけど、この限りではありません。
データ構造も適切に考えないといけませんね。

E問題

よくよく考えて中級程度のアルゴリズムを適用する問題
最近はクラスカル法が多いイメージですね。

正直難しいと思いますが、毎週2000人以上解けるというので皆さんすごいですね。（ChatGPTがすごい、という説もあります）

どう解くか？

計算量の意識

計算量が$10^6$以内になることを目指します。

よって、必ず制約欄をじっくり見る必要があります。

引用: AtCoder ABC351 C問題 https://atcoder.jp/contests/abc351/tasks/abc351_c

制約からどうするべきか分かったりもします。
この記事がいいですよ

競技プログラミングで解法を思いつくための典型的な考え方

順位表を見る

非本質の王、非本質キングではありますが、順位表を見ると「難しい問題」が分かったりします。

例えば、D問題よりE問題の正解者が多いという状況であれば、Dを飛ばしてE問題に移った方がいいです

飽きたのでここまで

気が向いたら続きを書きます
といっても

forのネストから計算量考えましょう

ぐらいしか言うことなし