TopCoder SRM 533 Div2

oox
963991
3回連続で上がりました。この調子を維持したいですね。

writerは日本人と見せかけての中国の方でした。

そろそろ500から解き始めても良いかもしれませんね。

250

ピカチューは "pi", "ka", "chu" の3音しか声に出せない。
与えられた文字列を話すことはできるだろうか。

範囲外参照をしてしまっていることに後から気づいたが、多めにメモリを確保してくれているのか、なぜか落ちなかった。
ちなみに、string#[] ではなく string#at を使うと"c"で落ちます。

"(pi|ka|chu)+"の正規表現にマッチするかどうか判定する、というコードを書いている人がいて、かっこ良かった。

500

星の器 (Casket of Star) の目的は、エネルギーを溜めることである。
intの配列weightの各々の要素にはエネルギーが溜まっていて、weight[i]を消すことで、weight[i - 1] * weight[i + 1] のエネルギーを得ることができる。(i はweightの最初や最後の要素ではない。また、この操作の後には、weight[i+1]以降の要素が前にずれる。)
この操作を要素が2つになるまで繰り返して、得ることのできる最大のエネルギーはいくつか。


Div2では、weightの要素数 <= 10 だったので、全探索して終わり。
はじめのうちはGreedy解を考えていたが、手動でやってもサンプルが通せなかった。(Div1は要素数 <= 50 なので全探索はできない。Greedyで解いて落ちた人が多いらしい。writerの方も、こんなにGreedy解が出るとは思っていなかったそうだ。)
かなり時間がたって得点が下がった後、全探索のオーダーが O((要素数-2)!) 程度しか無いことが分かり、全探索に切り替えた。

1000

魔法少女は初日にライフポイントをM持っていて、このMがライフポイントの最大値である。
1日の始まりにライフポイントが1ずつ減少していき、0になった時に、魔法少女は死ぬ。

ライフポイントを増やす唯一の方法は、魔女を倒すことである。
i番目の魔女は day[i] 日目に現れ、その魔女に勝てる確率は win[i] %である。勝利すると gain[i] のライフポイントを得ることができるが、負けると魔法少女はすぐに死ぬ。

その魔女と戦うかどうかは、あなた次第である。一番長く生きることのできる選択をしたとすると、生きられる日数の期待値はいくつか。生きられる日数の期待値を最大になるような選択をすると、その期待値はいくつか。

  • 魔女の数の最大が 1 <= N <= 50
  • ライフポイントは 1 <= M <= 100000

であることから、O(NM)のDPであることは分かったが、不慣れであることが災いして解くまでには至らなかった。
こういう問題を「期待値DP」と呼ぶらしい。そろそろDPを解けるようになりたい。

250

ひどいコードですが、一応置いておきましょう。

// System Test には通りましたが、範囲外参照をしているのでマネしないでください。
struct PikachuEasy {
    string check(string word) {
        int L = word.length();
        bool f = true;
        for(int i = 0; i < L; i++) {
            if(word[i] == 'p') {
                if(word[i + 1] == 'i') i++;
                else {
                    f = false; break;
                }
            }
            else if(word[i] == 'k') {
                if(word[i + 1] == 'a') i++;
                else {
                    f = false; break;
                }
            }
            else if(word[i] == 'c') {
                if(word[i + 1] == 'h' && word[i + 2] == 'u') i += 2;
                else {
                    f = false; break;
                }
            }
            else {
                f = false;
                break;
            }
        }
        return f ? "YES" : "NO";
    }
}

500

typedef vector<int> vint;

struct CasketOfStarEasy {
    int vmax;

    void solve(vint v, int score) {
        int L = v.size();

        if(L == 2) {
            if(score > vmax) {
                vmax = score;
            }
            return;
        }


        for(int i = 1; i < L - 1; i++) {
            vint nex;
            for(int j = 0; j < L; j++) {
                if(j != i) {
                    nex.push_back(v[j]);
                }
            }
            solve(nex, v[i - 1] * v[i + 1] + score);
        }
    }

    int maxEnergy(vint weight) {
        vmax = 0;
        solve(weight, 0);
        return vmax;
    }
}