CODE FESTIVAL 2016 Final B - Exactly N points
かなり明確に方針が立ってそのとおりにコードを書いてAC出せて手応えを感じた問題なので記事にしておく。
初手の方針（＋思考の流れ）
とりあえず{1,2,3}のパターンを列挙した。
{1},{2},{3},{1,2},{1,3},{2,3},{1,2,3}
同様に{1,2,3,4}のパターンを考えると
{1},{2},{3},{4},{1,2},{1,3},{1,4},{2,3},{2,4},{3,4},{1,2,3},{1,2,4},{1,3,4},{2,3,4},{1,2,3,4}
ぱっとみて{1,2,3,4}については4自身と{1,2,3}で列挙した要素に4を追加したもので構成されてることに気づいた。 この時点でBrute-force Attackでやったn+1番目の列挙をn番目の要素で表せないかなと頭をよぎった。
ABC 029 C - Brute-force Attack - sky’s 雑記
ここで全パターン列挙した場合に制約を満たせるかを考えたが、
で10^ 7だとメモリ的にきつそうだなと思った。
そこで改めて{1,2,3}を見てみると1+2+3がその集合で表せる最大値かつ1以上かつ6以下なら全ての数字をその集合で表せることに気づいた。 {1,2,3,4}についても同様で表現できる値は1以上かつ10以下の全ての数字となる。 なので入力例2で7が与えられた場合を考えると{1,2,3}では表現できないが{1,2,3,4}であれば表現できることに気づく。 更に7に対して4を利用すると、残りの3を表現するためには{1,2}があれば事足りることになり、最終的に4->2->1と辿る。
上記の内容をvectorで累積和を作った後にwhile,forループで回して出力をしたところACとなった。
Submission #9430321 - CODE FESTIVAL 2016 Final
正答と気付き
考察はほぼ同じような内容。 ただ集合の最大値はs=a*(a+1)/2であることとnを表現するためにn以上の集合は必要ないことに着目すると累積和を用いずもう少し簡略化できる。
