差分

このページの2つのバージョン間の差分を表示します。

--- programming_algorithm:contest_history:atcoder:2019:0316_agc031 [2019/03/17] – [解法] ikatakos
+++ programming_algorithm:contest_history:atcoder:2019:0316_agc031 [2019/03/19] (現在) – [解法] ikatakos
@@ 行 1: / 行 1: @@
-======AtCoder Grand Contest 031 A,B,C 問題メモ======
+======AtCoder Grand Contest 031 A,B,C,D 問題メモ======
 [[https://beta.atcoder.jp/contests/agc031|AtCoder Grand Contest 031]]
@@ 行 113: / 行 113: @@
 ==== 解法 ====
-$A$ と $B$ で異なっているbitで2分割していく。イメージとしては、解説YouTubeの $N$ 次元超立方体の切断を考えるとわかりやすい。
+区間を、最初と最後の数字で異なっているbitで2分割していく。イメージとしては、解説YouTubeの $N$ 次元超立方体の切断を考えるとわかりやすい。
-まず、出来るか出来ないかの問題として、2進数で立っている'1'の数を考えると、「...→奇数→偶数→奇数→偶数→...」と交互になっていく。
+まず、出来るか出来ないかの問題として、パリティ（2進数で立っている'1'の数の偶奇）を考えると、「...→奇数→偶数→奇数→偶数→...」と交互になっていく。
-順列は偶数項なので、$A$ から $B$ の立っている'1'の偶奇は異なっていないといけない。同じなら'NO'。
+順列は偶数項なので、$A$ と $B$ のパリティは異なっていないといけない。同じなら'NO'。
 逆にこれを満たすと行けるのか、この時点ではよく分からないが、出来るとしてとりあえず考えを進める。
@@ 行 129: / 行 129: @@
                                 011
-と3を見ると、2ビット目が異なっている。（複数ある場合、異なっているビットをどれか1つ選ぶ）
+$A,B=1,3$を見ると、2ビット目が異なっている。（複数ある場合、異なっているビットをどれか1つ選ぶ）
 $0～2^N-1$ の中で2ビット目が'0'と'1'の数字の数は等しい。
@@ 行 138: / 行 138: @@
   ?0?  ?0?  ?0? | ?1?  ?1?  ?1?  011
-前半の最後の数字（$P_3$）を適当に1つ決める。これもまた $A$ から偶数項なので、'1'の偶奇は異なっている必要がある。
+前半の最後の数字（$P_3$）を適当に1つ決める。これもまた $A$ から偶数項なので、パリティは異なっている必要がある。
-これまでに分割に用いたビット（2ビット目）以外から適当に1つビット位置を選び、$A$ をそのビットだけ変化させた数とすると、これまでに確定した数字とは被らないし、'1'の偶奇が異なっているという条件も満たす。ここでは1ビット目を選んだとする。
+これまでに分割に用いたビット（2ビット目）以外から適当に1つビット位置を選び、$P_3$ を $A$ についてそのビットだけ変化させた数とすると、これまでに確定した数字とは被らないし、'1'の偶奇が異なっているという条件も満たす。ここでは1ビット目を選んだとする。
     ?    ?    0 |   2    ?    ?    3
@@ 行 146: / 行 146: @@
     ^ 1bit目を変化 ^     ^ P3を決めるとP4も自動的に決まる
-すると、左半分を「$A=1,B=0$ とし、2ビット目はいじらない」問題として処理できる。
+すると、左半分を「$A=1,B=0$、ただし2ビット目はいじらない」問題として処理できる。
-と0では1ビット目が変化しているので（さっきそう変化させたからだが）、真ん中で1ビット目を変化させることにする。
+最初の問題と同様に異なるビットを探すと、1と0では1ビット目が変化しているので（さっきそう変化させたので当然だが）、真ん中で1ビット目を変化させることにする。
+前半の前半は「?01」、前半の後半は「?00」という数字を網羅することで、前前半と前後半でかぶりはなくなる。
    P0   P1    P2   P3    P4   P5   P6   P7
@@ 行 154: / 行 155: @@
   ?01 | ?00  000 | 010  ?1?  ?1?  011
-すると、前半の前半の最後の項（$P_1$）は、まだ分割に用いていない3ビット目を変化させ、5とするとよいことがわかる。
+前前半の最後の項（$P_1$）は、まだ分割に用いていない3ビット目を変化させ、5とするとよいことがわかる。
     5 |   4    0 |   2    ?    ?    3
   101 | 100  000 | 010  ?1?  ?1?  011
-さらに分割を進めて「$A=1,B=5$ とし、1,2ビット目はいじらない」問題となるが、これは既に隣り合っているのでここで終了。
+さらに分割を進めて「$A=1,B=5$、ただし1,2ビット目はいじらない」問題となるが、これは既に隣り合っているのでここで終了。右の「$A=4,B=0$」も同様に終了。
-右半分も同様に、「$A=2,B=3$ とし、2ビット目はいじらない」として、分割していくと、構築できる。
+右半分も同様に、「$A=2,B=3$、ただし2ビット目はいじらない」として分割していくと、構築できる。
     5 |   4    0 |   2    6 |   7    3
@@ 行 167: / 行 168: @@
 左半分と右半分で次に分割すべきビットは同じとは限らないため、「既に分割に用いたビット」の管理に注意。
-分割済ビット位置をリストで持ち、再帰関数の中でappendしてから子の探索に進み、終了後にpopするなどで実装できる。
+分割済ビット位置をリストで持ち、再帰関数の中で末尾にappendしてから子の探索に進み、終了後にpopするなどで実装できる。
 <sxh python>
@@ 行 206: / 行 207: @@
 </sxh>
+===== D - A Sequence of Permutations =====
+[[https://beta.atcoder.jp/contests/agc031/tasks/agc031_d|D - A Sequence of Permutations]]
+==== 問題 ====
+  * 長さ $N$ の順列（$1～N$ を並べ替えた配列）$p,q$ が与えられる
+  * 順列 $p,q$ に対して、$f(p,q)$ を以下のように定義する
+    * $p_i$ 番目が $q_i$ であるような順列
+  * さらに、順列の列 $a_i$ を、以下のように定義する
+    * $a_1=p$
+    * $a_2=q$
+    * $a_{n+2}=f(a_n,a_{n+1})$
+  * 整数 $K$ に対し、$a_K$ を求めよ
+  * $1 \le N \le 10^5$
+  * $1 \le K \le 10^9$
+==== 例 ====
+  a1 = p :  4 5 1 2 3  ┌  a1における'1'は3番目→a2の3番目は'1'→a3の'1'番目は'1'
+  a2 = q :  3 2 1 5 4  ├  a1における'2'は4番目→a2の4番目は'5'→a3の'2'番目は'5'
+  a3     :  1 5 4 3 2  ┼  a1における'3'は5番目→a2の5番目は'4'→a3の'3'番目は'4'
+  a4     :  4 5 1 2 3  ├  ...
+  a5     :  4 3 2 1 5
+==== 解法 ====
+写像とか全単射とかその辺を利用する。
+===考えたこと===
+まず、$K$ が大きすぎるので、おそらくまとめて計算できるような周期があると予測する。
+実際、サンプルでシミュレートしてみると3だったり72だったり、3の倍数で周期が発生している。
+また、合成した結果を合成するので、その合成過程は $p$ と $q$ のみで表現できそうだが、試しに $f(p,q)$ を単に $pq$ と表現してみても
+  a1 = p
+  a2 = q
+  a3 = pq
+  a4 = qpq
+  a5 = pqqpq
+  a6 = qpqpqqpq
+  ...
+となり、（だから何？）で終わってしまい、法則の手がかりが見つからなかった。
+===解説の解法===
+ここでは、数学の集合論における合成を利用すると法則が見つかりやすかったようだ。
+まず、順列 $p$ を、「$i$ から $p_i$ への写像」と捉える。
+  i   1  2  3  4  5
+     ↓ ↓ ↓ ↓ ↓
+  p   4  5  1  2  3
+$pq$ を $p$ と $q$ の合成とする。つまり、$i$ 番目が $p_{q_i}$ であるような順列とする。
+処理の順番が直感と反していて、$pq$ は $q$ を施した後に $p$ を施すことに注意する。
+  i   1  2  3  4  5
+  q   3  2  1  5  4    pq[1] = p[q[1]] = p[3] = 1
+  p   4  5  1  2  3    pq[2] = p[q[2]] = p[2] = 5
+  ↓                   pq[3] = p[q[3]] = p[1] = 4 ...
+  pq  1  5  4  3  2
+  * [[wpjp>写像]]
+  * [[wpjp>写像の合成]]
+  * 合成は結合法則が成り立つ。つまり、$pqpq$ とあった場合、$p((qp)q)$ などと先に後ろから計算しても結果が変わらない
+  * 合成は単位元 $e$ が存在する。つまり、$pe=ep=p$ となるような順列 $e$ が存在する。この問題の場合、$e=[1,2,3,4,...]$ である
+また、$p$ に対し、$p^{-1}$ を逆写像とする。つまり、
+  i   1  2  3  4  5  |   p{-1}  1  2  3  4  5
+     ↓ ↓ ↓ ↓ ↓  |         ↑ ↑ ↑ ↑ ↑
+  p   4  5  1  2  3  |   i      4  5  1  2  3
+                            ↓(並べ替え)
+                         i      1  2  3  4  5
+                         p{-1}  3  4  5  1  2
+となるような順列とする。以下のような性質がある。
+  * $p$ が全単射$\iff p^{-1}$ が存在
+  * $p^{-1}$ の逆写像は $p$
+  * $pq$ の逆写像は $q^{-1}p^{-1}$
+  * $pp^{-1}=e$
+$f(p,q)$ を合成の形で表すと、$qp^{-1}$ となる。
+ここで、$p^{-1}=P,q^{-1}=Q$ と表現することにし、$a_n$ をこの4つだけで表現すると、
+  a1 = p
+  a2 = q
+  a3 = qP
+  a4 = qPQ
+  a5 = qPQpQ
+  a6 = qPQpQqpQ         = qPQppQ
+  a7 = qPQppQqPqpQ      = qPQpqpQ
+  a8 = qPQpqpQqPPqpQ    = qPQpqPqpQ
+  a9 = qPQpqPqpQqPQPqpQ = qPQpqPPqpQ
+  ...
+と、なんとなく逆写像で打ち消し合って、長さのインフレが抑えられてる感じがする。
+またよく見ると、1～2個の中心部を挟んで、前半と後半が綺麗に逆写像の関係であることがわかる。
+  a1 = (e)       p      (e)
+  a2 = (e)       q      (e)
+  a3 = (e)      qP      (e)
+  a4 = q         P        Q
+  a5 = qP        Q       pQ
+  a6 = qP       Qp       pQ
+  a7 = qPQp      p     PqpQ
+  a8 = qPQp      q     PqpQ
+  a9 = qPQp     qP     PqpQ
+  a10= qPQpq     P    QPqpQ
+  a11= qPQpqP    Q   pQPqpQ
+  a12= qPQpqP   Qp   pQPqpQ
+  a13= qPQpqPQp  p PqpQPqpQ
+  * 前半と後半が逆写像で、6個ごとに $qPQp$（$PqpQ$） が増えていく
+  * 中心部は、「$p,q,qP,P,Q,Qp$」の6個周期を繰り返す
+これにより、以下の手順で $a_K$ が求められる。
+  * 前半の部分は、$\displaystyle \frac{a_K-1}{6}$ 回、$qPQp$ を合成する（あと余りに応じて $qP$ とか付け加える）と求められる
+  * 中心部は、$(a_K-1)\%6$ による場合分けで、数回のシミュレーションで求められる
+  * 後半の部分は、前半の逆写像である
+  * 3つを合成すると $a_K$
+ここで、$qPQp$ の合成の部分はそのまま計算すると $O(NK)$ かかるので、繰り返し二乗法を使って高速化すると $O(N \log{K})$ で求められる。
+他の合成も $O(N)$ とか $O(N \log{N})$ 程度なので、十分高速に求められる。
+<sxh python>
+from operator import itemgetter
+def get_identity():
+    return list(range(1, n + 1))
+def composition(ppp, qqq):
+    return [ppp[q - 1] for q in qqq]
+def inverse_composition(ppp, qqq):
+    return [ppp[i] for i, q in sorted(enumerate(qqq), key=itemgetter(1))]
+def solve(k, ppp, qqq):
+    qp = inverse_composition(qqq, ppp)
+    qpq = inverse_composition(qp, qqq)
+    qpqp = composition(qpq, ppp)
+    l, m = divmod(k - 1, 6)
+    res = get_identity()
+    tmp = qpqp
+    while l:
+        if l % 2 == 1:
+            res = composition(res, tmp)
+        tmp = composition(tmp, tmp)
+        l >>= 1
+    if m == 0:
+        base = ppp
+    elif m == 1:
+        base = qqq
+    elif m == 2:
+        base = inverse_composition(qqq, ppp)
+    elif m == 3:
+        res = composition(res, qqq)
+        base = inverse_composition(get_identity(), ppp)
+    elif m == 4:
+        res = composition(res, qqq)
+        res = inverse_composition(res, ppp)
+        base = inverse_composition(get_identity(), qqq)
+    elif m == 5:
+        res = composition(res, qqq)
+        res = inverse_composition(res, ppp)
+        base = inverse_composition(get_identity(), qqq)
+        base = composition(base, ppp)
+    else:
+        raise NotImplementedError
+    ans = composition(res, base)
+    ans = inverse_composition(ans, res)
+    return ans
+n, k = map(int, input().split())
+ppp = list(map(int, input().split()))
+qqq = list(map(int, input().split()))
+print(*solve(k, ppp, qqq))
+</sxh>