AtCoder Regular Contest 172 D,E問題メモ

AtCoder Regular Contest 172

D - Distance Ranking

• $N$ 次元空間上に、$N$ 個の点を配置する
• 点対は $\dfrac{N(N-1)}{2}$ 個あるが、これらが特定の順で与えられる
• 各点対のユークリッド距離が、与えられた順に狭義単調増加となるように、$N$ 個の点の配置の一例を決定せよ
• ただし各次元の座標は $0$ 以上 $10^8$ 以下の整数でなければならない
• $2 \le N \le 20$

点 $P_i$ の座標を $(x^i_1,x^i_2,...,x^i_N)$ として、$d(P_i,P_j)=(x^i_1-x^j_1)^2+(x^i_2-x^j_2)^2+...$ とする。
$d$ はユークリッド距離の2乗だが、ルートしても大小関係は変わらないので、距離の比較はこれでおこなってもよい。

一番近いのをとりあえず距離1とかにして考え始めたくなるが、、、

「$(1,2)$ は1番近く、$(2,3)$ は2番目に近いが、$(1,3)$ は200番目」みたいな入力もあり得る。
あまり近づけすぎると、$(1,3)$ の間に、他の197個の距離を収められなくなってしまう。

そもそも、$N$ 個の点に対して $N$ 次元あるというのが結構潤沢である。
$n$ 次元超立方体のような形でも $2^n$ 個の点が収められるので、次元が余る。

では、$i$ 番目の点は $i$ 次元目だけ正で、他は0なところから微調整するとどうだろうか？

P1 (100   0   0   0)
P2 (  0 100   0   0)
P3 (  0   0 100   0)
P4 (  0   0   0 100)

この時点では、どの点も同じ距離である。
ここで、$P_1$ と $P_2$ を近づけたければ、$x^1_2$ だけ、ちょっと増やしてやればよさそう。

P1 (100   1   0   0)
P2 (  0 100   0   0)
P3 (  0   0 100   0)
P4 (  0   0   0 100)

このとき、当然、$P_1$ と他の点の距離も近づいたり離れたりするが、最初の「100」の値を大きめにしておけば、

• $d(P_1,P_2)$ は、差分で考えると2次元目のみ $100^2$ → $99^2$ と、でかい値の2乗が減ることで大きく減少する
• $d(P_1,P_3)$ などは、差分で考えると2次元目のみ $0^2$ → $1^2$ と、小さい値の2乗が増える程度である
  • 仮に、他の部分の微調整の結果、$P_3$ の2次元目が0で無かったとしても、小さい値の2乗が増減する程度

このように、でかい値の2乗が減ることの価値が大きく、他の増減は相対的に無視出来る。

対角線上の値を最大の $10^8$ にし、頂点対それぞれに、近づける距離を微妙に変えてやる。
近い点対ほど、大きく近づけるようにすると、

P1 (100   6   1   4)   (1,2)→(2,3)→(1,4)→(2,4)→(3,4)→(1,3)
P2 (  0 100   5   3)
P3 (  0   0 100   2)
P4 (  0   0   0 100)

これが条件を満たす。

Python3

E - Last 9 Digits

• 正整数 $X$ が与えられる
• $n^n \equiv X \mod{10^9}$ となる正整数 $n$ があるか判定し、あるなら最小のものを求めよ
• 1つの入力に $Q$ 個のテストケースが与えられる
• $1 \le Q \le 10000$
• $X$ は2の倍数でも5の倍数でもない

$X$ は2の倍数でも5の倍数でもないという制約がだいぶ強く、$n$ も $X$ も下1桁が1,3,7,9に限られる。

$X$ の下 $k$ 桁を $X_k$ のように表すとして、

X=12345
→ X1=5,  X2=45,  X3=345, ...

それぞれについて、ひとまず下1桁が累乗でどう変わるかを見ていくと、

n1 = 1 のとき、1→1→1→1→1→...
n1 = 3 のとき、3→9→7→1→3→...
n1 = 7 のとき、7→9→3→1→7→...
n1 = 9 のとき、9→1→9→1→9→...

どれも、多くとも4回収期で1にもどる。$n$ は奇数なので、このうち2、4番目の数を下1桁目にすることはできない。

n1 = 1 のとき、1→x→1→x→1→...
n1 = 3 のとき、3→x→7→x→3→...
n1 = 7 のとき、7→x→3→x→7→...
n1 = 9 のとき、9→x→9→x→9→...

結局、$X_1=1$ なら、1が遷移中に出てくるのは $n_1=1$ しかない、というように、$n$ の選択肢はさらに限られることになる。

