制約条件:ある値<=K
基本的に Greedy にやればよさそうなのに、意外とやりづらい問題。基本に忠実にやれば解ける! 問題へのリンク 問題概要 文字 '0', '1', '?' のみからなる文字列 が与えられる。 中の各 '?' をそれぞれ '0' または '1' に置き換えて得られる文字列を二進法表…
じょえちゃんえるから。 「平均値が 以上」という条件を見たときにパッと考えつく話がある。 問題へのリンク 問題概要 個の正の整数列 と整数 が与えられる。 整数列の連続する部分列であって、その平均値が 以上であるものが何個あるかを求めよ。 制約 考え…
まさにこの考え方で解ける問題 drken1215.hatenablog.com 今回の問題も桁 DP でもよいのだが、実は桁 DP しなくても解ける。 問題へのリンク 問題概要 正整数 が二進数表記で与えられます。 以下の条件を満たす非負整数 の組がいくつ存在するか求めてくださ…
以下の典型思考で解けるけど、苦手意識...^^; XOR な問題は各桁ごとに見る の動ける範囲が 以下と指示されているときは、 を上位ビットから見ていったときに、それがどこまで と一致するかを考える (桁 DP でおなじみの考え方) 問題へのリンク 問題概要 個の…
RUPC 2018 の思い出。桁 DP。 問題へのリンク 問題概要 ごちうさ数とは、10 進法表記において「5?13」を含む正の整数のことである。? は 0〜9 のいずれでもよい。 以下の正の整数のうち、ごちうさ数が何個あるかを求めよ。 制約 解法 桁 DP。 一目、51?3 の…