問題はこちら 目次 問題概要 解説 提出プログラム 感想 問題概要歯車が個あり，歯車は枚の歯を持つ．歯車と歯車が噛み合っている．これらの歯車の歯に色の色を塗る方法は何通りあるか．ただし，回転によって一致する色の塗り方を同一視する． 解説ポリアの数…

ほとんど公式解説と同じなので簡単に書きます。問題はこちら 問題概要 解説 提出プログラム 感想 問題概要2点がそれぞれ上下左右に移動することを回繰り返す．移動は左右にはの確率で，上下にはの確率で移動するとき、2点が回目の移動直後に初めて重なる確率…

問題はこちら 問題概要 解説 提出プログラム 感想 問題概要個の互いに区別できるボールを個の互いに区別できる箱に入れる入れ方であって，ボールが1個も入っていない箱の個数が奇数であるようなものの数を求めよ．解説 が答えとなる(回の選択のうち，を選ぶ…

形式的冪級数を用いた珍しい(と思った)解き方がある問題集 (解けなかったやつも載せる)厳密には形式的冪級数ではないもの(有理数の指数が出るもの)も載せてる．ABC221 H 解説とする． なのでDP遷移がわかって解ける．ABC222 H 解説であるので はの逆関数とな…

形式的冪級数を用いた解法です．問題はこちら 問題概要 解説 提出プログラム 感想 問題概要について以下の値を求めよ． 個の正整数から多重集合のうち，以下の2つの条件をすべて満たすものの個数 要素の総和が 任意の正整数を高々個しか含まない 解説多重集…

グリッドの最短経路(North-East lattice path)の数え上げの例を解説していきます．よくある書き込み(動的計画法)による解法は扱いません．目次 最短経路の数え上げとは 一般的な最短経路 ある点を通る最短経路 ある点を通らない最短経路 ある長方形領域を通…

問題はこちら 問題概要 解説 包除原理 さらなる高速化 提出プログラム 感想 問題概要以上以下のについて以下の問題を解け． からまで番号が付いた人を空でない個の集合に分ける．で割った余りが等しい人は同じ集合に含まれないような分け方の総数を求めよ． …

問題はこちら 問題概要 解説 提出プログラム 感想 問題概要頂点の完全無向グラフから辺取り除く．このグラフの頂点から本の辺を辿るパス(一つの辺を複数回辿ってもいい)のうち終点が頂点であるようなパスの数を求めよ．解説頂点から頂点への長さのパス(厳密…

問題はこちら 問題概要 解説 提出プログラム 感想 問題概要行列のグリッド上の異なるマスを選ぶ，の最小値を求めよ．解説式の中に絶対値があって面倒なのでと決めることで絶対値を外す．グリッド全体を反転させれば他の場合も表せるので，の場合で求められれ…

形式的冪級数を用いた解法です．問題はこちら 問題概要 解説 提出プログラム 感想 問題概要次元グリッド上でからまでの最短経路の個数をとする．を求めよ．解説である．これは高校数学なので，分からない場合は復習が必要．次元累積和の典型みたいに考えると…

問題はこちら 問題概要 思考の流れ 提出プログラム 感想 問題概要整数に対し，正の約数の個数をとする．を求めよ．思考の流れ 正の約数の個数は，素因数分解や約数を列挙することによってで求まる．からに対してこれを行うとかかる． 実際に約数の分布をみて…

問題はこちら 問題概要 思考の流れ 提出プログラム 感想 問題概要ラベル付き頂点のパスグラフから頂点を削除していく. 頂点をつ削除するたび連結成分の個数の点数を得る. 通りの削除の仕方すべての点数の総和を求めよ.思考の流れ 連結成分の数というのは数え…

問題はこちら 問題概要 思考の流れ 提出プログラム 感想 問題概要長さの整数列が与えられる. の部分列におけるスコアをと定義する. としてあり得るすべての数列のスコアの総和を求めよ.思考の流れ を全て列挙するのは無理なのでの寄与分を考えると, からまで…

問題はこちら 問題概要 思考の流れ 提出プログラム 感想 問題概要長さの数列とが与えられる. となるを選んでをに変更する. この操作を何回か行ってにできるとき, 最小操作回数を求めよ.思考の流れ隣り合ったものに対して操作を行う場合, 隣り合ったものの差…

問題はこちらあんまり見てなかったけど本当はここらしい 問題概要 思考の流れ 提出プログラム 感想 問題概要4点があり, 最初にいる. 今いる点から別の点に移動することを回繰り返す. 回の移動の後ににいる移動方法が何通りあるか求めよ.思考の流れ回の移動後…

悩まなかったけど公式解説が出てなかったので書きました.問題はこちら 問題概要 思考の流れ 提出プログラム 感想 問題概要パスカルの三角形で(一番上を0段目として)1段目の数を,とし, 各段の一番左の数を,一番右の数をとする. このときの段目,左から番目の数…

問題はこちら 問題概要 思考の流れ 提出プログラム 感想 問題概要与えられた長さの数列を長さ以下の個の連続部分数列に分解する. 数列のスコアをその数列の要素の和の絶対値とするとき, スコアの和の最大値を求めよ.思考の流れ問題とか制約とかから明らかにD…

問題はこちら 問題概要 思考の流れ 提出プログラム 感想 問題概要かつとなるが存在するようなで始まりで終わるような長さの数列の数をで割った余りを求めよ.思考の流れに辺を張ったグラフの隣接行列を作る. 蟻本とかにも書いてあるように, この行列を乗した…

問題はこちら 問題概要 思考の流れ 提出プログラム 感想 問題概要が与えられる. 以下の連立漸化式で表される数列の第項を求めよ.思考の流れ蟻本とか見てるとわかるように線形の連立漸化式は行列累乗で高速に解くことができる. に注意 提出プログラムhttps://…

問題はこちら 問題概要 思考の流れ 提出プログラム 感想 問題概要 0,1からなる長さの2つの数列に対し, 関数を以下のように定める. に対し以下の操作を繰り返してと等しくすることを考える. このとき行う操作のコストの和として考えられる最小の値がである. …

問題はこちら 問題概要 思考の流れ 提出プログラム 感想 問題概要 長さのJ,O,Iからなる文字列が与えられる. の連続する部分文字列であり, 以下の条件を満たすものの中で最長の文字列を求めよ. 文字列に含まれるJ,O,Iの数が等しい. 思考の流れ 区間に含まれる…