メモ

yukicoderでゆるふわgolf

atcoder青になるまでにやったこと

注:この記事はマジもんのポエムです
こんなものを読むくらいなら精進しろ

2015年以前

学校の授業でBASICとCとSchemeを触る

2015年8月

ふるふわ競プロサイトyukicoderと出会う
最初のACがこれ
https://yukicoder.me/submissions/41598
このときコードゴルフというものの存在を知り、興味はそちらへ
3日後の成長がこれ
https://yukicoder.me/submissions/42583

そんな感じで主にgolf場としてyukicoderの低難易度問題で遊んだ
あなごるは知らない
yukicoder★2の問題を半分くらいは解ける実力をすでに持っていたようだ

2016年6月

数学系プログラミング問題を出題するproject eulerに出会う
最初の4日間で120問くらい解いたらしい。暇人かな?
第1問はこんな感じ:「1以上1000未満の数のうち、3または5で割り切れる数の合計を求めよ」
簡単ですね。
ちなみに最近出題された第625問はこんな感じ:「\sum_{i=1}^{10^{11}}\sum_{j=1}^{i}\gcd(i,j)を求めよ」
(※ML512MB、TL60sが目安)
簡単ですね。

現在までに300問以上解いているのでsolve数ランキングはかなり上の方。
競プロに関する諸処の知識は主にここで得たため、数論方向に非常に偏っている。

2018年

atcoderに参戦する
存在はかねてから知っていたが、レートがつくガチなコンテストとして敬遠していた。
が、1つくらいそういうのをやっても悪くないと思い直し挑戦。
2400近いパフォを2連発したおかげでコンテスト参加回数3回で無事青に。

現在

黄色にはなれない模様
蟻本なるものを読んだ方がいいんですかね……

atcoder参戦以前の時点で持っていた(使える)知識以下

・基本的なあれこれ(BFS/DFS、にぶたん、しゃくとり、etc)
・基本的なDP
・繰り返し二乗法
・UF
・累積和/imos法
grundy
・セグ木
・拡張gcd
・エラトステネス/区間
・Miller–Rabin(素数判定)
・きたまさ法
・行列累乗によるDP高速化
FFT(NTT)
・Berlekamp–Massey algorithm(線形漸化式復元)
・Tonelli–Shanks algorithm(mod pでの平方根

atcoder参戦以降で覚えたもの

・グラフアルゴリズム三種の神器(WF、BF、Dijkstra
・凸包
・遅延セグ木

書いたことがないもの、遥か昔に1度やったきりで覚えていないもの

・三分探索(書こうと思えば書けるはず)
・平方分割(同上)
・最大流関係
・グラフ関係(クラスカル法、強連結成分、etc)
・幾何関係
・文字列関係