2014年04月22日

AtCoder ABC#007 D問題について

アプリ開発とは関係ありませんが、土曜日にAtCoderという競技プログラミングに挑戦してみたことについて書いてみようと思います。

競技プログラミングというのは簡単に言うと、こんな処理をするプログラムを作りなさいという問題に対して、いかに早くプログラムを作るかを競うものです。

土曜日にやったのはAtCoderの初心者向けコンテストのAtCoder Begginer Contest(略称ABC)というもので、AtCoderのサイトの説明文を引用すると"プログラミングには興味あるけど、何をしていいかわからない...そんな人のためのコンテンツ"だそうです。

問題はAからDまでの4問あって、段々難易度が高くなるようになっています。で、AからCまでは普通に解くことができたのですが、D問題が解説を見てもわからなかったので、一晩頭を悩ませて出した答えを以下にまとめてみようと思います。

解けなかった問題は「ある整数AからBまでの間にある4または9を含む数値の数を求める」というものでした。

例えば、1から50までの場合なら、4、9、14、19、24、29、34、39、40〜49の18個になります。

当然、対称の範囲の数値について1個1個片っ端から調べていくのはNGとなります(部分点はもらえますが)。というのも問題の条件として2秒以内に処理を終わらせること、A、Bの範囲は1〜10^18となっているからです。

そんなわけで効率良く処理をする方法を考える必要があります。が、いきなり答えを出すのも難しいので単純なケースから考えてみようと思います。

まずは0〜9の場合。

これは考えるまでもないですね。0から9の間で4、9を含む数値は4、9の2個です。

次に0〜99の場合。

この位ならまだ手で数えることができそうです。10の位が4、9の場合は1の位に関係なく4、9を含んでいることになります。10の位が4、9以外の場合は1の位が4、9の場合に4、9を含んでいることになります。これをまとめると以下の図のようになります。

2.png

次に0〜999の場合。

この辺りから手で全部書き出すのは無理が出てくるような気がします。100の位が4、9の場合は下2桁の値に関係なく4、9を含んでいることになります。100の位が4、9以外の場合は下2桁で4、9を含んている場合に4、9を含んでいることになります。下2桁について4、9を含んでいる数値は先ほど求めた26個になります。これをまとめると以下の図のようになります。

2.png

段々と法則性が見えてきたような気がします。0から9がn個並んでいる数値までの間の4、9を含んでいる数値の数を配列dp[n - 1]に入れたとすると以下の様な式で表すことができそうです。(配列の添字は0始まりなのでn - 1としています)

dn[0] = 2
dp[n] = 2 * power(10, n) + 8 * dp[n - 1]
※power(10, n)は10のn乗

次にもう少し一般的なケースについて考えてみます。

0〜1234の場合、0〜999と1000〜1234に分けて考える事ができます。

0〜999の場合はすでに上のほうで計算しています。

1000〜1234の場合は最上位桁の1はあってもなくても4、9を含む数値の数に影響はないので0〜234の場合と置き換えることができます。

0〜234については、0〜99、100〜199と200〜234に分けて考えることができます。

100〜199は0〜99と同じ、200〜234は0〜34と同じと考えていくと、あとは同じことの繰り返しで分解していけそうです。

3.png

これで0から任意の数値までの間の4、9を含む数値を探す事ができそうです。

1点注意しないといけないのは最上位桁が4、9の場合の処理を分ける必要があるということ。例えば、1000〜1234は0〜234と同じですが、4000〜4234は235個全部が4を含む数値になります。

最後にA〜Bまでの範囲で4、9を含む数値の数を求めるには、0〜Bの場合の数から0〜A-1の場合の数を引いてやれば求めることができます。

アプリ作ってて4と9を含む数値を数えたいなんてことはなさそうなので、日常生活で役立つようなものではないですが、複雑な問題が解けるようになれば普通のプログラミングのスピードも上がらないかなぁと期待していたりします。単にこういう問題を解くのが好きだというだけだったりもしますが。
ラベル:AtCoder
posted by かねだ at 19:48| Comment(0) | その他 | このブログの読者になる | 更新情報をチェックする

広告


この広告は60日以上更新がないブログに表示がされております。

以下のいずれかの方法で非表示にすることが可能です。

・記事の投稿、編集をおこなう
・マイブログの【設定】 > 【広告設定】 より、「60日間更新が無い場合」 の 「広告を表示しない」にチェックを入れて保存する。


×

この広告は1年以上新しい記事の投稿がないブログに表示されております。