😎

AtCoderでレートが黄色になりました

2021/03/15に公開

.NET

競技プログラミング

tech

AtCoderでレートが黄色になりました

最初の2年では2回しか参加していないので実質開始2年ほどでしょうか。黄色になりました。

黄色になったので記念にやったことを記していきます。

C#の仕様に詳しくなる

C#はそれなりに高速でありながらも高級な記述力を持っているので、仕様に詳しくなると高速で汎用的な記述もできるようになります。

構造体をジェネリック型引数に渡すと実行時に高速というテクニックは筆頭です。

ライブラリを充実させる

C#はライブラリを非常に書きやすい言語です。

過去問を解いていてライブラリ化できそうなものがあれば片っ端からライブラリ化しました。

下記の記事にライブラリの使い方をまとめています。

これまでに作ったライブラリ

Mainメソッド(！？)(後述)
Bit演算
- PopCount, MSB, LSB
- ParallelBitDeposit(Intel Intrinsics の _pdep_u32)
- ParallelBitExtract(Intel Intrinsics の _pext_u32)
- Bitが立っているか判定
- 立っているBitの列挙
- 2進数文字列化(デバッグ用)
PriorityQueue
Set(赤黒木) System.Collections.Generic.SortedSet<T>を二分探索可能にして移植
- SetDictionary: multiset的なもの
- [x, y]の範囲を保持するやつ
- [x, y)の範囲を保持するやつ
定数倍高速化したList<T>
Comparer<T>の構造体とクラス
SparseTable
WaveletMatrix
2次元のFenwickTree
ACLのFenwickTreeの二分探索
区間加算できるFenwickTree
2次元セグ木
SegtreeBeats
SegtreeBeats
~~StarrySkyTree~~ (もはや不要)
永続セグ木
文字列
- BM法
- KMP法
- RollingHash
- Z-Algorithm
- SuffixArray
Trie
累積和ラッパー
2次元累積和ラッパー
ジャグ配列を一気に初期化
配列の便利拡張メソッド
- 値のフィル
- ソート
- マイナスインデックスで後ろから見る
- 範囲外アクセスでダミーを返す
コレクションの便利拡張メソッド
- List<T>をSpan<T>にするやつ
- Dictionary<TKey, TValue>の存在しないキーでダミーを返す
- 連続する要素をひとまとめにする
- 2次元のコレクションを1次元に平滑化
- インデックスをつけて列挙
- 要素数をカウントしたDictionary<TKey, TValue>
- MaxBy, MinBy 的なやつ
最大値、最小値に更新するやつ
配列などの二分探索
UnionFind
重み付きUnionFind
部分永続UnionFind
永続UnionFind
DynamicConnectivity
重みなし、重みつきグラフ
- 重み以外の要素も乗せられるやつ
- オイラーツアー
- オイラー路
- 強連結成分分解
- 最小共通祖先
- 最短経路
  - BFS
  - BellmanFord
  - Dijkstra
  - WarshallFloyd
- 最小全域木
  - BFS
  - Kruskal法
  - Prim法
- 最大流
- 閉路検出
- 木の子孫数を数える
- 木を(幅/深さ)優先探索するときに訪れる順序に並んだインデックスを返す
有理数
- 分母,分子をlongで保持
- 分母,分子をBigIntegerで保持
BigIntegerを自前でパース
数学的な関数
- 最大公約数
- 最小公倍数
- 約数列挙
- 高速な冪乗
- 組み合わせ関数
多項式
素数列挙
- 素因数分解
StaticModIntの便利メソッド
- 組み合わせ
- 重複組み合わせ
- 順列
行列
- 加減乗
- 冪乗
- 行列式
- 逆行列
グリッド
- 範囲外でデフォルトを返す
座標演算
- いろいろ
座標圧縮
スタックを多めに確保して実行

ライブラリをすぐ使えるようにする

こんなにたくさんのライブラリを作ってもすぐに使えなかったらもったいないのですぐに使えるようにします。

競技プログラミングの実力の向上には直接繋がらないのですが、コードを気持ちよく書くことができるという点で非常に大きな効果がありました。

これを書いていなかったら成長速度はもっと遅かったんじゃないかなと思います。

ライブラリのソースコードを埋め込む

ライブラリのソースコードを埋め込むためのライブラリ、ソースコードソースジェネレーターライブラリ SourceExpander.Embedder を作成しました。

/home/source/A.cs

using System;

