AtCoder Regular Contest 200 (Div. 2) A,B,C,D,E問題メモ

AtCoder Regular Contest 200 (Div. 2)

祝☆200回

A - Dot Product

• 長さ $N$ の正整数列 $A=(A_1,A_2,\ldots,A_N),B=(B_1,B_2,\ldots,B_N)$ が与えられます。
• 以下の条件を全て満たす整数列 $X=(X_1,X_2,\ldots,X_N)$ が存在するか判定し、存在するなら一つ求めてください。
  • $-10^8\le X_i\le 10^8$ $(1\le i\le N)$
  • $\displaystyle \sum_{i=1}^N A_iX_i \gt 0$
  • $\displaystyle \sum_{i=1}^N B_iX_i \lt 0$

• $T$ 個のテストケースが与えられるので、それぞれについて答えを求めてください。

• $1\le T\le 2\times 10^5$
• $1\le N\le 2\times 10^5$
• $1\le A_i,B_i\le 10^5$
• 全てのテストケースにおける $N$ の総和は $2\times 10^5$ 以下
• 入力される値は全て整数

$\displaystyle C=\sum_{i=1}^N A_iX_i, \ \ D=\sum_{i=1}^N B_iX_i$ とする。

$A_i,B_i$ は正より、$C,D$ も両方正か両方負にしかできないので不可能。

$(A_i,B_i)$ を $gcd(A_i,B_i)$ で割って、互いに素にしたものを $(A'_i,B'_i)$ とする。

$(A'_1,B'_1)=(A'_2,B'_2)$ の時は不可能である。
$(C,D)$ が取り得る領域は $y=\frac{B_1}{A_1}x$ 上の直線上にしか存在せず、この直線は第1と第3象限しか通らない。

それ以外の時、以下のようにできる。

A    20   25
B    31   41

まず、Aを揃える。

 X   25   20
AX  500  500
BX  775  840

この例では BX1 < BX2 なので、X=(25,-20) とすれば、C=0, D<0 にできる。

また、Bを揃える。

 X   41   31
AX  840  775
BX 1271 1271

この例では AX1 > AX2 なので、X=(41,-31) とすれば、C>0, D=0 にできる。

そしてこれは線形的に合成できるので、
X=(25+41, -20-31) とすれば、C>0,D<0 にできる。

 X   66   -51
AX 1320 -1275  →  C =  45 > 0
BX 2046 -2091  →  D = -45 < 0

大小関係が逆の場合は符号が逆になる。

$-2 \times 10^5 \le -(A_{\max}+B_{\max}) \le X_i \le (A_{\max}+B_{\max}) \le 2 \times 10^5$ より、値の範囲も大丈夫。

全ての $(A'_i,B'_i)$ が一致していたら不可能。

それ以外の場合、$(A'_i,B'_i)$ が異なる2つを持ってきて、$N=2$ の時に帰着し、他は $0$ にすればよい。

Python3

B - LCM

• 正整数 $A_1,A_2,A_3$ が与えられます。
• 以下の条件を全て満たす正整数の組 $(X_1,X_2)$ が存在するか判定し、存在する場合は一組求めてください。
  • $X_1$ は十進法で $A_1$ 桁の整数である。
  • $X_2$ は十進法で $A_2$ 桁の整数である。
  • $X_1$ と $X_2$ の最小公倍数は十進法で $A_3$ 桁の整数である。

• $T$ 個のテストケースが与えられるので、それぞれについて答えを求めてください。

• $1\le T\le 17^3$
• $1\le A_1,A_2,A_3\le 17$
• 入力される値は全て整数

互いに素な $X_1,X_2$ なら、最小公倍数は $X_1 \times X_2$ になるので桁数がわかりやすい。
そういう方向に持ってけないか考える。

$a$ 桁× $b$ 桁は、$a+b-1$ または $a+b$ 桁となる。

a=4, b=5
最小: 1000 * 10000 =  10000000  →8桁
最大: 9999 * 99999 = 999890001  →9桁

最小公倍数は2数の積より大きくはならないので、$A_1 + A_2 \lt A_3$ なら不可能。
また、最小公倍数は元の数より小さくならないので、$A_1 \gt A_3$ や $A_2 \gt A_3$ の場合も不可能。

それ以外の場合、互いに素であることが保証される素数を使って、構築できる。
直接的に $A_1+A_2=A_3$ または $A_1+A_2=A_3-1$ という関係性に無い場合は、末尾に0を追加して調整する。

xはa桁、yはb桁、x,yは互いに素、z=xy

