数え上げ
問題はこちら 目次 問題概要 解説 提出プログラム 感想 問題概要歯車が個あり，歯車は枚の歯を持つ．歯車と歯車が噛み合っている．これらの歯車の歯に色の色を塗る方法は何通りあるか．ただし，回転によって一致する色の塗り方を同一視する． 解説ポリアの数…
問題はこちら 目次 問題概要 解説 提出プログラム 感想 問題概要以上以下の整数からなる長さの整数について，，という数列にちょうど一度だけ現れる数の種類をとする． として考えられる個の数列全てにおいてを求め，その総和をで割った余りを求めよ． 解説…
問題はこちら目次 問題概要 解説 未満フラグを持つDP 未満フラグを持たない方法 メモ化再帰 場合分け オートマトンDP 問題概要以上以下の整数のうち，十進表記における各桁の数字の総和がの倍数であるようなものはいくつか． 解説桁DPというものを用いると解…
問題はこちら 問題概要 解説 提出プログラム 感想 問題概要平面上の を頂点とする六角形を考えます。 この六角形に次の3種類の図形を敷き詰めます。 yukicoder No.2023問題文中の画像これらの図形を回転・反転を許さずに、隙間も重なりもないように敷き詰め…
問題はこちら 問題概要 解説 提出プログラム 感想 問題概要個の互いに区別できるボールを個の互いに区別できる箱に入れる入れ方であって，ボールが1個も入っていない箱の個数が奇数であるようなものの数を求めよ．解説 が答えとなる(回の選択のうち，を選ぶ…
問題はこちら 問題概要 解説 提出プログラム 感想 問題概要長さの数列であって，以下の条件を満たすものの数を求めよ． 数列の総和が 解説とし，とすると， となるの組の数が答えとなる．したがってDPによりで求められる． で求めることもできる．kanpurin.h…
形式的冪級数を用いた解法です．問題はこちら 問題概要 解説 提出プログラム 感想 問題概要について以下の値を求めよ． 個の正整数から多重集合のうち，以下の2つの条件をすべて満たすものの個数 要素の総和が 任意の正整数を高々個しか含まない 解説多重集…
グリッドの最短経路(North-East lattice path)の数え上げの例を解説していきます．よくある書き込み(動的計画法)による解法は扱いません．目次 最短経路の数え上げとは 一般的な最短経路 ある点を通る最短経路 ある点を通らない最短経路 ある長方形領域を通…
問題はこちら 問題概要 解説 包除原理 さらなる高速化 提出プログラム 感想 問題概要以上以下のについて以下の問題を解け． からまで番号が付いた人を空でない個の集合に分ける．で割った余りが等しい人は同じ集合に含まれないような分け方の総数を求めよ． …
問題はこちら 問題概要 解説1 解説2 提出プログラム 感想 問題概要長さの正整数列が与えられる．以下の条件を満たすをすべて求めよ． すべてのを満たす整数について，である． 解説1となるのは，がの任意の素因数を持たないことと同じです．のすべての素因数…
問題はこちら 問題概要 解説 提出プログラム 感想 問題概要頂点の完全無向グラフから辺取り除く．このグラフの頂点から本の辺を辿るパス(一つの辺を複数回辿ってもいい)のうち終点が頂点であるようなパスの数を求めよ．解説頂点から頂点への長さのパス(厳密…
問題はこちら 問題概要 解説 提出プログラム 感想 問題概要長さの数列に対して以下の操作を行うことでの任意の要素をにするときのコストが最小となるような操作列の数を求めよ． を選びをにする．このとき，この操作を行う前の分だけコストがかかる． また，…
形式的冪級数を用いた解法です．問題はこちら 問題概要 解説 提出プログラム 感想 問題概要次元グリッド上のからマンハッタン距離がの格子点に移動することを回繰り返すしたあとにいるとして，となる確率にをかけた値を求めよ．各格子点への移動確率はである…
問題はこちら 問題概要 解説 提出プログラム 感想 問題概要整数が与えられるので，以下の条件を満たす整数組の数を求めよ． をの最大公約数とすると，以下が成立する． かつかつ 解説またはのときは条件を満たさないので，以下とする．各に対して，条件を満…
問題はこちら 問題概要 解説 提出プログラム 感想 問題概要白いボール個と黒いボール個を一列に並べるとき，各について左から個のボールのうち白いものの個数を，黒いものの個数をとおいたとき，すべてのについてが成り立つような並べ方の数を求めよ．解説結…
問題はこちら 問題概要 解説 提出プログラム 感想 問題概要のチェス盤があり，に白のポーンがある．他にも個の黒のポーンが置かれている．白のポーンはの方向に進むとき，白のポーンがに到達できるようなの数はいくつか．解説を「に到達できるか」とするよう…
問題はこちら 問題概要 解説 提出プログラム 感想 問題概要頂点の根付き木について以下の個のクエリに答えよ．整数が与えられる．次の条件を満たす頂点の個数を求めよ． から根への最短パス上に頂点が存在する． から根への最短パスに含まれる辺の数がちょう…
公式解説と同じになってしまいましたが，せっかく書いたので公開します．問題はこちら 問題概要 解説 提出プログラム 感想 問題概要頂点の木の任意の頂点についての総和を求めよ．ただし，とはからへの最短パスに含まれる辺全ての重みのXORと定める．解説も…
形式的冪級数を用いた解法です．問題はこちら 問題概要 解説 提出プログラム 感想 問題概要次元グリッド上でからまでの最短経路の個数をとする．を求めよ．解説である．これは高校数学なので，分からない場合は復習が必要．次元累積和の典型みたいに考えると…
別解です．ほぼ一緒なので丁寧には書きません．問題はこちら 問題概要 解説 提出プログラム 感想 問題概要を並び替えてできる数列で，以下の条件を満たすものの数を求めよ． を満たす全ての数列について，の中に以下の数は個以下しか存在しない． 解説公式解…
問題はこちら 問題概要 問題概要2 解説 別解 提出プログラム 感想 問題概要頂点辺の単純無向グラフの各頂点を赤，緑，青で塗り分ける方法で隣接する頂点が異なる色で塗られているようなものは何通りあるか．問題概要2グラフ理論っぽく書かれていますが，同じ…
問題はこちら 問題概要 解説 提出プログラム 感想 問題概要 を満たす整数の組全てについて の総和を求めよ．解説 形式的冪級数で解きます．とすると よってとしてが答え．を偶奇で分けると したがってBostan–Moriのアルゴリズムを用いたり，線形漸化式に直し…
そもそも回転の列挙が難しい．以下，厳密性を欠くので注意．問題はこちら 問題概要 解説 提出プログラム 感想 問題概要正六面体のつの面に正整数を書き込んだとき，正整数の和がとなるような物の数を求めよ．ただし，正六面体を回転して一致する書き込み方は…
問題はこちら 問題概要 思考の流れ 提出プログラム 感想 問題概要ラベル付き頂点のパスグラフから頂点を削除していく. 頂点をつ削除するたび連結成分の個数の点数を得る. 通りの削除の仕方すべての点数の総和を求めよ.思考の流れ 連結成分の数というのは数え…
問題はこちら 問題概要 思考の流れ 提出プログラム 感想 問題概要頂点辺の有向グラフの頂点からちょうど本の辺を辿って行くことのできる頂点の個数を求めよ.思考の流れ yukicoder No.1112 冥界の音楽の解法で書いたように隣接行列を乗した行列の成分は「頂点…
問題はこちら 問題概要 思考の流れ 提出プログラム 感想 問題概要長さの整数列が与えられる. の部分列におけるスコアをと定義する. としてあり得るすべての数列のスコアの総和を求めよ.思考の流れ を全て列挙するのは無理なのでの寄与分を考えると, からまで…
最終状態としてあり得るものの数え上げを行う問題をまとめる. 解法とかはあとでやる.目次 ARC108 D - AB ABC171 F - Strivore ABC156 E - Roaming ABC158 F - Removing Robots ARC110 E - Shorten ABC ARC107 C - Shuffle Permutation ARC108 D - AB ABC171 …
問題はこちら 問題概要 解説 提出プログラム 感想 問題概要かつはの約数でも倍数でもなく, はの約数であるような相異なる3数は何通りあるか.解説 求めるものは「かつかつかつは相異なる」ようなものの数. これを言い換えて次のものを求める「は相異なるとし…
問題はこちら 問題概要 思考の流れ 提出プログラム 感想 問題概要長さの数列の最長増加部分列は何通りあるか求めよ.思考の流れ すぐ思いつくのが最後にをとったときの番目まででのLISの取り出し方の総数, としたDPサンプル1(1 4 2 5 3)だとみたいになる.この…
競技プログラミングにおける数え上げ問題とその解法をまとめます.
