差分
このページの2つのバージョン間の差分を表示します。
両方とも前のリビジョン前のリビジョン次のリビジョン | 前のリビジョン次のリビジョン両方とも次のリビジョン | ||
programming_algorithm:contest_history:atcoder:2019:0316_agc031 [2019/03/16] – [解法] ikatakos | programming_algorithm:contest_history:atcoder:2019:0316_agc031 [2019/03/18] – [例] ikatakos | ||
---|---|---|---|
行 1: | 行 1: | ||
- | ======AtCoder Grand Contest 031 A,B,C 問題メモ====== | + | ======AtCoder Grand Contest 031 A,B,C,D 問題メモ====== |
[[https:// | [[https:// | ||
行 113: | 行 113: | ||
==== 解法 ==== | ==== 解法 ==== | ||
- | $A$ と $B$ で異なっているbitで2分割していく。イメージとしては、解説YouTubeの $N$ 次元超立方体の切断を考えるとわかりやすい。 | + | 区間を、最初と最後の数字で異なっているbitで2分割していく。イメージとしては、解説YouTubeの $N$ 次元超立方体の切断を考えるとわかりやすい。 |
- | まず、出来るか出来ないかの問題として、2進数で立っている' | + | まず、出来るか出来ないかの問題として、パリティ(2進数で立っている' |
+ | 順列は偶数項なので、$A$ と $B$ のパリティは異なっていないといけない。同じなら' | ||
逆にこれを満たすと行けるのか、この時点ではよく分からないが、出来るとしてとりあえず考えを進める。 | 逆にこれを満たすと行けるのか、この時点ではよく分からないが、出来るとしてとりあえず考えを進める。 | ||
行 128: | 行 129: | ||
001 011 | 001 011 | ||
- | 1と3を見ると、下2ビット目が異なっている。(複数ある場合、異なっているビットをどれか1つ選ぶ) | + | $A,B=1,3$を見ると、2ビット目が異なっている。(複数ある場合、異なっているビットをどれか1つ選ぶ) |
$0~2^N-1$ の中で2ビット目が' | $0~2^N-1$ の中で2ビット目が' | ||
よって、真ん中で2ビット目を1回切り替えれば、それ以外では2ビット目を操作する必要は無くなる。また、前半で「2ビット目が0の数字全て」、後半で「2ビット目が1の数字全て」を網羅すれば、少なくとも前半と後半の間で数字が被る心配は無くなる。 | よって、真ん中で2ビット目を1回切り替えれば、それ以外では2ビット目を操作する必要は無くなる。また、前半で「2ビット目が0の数字全て」、後半で「2ビット目が1の数字全て」を網羅すれば、少なくとも前半と後半の間で数字が被る心配は無くなる。 | ||
+ | | ||
1 ? ? ? | ? | 1 ? ? ? | ? | ||
001 ?0? ?0? ?0? | ?1? ?1? ?1? 011 | 001 ?0? ?0? ?0? | ?1? ?1? ?1? 011 | ||
- | 前半の最後の数字を適当に1つ決める。これまでに分割に用いたビット(2ビット目)以外から適当に1つビット位置を選び、$A$ | + | 前半の最後の数字($P_3$)を適当に1つ決める。これもまた $A$ から偶数項なので、パリティは異なっている必要がある。 |
+ | |||
+ | これまでに分割に用いたビット(2ビット目)以外から適当に1つビット位置を選び、$P_3$ を $A$ についてそのビットだけ変化させた数とすると、これまでに確定した数字とは被らないし、' | ||
1 ? ? 0 | | 1 ? ? 0 | | ||
001 ?0? ?0? 000 | 010 ?1? ?1? 011 | 001 ?0? ?0? 000 | 010 ?1? ?1? 011 | ||
- | ^1ビット目を変化^ | + | |
- | すると、左半分を「$A=1, | + | すると、左半分を「$A=1, |
- | 1と0では1ビット目が変化しているので(さっきそう変化させたからだが)、真ん中で1ビット目を変化させることにする。 | + | 1と0では1ビット目が変化しているので(さっきそう変化させたので当然だが)、真ん中で1ビット目を変化させることにする。 |
+ | 前半の前半は「? | ||
+ | | ||
1 ? | ? | 1 ? | ? | ||
001 ?01 | ?00 000 | 010 ?1? ?1? 011 | 001 ?01 | ?00 000 | 010 ?1? ?1? 011 | ||
- | すると、前四半の最後の項(2番目)は、$A=1$ からまだ分割に用いていない3ビット目を変化させ、5とするとよいことがわかる。 | + | 前前半の最後の項($P_1$)は、まだ分割に用いていない3ビット目を変化させ、5とするとよいことがわかる。 |
1 5 | | 1 5 | | ||
001 101 | 100 000 | 010 ?1? ?1? 011 | 001 101 | 100 000 | 010 ?1? ?1? 011 | ||
- | さらに分割を進めて左四半分を「$A=1, | + | さらに分割を進めて「$A=1, |
- | 右半分も同様に、「$A=2, | + | 右半分も同様に、「$A=2, |
1 5 | | 1 5 | | ||
行 162: | 行 168: | ||
左半分と右半分で次に分割すべきビットは同じとは限らないため、「既に分割に用いたビット」の管理に注意。 | 左半分と右半分で次に分割すべきビットは同じとは限らないため、「既に分割に用いたビット」の管理に注意。 | ||
- | 分割済ビット位置をリストで持ち、再帰関数の中でappendしてから子の探索に進み、終了後にpopするなどで実装できる。 | + | 分割済ビット位置をリストで持ち、再帰関数の中で末尾にappendしてから子の探索に進み、終了後にpopするなどで実装できる。 |
<sxh python> | <sxh python> | ||
行 201: | 行 207: | ||
</ | </ | ||
+ | ===== D - A Sequence of Permutations ===== | ||
+ | |||
+ | [[https:// | ||
+ | |||
+ | ==== 問題 ==== | ||
+ | |||
+ | * 長さ $N$ の順列($1~N$ を並べ替えた配列)$p, | ||
+ | * 順列 $p,q$ に対して、$f(p, | ||
+ | * $p_i$ 番目が $q_i$ であるような順列 | ||
+ | * さらに、順列の列 $a_i$ を、以下のように定義する | ||
+ | * $a_1=p$ | ||
+ | * $a_2=q$ | ||
+ | * $a_{n+2}=f(a_n, | ||
+ | * 整数 $K$ に対し、$a_K$ を求めよ | ||
+ | * $1 \le N \le 10^5$ | ||
+ | * $1 \le K \le 10^9$ | ||
+ | |||
+ | ==== 例 ==== | ||
+ | |||
+ | a1 = p : 4 5 1 2 3 ┌ a1における' | ||
+ | a2 = q : 3 2 1 5 4 ├ a1における' | ||
+ | a3 : | ||
+ | a4 : | ||
+ | a5 : | ||
+ | |||
+ | ==== 解法 ==== | ||
+ | |||
+ | 写像とか全単射とかその辺を利用する。解説を写経。 | ||
+ | |||
+ | ===考えたこと=== | ||
+ | |||
+ | まず、$K$ が大きすぎるので、おそらくまとめて計算できるような周期があると予測する。 | ||
+ | 実際、サンプルでシミュレートしてみると3だったり72だったり、3の倍数で周期が発生している。 | ||
+ | |||
+ | また、合成した結果を合成するので、その合成過程は $p$ と $q$ のみで表現できる。試しに $f(p,q)$ を単に $pq$ と表現してみると、 | ||
+ | |||
+ | a1 = p | ||
+ | a2 = q | ||
+ | a3 = pq | ||
+ | a4 = qpq = q p q | ||
+ | a5 = pqqpq = pq q pq | ||
+ | a6 = qpqpqqpq = qpq pq qpq | ||
+ | ... | ||
+ | |||
+ | となり、「2つ前」「3つ前」「2つ前」の合成で表されてたりする。 | ||
+ | ただ、この表現方法では(だから何?)で終わってしまい、法則の手がかりが見つからなかった。 | ||
+ | |||
+ | ===解説の解法=== | ||
+ | |||
+ | ここでは、数学の集合論における合成を利用すると法則が見つかりやすかったようだ。 | ||
+ | |||
+ | まず、$pq$ を $p$ と $q$ の合成とする。つまり、$i$ 番目が $p_{q_i}$ であるような順列とする。 | ||
+ | |||
+ | i | ||
+ | p | ||
+ | q | ||
+ | ↓ | ||
+ | pq 1 5 4 3 2 | ||
+ | |||
+ | * [[wpjp> | ||
+ | * 合成は結合法則が成り立つ。つまり、$pqpq$ とあった場合、$p((qp)q)$ などと先に後ろから計算しても結果が変わらないことが保証される | ||
+ | * 合成は単位元 $e$ が存在する。つまり、$pe=ep=p$ となるような順列 $e$ が存在する。この問題の場合、$e=[1, | ||
+ | |||
+ | また、$p$ に対し、$p^{-1}$ を逆写像とする。つまり、 | ||
+ | |||
+ | index 1 2 3 4 5 → p{-1} | ||
+ | p 4 5 1 2 3 → index | ||
+ | ↓(並べ替え) | ||
+ | index | ||
+ | p{-1} | ||
+ | |||
+ | となるような順列とする。以下のような性質がある。 | ||
+ | |||
+ | * $p^{-1}$ の逆写像は $p$ | ||
+ | * $pq$ の逆写像は $q^{-1}p^{-1}$ | ||
+ | * $pp^{-1}=e$ | ||
+ | |||
+ | $f(p,q)$ を合成の形で表すと、$qp^{-1}$ となる。 | ||
+ | |||
+ | ここで、$p^{-1}=P, | ||
+ | |||
+ | a1 = p | ||
+ | a2 = q | ||
+ | a3 = qP | ||
+ | a4 = qPQ | ||
+ | a5 = qPQpQ | ||
+ | a6 = qPQpQqpQ | ||
+ | a7 = qPQppQqPqpQ | ||
+ | a8 = qPQpqpQqPPqpQ | ||
+ | a9 = qPQpqPqpQqPQPqpQ = qPQpqPPqpQ | ||
+ | ... | ||
+ | |||
+ | と、なんとなく逆写像で打ち消し合って、長さのインフレが抑えられてる感じがする。 | ||
+ | |||
+ | またよく見ると、1~2個の中心部を挟んで、前半と後半が綺麗に逆写像の関係であることがわかる。 | ||
+ | |||
+ | a1 = (e) | ||
+ | a2 = (e) | ||
+ | a3 = (e) qP (e) | ||
+ | a4 = q | ||
+ | a5 = qP Q pQ | ||
+ | a6 = qP | ||
+ | a7 = qPQp p PqpQ | ||
+ | a8 = qPQp q PqpQ | ||
+ | a9 = qPQp | ||
+ | a10= qPQpq | ||
+ | a11= qPQpqP | ||
+ | a12= qPQpqP | ||
+ | a13= qPQpqPQp | ||
+ | |||
+ | * 前半と後半が逆写像で、6個ごとに $qPQp$($PqpQ$) が増えていく | ||
+ | * 中心部は、「$p, | ||
+ | |||
+ | これにより、以下の手順で $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, | ||
+ | |||
+ | |||
+ | def composition(ppp, | ||
+ | return [ppp[q - 1] for q in qqq] | ||
+ | |||
+ | |||
+ | def inverse_composition(ppp, | ||
+ | return [ppp[i] for i, q in sorted(enumerate(qqq), | ||
+ | |||
+ | |||
+ | def solve(k, ppp, qqq): | ||
+ | qp = inverse_composition(qqq, | ||
+ | qpq = inverse_composition(qp, | ||
+ | qpqp = composition(qpq, | ||
+ | |||
+ | l, m = divmod(k - 1, 6) | ||
+ | res = get_identity() | ||
+ | tmp = qpqp | ||
+ | while l: | ||
+ | if l % 2 == 1: | ||
+ | res = composition(res, | ||
+ | tmp = composition(tmp, | ||
+ | l >>= 1 | ||
+ | |||
+ | if m == 0: | ||
+ | base = ppp | ||
+ | elif m == 1: | ||
+ | base = qqq | ||
+ | elif m == 2: | ||
+ | base = inverse_composition(qqq, | ||
+ | elif m == 3: | ||
+ | res = composition(res, | ||
+ | base = inverse_composition(get_identity(), | ||
+ | elif m == 4: | ||
+ | res = composition(res, | ||
+ | res = inverse_composition(res, | ||
+ | base = inverse_composition(get_identity(), | ||
+ | elif m == 5: | ||
+ | res = composition(res, | ||
+ | res = inverse_composition(res, | ||
+ | base = inverse_composition(get_identity(), | ||
+ | base = composition(base, | ||
+ | else: | ||
+ | raise NotImplementedError | ||
+ | |||
+ | ans = composition(res, | ||
+ | ans = inverse_composition(ans, | ||
+ | return ans | ||
+ | |||
+ | |||
+ | n, k = map(int, input().split()) | ||
+ | ppp = list(map(int, | ||
+ | qqq = list(map(int, | ||
+ | print(*solve(k, | ||
+ | </ | ||