LCM( x0000 , y0000 ) = z0000
     ~~~~~   ~~~~~     ~~~~~
     a+4桁   b+4桁     a+b+4 または (a+b-1)+4 桁

$A_1+A_2-1 \le A_3 \le A_1+A_2$ になるまで、$A_1,A_2,A_3$ から1ずつ引いていく。
この時引いた回数を $d$、引いた結果を $A'_1,A'_2,A'_3$ として、$X_1,X_2$ は以下のように作れる。

• $A'_3=A'_1+A'_2-1$ の時
  • $X'_1=A'_1$ 桁の最小の素数
  • $X'_2=A'_2$ 桁の2番目に小さい素数
• $A'_3=A'_1+A'_2$ の時
  • $X'_1=A'_1$ 桁の最大の素数
  • $X'_2=A'_2$ 桁の2番目に大きい素数
• $X_1=X'_1$ の末尾に0を $d$ 個追加したもの
• $X_2=X'_2$ の末尾に0を $d$ 個追加したもの

この方法で $X'_1 \times X'_2$ が $A'_3$ 桁となり、$X_1 \times X_2$ が $A_3$ 桁となる。
素数はわりと密に存在するので、各桁の最小や最大（$1000$ や $9999$ など）から多少ずれたとしても、積の桁数が変わるほどずれることはない。

「$k$ 桁の最小・最大の素数」を得るには、Pythonなら sympy.nextprime, prevprime が使える。

• Number Theory - SymPy 1.14.0 documentation

Python3

C - Movie Theater

• 正整数 $N$ と長さ $N$ の正整数列 $L=(L_1,L_2,\ldots,L_N),R=(R_1,R_2,\ldots,R_N)$ が与えられます。
  • ここで、 $L_1,L_2,\ldots,L_N,R_1,R_2,\ldots,R_N$ は全て互いに異なることが保証されます。
• ある映画館には $N$ 個の席が左右一列に並んでいます。左から $i$ 番目の席を席 $i$ と呼びます。
• この映画館に人 $1$ から人 $N$ までの $N$ 人の人が訪れます。あなたは各人に席を $1$ つずつ割り当てます。
• 人 $i$ に割り当てた席を $P_i$ とすると、人 $i$ は時刻 $L_i$ に席 $1,2,\ldots,P_i-1$ を横切って席 $P_i$ に座り、時刻 $R_i$ に席 $1,2,\ldots,P_i-1$ を横切って席から離れます。
• 人 $i$ の 不満度 を時刻 $L_i$ から時刻 $R_i$ までの間（ちょうど $L_i,R_i$ は含まない）に他の人に席 $P_i$ を横切られた回数とします。
• 人 $1$ から人 $N$ までの $N$ 人の不満度の総和が最小となる $(1,2,\ldots,N)$ の順列 $P$ のうち辞書順最小のものを求めてください。
• $T$ 個のテストケースが与えられるので、それぞれについて答えを求めてください。

• $1\le T\le 500$
• $1\le N\le 500$
• $1\le L_i \lt R_i\le 2\times N$
• $L_1,L_2,\ldots,L_N,R_1,R_2,\ldots,R_N$ は全て互いに異なる
• 全てのテストケースにおける $N$ の総和は $500$ 以下
• 入力される値は全て整数

答えが逆（シート $i$ に誰を座らせるか）という問題だったらトポロジカルソートで簡単に求まるのに、、、
「人 $i$ をどのシートに座らせるか」を辞書順最小にするのに意外と手こずった。

$[L_i,R_i]$ を数直線にプロットし、その関係性を3種類に場合分けする。

■交わらない

  |----1----|     |---2---|

この場合、お互いに不満度を与えることはない。
座らせるシートの左右位置関係はどちらでも良い。

■交差する
  |----1----|
     |----2----|

人1を左に座らせると、人2の入館時に1が不満を1覚える。
人2を左に座らせると、人1の退館時に2が不満を1覚える。
どちらにしろ不満が1増えるのは変わらないので、座らせる位置関係はどちらでもよい。

■包含する
  |-------1-------|
     |----2---|

人1を左に座らせると、人2の入館時と退館時に不満を2覚える。
人2を左に座らせると、不満は増えない。
よってこの場合は、人2を左に座らせないといけない。P2 < P1 となる。

一部の $P$ の値に大小関係の制約ができたが、包含関係のみに由来するのでこの制約は推移的である。
つまり、$P_i \lt P_j$ かつ $P_j \lt P_k$ となる $(i,j,k)$ に対し、$P_i \lt P_k$ が必ず成り立ち、矛盾することはない。

