KCSは復活するのか？

こんにちは、かがみずです。去年まで ICT 委員会に所属していました。いわゆる老害です?
この記事は ICT Advent Calendar 2016 の 23 日目の記事として書かれ~~る予定でしたが 3 日遅れで書かれ~~ました。

コレ宣伝なんですけど, 去った 12 月 21 日に 21 歳になりました！ 1 と 2 に溢れた誕生日でした。
(amazon の wishlist を公開しているのでよろしくお願いします!!!毎年恒例のダイレクトマーケティングです?)

今日は、かつて動いていた*1 KCS (Kagamiz Contest System) のこれまでとこれからのお話です。

*1:噂によると今も動いているらしい

JOI Open Contest 2015 - Sterilizing Spray ふたたび

JOI データ構造

この問題、さすがに実装も定数倍も重い解法を書いてしまっていたので、別のアプローチで解き直してみました。

問題概要 :
数列 $a_1,\ a_2,\ \cdots,\ a_n$ が与えられる。次のクエリに $k$ 個答えよ。

数 $b_j$ は非負整数$x_1,\ x_2,\ \cdots,\ x_n$ を用いて $\displaystyle\sum_{i=1}^{n} x_i a_i$ と表せるか？