La Faïence

GDD2011の一人ゲーム解けた

ひとこと

一人ゲーム

数がいくつか与えられます。なるべく少ない手数で数を全て取り除いてください。

あなたは 1 手で、

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

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

入力例

4
2
10 21
3
0 9 9
4
81 67 83 86
3
11 22 30

入力例に対する回答

2
5
8
4

1 つめのテストケースでは、まず全ての数を半分にします (10, 21 → 5, 10) 。次に、5 の倍数を全て取り除きます。これで 2 手で全ての数を取り除けます。

2 つめのテストケースでは、全ての数を半分にする操作を 4 回行います。

0, 9, 9 → 0, 4, 4 → 0, 2, 2 → 0, 1, 1 → 0, 0, 0

その後、5 の倍数を全て取り除きます。これで 5 手で全ての数を取り除けます。

回答はまだ乗せられないので書かないでおく。ちなみに僕がとったアプローチは [二分木で深さ優先探索]。←選択反転で見れます

もっといい方法があったかもしれないけど（それこそ数学的な感じで）。

とりあえずこの問題と神経衰弱ソルバー解けたので、現在の得点は100点。あとは9パズルっぽいやつなんだけど、ちょっと頭をなやませている。

現在のところボーダーは40点らしいので、まだ大丈夫っぽいけど。

ツイートする

Permalink | コメント(0) | トラックバック(0) | 18:11