差分

この文書の現在のバージョンと選択したバージョンの差分を表示します。

この比較画面にリンクする

両方とも前のリビジョン 前のリビジョン
次のリビジョン
前のリビジョン
programming_algorithm:contest_history:atcoder:2019:0316_agc031 [2019/03/16]
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]] [[https://​beta.atcoder.jp/​contests/​agc031|AtCoder Grand Contest 031]]
ライン 113: ライン 113:
 ==== 解法 ==== ==== 解法 ====
  
-$A$ と $B$ で異なっているbitで2分割していく。イメージとしては、解説YouTubeの $N$ 次元超立方体の切断を考えるとわかりやすい。+区間を、最初最後の数字で異なっているbitで2分割していく。イメージとしては、解説YouTubeの $N$ 次元超立方体の切断を考えるとわかりやすい。
  
-まず、出来るか出来ないかの問題として、2進数で立っている'​1'​の数を考えると、「...→奇数→偶数→奇数→偶数→...」となっていくはなので、$A$ と $B$ の立っている'​1'​の偶奇は異なっていないといけない。同じなら'​NO'​。+まず、出来るか出来ないかの問題として、パリティ(2進数で立っている'​1'​の数の偶奇)を考えると、「...→奇数→偶数→奇数→偶数→...」と交互になっていく。 
 +順列偶数項なので、$A$ と $B$ のパリティは異なっていないといけない。同じなら'​NO'​。
  
 逆にこれを満たすと行けるのか、この時点ではよく分からないが、出来るとしてとりあえず考えを進める。 逆にこれを満たすと行けるのか、この時点ではよく分からないが、出来るとしてとりあえず考えを進める。
ライン 128: ライン 129:
   001                                011   001                                011
  
-13を見ると、2ビット目が異なっている。(複数ある場合、異なっているビットをどれか1つ選ぶ)+$A,B=1,3$を見ると、2ビット目が異なっている。(複数ある場合、異なっているビットをどれか1つ選ぶ)
  
 $0~2^N-1$ の中で2ビット目が'​0'​と'​1'​の数字の数は等しい。 $0~2^N-1$ の中で2ビット目が'​0'​と'​1'​の数字の数は等しい。
 よって、真ん中で2ビット目を1回切り替えれば、それ以外では2ビット目を操作する必要は無くなる。また、前半で「2ビット目が0の数字全て」、後半で「2ビット目が1の数字全て」を網羅すれば、少なくとも前半と後半の間で数字が被る心配は無くなる。 よって、真ん中で2ビット目を1回切り替えれば、それ以外では2ビット目を操作する必要は無くなる。また、前半で「2ビット目が0の数字全て」、後半で「2ビット目が1の数字全て」を網羅すれば、少なくとも前半と後半の間で数字が被る心配は無くなる。
  
 +   ​P0 ​  ​P1 ​  ​P2 ​  ​P3 ​   P4   ​P5 ​  ​P6 ​  P7
     1    ?    ?    ? |   ? ​   ?    ?    3     1    ?    ?    ? |   ? ​   ?    ?    3
   001  ?0?  ?0?  ?0? | ?1?  ?1?  ?1?  011   001  ?0?  ?0?  ?0? | ?1?  ?1?  ?1?  011
  
-前半の最後の数字を適当に1つ決める。ここでも $A$ と前半の最後の字と立っている'​1'​の偶奇は異なっている必要がある。+前半の最後の数字($P_3$)を適当に1つ決める。こまた ​$A$ から偶項なで、パリティは異なっている必要がある。
  
-これまでに分割に用いたビット(2ビット目)以外から適当に1つビット位置を選び、$A$ をそのビットだけ変化させた数とすると被らない。ここでは1ビット目を選んだとする。+これまでに分割に用いたビット(2ビット目)以外から適当に1つビット位置を選び、$P_3$ を $A$ についてそのビットだけ変化させた数とすると、これまでに確定した数字とは被らないし、'​1'​の偶奇が異なっているという条件も満たす。ここでは1ビット目を選んだとする。
  
     1    ?    ?    0 |   ​2 ​   ?    ?    3     1    ?    ?    0 |   ​2 ​   ?    ?    3
   001  ?0?  ?0?  000 | 010  ?1?  ?1?  011   001  ?0?  ?0?  000 | 010  ?1?  ?1?  011
-    ^ 1bit目を変化 ^+    ^ 1bit目を変化 ^     ^ P3を決めるとP4も自動的に決まる
  
-すると、左半分を「$A=1,​B=0$ ​とし、2ビット目はいじらない」同様の問題として処理できる。+すると、左半分を「$A=1,​B=0$、ただし2ビット目はいじらない」問題として処理できる。
  
-1と0では1ビット目が変化しているので(さっきそう変化させたからだが)、真ん中で1ビット目を変化させることにする。+最初の問題と同様に異なるビットを探すと、1と0では1ビット目が変化しているので(さっきそう変化させたので当然だが)、真ん中で1ビット目を変化させることにする。 
 +前半の前半は「?​01」、前半の後半は「?​00」という数字を網羅することで、前前半と前後半でかぶりはなくなる。
  
 +   ​P0 ​  ​P1 ​   P2   ​P3 ​   P4   ​P5 ​  ​P6 ​  P7
     1    ? |   ? ​   0 |   ​2 ​   ?    ?    3     1    ? |   ? ​   0 |   ​2 ​   ?    ?    3
   001  ?01 | ?00  000 | 010  ?1?  ?1?  011   001  ?01 | ?00  000 | 010  ?1?  ?1?  011
  
-すると、半の前半の最後の項($P_1$)は、$A=1$ からまだ分割に用いていない3ビット目を変化させ、5とするとよいことがわかる。+前前半の最後の項($P_1$)は、まだ分割に用いていない3ビット目を変化させ、5とするとよいことがわかる。
  
     1    5 |   ​4 ​   0 |   ​2 ​   ?    ?    3     1    5 |   ​4 ​   0 |   ​2 ​   ?    ?    3
   001  101 | 100  000 | 010  ?1?  ?1?  011   001  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ビット目はいじらない」として分割していくと、構築できる。
  
     1    5 |   ​4 ​   0 |   ​2 ​   6 |   ​7 ​   3     1    5 |   ​4 ​   0 |   ​2 ​   6 |   ​7 ​   3
ライン 164: ライン 168:
  
 左半分と右半分で次に分割すべきビットは同じとは限らないため、「既に分割に用いたビット」の管理に注意。 左半分と右半分で次に分割すべきビットは同じとは限らないため、「既に分割に用いたビット」の管理に注意。
-分割済ビット位置をリストで持ち、再帰関数の中でappendしてから子の探索に進み、終了後にpopするなどで実装できる。+分割済ビット位置をリストで持ち、再帰関数の中で末尾にappendしてから子の探索に進み、終了後にpopするなどで実装できる。
  
 <sxh python> <sxh python>
ライン 203: ライン 207:
 </​sxh>​ </​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>​
  
programming_algorithm/contest_history/atcoder/2019/0316_agc031.1552761835.txt.gz · 最終更新: 2019/03/16 by ikatakos
CC Attribution 4.0 International
Driven by DokuWiki Recent changes RSS feed Valid CSS Valid XHTML 1.0