ARC118 参加記録 - Xenous の精進記録

ACの2完0ペナ 79分でした

A - Tax Included Price

最初からなかなかハードな問題だと思いました。

式から $O(1)$ で求められそうな感じはしますが、わからなかったので実験しました。具体的には、実際に消費税 $t$ を固定して $1$ 円から順番に求めていき、スキップされたもの(税込み価格としては現れない正の整数の金額)を取りだして並べていきました。

そのあと、スキップされた値の差分を隣どうしとって行きます。そうすることで差分の周期性が見えてきます。実験から、以下のような動きをしていることがわかりました。

$t$ が 100 の約数であるときは、差分の周期は 1 で全て値は同じになる。
そうでないときは、差分のループは長さ $t$ の数列で表せる。

これらから、 $N$ をループの長さ $t$ で割ったときの商と余りを駆使して、 $N$ 番目の数字を $O(1)$ で計算することができます。

B - Village of M People

まず $a$ を数列 $A$ の各要素として、 $\frac{Ma}{N}$ を求めます。このとき、小数ではなく整数で扱いたいので、商を $B$ として扱い、余りの列を別で持っておきます。

数列 $B$ はこの時点では $\sum{B} = M$ を満たしていませんが、足りない部分を割り振ることによって数列 $B$ を完成させます。先ほど求めた余りの列の大きい順から割り振れば良くなります。余りは切り捨てたときの整数との距離のような値と解釈でき、余りが小さければ今 $B$ として決めた値に近く、そうでないときは +1 した値の方が近くなります。