【入水記事】水コーダーになりました！！【AtCoder】

はじめに

はじめまして！競技プログラミングをやっている高校生のButterFlvです！

5/19に開催されたAtCoder Regular Contest 178にてレートが1200になり、水コーダーになったので記念に記事を書きたいと思います！

誤りなどあるかもしれないので軽く読んでいただけると嬉しいです！

自己紹介

AtCoder -> https://atcoder.jp/users/Butterf1v
Twitter -> https://x.com/ButterFlv_beats?t=Jgfte2qGH6DQPDaeRbDObQ&s=09
その他、下の記事に書いています！

入水までの期間

自己紹介記事にも書いていますが、現在のアカウントは作り直しているのでAtCoderのコンテストに参加し始めてからは約半年かかっての入水となっています。
（↓前のアカウント）

勉強したアルゴリズム

僕が使えるアルゴリズムと理解度（★1～5）、つかえる度（★1～5）を表にしました。

つかえる度は最近のABC, ARCの水perfを出すのに解きたい問題たちの中で、よく要求されるものほど高くなっています。

アルゴリズム	理解度	つかえる度
DFS	★★★★☆	★★★★★★
BFS	★★★★★	★★★★★★
ダイクストラ法	★★★★☆	★★★★★
二分探索	★★★★☆	★★★★★★
しゃくとり法	★★★★☆	★★★★★
累積和	★★★★★	★★★★★★
imos法	★★★★☆	★★★☆☆
bit演算	★★★☆☆	★★★★★★
bit全探索（＋半分全列挙）	★★★★★	★★★★★
普通の数え上げるDP	★★★★☆	★★★★★
bitDP	★★★★☆	★★★☆☆
木DP	★★★☆☆	★★★★☆
その他のDP	★★☆☆☆	★★★☆☆
セグメント木	★★★★☆	★★★★★
遅延評価セグメント木	★★★☆☆	★★★★☆
フェニック木	★★★★☆	★★★★★
RAQ & RSQ フェニック木	★★★★☆	★★★☆☆
Union Find	★★★☆☆	★★★★★
ゲーム	★★★★☆	★★★★☆
平面走査	★★★☆☆	★★★☆☆
座標圧縮	★★★★★	★★★★☆
最小全域木	★★★☆☆	★★★☆☆
文字列のhash	★★★☆☆	★★★★☆
ダブリング	★★★★☆	★★☆☆☆
最大フロー問題	★☆☆☆☆	★☆☆☆☆
FPS (NTT)	★★★★☆	★★★☆☆
LIS	★★☆☆☆	★★★☆☆
平方分割	★★☆☆☆	★☆☆☆☆
ユークリッド互除法	★★★★★	★★★★☆
他の数学（特に整数）	★★★★☆	★★★★★

競プロ環境

• 言語は Python(PyPy3がメイン)
• ブラウザは brave
• エディタは VSCode
• Pythonの手元実行はコマンドプロンプト

Python について

実行時間の面で不利になりがちなPythonですが、僕が出会った問題の中で損をしたものは少ない()ので水コーダーになるのには問題ないと思います。言語間の違いは定数倍の違いなので言語を変えるというよりは書き方を工夫することを意識してみるのもいいかもしれません。Pythonにはそれほどのメリットもあります。（多倍長整数や文法のシンプルさ）以下に効果的だと感じた書き換えを少し書きます。

• 配列の参照を for i in range(len(配列)) から for elm in 配列 に変える
• ある長さの配列をすべて同じ値で初期化するとき、for文ではなく [要素]*N （Nは個数）を使う（ただし、シャローコピーとなるので二次元配列の初期化をするときは注意）
• heapq(priority queue) や deque を使うとき、探索する頂点に関する複数の値を１つの tuple にして挿入するのではなく、$N$進数にして挿入する
  例：グリッド上の全探索をダイクストラ法でheapqを使って行うとき、(costの最小値, i行目, j列目) のようなタプルとして挿入するのではなく、$N=(行および列の考えうる最大値)+1$として $(\mathrm{cost}の最小値)\times N^2 + (i行目)\times N + (j列目)$ を挿入する。
  （ダイクストラ法でやりたい操作は、『コストの最小値を取り出す』$\Longleftrightarrow$『最上位の桁を比較する』、という対応があるので達成できている）

brave について

Youtube を見るときに広告を消してくれることが多いので便利です（？）

VSCode について（好きな拡張機能など）

Theme

