読者です 読者をやめる 読者になる 読者になる

算譜王におれはなる!!!!

偏りはあると思うけど情報技術全般についてマイペースに書くよ。

GDD DevQuiz 一人ゲーム 僕の答え

Google

DevQuizをご存知ですか?

DevQuizとは2011年11月に開催されるGoogle Developer Day 2011 Japan (GDD) への参加資格を獲得するためのクイズのことです。
全部で7つのクイズが用意されており、ウォームアップクイズ、分野別クイズ、チャレンジクイズの3つの種類に分かれています。
各クイズと、それぞれの僕の獲得した点数は図のとおりです。
f:id:ngsw_taro:20110912101658p:image
DevQuiz突破のボーダーラインは暫定値ですが現在、100点前後となっているので、それより高い点数を取れたので嬉しいです。ただ、スライドパズルが心残りです。せめて20点は取りたかった…!
#ちなみに優先参加枠に当選しているので僕はDevQuizの結果に関わらずGDDへ行けます♪

一人ゲーム

一人ゲームの僕の回答についてお話しします。
一人ゲームのルールは以下のとおりです。

ルール
数がいくつか与えられます。なるべく少ない手数で数を全て取り除いてください。
あなたは 1 手で、

  • 全ての数を半分にする(端数は切り捨て)
  • 5 の倍数 (0 を含む) を全て取り除く

のどちらかの操作をすることができます。

一人ゲーム - Google Developer Day 2011 Japan DevQuizより引用

これは単純な幅優先探索で解けました。
枝刈りの方法は、これも単純で

  • 現在の数列が、すべて5の倍数(0を含む)によって構成されている
  • 現在の数列に、5の倍数(0を含まない)が存在する

上記のうち、少なくとも1つの条件を満たした場合に「5の倍数(0を含む)を全て取り除く」を実行します。

これだけの工夫で十分、本番データも解けました。

DevQuiz答え合わせ in 横浜

ところで、明日9月13日にDevQuizの答え合わせ会があります。
Google公式のものではなく、有志の方々による発表会・勉強会です。
まだ空きがあるので、よかったらどうぞ → DevQuiz答え合わせ in 横浜
おそらく僕はWeb Gameについて発表させていただくと思います。