問題はこちら 目次 問題概要 解説 提出プログラム 感想 問題概要以上以下の整数からなる長さの数列の長さ部分列であってが回ずつ登場するもののうち，辞書順最小のものを答えよ． 解説辞書順最小と言えば，前から貪欲に置けるもののうち最も小さいものを順に…

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

問題はこちら 目次 問題概要 解説 提出プログラム 感想 問題概要種類のカードがあり，最初，種類目のカードの得点は，枚数は枚である．以下の形式の個のクエリを順に処理せよ． 種類目のカードの得点をに変更 種類目のカードの枚数をに変更 枚のカードを選ぶ…

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

問題はこちら 目次 問題概要 解説 提出プログラム 感想 問題概要以上以下の整数からなる長さの整数について，，という数列にちょうど一度だけ現れる数の種類をとする． として考えられる個の数列全てにおいてを求め，その総和をで割った余りを求めよ． 解説…

問題はこちら 目次 問題概要 解説 提出プログラム 感想 問題概要長さの文字列が与えられる．長さの文字列であって，となるようなものを求めよ． 解説で文字列の文字目から文字目までの文字列とします． で文字列を反転させた文字列とします．すべてので以下…

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

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

燃やす埋める問題の解説記事です

燃やす埋める(Project Selection Problem)の練習問題についての解説です。問題はこちら ポイント 問題概要 解説 提出プログラム 感想 ポイント 負のコスト 複数の選択肢 機械的なグラフの構築 問題概要人の人が数直線上に家を建てようとしています。番目の人…

燃やす埋める(Project Selection Problem)の練習問題についての解説です。問題はこちら ポイント 問題概要 解説 提出プログラム 感想 ポイント 最大化を最小化へ言い換える グラフ表現可能なコストの性質 2部グラフの性質を用いたの選択肢の順序変更 問題概…

燃やす埋める(Project Selection Problem)の練習問題についての解説です。問題はこちら ポイント 問題概要 解説 提出プログラム 感想 ポイント 選択に対するコストからグラフを構築する 問題概要からなる文字列が与えられます。円支払うことにより、を(なら…

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

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

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

問題はこちら 問題概要 解説 提出プログラム 感想 問題概要個の半開区間の和集合を求めよ． 解説以下のように半開区間の集合に新たに半開区間を追加することを考えます．このような追加を高速に行うことができれば解くことができそうです． 既に集合に含まれ…

形式的冪級数を用いた解法です．問題はこちら 問題概要 解説 提出プログラム 感想 問題概要三次元グリッドのマスから隣り合う6つのマスのうち，いずれかのマスへの移動をちょうど回行った後にマスにいるような移動経路数を求めよ． 解説移動の仕方は対称なの…

問題はこちら 問題概要 解説 提出プログラム 感想 問題概要の順列および正整数が与えられる．について以下の値を求めよ． の先頭項のうち，番目に大きい値 解説公式解説にもある通り優先度付きキューで解けますが，BinaryTrieでも解くことができます．Binary…

問題はこちら 問題概要 解説 提出プログラム 感想 問題概要長さの数列について以下の個のクエリに答えよ． が与えられる．となるの数を答えよ． 解説これはBinaryTrieで解くことができます．BinaryTrieは整数の(多重)集合を管理することができるデータ構造で…

問題はこちら 問題概要 解説 例 提出プログラム 感想 問題概要頂点のグラフがあり，頂点から頂点に重みの有向辺が張られている．頂点から頂点までの最短距離を求めよ．解説であるからは なら なら となります．頂点をでソートすると，各についてとなるやとな…

問題はこちら 問題概要 解説 提出プログラム 感想 問題概要長さの数列と長さの数列がある．を求めよ．解説愚直に実装するとになります．各毎にが最小になるようなを求めます．もちろんこのままだと毎にかかるのでダメですがをソートすることで以下の性質をも…

有名問題問題はこちら 問題概要 解説1 解説2 提出プログラム 感想 問題概要を求めよ．解説1答えはの領域内の格子点の数となります．(上の格子点の数はになるため) N=10の例この領域はに関して対称であるための領域内の格子点を数えて2倍します．とします．領…

形式的冪級数を用いた解法です．問題はこちら 問題概要 解説 提出プログラム 感想 問題概要ある路線には駅から駅までの個の駅がある．準急は駅に止まり，{駅駅 }の部分集合に止まり，駅に止まる．連続する個以上の駅に止まると，客が飽きてしまうので，その…

メモがてら書きます．問題はこちら 問題概要 解説 提出プログラム 感想 問題概要長さの数列を作る．各には個の選択肢があり，を選ぶとのコストがかかる．さらに，各についてのコストが追加でかかる．コストの総和の最小値を求めよ．解説複数の選択間にコスト…

問題はこちら 問題概要 解説 提出プログラム 感想 問題概要少し変えてます． で定義される数列の第項を求めよ．解説の母関数をとする．は形式的冪級数を用いてと表される． なので， のときは のときはしたがってBostan–Moriのアルゴリズムを用いるとで解け…

問題はこちら 問題概要 解説 アルゴリズム 提出プログラム 感想 問題概要を並び替えて得られる数列であって以下の条件を満たすもののうち，辞書順最初のものを求めよ． に対し，においてはよりも先に現れる． 解説ポイント 辞書順最小は前から貪欲 要素の追…

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

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

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

問題はこちら 問題概要 解説 提出プログラム 感想 問題概要長さの数列が与えられる．この数列の要素を一つ選びを加えるという操作を回まで行うことができるとき，の全要素のgcdの最大値を求めよ．解説となるための最小操作回数が以下であるかが分かればいい(…