自己紹介
ZOIといいます。記事作成時点では高2です。
学校の部活でWebページ作ったり色々してました。
努力嫌いの飽き性です(なんだそれ)
2023/2/19のABC290で入緑できて嬉しいので色変記事書きます。
注: AtCoderでは、色が変わった時に「色変記事」と題して長文をネットに晒してもいいらしいです。何も考えずに書いたせいで、自己満足のポエムでしかないですが...もしよければ読んでみてください。
競プロ再開
グラフを見てわかるように、2年半ほどほとんど参加していない時期がありますね...
なぜ競プロを知ったのか、始めたのかはあまり覚えていないのですが、再開したきっかけは結構明確にあります。
2022/11/5~6に行われた、「パソコン甲子園」です。もちろんこの時点では競技プログラミングなどできないので、スマホアプリを作る部門での参加でしたが、なんか色々あってプログラミング部門の1位の方々と話す機会がありました。
僕は基本的にポジティブ、というか都合の悪いことは気にならないタイプなので、彼らが天才であることは忘れて「僕でもやってみたら伸びるんじゃね?!」と考えました。改めて見るとひどいですね...
帰宅後、とりあえずコンテストに出てみることにしました。もちろんテンプレもなく、Web開発などで使っていたVSCodeを引っ張り出してきました。11/12、ABC277です。
グラフを見て分かる通り、上がっても下がってもいませんでした。まあやってないので当然です。
12:30での2完でしたが、この時から「解けなかった問題を見直す」ということを始めました。これがめちゃくちゃ効果的でした。(勉強でもできたらいいなあ)
この時のC問題、「Ladder Takahashi」の解説を見た時の衝撃は、強く印象に残っています。
まずこの時の僕の回答(WA)を見てみると、どうやらDPは理解しているらしい(PCKからの数日でナップサックDPを履修したんだと思います)、そしてなんかネットから貰ってきた座圧を張り付けてますね。まあこのやり方ではTLEです。
テキストでの解説もありますが、まず1行目からわかりません。グラフってなんだ、折れ線か?という感じです。そこで、公式の解説放送を見てみました。snukeさんが解説してくれるやつです。
この動画を見て、やっとグラフを理解することができました。それまでは、なんでいきなり問題文に「木」「葉」が出てくるんだ、という感じで、出てきた瞬間詰んでいました。そして、stackやqueueの使い方、DFSやBFSがいかに天才的かに感激しました。
あれ考えた人凄すぎますね... 他のことを気にせず、TODOが余っている限り簡単な操作を繰り返すだけでいつの間にか木の全域を効率よく調べているわけです。天才です。
競プロへの没頭
はい。お分かりの通り、この段階ですでにめちゃくちゃハマってます。
元々自分の書いたコードがあまりにもひどい(探索は基本全探索、アプリを作ればカクつく、処理を書けば実行時間お化け、etc...)のは察していたのですが、それらを解決する手法が目の前に現れたのです。飛びつくしかありません。
ただ、競プロの世界は化け物(褒め言葉)だらけです。強い人の多くは東大/京大に在籍しているらしく、解説も「数学は知ってるだろ」という空気感です。流石に独学は無理だと確信しました。
そこで本の購入です。この時点で、競プロの本として聞いたことがあったのは、「プログラミングコンテストチャレンジブック」...いわゆる「蟻本」だけだったので、迷わずKindleで買いました。
後から知ったのですが、蟻本はかなりハイレベル帯向けの本です。灰コーダーが読むべきものではないです。後で出てきますが、「鹿本」(簡単)、「螺旋本」、(中級)「鉄則本」、(初級〜上級? 読んでないのでわかりません)のいずれかから読み始めるべきです。最悪わからなさすぎて競プロが嫌いになってしまいますし、あの本はAtCoderのできる前の本なので、出典も英語です。
おそらく、蟻本は「ガチ勢東大生がプログラミングしてる東大生に布教するための本」です。気をつけましょう。
まあなんだかんだあって、蟻本を買いました。中の問題は全くわかりませんでしたが、解説を流し読みしてました。
前回からグラフなどの知識も増えたおかげで、次のABC278(11/19)では4完できました。突然すぎる...!
ここからレートが伸び始めます。次のABC279(11/26)では、微分を駆使してDを、その後20分でEを解くという圧倒的成績で入茶しました。この時のパフォーマンスは、現時点でもまだ超えられていません。何でやねん。
JOI
ちょうどその頃、学校にJOIのポスターが貼ってあったため、友人2人と一緒に受けてみることにしました。全員が初心者だったため、過去問を見ても誰一人わからんという感じでした...
1次予選は、11/19にあったのでそれに参加しました。時間が微妙だったので学校帰りにマクドに寄ってそこでカタカタしてました。
18:15で全完しました。ある程度早いかなと思ったのですが、Twitter上に1分台などがいらっしゃって恐怖してました。
問題は2次予選(12/11)です。JOIは、1次予選は初心者Welcomeという雰囲気なのに対して2次予選は現実を突きつけてきます。部分点はあるものの、難易度が異常に高くなっており、倍率は10倍くらいあります。結構頑張ったんですが、100-77-9-6-0で192点でした。
Twitter見てる感じボーダーは250くらい?と言われていたので諦めてましたが、実際のボーダーは208点以上でした。思ったより惜しかった? まあ不合格には違いありません。さよなら...
今に至る
そしてそのまま続けて今に至る感じです。といっても所々変わっています。
参考書
蟻本は難しすぎたので、「プログラミングコンテスト攻略のためのアルゴリズムとデータ構造」、いわゆる「螺旋本」を1/26に買いました。とても読みやすいです。
また、弟への布教用に「アルゴリズム的思考力が身につく！ プログラミングコンテストAtCoder入門」、いわゆる「鹿本」を買いました。初心者が始めに読むならこれが一番だと思います。
一応、現時点でわかってる(と思っている)のはこんな感じです。
- 線形探索
- 2分探索
- bit全探索
- 単純無向グラフ
- DFS
- BFS
- Union-Find
- トポロジカルソート・判定
- しゃくとり法
- 累積和
- ナップサックDP
- ラムダ式
- 三項演算子
逆に、下に書いているのはあんまりわかっていないです。(わかってない分野なので、似たようなものも入っているかも...)
- セグ木
- 半分全列挙
- 区間DP
- 桁DP
- 中国剰余定理
- mod除算
- ダイクストラ
- ベルマンフォード
- 最小全域木
環境
初めから変わらずMacbook Air(M1)です。キーボードも本体のものを使っています。昔からパンタグラフしか使ってこなかったので、外部キーボードは逆に遅くなるんです...
また、僕はあくまで技術オタク、つまり「何かを自動化すること」に強い喜びを感じる人間なので、当然提出などは自動化しています。具体的には、「online-judge-tools」と「atcoder-cli」を使いました。
また、以下のようなエイリアスも作っています。
alias g++-atcoder='g++ -I ~/Documents/AtCoder/include -std=c++17 -O0 -g -ftrapv -fstack-protector-all -fno-omit-frame-pointer -D_FORTIFY_SOURCE=2 -D_GLIBCXX_DEBUG'
alias g++-atcoder-fast='g++ -I ~/Documents/AtCoder/include -std=c++17 -O0 -g'
alias oj-test='g++-atcoder-fast main.cpp && oj t -e 1e-6'
alias acc-submit='acc s -s -- --no-open --yes'
alias acc-check-submit='oj-test && acc-submit'
なんかネットで調べて出てきたオプションを書いたり、よく使うコマンドをまとめただけです。真似したら使いやすくなる、というわけではないと思います。
エディタ
少なくとも再開してからはC++(gcc)でやってきているので、初めはVSCodeに拡張を入れて使っていました。ただ、途中から技術オタク厨二病を発症してしまい、現在はNeoVimを使っています。
NeoVim、というかVimをご存知ない方のために軽く説明すると、Vimは最古参レベルのテキストエディタです。だいたい1988年からあります。Windows95より前です。ちなみに僕は全然生まれてません。怖いねー
操作に多少慣れが必要ですが、マウスを使わず操作できるため慣れるととても早いらしいです。僕の場合は思考が遅いのでそんなに変わりません。悲しい...
そんなVimを多少機能追加したのがNeoVimです。違いはほぼないです。
Vimは昔のエディタなので機能が少ない、という印象を持たれると思いますが、プラグインで機能拡張ができます。過去数十年のプラグインが積み上げられてきているので、ほとんどのことはできてしまいます。
こんな感じです。(Neovideに勝手に背景画像機能を付け足したものを使っています。アズサちゃんかわいい。)
エラー表示とか補完とかめちゃくちゃ早くて助かってます。
こんな感じのプラグインを入れてます。
| プラグイン名 | 説明 |
|---|---|
| Jetpack | プラグインマネージャ |
| iceberg | 綺麗なカラースキーム |
| lightline | 画面下部が綺麗になるやつ |
| Fern | 画面右側のファイルツリー |
| indentline | インデント表示 |
| ddc.vim | 補完 |
| mason.nvim | LSPとかのインストール画面 |
| nvim-treesitter | コードのハイライトが綺麗になる |
| telescope.nvim | ファイル検索などなど |
前提プラグインとか機能追加とかは省略しています。これ以外にもいろいろあるのでぜひ探してみてください。
メモ
ある程度難しい問題だと頭の中だけでは手に負えなくなるので、何かメモのようなものを用意したほうがいいです。
初めはiPad+Apple Pencilとか、mac上のFireAlpaca+ペンタブとかいろいろやってましたが、結局慣れているルーズリーフ+シャープペンシルが最強でした。紙の大きさは限られてるけれども次の紙使えばいいし、なんだかんだ言って一番細かく書けます。
Chrome拡張
Tempermonkey
なんか色々な拡張機能(スクリプト)を入れれるやつです。おそらく、ページロード時にJSコードを埋め込んでいるんだと思います。
AtCoder用のやつをたくさん入れました。入れすぎて覚えてないですが、とりあえずコンテスト中に予想レート見れるやつとかは便利です。
その他
マウスはVimのお陰でほぼ使わないし、ルーズリーフ置きたいので使ってません。
アプリ(といってもChromeとNeovideだけですが)はどちらもフルスクリーンにして、トラックパッドで動きながら使ってます。ウィンドウだとごちゃごちゃして苦手です...
精進
競プロ界では、レートを伸ばす=精進(過去問埋め)というのが一般論っぽいのでなんか喋ろうと思ったんですが、時間がなくてほぼ精進をせずに来たので何も喋ることができません。(ええ...)
はい...精進グラフ、灰です...
流石にそろそろやらないとまずい気がしてきました。登下校の時間でできたりしないかなあ?
最後に
というわけで、入緑色変記事として、僕が競プロを始めた(再開した?)時から今の環境までをだらだらと書いてみました。
実は1年後には受験なので競プロばっかやってる場合なのかは諸説ありますが、「レート変動チャンスが1週間に1回しかない」ので、他のゲームとかよりは時間を溶かさないはずです。きっとそうです(現実逃避)
まあすぐにでも再入茶しそうな感じはありますが、ぼちぼち頑張っていこうと思います。
それではみなさん、良い競プロライフを!