ABC171解説を書いてみた

A – alphabet

プログラミングで扱われる文字コードは一般的に a, b, c, …, z のように小文字・大文字が連続して並んでいるため、(‘a’ <= a && a <= ‘z’) で小文字かどうかの判定ができます。

これが true であれば ‘a’ 、false であれば ‘A’ を出力すれば良いです。

また、すべての小文字を並べた文字列を直接ソースコードに記入し、その中に入力文字が存在するかを判定する方法もあります。

 

B – Mix Juice

問題は、$p_1, \dots , p_N$ の中から値を $K$ 個選ぶときの、選んだ数の総和としてあり得る最小値を答える問題となります。

これは、$p_1, \dots , p_N$ の値の小さい方から $K$ 個選ぶと達成できるため、$p_1, \dots , p_N$ を昇順にソートし、先頭から $K$ 個の値を合計することで答えが分かります。

時間計算量はソート部分が重く、 $O(N\log N)$ です。

 

C – One Quadrillion and One Dalmatians

問題文に Dalmatians （ダルメシアン）とあるのは、『101匹ワンちゃん』のパロディでしょう。

単純に 26 進数に変換したくなるかもしれませんが、”0″ に対応する文字が無いため、うまくいきません。

（”a” を “0” に対応させると、”aa” が解釈できなくなります）

そのため、工夫が必要です。

問題文の例を見ると、末尾の文字が a, b, c, …, y, z, a, b, …, z, a, … と、26 種類の文字を繰り返していることが分かります。

また、末尾から 2 番目の文字は、最初は存在せず、存在するようになってからは a を $26$ 回、b を $26$ 回、…、z を $26$ 回、と繰り返した後にまた a を $26$ 回、…と繰り返していきます。

（末尾文字が a から z まで回るたびに、末尾から 2 番目の文字が変わります）

末尾から 3 番目の文字も、最初の $26+26^2$ 回は存在せず、その後は a から順に $26^2$ 回繰り返して次の文字に変わる、ということを繰り返します。

 

末尾から決めていくことを考えます。

まず、$N$ の値を $1$ 減らしておきます。

末尾の文字は、$N \bmod 26$ で得られます（$0$ は ‘a’ 、$1$ は b、…に対応）。

末尾の文字を削除して考えると、26 文字ごとに “”, “a”, “b”, …, “z”, “aa”, “ab”, … というように、最初に空文字があるものの元の並びと同じ構造になります。

したがって、$N$ の値を $26$ で割り（小数切り捨て）、空文字列を無視するために $N$ の値を $1$ 減らすと、末尾文字の決め方と同じように末尾から 2 番目の文字が得られます。

このように、「$N$ を $26$ で割った余りで文字を取得」→「$N$ を $26$ で切り捨て割り算」→「$N$ を $1$ 減らす」という操作を繰り返し、$N$ が負になれば終了することで、末尾から順に文字が得られます。

したがって、得られた文字を逆順に出力すれば正解できます。

操作のたびに $N$ の値が $1/26$ 倍以下になっていくため、時間計算量は $O(\log N)$ です。

 

D – Replacing

毎回数列を書き換えるのは、最悪 $NQ$ 回程度の計算が必要になり、今回の制約では間に合いません。

クエリで出力するものは数列の合計であるため、数がどう並んでいるかは記録する必要がなく、どのような値で構成されているかさえ把握していれば良いです。

したがって、「$A[i]=j$ となる値が何個あるか」という、ヒストグラムのような値を記録しておいても良いです。この値を $count[j]$ としておきましょう。

また、書き換え操作も、この記録の 2 箇所を書き換えるだけで実質的に可能となります。

クエリ $i$ では、値が $B_i$ である要素をすべて $C_i$ に変えるため、$count[C_i]$ の値が $count[B_i]$ だけ増え、$cound[B_i]$ の値は $0$ になります。

総和については、クエリ $i$ によって $B_i\times count[B_i]$ だけ減り、$C_i\times count[B_i]$ だけ増えます。

そのため、最初に数列 $A$ の総和を計算しておけば、クエリのたびに 4 回程度の和・差・積で更新することができます。

クエリの処理が高速にできるようになったため、問題が解けました。

 

E – Red Scarf

赤いスカーフというのは、すぬけさんのツイッターアイコン由来でしょうか。

$N$ が偶数であるという制約が重要な問題です。

xor には、順番が関係ない・0 を xor しても値が変わらない・同じ数を xor すると 0 になる、という性質があります。

そのため、「すべてのスカーフの整数の xor」の値が分かれば、この値と「自分以外のスカーフの整数の xor」の値（入力の $a_i$）を xor することで、自分のスカーフの値が得られます。

 

入力の $a_i$ は、$i$ 番目のスカーフの値のみが xor されていない、偏った値ですが、入力のすべてを xor すると偏りのない値が得られます。

