AtCoder黄色になった話

はじめに

僕は大学で情報ではなく化学をやっている人です。
それでも、約四年間AtCoderをやることで黄色になることができました。
しかし、情報についての知識はかなり無いので、アルゴリズムにだけ詳しい謎の生命体になってしまいました。
具体的にどれくらい知識がないかというとプログラムを書いて他のファイルを開くやり方すら知りませんし、簡単なWebページを作成するだけで死にそうになります。

AtCoder黄色になったコンテスト(ABC 233)

ABCDEGの6完で7817人中120位、パフォーマンス2400。
色変した記念のコンテストなので解説でも入れておきます。

A - 10yen Stamp

$${X\ge Y}$$なら$${0}$$、それ以外は$${Y-X}$$円以上が必要で$${(Y-X+9)/10}$$(整数の割り算)が答えです。

B - A Reverse

いわれた通りに文字列操作。

C - Product

DFSで全探索しましょう。
制約から必ず組み合わせが10^5以下なので通ります。

D - Count Interval

尺取り法で……と言いたいところですがマイナスもあるのでそう簡単にはいきません。
この問題は$${S_i=\sum_{k=1}^{i}A_i}$$とすると$${S_i-S_j=K}$$となる$${i}$$未満の$${j}$$の個数を数える問題と言い換えられます。
これは今までの$${S}$$を連想配列(map)などに記録しておくことで$${O(N\log N)}$$で解けます。

E - Σ[k=0..10^100]floor(X／10^k)

上からi桁目の数を$${A_i}$$とし、$${S_i=\sum_{k=1}^{i}A_i}$$とすると、答えは

$$
\sum _{i=1}^{|X|}S_i*10^{|X|-k}
$$

これはとても大きくなりますが、各桁に配列を割り当て、下の桁から上へ繰り上げていくことで解けます。

G - Strongest Takahashi

4次元DP(二次元の区間DP)+二次元累積和で$${O(N^5)}$$

$$
dp[d][u][l][r]=[d,u)*[l,r)の長方形内のブロックをすべて破壊するのにかかる体力の最小
$$

という配列を作成し、初期化は

$$
dp[d][u][l][r]= \left\{ \begin{array}{l} 0\ \ \ \ \ \ [d,u)*[l,r)が正方形でその中にブロックがない \\ r-l\ \ \ \ \ [d,u)*[l,r)が正方形でその中にブロックがある\\ INF\ \ \ \ \ \ [d,u)*[l,r)が正方形でない \end{array} \right.
$$

遷移は$${[d,u)}$$の区間が狭い順、$${[l,r)}$$の区間が狭い順に行い、$${d,u}$$について$${d<k<u}$$となる$${k}$$すべてにおいて

$$
dp[d][u][l][r]=\min(dp[d][u][l][r],dp[d][k][l][r]+dp[k][u][l][r])
$$

$${l,r}$$について$${l<k<r}$$となる$${k}$$すべてにおいて

$$
dp[d][u][l][r]=\min(dp[d][u][l][r],dp[d][u][l][k]+dp[d][u][k][r])
$$

AtCoder黄色になった頃のライブラリ

• ユークリッドの互除法(拡張も含む)

• 階乗・累乗・コンビネーション(区間和、カタラン数やリュカの定理含む)

• 行列累乗

• きたまさ法

• Union-Find木

• 中国式剰余定理(バグってる)

• 約数列挙

• 最長単調増加列(LIS)

• Zアルゴリズム

• セグメント木(2Dセグメント木も含む)

• 復元ありのBFS(二次元グリッド)

• グラフ系アルゴリズム(ベルマンフォード法・ダイクストラ法・ワーシャルフロイド法・プリム法・トポロジカルソート・フォードファルカーソン法・強連結成分分解(SCC))

• 最長共通部分列(LCS)

• オイラーのトーシェント関数

• Mex(使われていない次の数を$${O(\log N)}$$)

• マンハッタン距離の最小・最大

• 全方位木DP

• 転倒数(分割統治)

• エラトステネスの篩(区間篩・素因数分解含む)

• 高速ゼータ変換

• ローリングハッシュ

• カーテシアン木(デカルト木)

• 簡単な多倍長整数(和・差・カラツバ法による積)

• Convex Hull Trick

• Monotone Minima

黄色になるためやったこと

ずっと青色で停滞していて苦しんでいたのですが、解説をみてもいいけど一日黄Diff以上を一問以上通すということを一か月くらい続けたことで青から抜け出せました。

爆裂精進

これが続けられたのはICPCの予選で失敗し自分の弱さを確認したためです。

最後に

大学卒業前に黄色になれてよかったです。
ここまで来たらだいぶ強いと思います。
競技プログラミングを知らない人にAPEX Legendsで例えるとマスターくらいです。
とはいえTwitterには競技プログラミング魔人が跋扈しているのでここまで強くなっても怖いですね。

レートの人数分布