高々6桁の整数が二つ与えられるので、後者を任意に長さ1以上の部分に切り分ける。その合計値が前者を超えずに前者に一番近付くような切り分けを答えよ、という問題。何もない場合や、複数ある場合はその旨答える。 入力には0で開始する整数は来ない、と書い…

整数Mと分数A/Bが与えられるので、A/B素数組について、P*Qが最大になるものを答えよ、という問題。 Mが100kでAとBが1k程度なので、素数は10kくらいまで求めておけば良い。後は二重ループで全探索するのを適宜枝狩りするだけ。時間がかなりシビアなので、真面…

整数Nが与えられるので、非負整数AとBについてA^3+B*(B+1)*(B+2)/6のうちN以下で最大のものを答えよ、という問題。 AとBはいずれも高々100程度なので、全探索するだけ。もっと複雑な式で、AとBが取り得る範囲が10000個ずつくらいあるケースを考えるなら、そ…

1/Kの形の分数N個の総和が1未満の最大になるような分母列を答えよ、という問題。 できる限り大きいものをN個greedyに選択するだけ。greedyで良い理由は不明。

携帯電話のボタンの数と割り当てるキーの種類が与えられ、それぞれのキーが何回くらい入力されるかの頻度が与えられるので、最適キー配置を答えよ、という問題。 連続する任意のキー群を一つのボタンに割り当てたときのコストを事前に計算しておいて、全体と…

N!の末尾に続く0の個数を答えよ、という問題。 N!が2で割り切れる回数は5で割り切れる回数よりも圧倒的に多いので、5で割り切れる回数を数えればおしまい。