o-- 110点くらい + チャレンジで210位/950人くらい。レーティングは1660くらいから1730くらいに伸びた。
Easy 250
- n個の数字をn-1個の演算子(+か-)で結んだ数式があります。 1 + 2 + 3 + 4 とか。
- その隣接したペアを計算するとn-1個の数が出ます。1+2+3+4→ 3,5,7 (1+2,2+3,3+4)
- 元々n-1個の数字が与えられているので、結果がそうなるような元の式の数を求めなさい。無数にある場合は-1を出力しなさい。ただし、元の式は全て正の数から成っている。
- 1<=n<=50 , |出てくる値| <= 10^9 (これは負の数の場合もありうる)
感想
- 普通に難しいと思う。かなり悩んだ。ていうかDiv1/Div2正答率低すぎだし、解けたのがびっくりなくらい。
解法
反転↓
- とりあえず初項を決めたら一意に定まるから決め打ちしてやればいいんだけど、それだと計算量が大きすぎる。
- 初項はどっかの値からいくらか連続した範囲[lb,ub]にある。
- そのlbを求めるために、まず初項を1と仮定して、計算を進めていくと途中で0以下が出てくるので、そうなったら初項を途中結果がギリギリ1になるまで上げる。というのを繰り返すと、初項の下界がO(n)で分かる。
- 次にubを求める。これも同様で、初項をめちゃくちゃ大きい数(10^9*50よりもっと大きくないとやばい)と仮定して、計算を進めていくと同様に0以下が出てくるので、途中結果がギリギリ1になるまで下げる。とやるとまあ上界もO(n)で求まる。
- あとはub-lbを計算するんだけど、これがINT_MAX超えてたら無限にあるとして-1、負の数だったら0を返してやると良い。
Medium 550
- 問題文間違ってるかもしれないのでごめんなさい書けません。
- 最初条件の(少なくとも1つ満たす)という条件を(全て満たす)と勘違いしていたのでヌルゲーと思ったらサンプル合わなくて悲しみに包まれていました。
- 終了５分くらいにパッと思いついた解法では累積和を使えそうだったのですが実装明らかに間に合うわけない。Ｅａｓｙに時間を掛けてしまったナァ。
あとがき
そういや新入生がきました