この制約、つまり「入退館時刻が包含関係にある2人は、短い方を左のシートに座らせる」というルールさえ守っていれば、不満度最小は達成できる。

$i=1$ から、「シートの範囲と、この範囲のシートに座らせる人の集合」を分割していくように貪欲に求めていける。

例えば $N=8$ で、

• $P_1 \gt P_i$ となるような $i$ : $\{3,5,8\}$
• $P_1 \lt P_i$、または $1$ との制約がない $i$ : $\{2,4,6,7\}$

に分けられる場合、人 $1$ はなるべく左に座らせたい（$P_1$ を小さくしたい）ので、 $3,5,8$ のみ左に座らせ、人 $1$ は4番目のシートに座ることになる。$P_1=4$ と決まる。

シートに誰を座らせるか（$P$ の逆順列）の順列を $Q$ とすると、このように部分的に決まる。

i   1 2 3   4   5 6 7 8
Q  {3,5,8}  1  {2,4,6,7}

$i$ と $Q$（ひいては $P_i$ と $i$）の対応が分割され、左と右で再帰的に同じような問題と見なせる。

たとえば左では、$\{3,5,8\}$ のうち最小の番号の人が $3$ なので、$P_3$ の値を最小にすることを考える。

• $\{5,8\}$ のうち、$P_3 \gt P_i$ となるような $i$ : $\{8\}$
• $\{5,8\}$ のうち、$P_3 \lt P_i$ または制約がない $i$ : $\{5\}$

だったとすると、以下のように決まる。

i   1   2   3   4   5 6 7 8
Q  {8}  3  {5}  1  {2,4,6,7}

このように、グループのうち番号が最小の人の座るシートを決めていくと、$O(N^2)$ で解ける。

Python3

D - |A + A|

• 正整数 $M,K$ が与えられます。
• 以下の条件を全て満たす正整数 $N$ と整数列 $A=(A_1,A_2,\ldots, A_N)$ が存在するか判定し、存在するなら一つ求めてください。
  • $1\le N\le M$
  • $0\le A_i \lt M$ $(1\le i\le N)$
  • $k\equiv A_i+A_j \pmod M$ を満たす添字の組 $(i,j)$ が存在するような整数 $0\le k \lt M$ がちょうど $K$ 個存在する。

• $T$ 個のテストケースが与えられるので、それぞれについて答えを求めてください。

• $1\le T\le 2\times 10^5$
• $1\le K\le M\le 2\times 10^5$
• 全てのテストケースにおける $M$ の総和は $2\times 10^5$ 以下
• 入力される値は全て整数

3つめの条件がちょっと分かりづらいが、要は100ますけいさんのように数列 $A$ を縦と横に書いて足し算(mod)して、 その表に表れる数字の種類数が $K$ 個になるように $A$ を決めよ、と言っている。

  | 3  1  4
--+---------
3 | 6  4  7     2,4,5,6,7,8 の6種類
1 | 4  2  5
4 | 7  5  8

言わずもがな表の値は対角線を挟んで対称なので、右上の部分のみ考える。

いろいろ実験してみる。シンプルに、$A=(0,1,2,...)$ としてみると、

  | 0  1  2  3     A=(0,1,...,x) とすると、
--+------------    0～2x の 2x+1 個の値が現れる。
0 | 0  1  2  3
1 |    2  3  4
2 |       4  5
3 |          6

$A=(0,1,2,...,\frac{K-1}{2})$ とすることで、$K$ が奇数の場合は必ず構築できるとわかる。

では、$K$ が偶数の場合は？

何となく、$\mod{M}$ を利用することを考えると訳わかんなくなりそうなので、まずはなるべく和が $M$ 未満に収まるようなものを考えたい。
上記の場合は $0～2x$ の値が使われたが、では、$A=(0,2,3,...,x)$ とすると $1$ だけを使わないようにできるのでは？

     | 0  2  3  4  5
   --+---------------
   0 | 0  2  3  4  5
   2 |    4  5  6  7
   3 |       6  7  8
   4 |          8  9
   5 |            10
        ┘ ┘ ┘ ┘ ┘
種類数  1  3  6  8  10

$K \ge 6$ の偶数なら狙い通りとなり、$A=(0,2,3,...,\frac{K}{2})$ でできそう。
ただし、$K=M$ の時、たとえば $K=M=8$ の時、 $A=(0,2,3,4)$ とすると $4+4=8$ がmodで $0$ になってしまい、$7$ 種類になってしまう。

しかしこの場合は、そもそも $0～M-1$ を全て出現させれば良いので、適当に密に作ればよい。
$A=(0,1,...,M-1)$ などがあてはまる。

