TopCoder SRM 577 Div2

TopCoderとは、TopCoder社の主催するオンライン参加型のプログラミングコンテストである。
その中の競技形式のひとつであるSRMは、与えられた問題に対して正確な答えを出力するプログラムを書くスピードを競うというものである。問題は単純なものが多いが、データ数が多かったり処理時間に制限があったりするので、いかに最適なアルゴリズムを考え、素早く実装できるかが勝負のカギとなる。


今回、久々にSRMに参加したのでレポートを書いてみたり。




250点問題

与えられた文字列から連続する母音（a,e,i,u,o,y)をできるだけ取り除きたい。取り除いた後の文字列の長さの最小値を出力せよ。

（例）
 tourist  → turist または torist
この場合は6文字まで減らせるので 6 を出力する。

<解法>
文字列を端っこから順番に調べ、母音が連続していればもとの文字列の長さから1を引く。
与えられる文字列の長さは50以下なので一瞬で終わる。

<現実は…>
言い忘れていたが、問題文はすべて英語である…。
英語の読解力の低さにより、問題を理解するのに15分くらい、さらに変なバグを埋め込んで取り除くのに15分かかってしまった。回答の提出が遅かったので166点くらいしかもらえなかった。


500点問題

自分を含む競技者N人分のレーティングがN個与えられる。また、競技者は以下のアルゴリズムに従ってグループ分けされる。

1) グループはR個作られる。（R = N / 20。ただし、割り切れないなら R = N / 20 + 1）
2) 競技者をレーティングを基準に降順に並べる
3) 上からR人をランダムにグループに割り当てる。ただし、このR人は同じグループに属さないようにする。
4) 以降、割り当てられていない競技者がいなくなるまで(3)を続ける


このとき、自分が最も高いレーティングの競技者と同じグループに割り当てられる確率を出力しなさい。

<解法>
場合分けをして考える。
1) 競技者が20人以下ならグループは１つしかできない。つまり必ず同じグループになるので確率は1。
2) 競技者が21人以上であるなら、自分の順位を求める。順位がR位以内なら手順(3)で必ず別グループに分けられてしまうので確率は0。
3）(1)(2)以外なら、R個のグループからランダムに１つのグループを選んだとき１位の競技者がいる確率を求めればよい。その確率は　1 / R。


<現実は…>
英語の（略）。
なぜか上から20人固定で振り分けられると勘違いし間違ったコードを提出してしまった。Challengeよって回答無効となる。0点。

1000点問題
残り時間がすでに3分しかない。読めない。


総合
166点。たぶん最下位に近かった。
レーティング 921 → 829。
100近く下がったぞ！灰色コーダーに戻ってしまった。