hogecoder

tsutaj 競技プログラミングの記録

蟻本練習問題解説 Part3 (2-3)

蟻本練習問題の解説をします。今回のトピックは動的計画法です!

今回は難易度が割と混在しているため、水色 〜 青 の方でも解きごたえがある (ありそう、完全に主観) な問題に★をつけました競技プログラミングにある程度慣れている方も、★がついている問題を解くことをオススメします。

シリーズ目次はこちらからどうぞ。

tsutaj.hatenablog.com

値を覚えて再利用 "動的計画法"

基礎的な動的計画法

POJ 3176: Cow Bowling

問題リンク

数字が三角形状に並んでいる (詳細はリンク先を見てください)。一番上の数字から、その一段下であって隣接している  2 つの数字のどちらかに降りて行き、一番下に到達したときに終了することを考える。この時に通過した数字の和をスコアとするとき、スコアの最大値を求めよ。

▶表示する

POJ 2229: Sumsets

問題リンク

数字  N が与えられるので、要素が  2 の冪乗のみであり、要素の総和が  N となるような数列の総数を求めよ。ただし、並べ替えて同じになるものは同一視するものとする。

▶表示する

POJ 2385: Apple Catching

問題リンク

リンゴの木が  2 本あり、時刻  1 から  1 秒ごとにどちらかの木からリンゴが落ちてくる。落ちてくるリンゴは、その瞬間に木の下にいるときのみ拾うことができるが、木と木の間は最大で  W 回までしか移動できない (移動にかかる時間は微小であるとして良い)。あなたは時刻  0 のとき、  1 番目のリンゴの木の下にいる。このとき、最大でいくつのリンゴを拾うことができるか?

▶表示する

★ POJ 3616: Milking Time

問題リンク

 M 個の区間がある。 i 番目の区間  (l_{i}, r_{i}) 0 \leq l_{i} \lt r_{i} \leq 10^{6} を満たし、その重みは  c_{i} である。

この区間の中から、区間の間の距離 (右端と左端の距離) が  R 以上を満たすように選ぶとき、選んだ区間の重み総和の最大値を求めよ。

▶表示する

★ POJ 3280: Cheapest Palindrome

問題リンク

文字列  S が与えられる。この文字列に対して、任意の場所に文字を追加、または任意の場所の文字を削除して回文を作りたい。アルファベット  c_{i} を追加するにはコスト  w_{i} が、削除するにはコスト  d_{i} がかかる。回文にするためのコストの最小値を求めよ。

▶表示する

漸化式を工夫して高速化

★ POJ 1742: Coins

問題リンク

 N 枚の硬貨があり、 i 番目の硬貨は  A_{i} 枚硬貨であり、 C_{i} 枚持っている。

いま持っている硬貨だけを使って、 i \ \ (1 \leq i \leq M) 円払うことを考える。ちょうど払える金額は何種類あるか?

▶表示する

★ POJ 3046: Ant Counting

問題リンク

数字が  A 個ある。値が  i である数は  n_i 個あり、同じ数字どうしは区別できない。

この中から  m \ \ (S \leq m \leq B) 個の数字を選ぶことを考える。すべての  m についてこの場合の数を求め、その総和を出力せよ。

▶表示する

POJ 3181: Dollar Days

問題リンク

 1 K ドルの商品がそれぞれ無限個あり、同じ商品どうしは区別できない。 N ドルぴったりを使ってこれらの商品を買うとき、商品の買い方は何通りあるか?

▶表示する

少し考察を要する問題

★ POJ 1065: Wooden Sticks

問題リンク

 N 個のアイテムがあり、各アイテムには  l_{i}, w_{i} という  2 つのパラメーターが付いている。これらのアイテムを、次の条件を満たすようないくつかの数列に分けることを考える。

 i \lt j を満たす、数列のインデックスの組  (i, j) について、 l_{i} \leq l_{j} かつ  w_{i} \leq w_{j} が、すべての組に対して成立する (すなわち、数列はどちらのパラメータに対しても単調増加列である)。

このとき、数列の個数を最小化せよ。

▶表示する

POJ 1631: Bridging signals

問題リンク

定義域、値域ともに  \left[ 1, N \right] である全単射の関数  f(x) がある。 x_{1} \lt x_{2} \lt \dots \lt x_{m} かつ  f(x_{1}) \lt f(x_{2}) \lt \dots \lt f(x_{m}) を満たすような数列の長さの最大値を求めよ。

▶表示する

★ POJ 3666: Making the Grade

問題リンク

長さ  N の数列  A が与えられる。この数列を、単調増加または単調減少列  B に変えることを考える。このときのコストは、 | A_{1} - B_{1} | + \dots | A_{N} - B_{N} | と表される。コストの最小値を求めよ。

▶表示する

POJ 2392: Space Elevator

問題リンク

 N 個のブロックがある。 i 番目のブロックは  c_{i} 個あり、ブロック自体の高さが  h_{i} であり、高さ  a_{i} を超える場所に置くことはできない (そのブロックの一部が  a_{i} を超えるのもダメ)

これらのブロックをできるだけ高く積み上げたとき、その高さの最大値を求めよ。

▶表示する

★ POJ 2184: Cow Exhibition

問題リンク

 N 個のアイテムがある。それぞれのアイテムは  2 つのパラメータ  a_{i}, b_{i} を持っている。

このうちいくつかを選び、パラメータの合計  \sum_{i} a_{i} + \sum_{i} b_{i} を最大化したい。しかしこのとき、 \sum_{i} a_{i} \geq 0 かつ  \sum_{i} b_{i} \geq 0 でなければならない。これを満たす選び方であるときのパラメータの合計の最大値を求めよ。

▶表示する

次回はデータ構造の問題を解説します!