これを最初に判定して除けば、$K \ge 6$ の偶数ならできることが分かった。

残るは $K=2,4$ の時のみ。
愚直ケースを書いて調べると、$M$ が $K$ の倍数の時は、 $(0,\frac{M}{K},2\frac{M}{K},...,(K-1)\frac{M}{K})$ を和に全て出現させることで達成できることがわかる。

M=12  K=4

  | 0  3  6  9     K=M の場合の応用バージョン
--+------------
0 | 0  3  6  9
3 |    6  9  0
6 |       0  3
9 |          6

$K=2,4$ で $M$ が $K$ の倍数でない時にできない証明がなかなか難しいが、まぁ、愚直でここまで綺麗な法則が現れたら大丈夫やろと信じれば通る。

証明は公式Editorial参照。

• 解説 - AtCoder Regular Contest 200 (Div. 2)

まとめると、（上から順に判定して当てはまれば終了）

• $M$ が $K$ の倍数なら、$A=(0,\frac{M}{K},2\frac{M}{K},...,(K-1)\frac{M}{K})$
• $K$ が奇数なら、$A=(0,1,2,...,\frac{K-1}{2})$
• $K$ が6以上の偶数なら、$A=(0,2,3,...,\frac{K}{2})$
• それ以外は不可能

Python3

E - popcount <= 2

• 正整数 $N,M$ が与えられます。
• 長さ $N$ の非負整数列 $A=(A_1,A_2,\ldots,A_N)$ であって、以下の条件を全て満たすものの個数を $998244353$ で割ったあまりを求めてください。
  • $0\le A_i \lt 2^M$ $(1\le i\le N)$
  • $\operatorname{popcount}(A_i\oplus A_j) \le 2$ $(1\le i \lt j\le N)$

• $T$ 個のテストケースが与えられるので、それぞれについて答えを求めてください。

• $1\le T\le 2\times 10^5$
• $2\le N,M \lt 998244353$
• 入力される値は全て整数

丁寧な場合分け。

まず、条件を満たす数列 $A$ の各要素に対し $1$ 以上 $2^M$ 未満の同じ値をXORしたものも、 また別の条件を満たす数列となる。
よって $A_1=0$ の場合を考えることとし、最終的な答えはそれを $2^M$ 倍すればよい。

$A_1=0$ の時、当然、他の全ての要素のpopcountは $2$ 以下でなければならない。

全ての $A_i$ が、$0$ または1つだけbitが立っている数列は条件を満たす。

$i=2～N$ につき、$A_i$ の選択肢が $M+1$ 通り、独立にあるので、$(M+1)^{N-1}$ 通り。

愚直を書いて観察すると、3パターンに分かれて考えられそう。

• ①ある共通のbit1つと、他に高々1つのbitが立っている場合
• ②$\{00,01,10,11\}$ の4つからなる場合
• ③$\{000,011,101,110\}$ の4つからなる場合

こんなやつ

00000000
00001010
00101000
10001000
00001000
00011000
    ^ 共通のbit

共通のbit位置が $M$ 通りある。それを固定したとき、$A_2～A_{N}$ に置く数は以下の $M+1$ 通りが選択肢としてあり得る。

• a) 他にどこか立っている $M-1$ 通り
• b) 共通のbitのみが立っている
• c) $0$

このうち、「b) または c) のみからなる」ものは、$\max(\operatorname{popcount}(A_i)) \le 1$ で既に数えられている。

また、「a) または c) のみからなり、a) で共通のbitの他に立てたbitが全てで一致」するものは、 ①の過程で2回ずつ重複して数えられる。

よって、共通bitを固定すると $(M+1)^{N-1}-2^{N-1}-\frac{(2^{N-1}-1)(M-1)}{2}$ の組合せがある。
この $M$ 倍が①の場合の答えとなる。

補足すると、「$\{00,01,10,11\}$ の4つからなる」とは、$M$ 個中どこか2箇所のbitを選んで、 それが $(0,0),(0,1),(1,0),(1,1)$ のどれか、他は $0$ である状態を示す。

どのbitを選ぶかは、②は ${}_M C_2$ 通り、③は ${}_M C_3$ 通りある。
これを固定した場合を考えて、あとで倍加する。

いずれも、4つ全てが出現する場合以外は既に数えられている。

$0$ は $A_1$ で必ず出現することに注意して包除原理を適用すると、 $A_2$ 以降の決め方は $4^{N-1} - 3 \times 3^{N-1} + 3 \times 2^{N-1} - 1$ 通りずつある。

この $({}_M C_2 + {}_M C_3)$ 倍が、②③の場合の答えとなる。

Python3