問題
$3$ つ以下その中から選んで和をとるとき、$1 ～W$ までの数を全て作れるような、要素数 $300$ 以下の集合を作成する問題。
サービス問題のようで全くサービス問題ではない問題。
初めに考えたこと(誤った方針)
$1$ から順番に数を見ていって、以下の操作を行う。
始め集合 $S$ は空集合としておく。みている数字を $i$ とする。
- $i+1$ から $i+i-1$ まで数を見ていく。
- $j$ を作るのにすでに $3$ つの要素を使ってしまっているなら、集合 $S$ に $i+j$ を追加する。ここが呼び出さたなら、ループを終了し、$i$ を $i+j$ と改めてループを開始する。
- $i$ が $W$ をこえたら終了。
$1$ つの数に対しては $1$ 回の条件分岐が発生するので、計算量としては $O(W)$ となって間に合う。
ところが、この解法は要素数 $300$ という制約を完全に無視した方針となっている。
そして、案の定というか、$W$ が1000を超えたあたりですでに要素数が $300$ を上回っていた。
なんでこんなことをしたかというと、『この解法が模範解答に違いない！制約も自動的に追いついてくれる！』と思い込んでいたというのがある。
こういった支離滅裂で崩壊した思考をする癖は、将来仕事についたときに足を引っ張るものだと思うので、これを機にやめたい。
次に考えたこと (誤った方針2)(すでに残り時間10分)
さて、上記の思考と実装で三十分近く時間を無駄にした。
B問題で $map$ の計算量の重さを知らず、TLEで四十分近く悩んでいたというのもあり、残り時間は十分くらいしかなかった。
ここでふと脳裏に以下の方針を思いついた。
- $W$ をちょうど超える $2^n$を見つける
- 1,10,100,1000,みたなものを用意していけば、いけるのでは...
近からず遠からずみたいな発想ではあったが、結果的に実装すら間に合わず終了。
結局コンテストの流れとしては、
- D(絶望)→C→B(mapの仕様を知らず、40分程度悩む)→A→D(希望がみえつつ実装が追い付かないことを悟る)→＼(^o^)／
という悲しい感じで終了した。
結果的にEから始めていれば...という感じ。結局E問題は読むことすらなく終了した。
パフォーマンスも過去最低値を記録し、若干モチベが低下した(その後回復した)。
模範解答
これ以上にスッキリする答えはないだろう、というくらい、過去一『あ～なるほどね！』となった問題だ。
『要素数 $300$』という制約と、『$10^6$』というのがヒントだった。
要するに桁を一と十の位、百と千のくらい、万と十万のくらいに分けて考えればよい。
そうすれば、$1～99(1とばし),100～9900(100とばし),10000～990000(10000とばし)$ という $297$ 個の数を用意するだけで$ 000001～999999$が全て作成できる。
これに $1000000$ を追加した $298$ 個の要素で、どんな $W$ に対しても対応できることになる。
プログラミングというよりただ発想の問題だった。完全に意表をつかれたので、こういった問題の対策もしていきい。
実装
int main() {
int w; cin >> w;
cout << 298 << endl;
repa(i, 99) cout << i << " ";
for (int i = 100; i < 10000; i += 100) cout << i << " ";
for (int i = 10000; i < 1000000; i += 10000) cout << i << " ";
cout << 1000000 << endl;
return 0;
}