atcoder.jp 解法 エラトステネスの篩で素数かどうか判定する代わりに、素因数の種類を数えればOK。 N ≦ 107 でも間に合うんですね。 実装 K=1のときは場合分けした方が実装が楽だと思った。 void solve(long long N, long long K) { if (K == 1) { c(N-1) re…

atcoder.jp 強連結成分分解を初めて学んだので、メモしておくために記事にします。 アルゴリズムの正当性とかはまだちゃんと分かっていない気がするので、役に立ったリソースだけまとめておきます。 高校数学の美しい物語ってグラフ理論の解説とかもしている…

atcoder.jp 解法 二次元グリッドの問題はHとWの制約が同じことが多いが、この問題はHだけが何故かとても小さい。 あからさまに怪しいのでHの小ささを利用したくなる。 そこで、bit全探索を使って横方向の切り方を全探索することにする。 縦方向の切れ目の入…

atcoder.jp 解法 絶対値を外すことができれば、(i, j)と(i', j') を分離できるので計算しやすくなる。 そこで、i ≧ i'かつ j ≧ j' という条件をつけることにする。 これで絶対値の中が必ず0以上になるため、絶対値を外して計算できるようになる。 i < i' か…

atcoder.jp 解法 都市から都市への移動を繰り返すという行為が、DPで遷移するというのに酷似しているため、DPをしたくなる。 次のようなDPを考える。 dp[i][j] ← i日目に都市jにいる旅の仕方は何通りか ただ問題文通りにK回、N個の町から通れる道を使って遷…