AtCoder Beginner Contest 021

 C問題の方が難しい…。

結果

 300/400 40:54 85位相当


 開始時刻 2017/08/04 10:52:00 提出履歴

A: 足し算 - AtCoder Beginner Contest 021 | AtCoder

 1:03(AC)
 1をN個出力すればAC。

B: 嘘つきの高橋くん - AtCoder Beginner Contest 021 | AtCoder

 6:19(AC)
 既に通った場所を通るようだと最短経路でゴールに辿り着けないので"NO"。そうでなければ自由に経路を組み立てられるので"YES"。

C: 正直者の高橋くん - AtCoder Beginner Contest 021 | AtCoder

 未提出
 いや、難しくない…?グラフに弱いってのはあるけど…。
 ダイクストラ法で頂点aからの最短経路を出すまではできたけど、それまでだった。
 そのあとは最短経路でDAGを構築して、トロポジカルソートとかして経路数え上げDPだって(解説丸写し)。何言ってるのか半分しかわからないから今度また別に練習します。

D: 多重ループ - AtCoder Beginner Contest 021 | AtCoder

 40:54(AC)
 重複組み合わせに帰着できる。要は_n H _k = _{n+k-1} C _k
 コンビネーションの計算だけど、1 \leq N,K \leq 10^5の条件下だとパスカルの三角形を使ったメモ化再帰だとメモリが足りないので、階乗の逆元を取って_n C _r = \frac{n!}{r!(n-r)!}で計算する。フェルマーの小定理から、pが素数のときx^{-1} \equiv x^{p-2} \pmod pなので、ダブリングを使って計算する。ちなみに、(N!)^{-1}を求めたら((N-1)!)^{-1} = N(N!)^{-1}で求めることもできる。いちいちダブリングするよりはこっちの方が早い。

感想

 グラフの問題に弱いのはやっぱり辛いなぁ。きちんと組めるようになりたい。