割とよく変えますが、今一番気に入っているのはShades of Purpleです。ページはこちら。かっこいいです！！

ranbow indent

インデントの深さごとに色を付けてくれます。

余計なパーティクル

Power Mode というタイピング時にカーソルの近くにパーティクルや花火を表示させる拡張機能があってコーディングが盛り上がるのでおすすめです。人によっては邪魔かもしれません。

その他

VSCodeには拡張機能でなくても設定で付加できる便利な機能がいくつかあります。

コンテストに参加するモチベ！？

僕はコンテストに参加するときは決まって Monster エナジードリンクを飲むようにしていて、それがある種のモチベーションになっていたりもします。（そもそもコンテストに参加すること自体が楽しいので他のモチベは必要ないですが）

ここで好きなMonsterを発表します

MONSTER ULTRA PARADISE

• 1800 perfを出したときに飲んでたやつで、頼りにしています。（?）
• キウイの酸味が他のモンスターにない独特な味を作り出していて、とてもすっきりとしています。
• 一番好きです。プロフィール画像にしているくらい好きです。

MONSTER PIPELINE PUNCH

• おそらく一番人気の味なのではないでしょうか。
• 甘みが強くフルーティーで、しかしモンスターらしさも確かに感じられる、そんな味です。
• この味は特に集中力を上げてくれるのでおすすめです！

MONSTER MANGO LOCO

• 酸味が強めでおいしいです。モンスターはシンプルに甘いやつが多いのでこういうのがたまに無性に飲みたくなりますね。
• あと缶の見た目がかわいらしい...

MONSTER KHAOS

• もう名前からおいしそうです。
• 果汁30%からわかるようにとてもフルーティーで甘みが強くおいしいです。
• 山口にぜんぜん売ってないので売ってください！！

MONSTER ULTRA VIOLET

• これは割と最近に日本上陸してきたやつですね。
• 思ったよりグレープ感が強くて甘さが若干抑えめなので僕が好きなタイプのモンスターです！
• グラスに注ぐとまたいい感じの色をしてます。
• というかこの缶イカツすぎませんか？？？？？
• ZERO SUGER なのもいいですね(((

最近大事だなーと思い始めたこと

ペナはほんとうに痛すぎる！！

• ペナルティは一回5分です。いわゆる崖回では同じ点数でも時間によって 大きく パフォーマンスが変わります。例えば東京海上日動プログラミングコンテスト2024（AtCoder Beginner Contest 355）では同じABCD4完でもパフォーマンスに 778～1810 の差が生まれます。（僕は大負けしました。）
• 特にARCの崖回で遅解きをすると取り返すのがABCに比べて圧倒的に難しくなるので、１ペナ５分のために提出する前に１分くらいコーナーケースがないか探してみるのもいいと思います。（特に、未証明のままなんとなく書いてサンプルがすべて通った時は怪しいです）
• 僕はこれでかなり悔しい思いをしました。"はじめに"のグラフを見ていただけるとわかりますが水直前まで急上昇している部分があります。実はペナがなければ余裕で入水していて、たったの１ペナによりパフォーマンスが1926→1800まで落ちて入水を逃しています。（順位もちょうど100位下がりました）そのあとの約１時間半、定期的に順位表を見ながらペナを後悔していたので、ペナはほんとうに避けましょう。

言語への理解、アルゴリズムへの理解

• 言語のもつ特徴のせいでハマったときは意外とその原因に気づきにくいのであらかじめ知っておくといいです。（C++だとオーバーフロー、PythonだとPyPyの再帰関数が遅い・ライブラリで深さの上限を上げないとエラーになるなど）
• ソートアルゴリズムなど、実用上内部の動きを知らなくても良さそうなアルゴリズムの知識が問題を解く上で必要になることもあります（例：ARC179 C - Beware of Overflow）

冷えてかなしいとき

• 問題はたったの６or７しかないので、「みんなが解けるのに自分だけ解けない！！」なんてこともあって当然です。そういうときは終わった後に解説を読んで理解すればＯＫ～！の精神で行きましょう

勉強したいこと

• 最近AHCにも参加し始めたので焼きなまし法やビームサーチといったアルゴリズムを書けるようになりたいです。
• ABCの過去問を解いて、知らない典型を減らしたいです。

おわりに

• 今後は青コーダーを目標にがんばります！
• AJLもあるので高3 Algorithmで最終20位以内、Heuristicで最終10位以内を目安に良い結果を残せるよう努力します。

ここまで読んでいただきありがとうございます！！