https://csacademy.com/contest/round-9/summary/
$N$要素の数列が与えられる。要素のペアのなかで、その和が3で割り切れるものの数を出力せよ。
3で割ったあまりが$m$であるような要素の数を$c_m$とすると $$\frac{a_0(a_0-1)}{2}+a_1a_2$$ が答えである。
自力AC。簡単。
英小文字のみからなる単語が$N$個与えられる。これらの単語を使って辞書を作ることを考える。辞書には、単語が辞書式順序で掲載される。以下の形式のクエリが$Q$個与えられるので、その答えを出力せよ。
各単語が辞書順で何番目かをstd::mapで記憶しておき、各Queryについて$\lceil \frac{num_w}{x} \rceil$を出力すればよい。
自力AC。1問目と簡単さではいい勝負だと思う。
$N$行$M$列の0/1行列が与えられる。この行列に対して、以下の操作を何度でも行ってよい。
操作を終えたあと行列の各行を$M$bitの整数として解釈するとき、すべての行の和の最大値を出力せよ。
前提として、2進数において最上位桁を1にすることの価値はそれ以下のすべての桁を1にすることの価値よりも大きいので、$N$個の整数すべてについて最上位桁を1にする必要がある。これは適切に行の反転を行うことで必ず実現できる。すべての整数の最上位桁を同じにすることは行の反転でしか実現できず、列の反転では実現できない。このことから、一度すべての整数について最上位桁を1にしたならば、それ以上行の反転を行うことはできない。
以上のことから、以降は列の反転のみを行うことになるが、これは各列について貪欲に行ってよい。すなわち、各列について1の数が0の数よりも少ないならばその列を反転するという操作を順に行えばよい。すべての列に対してこの操作を行ったあとの状態が答えである。
自力AC。典型だと思った。
$N$要素の数列が与えられ、この数列から使用可能な要素を1つずつ選んで使用不能にしていく操作を考える。要素を使用不能にする順番が与えられるので、各操作の前に連続な(使用不能である要素を含まない)部分列の和の最大値を出力せよ。
操作を逆順に処理することで、最初にすべて使用不能だった数列が1つずつ使用可能になっていくと考えることができる。数列には負の数が存在しないため、連続な部分列は必ずそのすべての要素を使用するとしてよい。Union-Find treeなどで隣接する使用可能な要素の集合を管理し、操作が行われるごとにその和の最大値を出力すればよい。
自力AC。Beta Round #4 - Online XorMaxと問題の本質が全く同じである。あちらはBinary Trieで要素の集合を管理する必要があったが、こちらはただ足し合わせるだけでよいので完全に下位互換と言っていいと思う。
整数$N, K$が与えられる。$a_1+a_2+...+a_K=N$となるような$K$個の正整数の(sortedな)集合{$a_1, a_2, ..., a_K$}すべてについて、$a_1^2+a_2^2+...+a_K^2$を足し合わせた数を$10^9+7$で割ったあまりを出力せよ。
総和が$N$となるような$K$要素のsortedな正数列を数え上げる方法を考える。個数制限なしナップサック問題のような方法は比較的すぐに思いつくが、現在の和と個数、最大の数をDPの引数として持たなくてはならず、$N\leq10000$では間に合わない。
$K$要素のsortedな正数列を生成する方法として、はじめに$K$個の0を並べた数列を用意し、右端から$i$個の要素に1を足すという操作を繰り返すというものがある。例として $$ 0, 0, 0, 0 \\ 0, 0, 0, 1 \\ 0, 1, 1, 2 \\ 1, 2, 2, 3 $$ のように行う(右端から1, 3, 4個の要素に1を足す操作を順番に行うことで長さ4のsortedな整数を作る例)。ここで、一度長さ$i$の操作を行ったら、以降その状態に対して長さ$i-1$以下の操作を行ってはならない(ダブルカウントを防ぐため)。
ここで、長さ$k$の数列$a$に対して、すべての要素に1を足した際の二乗和の変化は \begin{align*} \sum_{i=1}^k \left[ (a_i+1)^2 - a_i^2 \right] &= \sum_{i=1}^k \left[ a_i^2 + 2a_i + 1 - a_i^2 \right]\\ &= \sum_{i=1}^k \left[ 2a_i + 1 \right]\\ &= 2\sum_{i=1}^k a_i + k \end{align*} であり、これは要素の和と数列の長さのみから決まっていることがわかる。このことを利用して、以下のようなDPを考える。
$DP[i][j]=$今までに行われた操作の最大長さが$i$であるような状態のうち、要素の和が$j$であるようなものの(数, 要素の二乗和)
状態の遷移は、以下の2種類である。
それぞれ、これまでに行われた操作の最大長さが$i$の状態に対して「長さ$i$の操作を行う」「前回の操作の長さが$i+1$であったことにする(右から$i+1$番目の要素を0から1に変える)」遷移を表す。求める答えは$DP[K][N]$である。メモリ制限が厳しいので、適当に節約すると通る。
解説AC。ナップサックのような解法を考えていたがどう考えても間に合わないのでギブアップ。昇順の数列を生成する方法を新しく知ったので勉強になった。
各文字が0から9の数字であるような文字列$S$が与えられる。この文字列の部分列(連続でなくてよい)のなかで、回文かつ101の倍数であるようなものの数を$10^9+7$で割ったあまりを出力せよ。
$DP[l][r][len][rem]=S[l..r]$の部分列のなかで、長さが$len$かつ10進数として解釈した場合に10で割ったあまりが$rem$となるようなものの数
のようなDPを考える。このDPの遷移は
となる。ここで、1つ目の遷移はより小さい区間にある部分列を包除原理で数え上げる遷移であり、下の2つは両端が$S[l], S[r]$であるような部分列を数える遷移である。遷移の順番は、区間[$l, r$]の小さい順に回せばトポロジカル順序となる。
このままでは全体でO($N^4$)となるため$N\leq200$で間に合わない。ここで、$10000\%101=1$であることを利用して計算量を削減できる。たとえば $$9876543210\equiv (0+4+8)*10^0+(1+5+9)*10^1+(2+6)*10^2+(3+7)*10^3 \mod 101$$ であり、部分列の長さは2番目の遷移で$S[l]$に掛ける10の数を決めるために使うだけなので、これを圧縮して$0\leq len\lt4$としてよい($len$ mod 4を変数にする)。これで時間計算量は全体でO($N^3$)であり、すべての$len$についてDP[0][N-1][len][0]を足し合わせたものが答えである。
解説AC。101の倍数を数えるためにmod 101をDPの変数にとるテクニックは、以前に出てきた「同じ数字が隣り合わない状態の数」を数えるために同じ数字が隣り合っている場所の数をDPの変数にした問題と似ていると思った(こういうDPがなかなか思いつけない)。$len$を圧縮するのは賢いと思った。1桁の数を$len=1$とすると、それが$10^0$の係数であることとズレが生じて気持ち悪さがあるが、結局すべての$len$について足し合わせるのでそこがズレていても答えには関係ないのだった。
アライグマが2次元平面上の点($0, 0$)に存在していて、($N, 0$)を目指す。ここで、アライグマはJetpackを装備していて、以下の2種類の移動が可能である。
Jetpackは1度に$K$回分までチャージでき、アライグマが$y=0$にたどり着くたびに満タンまでチャージされる。アライグマが($N, 0$)にたどり着くために可能な道筋の数を$10^9+7$で割ったあまりを出力せよ。
$DP[i]=(0, 0)$から$(i, 0)$に移動する方法のうち、$(i, 0)$にちょうど着地するようなものの数
というDPを考える。ある場所からJetpackで浮き上がり、一度も着地せずに距離$2x$を飛ぶような場合の数はカタラン数$C_{x-1}$で表せる。このことを利用して、このDPの遷移は $$DP[i]=\sum_{j=0}^{i-1}DP[0..j]\times jump[i]$$ と表せる。ここで、$DP[0..a]$は$\sum_{i=0}^a DP[i]$を表し、$jump[i]$は距離$i$を(途中で着地することなく)飛ぶ場合の数を表す。$jump[i]$は$i$が奇数のとき0、偶数のとき$C_{i/2-1}$となる。ただし、$K\lt i$のとき0である。
上記の遷移は全体でO($N^2$)であるが、問題の制約が$N\leq10^5$なので間に合わない。そこで、これを高速化する方法を考える。
DPテーブルを高速に計算するために、分割統治を用いる。区間[$l, r$]についてそのDPテーブルを計算したい場合を考える。ここで、区間の中点$m$について[$l, m$)でのDPテーブルの値が計算されているとする。このとき、区間[$l, m$)の要素から[$m, r$]の要素への寄与は多項式 $$(DP[0..l]x^0 + DP[0..l+1]x^1 + ... + DP[0..m-1]x^{m-1-l})\times (jump[0]x^0 + jump[1]x^1 + ... + jump[r-l]x^{r-l})$$ の係数で与えられ、これはFFTによってO($(r-l)\log (r-l)$)で計算できる。$DP[i]\ (m\leq i \leq r)$に対する区間[$l, m$)からの寄与は、$x^i$の係数となっている。この段階では区間[$m, r$]に対しては[$l, m$)からの寄与しか計算されていないが、このあと[$m, r$]について分割統治を行うことですべての項からの寄与が足されることになる。つまり
とすればすべての$i$について$DP[i]$を計算できる。時間計算量は全体でO($N\log^2 N$)である。
解説AC。$N\leq 1000$であれば超典型といえる問題が、$N$が大きくなるだけでここまで難しくなるのかと驚いた。