WARushスマートフォン用の表示で見るWARushSRMの結果とか、解けた問題のコードを書いていきますこの広告は、90日以上更新していないブログに表示しています。整数Sが2進数表記の文字列で与えられる。足したり引いたりする回数の最小を返せ。10^6考えた事DPっぽいが、Tagにあるように貪欲にいける。基本的には'1'になっている所の分だけ足していけばいいのだが、Sampleの"111"や"1011011"の時に、あえてその数値よりも大きい数値を足して回数を節約している。これを"おっきい数足すぞテクニック"と呼ぶ。このテクニックは1が2つ以上続いている場合有効である。"111101111"の時、まずおっきい数"100000000"を足す。111100000となり、1を4つも消化できるのだ。普通に1を足していったら4回のところテクニックを使うと2回に抑えられる。残りの"1111"もテクニックを駆使すればあと2回でよさそうだ。"111101111"の'0'の所まで'1'がくるように"1000"を引くとどうだろう。111110000となり、なんとおっきい数がもう足された状態になり、すぐにでもテクニックが使える状態にできるのだ。これは"おっきい数足すぞチェイン"と呼ばれる高等テクニックだ。このチェインは'0'が2つ以上続いていなければ使える。この2つのテクニックを使えば、0が2個以上続いていない部分をひとまとまりとして扱い、回数を最大限節約できる。例の"111101111"は3回で作れてしまうのだ。素直に1を足していったら8回かかると考えると凄い節約である。このテクニックを使う上で1つだけ注意点がある。それは、まとまりの中に1が2個以上続いている部分が全くなければ、このテクニックは返って回数を増やしてしまうと言う事だ。素直に1を足してけば3回ですむ。1が続いていなければ素直に足していこう。"ABBADiv1"月別アーカイブリンクはてなブログブログをはじめる(無料)お知らせはてなブログをはじめよう!Ekaingさんは、はてなブログを使っています。ブログを報告するスターをつけました引用をストックしましたストック一覧を見る閉じる引用するにはまずログインしてくださいログイン閉じる引用をストックできませんでした。再度お試しください閉じる限定公開記事のため引用できません。