SoundHound Inc. Programming Contest 2018 -Masters Tournament-に出て
３完までは簡単に行けたはずだったのにcoutの精度でCハマった。辛かった。
Dは上手いことダイクストラに持ち込むのかなぁと思ったけど、ダイクストラをそもそも書いたことがないので険しかったです。復習する価値ありそうだと思ったのでまたやります。ダイクストラは是非自分のものにしていきたいので(初めて知ったアルゴリズムがダイクストラ法っていうのがある。橋本環奈から教わったってinf回言ってる)
一応ギリギリ水パフォだったので良かった
以下総評
A:ばつはエックスです
B:
- for (int i = 0; i < s.size(); i += w) {
- cout << s[i];
- }
C:全通りの期待値を出すので独立であるとして考えればいい。つまり一文字目から順番にペアを考えて美しいかを調べていけばよい。
比べている一文字目が1～dまたはn - d～nに入っていればこのペアに関して稼げる美しさの期待値は1/nそうでないときは2/n
ここから求める美しさの期待値は
p=min(2d,n)/nを用いて
(m-1){p(1/n)+(1-p)(2/n)}
で求まる。
ただしd=0がコーナーケース(今回は優しい世界なのでサンプルがそう)
あと、冒頭にも書きましたがcoutの精度でハマったのが初めてだったので大変でした。
しかし、無事解決しました。同じとこでハマった人使ってください
- void exact_say(double x) {
- cout << setprecision(numeric_limits<double>::max_digits10) << x << endl;
- }
Ｄ解いたらまた上げます
