AtCoder Grand Contest 031 A,B,C,D 問題メモ

AtCoder Grand Contest 031

• AtCoder Grand Contest 031 解説放送 - YouTube

A - Colorful Subsequence

• 英小文字からなる文字列 $S$ の部分列であって、全て異なる文字からなるものの個数を $\mod 10^9+7$ で求めよ
• 文字列として同じでも、いずれかの文字が異なる場所から取り出されていれば、異なる部分列として数える
• $1 \le |S| \le 10^5$

「'a'を使うとしたら、どの位置の'a'を使うか」は、$S$ における 'a' の個数通りある。これを $P_a$ とする。これを各文字について求める。

どの文字を使うかのパターン数は、使わない場合の1通りを加えて $(P_a+1)\times(P_b+1)\times ... \times(P_z+1)$ となる。

どの文字を使うか決めれば、部分列の並び方は自動的に $S$ における順番になり一意に決まるので、並び順については考えなくてよい。

よってこのパターン数がそのまま答えとなる。ただし、1文字も選ばない1パターンは除いておく。

B - Reversi

• $N$ 個の石が一列に並ぶ
• 石はそれぞれ色 $c_1,c_2,...,c_N$ で塗られている
• 以下の操作を0回以上、任意の回数行える
  • 同じ色の2つの石に挟まれた間の石を、挟んだ石の色で塗り替える
• 最終的な石の色の並び方としてありうるものの個数を $\mod{10^9+7}$ で求めよ
• $1 \le N \le 2\times 10^5$

DPで解く。

• $dp[i]=i$ 番目の石までを使った、あり得る並び方の個数
• $dp[0]=1$

今考えている石の色を $c_i$ とした時、1つ前に $c_i$ が出てきた場所を $j$ とする。

DPの更新は、$j～i$ について操作を行う場合と行わない場合を合算する。

• $c_i$ がはじめて出てきたとき
  • 操作を行えない
  • $dp[i] = dp[i-1]$
• $j+1=i$ の時
  • 同じ色が連続していて挟まれた石がないので、操作してもしなくても同じ
  • $dp[i] = dp[i-1]$
• それ以外の時
  • $dp[i] = dp[i-1] + dp[j]$

問題の条件では、操作自体は直前の同色でなくてもっと前の同色の石との間でも行えるが、求めるのは最終的な色の並びなので、「もっと前の同色～$j$」「$j～i$」の2回操作を行ったと考えても変わらない。「もっと前の同色～$j$」の部分は $dp[j]$ までで考慮されているので、新規に考えるのは $j～i$ 間のみでよい。

実装では、あらかじめ同じ色が連続する部分は事前処理で1つにまとめてしまうと $j+1=i$ の場合分けが減って楽。

C - Differ by 1 Bit

• 正整数 $N$ が与えられる
• $(0,1,2,3,...,2^N-1)$ の順列（並べ替えた数列）を$(P_0,P_1,...,P_{2^N-1})$ とする
• 以下の条件を満たす順列が構築できるか調べ、可能ならば1つ構築せよ
  • $A$ で始まり、$B$ で終わる
  • 隣り合う全ての2要素について、2進数表現は1桁だけ異なっている
• $1 \le N \le 17$

区間を、最初と最後の数字で異なっているbitで2分割していく。イメージとしては、解説YouTubeの $N$ 次元超立方体の切断を考えるとわかりやすい。

まず、出来るか出来ないかの問題として、パリティ（2進数で立っている'1'の数の偶奇）を考えると、「…→奇数→偶数→奇数→偶数→…」と交互になっていく。 順列は偶数項なので、$A$ と $B$ のパリティは異なっていないといけない。同じなら'NO'。

逆にこれを満たすと行けるのか、この時点ではよく分からないが、出来るとしてとりあえず考えを進める。

順列なので、途中で同じ数字が被らないように、1ビットずつ変化させていかなくてはいけない。以下の例を考える。

N=3  A=1  B=3
  0    1    2    3    4    5    6    7
000  001  010  011  100  101  110  111

  1    ?    ?    ?    ?    ?    ?    3
001                                011

$A,B=1,3$を見ると、2ビット目が異なっている。（複数ある場合、異なっているビットをどれか1つ選ぶ）

$0～2^N-1$ の中で2ビット目が'0'と'1'の数字の数は等しい。 よって、真ん中で2ビット目を1回切り替えれば、それ以外では2ビット目を操作する必要は無くなる。また、前半で「2ビット目が0の数字全て」、後半で「2ビット目が1の数字全て」を網羅すれば、少なくとも前半と後半の間で数字が被る心配は無くなる。

 P0   P1   P2   P3    P4   P5   P6   P7
  1    ?    ?    ? |   ?    ?    ?    3
001  ?0?  ?0?  ?0? | ?1?  ?1?  ?1?  011

前半の最後の数字（$P_3$）を適当に1つ決める。これもまた $A$ から偶数項なので、パリティは異なっている必要がある。

これまでに分割に用いたビット（2ビット目）以外から適当に1つビット位置を選び、$P_3$ を $A$ についてそのビットだけ変化させた数とすると、これまでに確定した数字とは被らないし、'1'の偶奇が異なっているという条件も満たす。ここでは1ビット目を選んだとする。

  1    ?    ?    0 |   2    ?    ?    3
001  ?0?  ?0?  000 | 010  ?1?  ?1?  011
  ^ 1bit目を変化 ^     ^ P3を決めるとP4も自動的に決まる

すると、左半分を「$A=1,B=0$、ただし2ビット目はいじらない」問題として処理できる。

最初の問題と同様に異なるビットを探すと、1と0では1ビット目が変化しているので（さっきそう変化させたので当然だが）、真ん中で1ビット目を変化させることにする。 前半の前半は「?01」、前半の後半は「?00」という数字を網羅することで、前前半と前後半でかぶりはなくなる。

 P0   P1    P2   P3    P4   P5   P6   P7
  1    ? |   ?    0 |   2    ?    ?    3
001  ?01 | ?00  000 | 010  ?1?  ?1?  011

前前半の最後の項（$P_1$）は、まだ分割に用いていない3ビット目を変化させ、5とするとよいことがわかる。

  1    5 |   4    0 |   2    ?    ?    3
001  101 | 100  000 | 010  ?1?  ?1?  011

さらに分割を進めて「$A=1,B=5$、ただし1,2ビット目はいじらない」問題となるが、これは既に隣り合っているのでここで終了。右の「$A=4,B=0$」も同様に終了。

右半分も同様に、「$A=2,B=3$、ただし2ビット目はいじらない」として分割していくと、構築できる。

  1    5 |   4    0 |   2    6 |   7    3
001  101 | 100  000 | 010  110 | 111  011

左半分と右半分で次に分割すべきビットは同じとは限らないため、「既に分割に用いたビット」の管理に注意。 分割済ビット位置をリストで持ち、再帰関数の中で末尾にappendしてから子の探索に進み、終了後にpopするなどで実装できる。

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

• 写像
• 写像の合成
• 合成は結合法則が成り立つ。つまり、$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})$ 程度なので、十分高速に求められる。