目次
AtCoder Regular Contest 200 (Div. 2) A,B,C,D,E問題メモ
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$ とする。
$N=1$ のとき
$A_i,B_i$ は正より、$C,D$ も両方正か両方負にしかできないので不可能。
$N=2$ のとき
$(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$ より、値の範囲も大丈夫。
$N \ge 3$ のとき
全ての $(A'_i,B'_i)$ が一致していたら不可能。
それ以外の場合、$(A'_i,B'_i)$ が異なる2つを持ってきて、$N=2$ の時に帰着し、他は $0$ にすればよい。
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 が使える。
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)$ で解ける。
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参照。
まとめると、(上から順に判定して当てはまれば終了)
- $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})$
- それ以外は不可能
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$ 以下でなければならない。
$\max(\operatorname{popcount}(A_i)) \le 1$
全ての $A_i$ が、$0$ または1つだけbitが立っている数列は条件を満たす。
$i=2~N$ につき、$A_i$ の選択肢が $M+1$ 通り、独立にあるので、$(M+1)^{N-1}$ 通り。
$\max(\operatorname{popcount}(A_i)) = 2$
愚直を書いて観察すると、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)$ 倍が、②③の場合の答えとなる。