namespace N
{
    class A
    {
        public static int Foo() => int.MaxValue;
    }
}

/home/source/B.cs

namespace N
{
    class B
    {
        public static int Bar() => A.Foo();
    }
}

上記のようなライブラリがあったとき、下記のようなJSONを作ってAssemblyMetadataに埋め込みます。

埋め込むJSON

[
    {
        "CodeBody": "namespace N\n{\n    class A\n    {\n        public static int Foo() => int.MaxValue;\n    }\n}",
        "Dependencies": [],
        "FileName": "Project>A.cs",
        "TypeNames": [
            "N.A"
        ],
        "Usings": [
            "using System;"
        ]
    },
    {
        "CodeBody": "namespace N\n{\n    class B\n    {\n        public static int Bar() => A.Foo();\n    }\n}",
        "Dependencies": [
            "Project>A.cs"
        ],
        "FileName": "Project>B.cs",
        "TypeNames": [
            "N.B"
        ],
        "Usings": []
    }
]

埋め込む動作

Usings

あとで使うためにusingは埋め込む時点で分離しておきます。

C#ではnamespaceの中にもusingを書けますがそっちは分離しません。その方が小回りが利きます。

定義されている型

ソースジェネレーターではコンパイル時の情報を取得できるので、

構文木から構造体やクラスの定義を見つける
定義されている型の名称をコンパイル情報から取得する

とすることで定義されている型を取得できます。

依存関係

メソッドの戻り値、引数、変数、メソッド呼び出し、型引数などあらゆる箇所から使用している型の情報を取得できます。

その型が別途埋め込まれた型ならば依存関係に追加することで実現できます。

強連結成分分解そのものですね。

埋め込んだソースの利用

埋め込んだソースを SourceExpander で使用します。

問題を解く際に使用した型の依存関係を解決して、埋め込んだソースを展開するという単純などうさです。

あらゆるライブラリを別のファイルに置くことができるので、実際にコードを書くファイルは非常に簡潔にできます。

依存関係の解決を上手いことやることでMainメソッドさえもライブラリ側に持たせています。

実際の例

問題を解く部分とライブラリが結合されて一つのファイルになるので、そのまま提出できます。

アナライザーで高速な記述

アナライザーも書いてさらに快適なコーディングを目指します。

int から long へのキャスト

long N = 1L << 50; // 問題の入力のつもり
for(int i=0;i*i<=N;i++){

}

こういう記述をすることってよくありますよね。しかし、このコードは危険です。i*iがオーバーフローする危険があります。

正しいコード

long N = 1L << 50; // 問題の入力のつもり
for(int i=0;(long)i*i<=N;i++){

}

こういうint*intをlongに代入する危険なコードがあったら警告を出して自動で修正するアナライザーを用意しました。

余計なバグをアナライザーで避けられるなら良いですね。

セグ木を速やかに書く

セグ木の実装はモノイドを用意しなければならないので面倒ですね。

そこでアナライザーで自動生成するようにしました。

何を書かなければいけないかがすぐわかるので、セグ木を書くときに余計なことを考えずに済みます。

最後に

ここまで整えたライブラリを駆使すれば非常に気持ちよくコードを書けるようになります。

Before

💡「この問題はセグ木で解ける！」
セグ木ライブラリをコピペして
セグ木ライブラリにモノイド演算を書き込んで
計算を記述するメソッドに戻って(セグ木をコピペしたのでだいぶ離れてる)
完成！

After

💡「この問題はセグ木で解ける！」
セグ木を呼び出す
自動生成された型にモノイド演算を書き込んむ
計算を記述するメソッドに戻って(一画面に収まってるのですぐ戻れる)
完成！

2,3,4の手順が大幅に簡略化されてコードを書く際のストレスが非常に低減されます。

ということで競技プログラミングをやるときには気持ちよくコードを書ける環境を整えるのがおすすめです。

本記事のライブラリはNuGetで公開しているので、ライセンスの範囲でご自由にお使いください。

GitHubで編集を提案

AtCoderでレートが黄色になりました

C#の仕様に詳しくなる

ライブラリを充実させる

これまでに作ったライブラリ

ライブラリをすぐ使えるようにする

ライブラリのソースコードを埋め込む

埋め込む動作

Usings

定義されている型

依存関係

埋め込んだソースの利用

実際の例

アナライザーで高速な記述

int から long へのキャスト

セグ木を速やかに書く

最後に

Discussion