面白い。各値に対する答えを予め整理して求めておく手法は頻出！ 問題へのリンク 問題概要 個の品物がある。品物 は、重さが であり、価値が である。 いくつかの品物を、総和が 以下となるように選ぶとき、選んだ品物の価値の総和の最大値を求めよ。 制約 …

ナップサック問題。鉄則本の問題なのでコードのみ。 問題へのリンク 問題概要 宝箱には 個の品物が入っている。品物 の重さは 、価値は である。 太郎君は、いくつかの品物を選んで持ち帰りたいと考えている。しかし、彼のナップザックには容量制限があるの…

ちゃんと証明しようとすると、結構大変！ 問題へのリンク 問題概要 人の生徒がいて、生徒 の身長は である。 これらの生徒を 2 人ずつ 組に分けて、どの組も身長差が 以下となるようにしたい。 そのようなことが可能かどうかを判定せよ。 制約 考えたこと こ…

この回、B と C が異常難易度だったために、D が実際の難易度よりもだいぶ Diff が上がってそうだ！ 問題へのリンク 問題概要 台のソリがあり、それぞれトナカイを 匹必要とする。次の 回のクエリに答えよ。 【クエリ】 トナカイが 匹いるときに、最大で何台…

基本的に Greedy にやればよさそうなのに、意外とやりづらい問題。基本に忠実にやれば解ける！ 問題へのリンク 問題概要 文字 '0', '1', '?' のみからなる文字列 が与えられる。 中の各 '?' をそれぞれ '0' または '1' に置き換えて得られる文字列を二進法表…

じょえちゃんえるから。 「平均値が 以上」という条件を見たときにパッと考えつく話がある。 問題へのリンク 問題概要 個の正の整数列 と整数 が与えられる。 整数列の連続する部分列であって、その平均値が 以上であるものが何個あるかを求めよ。 制約 考え…

まさにこの考え方で解ける問題 drken1215.hatenablog.com 今回の問題も桁 DP でもよいのだが、実は桁 DP しなくても解ける。 問題へのリンク 問題概要 正整数 が二進数表記で与えられます。 以下の条件を満たす非負整数 の組がいくつ存在するか求めてくださ…

以下の典型思考で解けるけど、苦手意識...^^; XOR な問題は各桁ごとに見る の動ける範囲が 以下と指示されているときは、 を上位ビットから見ていったときに、それがどこまで と一致するかを考える (桁 DP でおなじみの考え方) 問題へのリンク 問題概要 個の…

RUPC 2018 の思い出。桁 DP。 問題へのリンク 問題概要 ごちうさ数とは、10 進法表記において「5?13」を含む正の整数のことである。? は 0〜9 のいずれでもよい。 以下の正の整数のうち、ごちうさ数が何個あるかを求めよ。 制約 解法 桁 DP。 一目、51?3 の…