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) | その他 | このブログの読者になる | 更新情報をチェックする

2014年04月13日

ステージ構成作成、バランス調整はこれからだけど。

また随分と久しぶりの更新です。

元々は週1ペースを目標としていたのですが完全に月1ペースへと落ち着きそうな感じです。今週からは元のペースに何とか戻していきたいですね、仕事も落ち着いてきたので。

相変わらず全然ほとんど開発は進んでいませんが、とりあえずステージ構成を全ステージ分作るところまではできました。まだバランス調整とかやってないので、とても遊べたものではありませんが。

最近は後回しにしたバグの修正とか機能を入れ込んだりしてますが、だいぶ時間が空いているので何をやらないといけなかったのか忘れがちです。

そういえば先月の記事に初コメント付いていたことに今頃気付きました。

弾が出ない瞬間を作って緩急を作った方が遊びやすいとのことで、貴重なご意見ありがとうございます。

確かにそういった休憩場面があった方がメリハリもできるし良いような気がします。バランス調整する時にこの辺も意識してステージ構成を見直していきたいと思います。
ラベル:とりとま
posted by かねだ at 23:18| Comment(0) | 開発記録 | このブログの読者になる | 更新情報をチェックする

2014年03月10日

コマンドラインからXcodeのビルド・実行をやってみる

今週もほとんど進捗なかったのでちょっと小ネタ。

私の場合、vimでソースコードを書くことが結構あります。そんなとき、ビルドして実行するためだけにXcodeにフォーカスを移動するのがめんどくさいと感じることがたまにあります。

というわけで、コマンドラインからXcodeでのビルドとか実行とかを行う方法を調べてみました。といっても、別に高度なことをやるわけではなく、AppleScriptでXcodeにショートカットのキー入力Command + rを飛ばすだけなんですけど。

スクリプトのソースはこんな感じです。

#!/usr/bin/osascript
tell application "Xcode" to activate
tell application "System Events"
    tell process "Xcode"
        keystroke "r" using {command down}
    end tell
end tell
tell application "Terminal" to activate

これをxrun.scptとか適当な名前を付けて、実行権限付けてPATH通ってる場所に配置。で、vimからおもむろに:!xrun.scptと入力してやればアプリの実行ができるようになります。

keystrokeを"."に変えてやれば停止させることも可能ですね。

でも、Xcode使って開発してれば最初からそんな苦労はいらないわけですが。

ラベル:Mac
posted by かねだ at 00:11| Comment(0) | 開発記録 | このブログの読者になる | 更新情報をチェックする

広告


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

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

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


×

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