AtCoderで黄色になりました
ABC190 で黄色になりました。
進捗状況
黄色達成時はこんな感じでした。
黄色になるまでやったこと
色んな〇〇埋めをやってましたが、その中でも有効だと感じたものを挙げていきます。
ABCを全部埋める
これが一番の近道だと個人的に思いました。もちろん企業コンのABCも含みます。ABCの問題はいわゆる典型がほとんどなので、これを埋め終わる頃にはかなりの基礎知識が身につくはずです。
緑～青diffを全部埋める
黄色になるためには青diff以下を早く解けば良くて、黄diffを解けるようになることは必ずしも必須とは限りません。実際、自分はコンテスト中に黄diffを通したことは1回しかないです (ARC104 C. Fair Elevator)。青diff以下を早解きできるようになるために、同じレベルの問題をたくさん解いて引き出しを多くすることが大事だと思います。
Educational DP Contest (EDPC)を埋める
これはDPの教育的な問題が26問あるコンテストです。自分はW,X,Z以外は埋めました。様々なタイプのDPがあり、ここにあるDPと同じアプローチで解ける問題がたくさん出題されています。全方位木DPとか部分集合を列挙するのbitDPとか、知らないと解けないDPもあるので一通り問題に触れておくと良いと思います。
今後
上でも書いたように自分はコンテスト中に黄diffを通したことが1回しかなく、また、考察力もないためARCやAGCで黄パフォ以上を出したことが一度もないです。現状だとここからレートを伸ばすことはかなり厳しいです。今後は、蟻本がARCの対策になるとあるレッドコーダーの方が仰っていたので、蟻本を進めたいと思います。蟻本を進めつつ、黄diffや700、800点問題をじっくり考えて取り組み、考察力をつけたいと思います。
HaskellでModintを実装
最近Haskellの勉強を始めました。最初に作りたかったものがModintだったので、型クラスの定義の仕方を学んで早速作ってみました。
Modintとは
競プロの数え上げなどの問題でよく見るこれ
次の条件を満たす○○が何通りあるか求めてください。
- (条件1)
- (条件2)
- …
ただし、答えは非常に大きくなる場合があるので、998244353で割った余りを出力してください。
で使うアレです。modを意識せずに計算できるので、Modintがあると便利です。
実装
class (Integral a) => Modint a where p :: a modp :: a -> a (+%) :: a -> a -> a (-%) :: a -> a -> a (*%) :: a -> a -> a (^%) :: a -> a -> a inv :: a -> a (/%) :: a -> a -> a instance Modint Int where p = 998244353 modp a = mod a p a +% b = modp $ a+b a -% b = modp $ a-b a *% b = modp $ a*b a ^% 0 = 1 a ^% x = let aa = modp $ (a ^% (div x 2)) ^ 2 in aa *% (a ^ (mod x 2)) inv a = a ^% (p-2) a /% b = a *% (inv b)
はい。特に解説はしません。
階乗とcombinationも
Modintと一緒に使うことが多い階乗やcombinationもついでに実装します。
import qualified Data.Vector as V facts :: V.Vector Int facts = V.scanl (\acc x -> acc *% x) 1 $ V.generate 200200 (+1) fact :: Int -> Int fact = (facts V.!) comb :: Int -> Int -> Int comb n r | n < 0 || r < 0 || n < r = 0 | otherwise = (fact n) /% (fact r) /% (fact $ n-r)
上のコードではまで計算できますが、必要に応じて書き換えます。
