問題はこちら 目次 問題概要 解説 提出プログラム 感想 問題概要曜日からなる一週間の各曜日に「平日」か「休日」のどちらかを割り当てる．このとき，曜日の生産量は以下のように表される． 曜日が「休日」である場合は 曜日が「平日」のとき，直前の休日が…

問題はこちら目次 問題概要 解説 未満フラグを持つDP 未満フラグを持たない方法 メモ化再帰 場合分け オートマトンDP 問題概要以上以下の整数のうち，十進表記における各桁の数字の総和がの倍数であるようなものはいくつか． 解説桁DPというものを用いると解…

問題はこちら 目次 問題概要 解説 提出プログラム 解説 問題概要正整数列に対して次の操作を回以上行う． から連続部分列を選び，削除する． に対し，の要素の総和をちょうどにするために必要な操作回数の最小値を求めよ． 解説操作も制約も明らかにDPの気配…

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

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

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

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

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

問題はこちら 問題概要 解説 提出プログラム 感想 問題概要長さの数列に対して以下の操作を行うことでの任意の要素をにするときのコストが最小となるような操作列の数を求めよ． を選びをにする．このとき，この操作を行う前の分だけコストがかかる． また，…

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

問題はこちら 問題概要 解説 おまけ おまけ2 提出プログラム 感想 問題概要個の料理があり，それぞれ作るためにオーブンを使う時間はである．つのオーブンを用いてすべての料理を作るのにかかる時間は最短何分か．解説つのオーブンのみを用いることを考える…

問題はこちら 問題概要 解説 提出プログラム 感想 問題概要のチェス盤があり，に白のポーンがある．他にも個の黒のポーンが置かれている．白のポーンはの方向に進むとき，白のポーンがに到達できるようなの数はいくつか．解説を「に到達できるか」とするよう…

問題はこちら 問題概要 解説 提出プログラム 感想 問題概要がいて，左から番目は人である．以下の種類の操作を繰り返し，人を昇順に並び替えるときのコストの最小値を求めよ． コストを払い，人を好きな位置に移動させる． コストを払い，人を左端に移動させ…

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

問題はこちら 問題概要 解説 提出プログラム 感想 問題概要個の正整数からなる数列が与えられる．とを満たす異なる数列であってを満たすものが存在するか判定し，存在するならばつ出力せよ．解説の要素を「に振り分ける」，「に振り分ける」，「どちらにも振…

別解です．ほぼ一緒なので丁寧には書きません．問題はこちら 問題概要 解説 提出プログラム 感想 問題概要を並び替えてできる数列で，以下の条件を満たすものの数を求めよ． を満たす全ての数列について，の中に以下の数は個以下しか存在しない． 解説公式解…

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

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

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

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

問題はこちら 問題概要 思考の流れ 提出プログラム 感想 問題概要 長さの文字列と長さの文字列が与えられる. 空文字列を用意して, の先頭か末尾にを挿入していくことを考える. の接頭辞がに等しくなるような挿入の仕方の総数を998244353で割った余りを求めよ…

問題はこちら 問題概要 思考の流れ 提出プログラム 感想 問題概要 頂点の木と, 各頂点にの値が与えられる. 全ての頂点に対して, 頂点1から頂点までのパスを頂点1から見た数列ととらえて狭義最長増加部分列の長さを求めよ. 思考の流れ ある数列Sが与えられた…

問題はこちら 問題概要 思考の流れ 提出プログラム 感想 問題概要 頂点辺の閉路のない有向グラフ(=DAG)が与えられる. 頂点から辺をたどって頂点Nに行くことを考える. 各頂点から出ている辺から等確率でランダムに選び進む. このグラフから一つだけ辺を取り除…

問題はこちら 問題概要 思考の流れ 提出プログラム 感想 問題概要 2次元上の点が与えらえれる. すべての点集合について, その集合のすべての点を含む最小の長方形の内部にある点の総数を998244353で割った値を求めよ. 思考の流れ 全列挙できない場合は寄与分…

問題はこちら 問題概要 思考の流れ(自分の解法) 思考の流れ(公式解説動画の解法) 思考の流れ(公式解説pdfの解法) 提出プログラム 感想 問題概要 東西に無限に続く1本の大通りがあり, 数直線とみなすことができる. 回道路工事が行われる. 番目の道路工事は時…

問題はこちら 問題概要 思考の流れ 提出プログラム 感想 問題概要 頂点の木が与えられる. 木の各辺には色が塗られていて長さはである. このとき, 以下の個の問いに答えよ. 色が塗られている辺の長さがに変更されたと仮定したときの二頂点間の距離を求めよ. (…

問題はこちら 問題概要 思考の流れ 提出プログラム 感想 問題概要 の正方形のチョコからなる長方形の板チョコがあり, その板チョコを縦横に割っていく. 割るときにかかるコストは割る長さの2乗であり, ちょうどこの正方形のチョコに分割したい. そのように分…

問題はこちら 問題概要 思考の流れ 提出プログラム 感想 問題概要 頂点の木が与えられ, 頂点には色が塗られている. に対して, 以下の問題を解け. 色が塗られている頂点を一度以上通るような単純パスの数を求めよ. 思考の流れ 一度以上通るっていうのは難しい…

問題はこちら 問題概要 思考の流れ 証明 提出プログラム 感想 問題概要 人の幼児が左右一列に並んでおり, 左から番目の幼児の活発度はである. 幼児の順番を好きに並び替える. はじめ左から番目に並んでいた幼児が左から番目に移動するとき,うれしさがだけ生…

問題はこちら 問題概要 思考の流れ 提出プログラム 感想 問題概要 買い取り価格円の本が冊与えられる. 本にはそれぞれジャンルのジャンルが決まっていて同ジャンルの本を冊売ると, そのジャンルの本の買い取り価格が冊につき円上がる. 冊の本から冊選んで売…