X1 = 1 のとき、n1 = 1
X1 = 3 のとき、(n1 = 3 かつ n ≡ 1 mod 4)  or  (n1 = 7 かつ n ≡ 3 mod 4)
X1 = 7 のとき、(n1 = 7 かつ n ≡ 1 mod 4)  or  (n1 = 3 かつ n ≡ 3 mod 4)
X1 = 9 のとき、n1 = 9

上記の通り、$n_1=1$ の場合にしか $X_1=1$ とならない。
逆に $n_1=1$ なら常に $X_1=1$ となる。

$n_1=9$ の場合にしか $X_1=9$ とならない。
逆に $n_1=9$ なら（指数が奇数なので）常に $X_1=9$ となる。

よって、下2桁目より上位には何を付け足しても、$n^n$ と $X$ の下1桁の合致が崩れることはない。

100が4の倍数なので、mod4 の制約を満たすかどうかは $n$ の下2桁を見るだけで判断することができる。

X1 = 3 のとき、n2 = 13,33,53,73,93, 07,27,47,67,87 のどれか
X1 = 7 のとき、n2 = 03,23,43,63,83, 17,37,57,77,97 のどれか

こうなる。候補の中から、$n_2^{n_2} \equiv X \mod{100}$ となるかどうかを調べ、合致するもののみ残す。

ここまできたら、下3桁目より上位は何を付け足しても、$n^{n}$ と $X$ の下2桁の合致が崩れることはない。

どちらの場合も、ここから残りの桁 $d=(2),3,4,...,9$ 桁目に置く数字を順番に試していきたい。
（$X_1=1,9$ と $X_1=3,7$ の上記の考察では確定する桁数が異なるが、説明が冗長になるので、$X_1=3,7$ の場合を例に出し、下2桁は合致済みとする。下1桁のみ合致済みの場合でも同様の議論は成り立つ）

• 方法案
  • 一致済みの $n_2$ に対して、$d=3,4,...,9$ について、$n_d^{n_d} \equiv X \mod{10^d}$ を確認し、合致したもののみ残して次の桁を試す
  • 最終的に $n_9$ まで残った数（あれば）の中で、最も小さいものが答え

下3桁目を置いたとき、「$n_3^{n_3} \equiv X \mod{10^3}$ なら、 その後、$n_3$ の上位に何を付け足しても、$n^n$ と $X$ の下3桁は一致する」ことが示せれば嬉しい。 （これを4,5,6,…,桁目に拡張していけば、下から順に決めていくことができることが証明できる）

4桁目以降に置く数（$n$ を1000で切り捨て除算した数）を $t$ として $n=n_3+1000t$ とすると、二項定理により

$$\begin{eqnarray} (n_3+1000t)^{n_3+1000t} &=& {}_{n_3+1000t}C_{0} \times n_3^0 \times (1000t)^{n_3+1000t} \\ && + {}_{n_3+1000t}C_{1} \times n_3^1 \times (1000t)^{n_3+1000t-1} \\ && + ... \\ && + {}_{n_3+1000t}C_{n_3+1000t} \times n_3^{n_3+1000t} \times (1000t)^0 \\ &\equiv& n_3^{n_3+1000t} \\ &\equiv& n_3^{n_3} \times n_3^{1000t} \mod{1000} \end{eqnarray}$$

$1000t$ の指数が1以上のものは $\mod{1000}$ で消えるので、結局残るのは二項定理で分解した中の最後の項のみとなる。

ここで、オイラーの定理が使える。

• $a$ と $m$ が互いに素なとき、$\varphi(m)$ を「$1～m-1$ のうち $m$ と互いに素なものの個数」として、$a^{\varphi(m)} \equiv 1 \mod{m}$

1000 を因数 $8 \cdot 125$ に分解する。$n_3$ は偶数でも、末尾が5でも無いので、どちらとも互いに素である。

• $\varphi(8)=8 \times \frac{1}{2}=4$ より、$n_3^4 \equiv n_3^{1000} \equiv 1 \mod{8}$
• $\varphi(125)=125 \times \frac{4}{5}=100$ より、$n_3^{100} \equiv n_3^{1000} \equiv 1 \mod{125}$

よって、$n_3^{1000} \equiv 1 \mod{1000}$ であることが言える。

最終的に、$(n_3+1000t)^{n_3+1000t} \equiv n_3^{n_3} \mod{1000}$ となり、$n^n$ の下3桁と $n_3^{n_3}$ の下3桁は、4桁目以降の数 $t$ に関わらず一致することが分かる。
4,5,6,… 桁目に対しても同様の議論が成り立つ。

ちゃんとした証明は公式Editorial参照。

Python3