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

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$

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

まず、出来るか出来ないかの問題として、2進数で立っている'1'の数を考えると、「…→奇数→偶数→奇数→偶数→…」となっていくはずなので、$A$ と $B$ の立っている'1'の偶奇は異なっていないといけない。同じなら'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

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

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

  1    ?    ?    ? |   ?    ?    ?    3
001  ?0?  ?0?  ?0? | ?1?  ?1?  ?1?  011

前半の最後の数字を適当に1つ決める。ここでも $A$ と前半の最後の数字との立っている'1'の偶奇は異なっている必要がある。

これまでに分割に用いたビット（2ビット目）以外から適当に1つビット位置を選び、$A$ をそのビットだけ変化させた数とすると被らない。ここでは1ビット目を選んだとする。

  1    ?    ?    0 |   2    ?    ?    3
001  ?0?  ?0?  000 | 010  ?1?  ?1?  011
  ^ 1bit目を変化 ^

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

1と0では1ビット目が変化しているので（さっきそう変化させたからだが）、真ん中で1ビット目を変化させることにする。

  1    ? |   ?    0 |   2    ?    ?    3
001  ?01 | ?00  000 | 010  ?1?  ?1?  011

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

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

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

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

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

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