DP状態空間を絞る
ずっと、「2 個分開いているかっこについて、1 個閉じてから、また 1 個開く」というパターンを見落として、WA 12 個がとれなかった!! 問題へのリンク 問題概要 1 - 20 - 13 + 14 - 5 のような、 個の正の整数を「+」「-」で連結した計算式が与えられる。…
個の区間を、プチ区間たちを用いて、最小コストですべて被覆しようという問題。DP 状態の持ち方を工夫することで計算量を小さくしたい。 問題へのリンク 問題概要 個の区間があって、長さが である。これらすべてを 2 種類の区間で被覆したい。 長さが であ…
木 DP のいい感じの練習問題だった! 問題へのリンク 問題概要 頂点数 の重み付き木が与えられる (重みは負のこともある)。 この木の辺の部分集合であって、各頂点 に接続する辺の本数が 本以下であるようなものに対して、辺の重みの総和の最大値を求めよ。 …
状態空間を上手に削減する系の問題 問題へのリンク editorial 問題概要 種類の長方形形状 () をしたスタンプがある (それぞれ「赤」「緑」「青」の 3 種類がある)。 これらを使って 4 × 4 のグリッド上に所望の模様を作りたい。グリッドからはみ出して押して…
比較的素直な考察で解ける問題 問題へのリンク 問題概要 umgくんは 1 次元上の座標 0 にいます。今は時刻 0 です。時刻が 1 進むごとに、今いる座標より 1 大きい座標に移動するか、 1 小さい座標に移動するか、その座標にとどまるかという行動ができます。 …