oox
963→991
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; } }