DP高速化
問題はこちら 目次 問題概要 解説 提出プログラム 解説 問題概要正整数列に対して次の操作を回以上行う. から連続部分列を選び,削除する. に対し,の要素の総和をちょうどにするために必要な操作回数の最小値を求めよ. 解説操作も制約も明らかにDPの気配…
問題はこちら 問題概要 解説 提出プログラム 感想 問題概要頂点の完全無向グラフから辺取り除く.このグラフの頂点から本の辺を辿るパス(一つの辺を複数回辿ってもいい)のうち終点が頂点であるようなパスの数を求めよ.解説頂点から頂点への長さのパス(厳密…
問題はこちら 問題概要 解説 提出プログラム 感想 問題概要長さの数列に対して以下の操作を行うことでの任意の要素をにするときのコストが最小となるような操作列の数を求めよ. を選びをにする.このとき,この操作を行う前の分だけコストがかかる. また,…
問題はこちら 問題概要 解説 提出プログラム 感想 問題概要のチェス盤があり,に白のポーンがある.他にも個の黒のポーンが置かれている.白のポーンはの方向に進むとき,白のポーンがに到達できるようなの数はいくつか.解説を「に到達できるか」とするよう…
問題はこちら 問題概要 解説 提出プログラム 感想 問題概要がいて,左から番目は人である.以下の種類の操作を繰り返し,人を昇順に並び替えるときのコストの最小値を求めよ. コストを払い,人を好きな位置に移動させる. コストを払い,人を左端に移動させ…
Mo's algorithmを用いた方法を説明します.問題はこちら 問題概要 解説 提出プログラム 感想 問題概要長さの数列に関して「番目から番目までに含まれる数の種類を求めよ」という個のクエリに答えよ.解説 Range Set Queryという名前とか数列の区間に対するク…
問題はこちら 問題概要 思考の流れ 提出プログラム 感想 問題概要頂点の重み無し有向グラフの隣接行列が与えられる.任意の頂点から任意の頂点までちょうど本の辺を辿って行くことのができるか判定せよ.思考の流れ yukicoder No.1340 おーじ君をさがせとほ…
問題はこちら 問題概要 思考の流れ 提出プログラム 感想 問題概要頂点辺の有向グラフの頂点からちょうど本の辺を辿って行くことのできる頂点の個数を求めよ.思考の流れ yukicoder No.1112 冥界の音楽の解法で書いたように隣接行列を乗した行列の成分は「頂点…
問題はこちら 問題概要 思考の流れ 提出プログラム 感想 問題概要長さの数列の最長増加部分列は何通りあるか求めよ.思考の流れ すぐ思いつくのが最後にをとったときの番目まででのLISの取り出し方の総数, としたDPサンプル1(1 4 2 5 3)だとみたいになる.この…
問題はこちら 問題概要 思考の流れ 提出プログラム 感想 問題概要与えられた長さの数列を長さ以下の個の連続部分数列に分解する. 数列のスコアをその数列の要素の和の絶対値とするとき, スコアの和の最大値を求めよ.思考の流れ問題とか制約とかから明らかにD…
問題はこちら 問題概要 思考の流れ 提出プログラム 感想 問題概要 店舗から日間店舗選んで商品を(日店舗のみから必ず)買う). 商品の値段はの倍数で与えられ, 毎日各店舗で値段が変わる. 日連続で同じ店で買うと割引, 日連続同じ店で買うと割引になる. このと…
問題はこちら 問題概要 思考の流れ 提出プログラム 感想 問題概要 の段数がある階段がある. その階段の番目の段差の高さはであり, である. 段差の和が以下の段を一度に上ることができるとき, 階段の上り方の数を1234567で割った余りを求めよ. 思考の流れ ぱ…
問題はこちら 問題概要 思考の流れ 提出プログラム 感想 問題概要 価格の個の饅頭, 入る饅頭の個数で価格の個の箱が与えられるので箱をいくつか買って饅頭を詰めて売るときの利益の最大値を求めよ. 思考の流れ 詰める饅頭は高いものから. 饅頭を個詰められる…