izumo’s diary

主に競プロの精進記録

二項係数 (nCr) の計算方法

アルゴリズム 競プロ

AtCoder Grand Contest 025 にて _n \mathrm{C} _r\ \bmod\ p を使う問題が出題されました。いい機会だと思ったので i!,\ \left(i!\right)^{-1},\ _n \mathrm{C} _r\ \bmod\ p の高速な実装をしてみました。

使用言語: C++

1. なぜ逆元 \left(i!\right)^{-1} が必要なのか

_n \mathrm{C} _r=\frac{n!}{r!\times(n-r)!}
なので、n!,\ r!,\ (n-r)! が分かればO(1) で _n \mathrm{C} _r が求まります。よって事前に階乗を計算しておけばよいことが分かります。

続きを読む

AtCoder Beginner Contest 098

競プロ

だいぶ間が空きましたが今回はABC098の参加記です。結果はA, B, Cの3完で緑パフォでした。ちなみに前回のAGCはno-submissionで逃げました。（は？）
使用言語: C++

A - Add Sub Mul

問題

A-B, A\times{B}の大きい方とA+Bを比較すれば3つの中で最大のものが分かる。

続きを読む

AtCoder Beginner Contest 095

競プロ

今回はABC095の参加記です。結果はA, B, Cの3完で緑パフォでした。
使用言語: C++

A - Something on It

問題

Sにoがいくつあるか数えるだけ。for文を使う方法しか思いつかなかった。

続きを読む

AtCoder Beginner Contest 093

競プロ

ブログを始めてみました！競技プログラミング(主にAtCoder)の参加記などを書く予定です。現状、AtCoderのパフォーマンスは茶色か緑です。半年後とかに読んで成長が感じられたら良いなと思います。

今回はABC093の参加記です。結果はA, B, Cの3完でした。

続きを読む