Hatena::Grouptopcoder

TopCoder煮ブログ

本家ブログはこっち → http://d.hatena.ne.jp/nitoyon/

2011-07-13

SRM 512 DIV1

| 02:06 | SRM 512 DIV1 - TopCoder煮ブログ を含むブックマーク はてなブックマーク - SRM 512 DIV1 - TopCoder煮ブログ

1<<9 というキリ番の回。前回に引き続いて参加。

14121448 (163.88pt 424位/905人)

○-- (challenge: -25pt 0勝1敗)

MysteriousRestaurant (Easy)

250pt じゃなく 256pt だった。さすがキリ番の回。

N 日間 M 皿個の皿を出す料理店があって、それぞれの日の値段と手持ちの総額を与えられる。1回でもパスするとそれ以降食べられない。ある日に皿 m を選んだら、一週間後にも同じ皿を選ばなきゃいけない。最大何日食べ続けられるか。

最初、どうすりゃいいんだと途方にくれたが、1日でも食べられなかったらそこで終わりなので、支払い総額を最小にする選び方を最初の日からしていけばよいだけだと気づいた。ただし、8日目以降は、どの皿を選ぶのがにするのがトータルでのコストを抑えられるかを以前の週にさかのぼって再計算する必要がある。

ざっとコーディングして 188.88pt。チャレンジでは早とちりして失敗。-25pt…。

SubFibonacci (Medium)

与えられた数列からフィボナッチ数列の部分集合を2回取り出したときの最大長を求める問題。

ある数列がフィボナッチの部分集合かどうかを求める方法がさっぱり分からず諦める。

twitter の TL みてると2分探索でやるらしいのだが、それでもやっぱり分からん。

PickAndDelete (Hard)

5,1,2 が与えられたら、1、1~2、1~5 の順列の総数を数え上げる問題。総数が多いので mod して求める、という時点でいい方法が思いつかず。

まとめ

challenge してなかったら 294位。ちょっともったいなかった。

月之宮 帝月之宮 帝2011/07/22 22:58与えられた数列に対してmid(0~n)を決めて二つの数列に分割してから探索するだけで二分探索はしないんじゃないのでしょうか。分割後の探索は二分探索には関係ないですし。