Rubyで競技プログラミング
背景
個人的に緑~水色くらいまでイケればひとまず充分なのでそれなら普段描き慣れているRubyで参戦できれば楽しそうと感じた。少々Ruby特有のハックが必要なこともあるっぽい( Ruby競プロTips(基本・罠・高速化108 2.7x2.7) を参照 )のだけどD問題くらいまでならなんとかなりそう。10^6がギリギリみたいな話やN^2やN^3系の問題もシビアっぽいのだけど、そういう時はCrystal使えばいいかくらいな気持ちで雑にやってみたい思う。 やること
水色までに必須の知識
計算量の見積もり力
全探索
modの巡回性質
式変形
エラトステネスの篩
gcd、lcmの理論
処理すべきクエリQがいっぱい出てきたら大体使う
その他の知識(随時追加)
負辺: 負の重みを持つ辺
負閉路: 長さが負の閉路。負閉路を持つグラフでは(そこへ到達するパスがあるかぎり)そこをぐるぐる回ればいくらでも重みを小さくできるので最短経路が求められない。
不変量
AtCoderで出来なかった問題
リンク
問題集
解説集
けんちょんさんのQiita全て
競プロの典型アルゴリズム解説が豊富
Ruby用便利情報満載
その他
解説が程よい丁寧さ。ど初心者向けではないが。
自分のメモコード