Search on the blog

2011年3月31日木曜日

SRM BrushUp: FoxPlayingGame (501 div2 Middle)

SRM501。狐さんの回。

こんこん♪

平日なので参加できなかったので、今日解いてみた。。
が、ダメでした。

250は、sequenceが与えられるので、これにある整数nを加ると、arithmetic progression または geometric progressionになるときのnの個数を求めよ。
という感じ。(やばい、日本語へたい。。笑)

500はかなりトリッキー。DPで解いたけど、マイナスの場合ダメじゃんと気付いて、じゃあ
  • 整数の大きさ
  • 整数の絶対値
2つでDPじゃん。って思ったけどこれもダメ。。
こういうときは、例題をよく読むといい。
なるほど。。先に足すか、先に掛けるかをやればよさそう。書く。サブミット。テスト。落ちる・・

で、(paramA, paramB)が
  • {正 or 負}^2 の4分岐
  • paramBが{1000以上、未満}の2分岐
の8分岐くらいのソースを書く。通った。。でもこんなややこしいのか。。。
後でシンプルに書けることに気付く。
class FoxPlayingGame {
public:
double theMax(int nA, int nB, int paramA, int paramB) {
double a = paramA / 1000.0;
double b = paramB / 1000.0;

if (!nA) return 0;
if (!nB) return nA*a;

double ret = nA*a;
ret = max(ret, nA*a*pow(b, nB));
ret = max(ret, nA*a*pow(b, nB-1));
ret = max(ret, nA*a*b);

return ret;
}
};

この問題は、新しい思考パターンを教えてくれます。
分岐がいくつあるのかを考えるのではなくて、最終的に最大値を取りそうな値はどんなパターンがあるか最終段のみ考えればよいです。
入力があって、マッピング先だけに目を向けるという発想。。。
なるほど。良い準備をさせてもらいました。

もうちょっと分析すると、
paramA/1000.0は全部足した方がいい。(足せば足すほど、絶対値は大きくなる)
paramB/1000.0は以下の4つの選択肢がある
  • 掛けない(掛けると小さくなる)
  • 全部掛ける
  • (全部-1)掛ける(符号の都合で)
  • 1回だけかける(掛けると絶対値は小さくなるが、符号を逆転できる)
まあでも、This is what they call "hindsight is 20/20."

0 件のコメント:

コメントを投稿