【C#】AtCoder水色になりました

5/30のNOMURAプログラミングコンテスト2020で無事水色になれました！わーい！

terry_u16さんのNOMURA プログラミングコンテスト 2020での成績：902位
パフォーマンス：1668相当
レーティング：1148→1237 (+89) :)
Highestを更新し、4 級になりました！#AtCoder https://t.co/vtygnqQuAe 入水しました！！！！！！！！！！！！！！！ pic.twitter.com/VJ5vfVPQ1K

— TERRY (@terry_u16) 2020年5月30日

色が変わると全人類ブログ記事を書くようなので、ぼくもこの機会に書き残しておきます。

自分語りパート

自己紹介

初めましての人も多いかと思うので一応自己紹介を。興味ない人は飛ばしてください。

機械系専攻の修士卒です。今は某メーカーの社畜5年目をやっています。業務中はあまりプログラミングに触れる機会はなく*1、完全に趣味でやっています。年齢を14で割ったmodを取ると0になるので、事実上の14歳JCと思って頂いて良いかと思います。

機械系だとたいていプログラミングは大学の学部でC言語とかをサラッとやって終わりなのですが、QpicというPCサークル的なところ*2でゲームやアプリを作って遊んでいたり、研究室でシミュレーション用のプログラムを組んでいたこともあり、プログラミングにはある程度慣れていました。このあたりの下地でゴリ押した感はあります。

使用言語はchokudaiさん等と同じC#です。学部1年の夏に初めてC#に触れて、かれこれ10年ほどの付き合いになります。競プロ界隈ではマイナー言語寄りなのがちょっと寂しいところですね。C#はさすがにC++とかに比べると標準ライブラリが弱い*3のですが、この辺の自作ライブラリ整備については後述します。

レート・パフォーマンス推移

始めたては緑～水下位パフォあたりをうろうろ。最近は青パフォタッチあたりで安定している感があります。

こどふぉも最近始めて現在青色。あと第三回アルゴリズム実技検定（PAST）は上級88点でした。

レーティング推移

パフォーマンス推移（AtCoder Performancesより）

水色までにやったこと

精進

新型コロナウイルスの影響で引き籠もらざるを得なかった影響もあり、精進はそれなりに捗りました。というか何ですかこの精進グラフのシンクロ率？ちょっとびっくりしちゃったんですが。

精進グラフ（AtCoder Scoresより）

Difficulty別AC数（AtCoder Problemsより）

有志の方がよるかつというバーチャルコンテストを開催して下さっているので、基本的に毎晩参加しています。水・青diffあたりの問題に恒常的に触れる良い機会になってまして、おかげさまでだいぶ力が付いた実感があります。一通り知識を付けたらあとは実践あるのみですね。

あとは最近高難易度特攻の不足を感じてきているので、AtCoder ProblemsのRecommendationでModerate～Difficultを解いています*4。早解きだけではなく、1時間くらいじっくり考える経験を積んでおく*5とコンテスト中に難しい問題に当たっても冷静に考えられるような気がします。その分疲労度も大きいですが……。

スキルセット

だいたいみんな似たり寄ったりになりそうな気はしますが、一応列挙しておきます。アルゴリズムとデータ構造がごちゃ混ぜですが許してください。

よく使う・定着している

• 全探索
• 二分探索
• 累積和・imos法
• GCD・LCM
• 素数判定・素因数分解・約数列挙
• modの逆元
• Union-Find
• 深さ優先探索
• 幅優先探索
• 二部グラフ判定
• 動的計画法（基本的なやつのみ）
  • ナップサック系
  • 桁DP（よくバグる）
• ワーシャルフロイド法
• 計算量の概算（アルゴリズムではないですが大事）

あまり使わない・見ながらじゃないと書けない

• しゃくとり法（無限にバグるので好きではない）
• bit DP
• ダイクストラ法
• ベルマンフォード法
• クラスカル法
• セグメント木
• BIT
• 座標圧縮

名前だけは聞いたことがある

• 区間DP
• LIS
• セグメント木（遅延評価）
• ダブリング
• 平方分割
• 半分全列挙
• Rolling Hash
• Z-Algorithm
• 最大流

あまり使わないものはどうしても理解があやふやになっちゃいますね……。

「名前だけは聞いたことがある」ってところは意外と大事です。コンテスト中やバチャ中に「名前だけ聞いたアレが使えるかも……？」と思い付いて調べながら実装したら通った、という経験が何度もあります。蟻本流し読みとかも良いのではないのでしょうか。おもむろにリンクを貼っておきますね。

プログラミングコンテストチャレンジブック [第2版]　～問題解決のアルゴリズム活用力とコーディングテクニックを鍛える～

自作ライブラリ

C#は競プロ用途としてはライブラリが貧弱です。lower_boundもpriority_queueもありません。なので自作します。

幸いこういうライブラリ整備は大好きなので、暇を見付けてはちまちまと作っています。オタクなので。

作ったもの

• 入力読み込み用拡張メソッド
• GCD・LCM
• 順列・組み合わせ
• next_permutation
• ModInt
• 既約分数
• 二分探索（lower_bound・upper_bound等）
• priority_queue
• モノイド
• 抽象化セグメント木（遅延評価なし）
• BIT（抽象化なし。1次元と2次元）
• Union-Find
• 座標圧縮
• Z-Algorithm
• 抽象化グラフライブラリ*6
• 深さ優先探索
• 幅優先探索
• ダイクストラ法
• ワーシャルフロイド法
• ベルマンフォード法
• 最小全域木

ふと見たらライブラリだけで2200行を超えていました（は？）Codeforcesだとファイルサイズ制限に引っかかりそうです。でもライブラリ整備は楽しいのでしょうがないですね。

セグメント木とかグラフとか、interfaceを駆使して抽象化して汎用的に使えるようにするのが好きです。競プロだとその場で書き換えちゃった方が早い感はあるのですが、モノイドとかその辺の知識も増えてより深い理解に繋がるような気がしています。

githubに上げているので一応リンクを張っておきます（長いですが……）。これをベースにソリューションテンプレートを作成して使っています。 github.com

テスト環境・自作ツールとか

提出前のテストは大事です。でも毎回手作業でやるのは面倒ですよね。

なのでVisual Studioのテスト機能を使ってCtrl+R, Aで全テストが走るようにしています。オールグリーンになったら投げます。楽です。これも先述のgithubリポジトリに突っ込んであるので、興味のある方は見てみてください。

あとはテストケースを落としてくる自作ツールがあるとコピペの手間が省けて楽になります。早解き回なんかはこの辺にだいぶ助けられている感はありますね。

おわりに

だいぶ長くなってしまいましたが、読んで頂きありがとうございます。機械系専攻ということもあり転職等にAtCoderを使うことは残念ながらなさそうなのですが、今後も良きネトゲとしてお世話になることになりそうです。

次はABC全完、*7そして青色を目指します！

*1:あってもVBAとか……。

*2:昔はもっともっと小さいサークルだったのですが、今はとても立派になっているようでおじさんはびっくりしています。

*3:あくまで競プロに限った話。アプリ開発向けは公式もサードパーティ製ライブラリもめちゃくちゃ充実していると思います。

*4:@kenkooooさんには足を向けて寝られません。

*5:「もうちょっとで解けそう」な問題がオススメです。単に知識不足っぽい場合はさっさと解説を読んでしまった方が早いです。

*6:普通のグラフとかグリッドグラフとかを統一的に扱ってDFS/BFSとかするやつ。

*7:これ書いた夜のABC169で初全完・初黄パフォ達成しました……！