https://csacademy.com/contest/beta-round-7/summary/
$N$個の文字列が与えられる。各文字列から文字を1つだけ選び、それ以外の文字をすべて捨てる。最適に文字を選んだとき、選んだ文字から作れる文字列のなかで辞書順最小のものを出力せよ。
各文字列から辞書順最小の文字を選び、選んだ文字を昇順でソートした文字列を出力すればよい。
自力AC。簡単。
$N$要素の整数列が与えられる。この数列のなかから要素数が1以上$N-1$以下の連続な部分列を1つ取り除き、できた数列から和が最大となるように空でない連続な部分列を選ぶとき、選んだ部分列の総和の最大値を出力せよ。
最初に、数列$A$から和が最大となる連続な部分列を取り出す方法を考える。DPテーブルを
$end[i]=A_i$で終わる連続な部分列の和の最大値
と置けば $$end[i]=\max(end[i-1]+A_i, A_i)$$ のように更新できる。この数列の最大値が連続な部分列の和の最大値である。さらに、
$left[i]=i$番目の要素以前で完結する連続な部分列の和の最大値
とすれば $$left[i]=\max(left[i-1], end[i])$$ のように更新できる。これを後ろからも行い、$i$番目の要素以降で完結する連続な部分列の和の最大値の配列$right$を得る。
はじめに取り除く部分列のなかに要素$A_i$が含まれているとすると、その場合の答えは $$\max(left[i-1], right[i+1], left[i-1]+right[i+1])$$ で表すことができるので、これをすべての$i$について確認すればこの問題が解ける。
解説AC。この問題が解けなかったのは自分でも意外だった。
ladder graph $L(N)$は$2N$頂点$N+2(N-1)$辺のグラフであり、2行$N$列のグリッドグラフと同じ形のグラフである。整数$N$が与えられるので、$L(N)$を連結に保ったまま辺の部分集合を削除することを考える。可能な削除の仕方を$10^9+7$で割った余りを出力せよ。
グラフを$i$列目までみたときに、$i$列目までのすべての頂点が連結ではなく、かつ$i$列目の上下の頂点をどちらも含まない連結成分があるとき、そこから右をどのように繋いでもすべての頂点を連結にすることはできない。よって、DPテーブルを
$DP[i][0/1]=i$列目までで(すべての頂点が連結である / 頂点がちょうど2つの連結成分に分かれていて、$i$列目の上下の頂点が別の連結成分に属している)場合の数
とすると、このDPの遷移は $$ DP[i+1][0]=4\times DP[i][0]+DP[i][1] \\ DP[i+1][1]=2\times DP[i][0]+DP[i][1] $$ であり(公式Editorialの図参照)、$DP[N][0]$が答えである。ただし、$N\leq10^{18}$であり、このDPを愚直に更新していると間に合わない。
更新は $$ \left( \begin{array}{rr} DP[i+1][0] \\ DP[i+1][1] \end{array}\right) = \left( \begin{array}{rr} 4 & 1 \\ 2 & 1 \end{array}\right) \left( \begin{array}{rr} DP[i][0] \\ DP[i][1] \end{array}\right) $$ と書き換えることができて $$ \left( \begin{array}{rr} DP[N][0] \\ DP[N][1] \end{array}\right) = \left( \begin{array}{rr} 4 & 1 \\ 2 & 1 \end{array}\right)^{N-1} \left( \begin{array}{rr} 1 \\ 1 \end{array}\right) $$ となる。これを行列累乗で計算すれば、全体でO($\log N$)となる。
解説AC。端の状態を持ってO($N$)のDPは思いついていて、2進数で高速化できそうだが端の状態をうまく処理できないのでは？と思って諦めた。DPの遷移までちゃんと詰めていれば行列累乗でいけることに気づけたかもしれない。
$N$個のマスがあり、最初すべてのマスは白である。空でない連続な部分列を選び、1から$M$までの色で塗る操作を$M$回行うことを考える。ただし、$M$回の操作で$M$色をすべて1度ずつ使用する必要がある。ここで、操作全体のコストは操作全体でもっとも頻繁に塗り替えられたマスが塗り替えられた数に等しい。
$M$回の操作を行ったあとの各マスの色が与えられるので、そのような終状態を持つような操作のなかであり得る最大コストを出力せよ。
終状態において、ある色$c$が塗られているマスのなかで一番左のindexを$l_c$、一番右のindexを$r_c$と呼ぶことにすると、操作の性質上、2つの色$a, b$について区間$[l_a, r_a],[l_b, r_b]$は一方がもう一方に完全に含まれているか、もしくは全く重なっていないかのどちらかであることが分かる。ここで、$[l_c, r_c]$が別の区間に完全に含まれているとき、$[l_c, r_c]$を含む区間のなかで最も小さい区間をもつ色を$c$の親と定義する。このとき、親は子よりも必ず先に塗られなければならないことがわかる。
ここで、操作を逆順に行うことを考える。このとき、子は親よりも先に塗られなくてはならず、一度塗られたマスの色が再び変わることはない。この場合、ある色$c$を塗るとき、区間$[l_c, r_c]$の内部には「すでに塗られたマス($c$の子孫)」と「色$c$に塗られるマス」の2種類しかなく、$c$の子は$c$で塗られるマスをまたいで他の色に干渉することができない。逆に、$c$によって分断されていないならば$c$の子を他の$c$の子の下に塗り重ねることができる(ある色を塗るとき、すでに塗られたマスがある分だけその色のもつ区間の外側に広げて塗ってよい)。
DPテーブルを
$DP[c]=$区間$[l_c, r_c]$の内部で(色$c$を除いて)塗り重ねられる最大数
と定義すると、$DP[c]$は、区間$[l_c, r_c]$のなかで$c$によって分けられた区間のうちからひとつ選び、そのなかに存在する$c$の子$child$に対して
$\max(DP[child])+$その区間の中にある$c$の子の数
となる。これは、色の親子関係を辺とした木の上でDFSすることで再帰的に更新できる(一番外側の色は、色0の子であるとする)。$DP[0]$に終状態に存在しない色の数を足し合わたものが答えである。
自力AC。操作を逆順に見るのは典型なので解けた。
$N$要素の整数列が与えられる。この数列の要素を並べ替えて作れる数列のうち、同じ整数が隣り合わないようなものの数を$10^9+7$で割った余りを出力せよ。
与えられた数列を同じ数ごとにグループに分け、DPテーブルを
$DP[i][j]=i$番目のグループまで配置したときに、同じ数字が隣り合っているペアが$j$個あるような並べ方の数
と定義し、$i$番目の整数の数を$n_i$、$i$番目までの整数の数の合計を$s_i$とする。$DP[i][j]$の状態に新たに$i+1$番目の整数$n_{i+1}$個を置くとき、$s_i$個ある隙間のなかから$k$個選んで配置するとし、$s_i$個中$j$個ある「左右の整数が同じ隙間」のなかから$l$個が使用されるとする。つまり、左右の整数が同じでない隙間は$s_i+1-j$個使われることになる。$n_i$個の整数を$k$個の隙間に1つ以上入れるような場合の数は$_{n_i-1}C_{k-1}$通りなので、配置の方法は $DP[i][j]\times _{s_i+1-j}C_{k-l}\cdot _{j}C_{l}\cdot _{n_i-1}C_{k-1}$ 通りあることがわかり、これを$DP[i+1][j+n_i-k-l]$に足しあわせればよい。
以上の遷移を各$i, j, k, l$について行えば、$DP[$グループ数$][0]$が求める答えとなる。遷移は全体で$O(N^4)$であるように見えるが、$i$の最大値がグループの数、$k, l$の最大値が各グループの整数の数なので、合計で$O(N^3)$程度となり、$N\leq 750$で充分高速である。
解説AC。DPを色々考えたが、思いつかず悔しい。
$N$行$M$列の行列が与えられ、この行列には0から$N\times M-1$までの整数が1度ずつ現れる。この行列に対して、行または列を一つ選び、選んだ行/列の数字を好きな回数だけスライドする($n$回スライドするとき、$i$番目の数を$i+n\ mod\ (N\ or\ M)$番目に移動させる)操作を繰り返し、すべての$i, j$に対して$i$行$j$列目の整数を$i\times M+j$にできるかを判定し、できる場合はそのような操作をひとつ構築して出力せよ。
はじめに、$[0, N-1]$行目をすべて揃える。整数$[0, i]$が正しい位置にあるとき、$[0, N-1]$行目では高々4回の操作で整数$i+1$を(これまで揃えた部分を崩すことなく)正しい位置に移動させることが可能である(公式Editorialのアニメーション参照)。この操作は、整数$i+1$が正しい位置から(a)列だけ異なる場合、(b)行だけ異なる場合、(c)行も列も異なる場合の3通りの場合がある。
以上の操作を行えば、$N-1$行目のみが揃っていない状態になる。ここで、整数$NM-1$から順に$(N-1)M$までを揃えることを考える。整数$i$を$i+1$の左側に入れたいとき、0列目を使って$i$をどけて、直接$i+1$の左側に入れることを繰り返すことで$N-1$行目をすべて揃えることが可能である(公式Editorialのアニメーション参照)。
ここで、初期状態によっては$N-1$行目を揃えた際に0列目がずれることがある(0が一番上に戻らず下から2番目にくるなど)。その場合は0行目を使って、先ほどと同じ方法で0列目を揃えることができる。0列目を揃えたときに0行目が揃っていない場合は、$M-1$列目を使って同じ方法で0行目を揃える。ここで$M-1$列目が揃わなかった場合は、解がないことがいえる。解の有無は$N, M$の偶奇に関連していて、解がない場合があるのは$N, M$が両方とも奇数のときのみである。
$N, M\leq300$なので、各操作を$O(N)$もしくは$O(M)$で愚直にシミュレートしても間に合う。
解説AC。操作による不変量を探して……というようなことを考えていたが全く関係なかった。解法がアドホックすぎて解説を見たとき強めの虚無を感じた(汎用性がなさそう)。実装をバグらせて地獄を見た。最初のほうがルービックキューブの1面揃える動きに似ていると思った。