Matsushita's Blog

組み合わせ

重複組合せを用いた多重ループ

問題 D: 多重ループ - AtCoder Beginner Contest 021 | AtCoder 解法 問題文の以下に注目 このプログラムの出力する答えは 1≦a1≦a2≦…≦ak≦n であるような整数の組 (a1,a2,…,ak) の個数に等しい 公式の解説に則ってこの文章を以下のように変換して考える。 「…

フェルマーの小定理による組み合わせ計算によって経路数を数え上げる

問題 D: いろはちゃんとマス目 / Iroha and a Grid - AtCoder Beginner Contest 042 | AtCoder 解法 まず、この問題のポイントを抑える 問題のポイント 右と下にのみ移動可能なマス目の経路数の数え上げ 縦マスH, 横マスWはそれぞれ、1≦H,W≦100,000 (105) AB…

フェルマーの小定理を用いてコンビネーションを計算する

背景 nCk nCkを計算したい。(n個の中からkこ取り出す組み合わせ) nCkはnCk = n! / k! * (n - k)!となる。これを計算すれば求まる。しかし、分母のk! * (n - k)!の部分に着目した時に、nの値が大きいと値が大きすぎて計算できない。 そこで、プロコンの世界で…

大ジャンプ AtCoder ABC 011D

問題 D: 大ジャンプ - AtCoder Beginner Contest 011 | AtCoder 解き方(満点解法) 以下のステップで解くことができる。 左右に移動する回数と上下に移動する回数の2パターンについて考える 左右に移動する回数をhorizon回と固定する すると上下に移動する回…

パスカルの三角形を用いてコンビネーション(組み合わせ)のクラスを実装する

コンビネーション(組み合わせ)とは nCk = n! / k! * (n - k)! n個の中からk個取り出す場合の数を算出するものである。 パスカルの三角形とは 2項展開における係数を三角形状に並べたものである。 パスカルの三角形 - Wikipedia それぞれの値はnCkの計算結果…