Qiita Teams that are logged in
You are not logged in to any team

Log in to Qiita Team
Community
OrganizationAdvent CalendarQiitadon (β)
Service
Qiita JobsQiita ZineQiita Blog
2
Help us understand the problem. What is going on with this article?
More than 1 year has passed since last update.

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らしい問題だと思いました。
ではまた。

2
Help us understand the problem. What is going on with this article?
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
ageprocpp
kaageです。競プロの記事を書きます。

Comments

No comments
Sign up for free and join this conversation.
Sign Up
If you already have a Qiita account Login
2
Help us understand the problem. What is going on with this article?