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."