【振り返り】初！競プロからひと月

RNSです

10月10日に初めて競プロのコンテストに参加しました

最初は時間制限にテンパり

ケアレスミス、考慮もれの嵐だったことを

鮮明に覚えています

3回目のコンテストまでは似たような感じで

とても壁にぶつかりました

そんなこんなで早くもひと月がたち

ようやく最初の色がつきました

直近の4 5 6回目のコンテストは、改善と学習の効果をとても実感できました

今では300点以下の問題は30秒程度で一発クリアできるようになりました

目標としては2021年3月までに水色になりたいです

言語はGolangのみでやっていこうと思っています

今回の記事では

何にぶつかったか　何を知ったか

どんな改善をしたか(主にGolang事情)

を残そうと思います

同じく競プロを初める人の参考になれば幸いです

注意：私のレベル感

私は大学では情報工学を専攻していました

現在はエンジニアとして働いています

そのため数学、グラフ理論、プログラミングに疎くはないです

AtCoder プロフィール

https://atcoder.jp/users/rns

ここからが本題です

まずこれまでの問題で出てきたもののうち

私がもともとわかっていた知識がこれです

• O(n)の意味
• 2分探索
• グラフ理論のうち、幅優先、深さ優先、ダイクストラ
• ユークリッドの互除法
• 一番速い素数判定
• bit演算

これらについては言及しませんが

どれも必要だと思います

ここからは新しく学んだことの一覧と解説です

知らないだけで解けない壁

• モジュラ逆数
• オーバーフローケア
• Union-Find
• next_permutation

慣れないと難しかった壁

• 動的計画法

知って便利だったこと

• Segment Tree
• 平方分割

モジュラ逆数

まず初めに驚いたのがこれです

modの世界で割り算、、、

どうやるんだ、、、

7 / 2 (mod 3)

これがわからなかったです

3.5 (mod 3) も 7 mod 3 / 2 = 0.5

もmodの世界であまりが少数になり

訳がわかりません

modの除算は逆元の乗算として扱います

よく考えると行列の世界でも逆元をかけました

この逆元がモジュラ逆数です

計算したい人はググりましょう

Combinationとmodがからむ時も必要になります
nCr = n!(n-r)!/r! // modの世界でr!で割る時に必要

オーバーフロー

Golangでの話になります

Golangで普通にpowやlogを計算しようとすると

mathライブラリを使うことになります

mathライブラリの出力はfloat64型です

なのでこのライブラリの出力を最後に

intに戻したい場合オーバーフローがおきます

int(math.Pow(10, 17)) // 100000000000000000
int(math.Pow(10, 18)) // 1000000000000000000
int(math.Pow(10, 19)) // -9223372036854775808

解決方法は簡単で

mathライブラリにあるメジャーなオペレーションは

自前実装しましょう

pow log fact あたりですね

また先に引き算、割り算をするなどはもちろん必要です

平均の例

(a + b) / 2 // x
a + (b - a) / 2 // o

Union-Find

初見殺しです

要素を集合に分けて扱う時に便利です

そこそこ必要になるので必須です

ぐぐったら出るので名前の紹介程度に

next_permutation

nPr を列挙したい時がたまにあります

この関数はC++の組み込み関数で

引数の順列の辞書順で次の順列を返します

ex. next_permutation(123) -> 132

当日に0から実装すると時間がなくなるので

あらかじめ用意しましょう

動的計画法

主に高速化のためのものだと思っています

漸化式のn項目を求めるイメージです

An = An-1 + b

この時(複数回計算する必要があるかもしれない) An-1 が

事前に計算されていることによって

An が速く求まります

これ自体は簡単です

いつ使えるか、どう立式するかが大切なやつです

実装方法は大きく2つあります

メモ化再帰とfor文です

私のレベルだと違いがわかりませんが

なんとなくこの問題はこっちの方が実装しやすい

とか感じます

Segment Treeと平方分割

配列の要素が多い時に使う高速化テクニックです

どっちも要素nを分割しておいて

その区間内での結果をキャッシュするイメージです

これは必須ではないと思うので軽めで

Golang環境の改善

ここからはGolangで競プロをやるにあたって

改善したことを書きます

Golangは記述量が多い

Golangは基本forとifで記述することになります

配列の最大値を求めるのに3行必要です

max := 0
for i := 0; i < n; i++ {
    if arr[i] > max { max = arr[i] }
}

なので汎用的なメソッドは

あらかじめ用意する必要があります

競プロは時間との勝負なので

任意ではなく必須だと思っています

ファイルの変更を検知して自動で実行

realize というライブラリを使っています

ファイルを保存するたびにgo runが走ってくれます

これも必須だと思います

エッジケースの修正などで直しては実行を

何回も繰り返すことが多いからです(私だけかもしれません笑)

Localでのみprintする関数を用意

func d(r ...interface{}) {
    if os.Getenv("RNS") == "true" {
        fmt.Println(r...)
    }
}

デバッグ関数を提出前に消すようにすると

消し忘れでペナルティをもらいます

環境変数をセットしローカルを判定します

もしAtCoder運営の方がこの記事を読んでも

実行環境にこの環境変数をセットしないでください笑

終わりに

以上がこのひと月で

知ったり工夫したことでした

できるだけ速く水色になるために

500~600点の問題を1日に1つ解くようにしています

同じくらいの色の人はフォローしてくれると嬉しいです

競プロ勢ならフォロー返します