この値について考えると、すべてのスカーフの値が、対応する入力以外のすべてに xor として含まれているため、$N-1$ 回 xor されていることになります。

例えば、$N=4$ のとき、スカーフの値を $b_i$ とすると、

$a_1=b_2 xor b_3 xor b_4$

$a_2=b_1 xor b_3 xor b_4$

$a_3=b_1 xor b_2 xor b_4$

$a_4=b_1 xor b_2 xor b_3$

であるため、

$a_1 xor a_2 xor a_3 xor a_4 = b_1 xor b_2 xor b_3 xor b_4$

となります（$n xor n xor n = 0 xor n = n$ であることを利用します）。

 

同じ値を奇数回 xor すると元の値になることから、この「すべての入力 $a_i$ の xor」という値が、「すべてのスカーフの値の xor」と一致します。

したがって、この値をまず計算し、得られた値と各 $a_i$ の値の xor を計算することで、出力すべき値が得られます。

 

F – Strivore

これのほうが賢い↓

アライグマ「F問題は、最後にできる|S|+K文字のうち、Sの文字がどこにいるかで考えたいけど、それをすると同じ文字列を何回も数えちゃうから、うまく重複しないような条件をつけるのだ！」 pic.twitter.com/EJUzqx6Epo

— 競技プログラミングをするフレンズ (@kyopro_friends) June 21, 2020

以下、私の解法（回りくどい）

条件を満たす文字列は「長さ $|S|+K$ で、連続とは限らない部分列に $S$ を（そのままの順番で）含む文字列」と表現できます。

なぜなら、そのような文字列について、文字列 $S$ をそのままの順で選ぶことができ、それ以外の文字を挿入すれば構成できるからです。

 

そこで、計算量を無視して考えると、以下のような動的計画法で解くことができます。

$dp[i][j]=i$ 文字目まで決めたときに、文字列 $S$ の先頭 $j$ 文字をそのままの順番で含む文字列の個数

そのような文字列を作る方法は、$i-1$ 目までを決めた文字列のうち、$S$ を $j$ 文字含むものに $S[j+1]$ 以外の $25$ 文字を追加するか、$S$ を $j-1$ 文字含むものに $S[j]$ を追加するかの $2$ 通りがあるため、以下のように更新できます。

$dp[i][j]=dp[i-1][j]\times 25 + dp[i-1][j-1]$

$dp[0][0]=1$

ただし、$j=0$ のときは前者のパターンしか無いため

$dp[i][0]=dp[i-1][j]\times 25$

となり、$j=|S|$ のときは、前者について $S[j+1]$ 以外という制約がなくなるため、

$dp[i][|S|]=dp[i-1][|S|]\times 26 + dp[i-1][|S|-1]$

となります。

つまり、入力文字列 $S$ は長さのみが重要で、その内容は無関係ということです。

この動的計画法をそのまま実装すると、$dp$ 配列のサイズが $|S|\times K$ 程度になり、今回の制約ではメモリや更新の計算時間が足りません。

そのため、これを高速化することを考えます。

 

最終的に必要なのは $dp[|S|+K][|S|]$ であるため、$dp$ 配列の $j=|S|$ の部分だけ計算できれば良いです。

したがって、$dp[i][|S|-1]$ の値が高速に計算できると良いです。

$dp[i][|S|-1]$ の値は、$i<|S|-1$ のときは $0$、$i=|S|-1$ のときに $1$ となります。

 

ここで DP 遷移の表を考えると、$j\le |S|-1$ の範囲では、「$(i, j)$→$(i+1, j)$ では値が 25 倍、$(i,j)$→$(i+1,j+1)$ では値が 1 倍」となります。

すべての値は $(0,0)$ における値 $1$ に由来しており、$(i, |S|-1)$ に至るまでの経路では、$(i,j)$→$(i+1,j+1)$ の移動を $|S|-1$ 回、$(i, j)$→$(i+1, j)$ の移動を $i-|S|+1$ 回、行うことになります。

この過程で、最初に $1$ だった値は経路の選び方によらず $25^{i-|S|+1}$ 倍され、経路の選び方が ${}_i\mathrm{C}_{|S|-1}$ 通りあるため、dp[i][|S|] の値はそのすべての和であるため、 $25^{i-|S|+1}\times {}_i\mathrm{C}_{|S|-1}$ となります。

累乗に繰り返し二乗法を用い、組合せの計算に階乗やその逆元を事前計算しておくことで、この計算は高速に行えます。

そのため、

$dp[i][|S|]=dp[i-1][|S|]\times 26 + dp[i-1][|S|-1]$

を用いて $dp[i][|S|]$ の値を高速に計算することができるため、最終的な出力である $dp[|S|+K][|S|]$ を時間内に計算することができます。

時間計算量は、階乗とその逆元の前計算に $O(|S|+K)$ か $O((|S|+K)\log M)$（$M=10^9+7$）、繰り返し二乗法を用いた $dp$ 更新に $O(K\log K)$ となります。