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

ぱろっと・すたじお

技術メモなどをまったりと / my site : http://parrot-studio.com/

アンドロイドはアイドルの夢を見るか(恋するハッカソン〜君色に染まるアイドル〜を解いた件)

ということで、8回目のPOHなのですが・・・

paiza.jp

・・・前回あたりから「ゲーム」としてPRしていたり、
今回から会員登録しないとダメだったりと、
そろそろいいかな・・・とも思いまして(´-ω-)

しかも、先月は死ぬほど忙しくて、
普段飲まないエナジードリンクを飲みながら仕事していたレベルで、
こういう遊びをやっている余裕もなくてですね・・・

でも、仕事もやっと一段落して、そもそもそのエナジードリンクは、
以前のPOHで当たったやつだったりしたので、
会員登録くらいはまあいいかな・・・とかΣ(・ω・ノ)ノ

ただ、外部サイト連携で登録しようとしたら全然うまくいかなくて、
結局ID/PASSで登録するはめになったはちょっと・・・
何がおかしかったのは不明です

そんなこんなで先日挑戦しまして、
数時間で(現時点である問題を)全てクリアしました∠( ゚д゚)/

f:id:parrot_studio:20160703110902p:plain

まだロックされているドレスは、
「お仕事」(イベントシーン)をあと20回くらい見ないと解放されないやつで、
面倒なので放置しています( ゚Д゚)y─~~

今回もほとんどは楽勝だったのですが、
水着問題はパフォーマンス的にやや難易度が高め(雑に書くと何秒もかかる)で、
浴衣問題と制服問題がBOSS・・・という感じでしょうか
(それでも初期の頃の問題に比べれば瞬殺のレベルですが)

一応、全部のコードがこちらに(´・ω・)っ

https://gist.github.com/parrot-studio/d657f61ce60969685995b6e7f22bf119

ということで、今回は浴衣問題と制服問題の話だけ書いていきます

浴衣問題

冷蔵庫の電気料金に関する問題です

設定温度より高いと2円/h、設定温度で維持できるなら1円/h
1日に何度か開け閉めすると、そのタイミングで温度が上昇
1日で電気料金はいくら・・・という問題です

この、「状態が変化する」系の問題は、
クロージャーの出番でございます(`・ω・´)

# クロージャー生成
count = 0
counter = lambda do
  count += 1
end

# クロージャーを呼び出す
counter.call
puts count # => 1
counter.call
puts count # => 2
3.times { counter.call }
puts count # => 5

クロージャー(今回の場合はRubyのProcオブジェクト*1)は、
作られた時点での外部環境(countという変数)を参照しているので、
こういうことができるわけですね

今回の問題はこれを使えば簡単で、
クロージャーの中に問題の仕様をそのまま織り込んでしまい、
1時間ごとにcallするだけで終わりです

与えられているのは開け閉めする時刻なので、
その時刻まで状態を進めて、開け閉めした時点で温度を加算して、
また次まで進めて・・・というわけです

これを真面目に解こうとすると結構面倒だと思いますが、
仕様をそのまま書けば解けてしまうというのが面白いですね(`・ω・´) b

制服問題

ざっくり言うと、「52人で大富豪をやって、全員の順位を決めろ」という問題です
先ほどの浴衣問題が「業務系にありがちな問題」だとすれば、
こちらは「ゲーム系にありがちな問題」という感じでしょうか

まず面倒なのが、「カードの強弱」です
大富豪は3が一番弱く、10->J->Q->K->A->2という感じで強さが決まっており、
これを毎回比較するのはコストが高いです(´-ω-)

なので、データを読み込む時点で、3を0、4を1・・・2を12というように、
全部強さの順に数値化してしまい、単純な大小比較に持ち込みました

でもこれはたいした話ではなく、最大の問題は「場が流れる条件判定」です

問題通りだと、ある人がカードを出したあと、その人の次まで誰も出せなければ、
次の人が自分の手札を出せる・・・となっていますが、
そのまんま実装したら明らかに計算が無駄です(´・ω・`)

要は、「その人が出したカードが現時点で最強なら場を流す」ということなのですが、
そうなると「その人の出したカードが最強かどうかをどう判定するか?」という問題が

最初のうちは「2」が最強なので、2を出したら場が流れます
しかし、4枚2を出されたら、次の最強はAですし、
刻々と最強のカードは変わっていくわけです

これをどうしたものかな・・・と思ったのですが、
わりとシンプルに「使ったカードを排除していく」という手段をとりました
(コード内のuse!メソッド)

あとは「場が流れた」ことを-1で表現して、次の人が確実に出せるように単純化したとか、
ランキングを配列で表現したとか、いつものレベルの最適化でして、
52枚と枚数が決まっているため、計算量もほぼ一定で、パフォーマンス的にも難しくありません

まとめ

ということで、現時点ではこの2問がやや難しいといった感じで、
他は効率よく書けるかはともかくとして、「書けない」ということはないはずです

見た感じあと2問、まだ解放されていない問題があるようなので、
これがさっきの2問より難しいようなら、またこの記事に追記します...φ(・ω・`)

*1: 突っ込まれそうなので先に書いておきますが、厳密にいうと、Rubyラムダ式とProcオブジェクトは振る舞いが違います ただ、私は普段、その違いを意識しなければならないような使い方はしてないので、ほぼ同じようなものとして扱っています 重要なのは、「クロージャーという(一般的な)概念がこういう場合に使える」ということです