Help us understand the problem. What is going on with this article?

ABC156 解説

ABC156の解説です。
36:51全完で、12位を取って最高記録を更新しました。
では、解説に入ります。

A問題

問題文解読ゲーです。
$N$ が $10$ 以上の場合とそうでない場合に分けるか、$max$ で適当に処理するかしましょう。
それでもこれはB問題相当くらいあると思うのですが…

B問題

結論から言えば、${\rm ceil}(\log_K N)$ を求めればいいのですが、$N$ を $K$ で順々に割っていくのが一番楽で早いです。

C問題

集会をする位置を全探索します。
$X_i$ の制約を考えると、集会は $1$ 以上 $100$ 以下のどこかで開かれるので、これを全部試せばよいです。

D問題

$1$ 以上 $n$ 以下の、 $a,b$ 以外のすべての整数 $i$ について ${}_n\mathrm{C} _i$ を計算して、その総和を求めます。
$N$ の制約は大きいので、このままだと間に合いません。

\sum_{i=0}^{N} {}_N \mathrm{C} _i=2^N

が成り立つことはあまりにも有名で、これは前提知識となります。
結局、$2^N$ から ${}_N\mathrm{C} _a$ と ${}_N\mathrm{C} _b$ と $1$ (0本の場合)を引いたものが答えです。

E問題

D問題に引き続き、組み合わせの問題です。
$n$ と $k$ の条件を満たすような人数の組み合わせは、どのような性質があるでしょうか。
結局のところ、条件を満たすのは、$0$ 人の部屋が $k$ 部屋以下であることと同値です。
$k\geq 2$ の条件がないと実はこれは成り立ちませんが、簡単に証明できるので省略します。
$0$ 人の部屋の個数を $i$ 個と決めたとすると、この時の組み合わせの個数は、人の入る部屋への人の入り方と、人の入る部屋の集合の選び方を考えて、

{}_{i} \mathrm{H} _{N-i}\cdot{}_{n} \mathrm{C}_i={}_{n-1} \mathrm{C}_i\cdot{}_{n} \mathrm{C}_i

となるので、これを $i$ が $min(n,k+1)$ 未満になるまで計算して加算すればよいです。

F問題

それぞれのクエリで構成される数列は、$x_i$ を初項として、差が $d$ の各要素の繰り返しによって周期的に変化する数列です。
それぞれのクエリについて、$d$ の各要素と$x_j$ は、$\bmod{m_j}$ で考えて問題ありません。
$(a_j \bmod{m_i})<(a_{j+1} \bmod{m_i})$ となる $j$ の個数は、$(a_j \bmod{m_i})\geq(a_{j+1} \bmod{m_i})$ とならない $j$ の個数を $n_i-1$ から引いたものに他なりません。
これを求めることで答えを引き算で求めることを考えます。
まず、$(a_j \bmod{m_i})=(a_{j+1} \bmod{m_i})$ となる場合は、$d$ の各要素が加算されるときにそれが $0$ かどうか考えればいいので、周期性を利用すれば簡単に求められます。
$(a_j \bmod{m_i})>(a_{j+1} \bmod{m_i})$ となる時には、modの世界で繰り上がりが起きている、と解釈して、最初から最後までで繰り上がりが何回起こるか計算します。$d$ の各要素について先にmodをとっておき、ここでも周期性を利用して初項からmodの値がいくら増えるかわかれば、繰り上がりの回数も計算できます。
こうして、$(a_j \bmod{m_i})\geq(a_{j+1} \bmod{m_i})$ となる $j$ の個数が求められたので、答えが求まりました。
計算量は各回のクエリで $O(k)$ で、全体で $O(kq)$ です。

おわりに

今回は、前回とは違って結構な早解きセットでした。
DとEで数学力が試されたのもありましたが、簡単めな回だったと思います。
Fは、とてもABCらしい問題だと思いました。
ではまた。

Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
Comments
No comments
Sign up for free and join this conversation.
If you already have a Qiita account
Why do not you register as a user and use Qiita more conveniently?
You need to log in to use this function. Qiita can be used more conveniently after logging in.
You seem to be reading articles frequently this month. Qiita can be used more conveniently after logging in.
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
ユーザーは見つかりませんでした