SRM356

授業受けながらやろうと思ってノートPCを持っていく。
が、 Arena 立ち上げてもつながらない。なぜかTunnelingに失敗する。
しょうがないので、授業をほっぽり出して研究室へ。

直前でFileEditとかのプラグインが入っていないことに気づき愕然とするが、セットアップする時間が無かったため裸のまま開始。

250pt

なんでこんなの落とすんだ…orz
LCMとる必要全く無いし。何やってるんだろう。
1000人いれば十分だってことに気づけば平均値全部について1000回試せばいいだけだとすぐ分かる。

550pt

問題を読み間違えすぎ。 設定がややこしい…。
ノード数少なめだし、計算量的にキツイ計算が避けられない感じ。

単なるグラフだと思って、毎回一つのノードを選択し、そこから伸びるそれぞれの枝について一緒に連れて行くかどうかを選択して（少なくとも一つは連れて行く）順番にノードを取り去っていくという方法だと愚直すぎるか？

枝狩りとビット演算で最適化頑張ってみたのですが、サンプルの n = 16 くらいだと一瞬で解くものの、n = 24 の壁がでかすぎる。とても2秒で解ける気がしない。
どう見てもアルゴリズムそのものに改善が必要です。本当にありがとうございました。

追記

250pt は double を一切扱わずに解けることに気づいた。

0 ≦ s ≦ 10*n を満たす整数 s が存在して

よって、
{ 1000の倍数のうち n*a以上で最小の数 } < n*(a+1)
が求める条件。

コードに落とすと

bool check(int n, int a) {
  return (n*a + 999) / 1000 * 1000 < n * (a+1);
}

誤差を気にしなくていいと随分と気が楽になる*1 ので、小数が絡んだら整数の範囲に問題を置き換えてみることを考えよう。

*1:その代わり上限・下限を気にする必要はある