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

問題はこちら 問題概要 解説 提出プログラム 感想 問題概要平面上の を頂点とする六角形を考えます。 この六角形に次の3種類の図形を敷き詰めます。 yukicoder No.2023問題文中の画像これらの図形を回転・反転を許さずに、隙間も重なりもないように敷き詰め…

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

問題はこちら 問題概要 解説 提出プログラム 感想 問題概要長さの数列と個の操作があり，操作はとを入れ替える． 以下の個のクエリを処理せよ． 操作をこの順に行ったときのを求めよ． 解説このクエリはオフラインで処理できるのでMo's algorithmが使えない…

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

問題はこちら 問題概要 解説 提出プログラム 感想 問題概要長さの数列であって，以下の条件を満たすものの数を求めよ． 数列の総和が 解説とし，とすると， となるの組の数が答えとなる．したがってDPによりで求められる． で求めることもできる．kanpurin.h…

公式解説とは別の解法です． 問題はこちら 問題概要 解説1：最大二部マッチング 解説2：2-SAT 提出プログラム 感想 問題概要と番号付けされた個の白い球がある．球または球を選んで黒く塗ることができるという操作を回行う．すべての球を黒で塗ることが可能…

問題はこちら 問題概要 解説 提出プログラム 感想 問題概要最初紙に文字書いてある．コピーとペーストを行うことにより，紙に文字以上書いてあるようにしたい．コピーには，ペーストにはのコストがかかる．最小でいくらのコストがかかるか．解説連続でコピー…

問題はこちら 問題概要 解説 提出プログラム 感想 問題概要長さの正整数列が与えられる．としてを求めよ．解説 できるだけ大きなを使いたい．であるから，貪欲で大丈夫．との比較はとを比較すればよい．もしくは，二分探索でも解ける．基本的には，https://a…

問題はこちら 問題概要 解説 提出プログラム 感想 問題概要以上以下の整数をランダムに選ぶという操作を回行うとき，選ばれた整数の種類数の期待値にをかけた値を求めよ．解説種類数をとする. 求めるものはで, は包除原理とかで求められそうだが面倒なので別…

問題はこちら 問題概要 解説 提出プログラム 感想 問題概要長さの数列があり，の末尾の要素をとして，末尾の要素を以上未満の整数に変えてになった要素は消すという操作を人のプレーヤーが交互に行う．操作ができなくなる(自分の操作開始時にが空)と負けとな…

問題はこちら 問題概要 解説 提出プログラム 感想 問題概要マスのマス目がある．以下の操作のうちつを選び，マスからマスまで移動するときの操作回数の最小値を求めよ． 操作：マスにいるときマスに移動する． 操作：ワープマスにいるときランダムにワープマ…

Mo's algorithmを用いた方法を説明します．問題はこちら 問題概要 解説 提出プログラム 感想 問題概要英小文字からなら長さの文字列について「文字目から文字目までからなる部分文字列を任意に並べ替えたものの中で辞書順最小である文字列の文字目を出力せよ…

問題はこちら 問題概要 思考の流れ 提出プログラム 感想 問題概要頂点の重み無し有向グラフの隣接行列が与えられる．任意の頂点から任意の頂点までちょうど本の辺を辿って行くことのができるか判定せよ．思考の流れ yukicoder No.1340 おーじ君をさがせとほ…

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

問題はこちら 問題概要 思考の流れ 提出プログラム 感想 問題概要頂点辺の有向グラフの頂点からちょうど本の辺を辿って行くことのできる頂点の個数を求めよ.思考の流れ yukicoder No.1112 冥界の音楽の解法で書いたように隣接行列を乗した行列の成分は「頂点…

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

問題はこちら 問題概要 解説 提出プログラム 感想 問題概要かつはの約数でも倍数でもなく, はの約数であるような相異なる3数は何通りあるか.解説 求めるものは「かつかつかつは相異なる」ようなものの数. これを言い換えて次のものを求める「は相異なるとし…

問題はこちら 問題概要 解説 提出プログラム 感想 問題概要行列のマスのうちいくつかを選ぶ. 行列のマスを選ぶと, 円失う. また, 行目のすべてのマスを選ぶと円得ることができ, 列目のすべてのマスを選ぶと円得ることができる. このとき最大何円得ることがで…

問題はこちら 問題概要 思考の流れ 提出プログラム 感想 問題概要長さの数列の最長増加部分列は何通りあるか求めよ.思考の流れ すぐ思いつくのが最後にをとったときの番目まででのLISの取り出し方の総数, としたDPサンプル1(1 4 2 5 3)だとみたいになる.この…

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

問題はこちら 問題概要 思考の流れ 提出プログラム 感想 問題概要中心が軸上にあるような円が個与えられる. 平面上の点のある点を内部(円周は内部ではないとする)に持つ円の数の最大値を求めよ.思考の流れ円の内部とかいう条件が幾何っぽくて扱いづらい. ち…

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

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

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

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

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

問題はこちら 問題概要 思考の流れ 提出プログラム 感想 問題概要 の異なる番号が書かれた個の箱に種類の色を塗る. このとき種類全ての色を使い, 各箱を何かの色で塗るとき, 塗り方の総数をで割った余りを求めよ. 思考の流れ がそこそこ大きいのでDPとかじゃ…