hotpepsiの練習帳

TCO12 Round 1A

00:49

Easy (250) EllysJuice

問題

• みかんジュースとりんごジュースが1ガロンずつある
• n人で、1ターンにみかんとりんごを交互に飲む
• 一度に残量の半分飲む
• 一番飲んだ人が勝ち
• ただし一番が複数いる場合は勝ちなし
• 勝つ可能性がある人の名前のリストを求める

方針

• 3人の場合とかで自信がないのでnext_permutationで全探索
• 解きなおし
• https://github.com/firewood/topcoder/blob/master/tco_2012/EllysJuice.cpp

Medium (500) EllysFractions

問題

• 約分できない分数A/Bを既約分数と呼ぶ。
• A×Bがnの階乗で表せるとき、それを「階乗分数」と呼ぶことにする。
• A/Bは0より大きく1未満
• 数Nが与えられるとき、A×BがN!以下の階乗分数の総数を求める。

方針

• 256未満の素数表を用意しておく
• 候補数の初期値は1
• 1からNまでループして候補数を加算
• 素数が出てきたら、候補数を2倍にする
• https://github.com/firewood/topcoder/blob/master/tco_2012/EllysFractions.cpp

結果

xo- -1 149.55*0 + 251.57 - 25 = 226.57 780th rating 1322 -> 1334

easyはnext_permutation対象の配列の扱いがバグっていて落とした。それよりも判断＆実装が遅かった。

mediumは紙に書いたら素数が増える毎に2倍になっているようだったので、なんとなく書いたら通った。まぐれだけど結果オーライ。(a)素因数毎にまとめる≒素数の数(b)どちら側に使うかどうかの2択なので2倍になっていく(c)AとBの小さいほうが分子になるので大小関係の判別は不要、というようなことを考えればよいようだ。

予選通過には400点ちょい必要だったらしい。あと二歩くらい...