https://csacademy.com/contest/beta-round-2/summary/
長さ$N$の順列$\sigma$があり、$N$個の文字列が与えられる。これらの文字列の順番は$\sigma$によって入れ替わっていて、辞書順で$i$番目の文字列が$\sigma_i$番目に与えられる。$\sigma$を出力せよ。
(文字列, 与えられた順番)のペアを辞書順でソートして、各文字列が与えられた順番を上から出力していけばよい。
自力AC。簡単。
$N$個の整数が与えられる。「$i$番目の数字を$a_i$で割る」という操作が$M$個与えられるので、各操作を行った直後の$N$個の整数のGCDを順番に出力せよ。なお、操作を実行する時点で$i$番目の整数はかならず$a_i$で割り切れることが保証される。
最初に$N$個の整数すべてのGCDをとり、操作をするたびに現在のGCDと$i$番目の要素を$a$で割ったもののGCDをとればよい。
一瞬セグ木で殴りたくなってしまった。反省。
$N$要素の円形数列($a_N$の次が$a_1$であるような数列)が与えられる。この数列に対して、要素を1つ選んで1加える操作および1引く操作を好きな回数行うことができる。この数列がもつ長さ$K$の連続な部分列$N$個について、その合計がすべて等しくなるように操作を行うとき、その最小回数を出力せよ。
もし数列が円形ではない場合には、周期$K$の数列はすべての連続な長さ$K$の部分列の和が同じになることは簡単にわかる(部分列を1つずらしたときに、部分列から外れた数字と同じ数字が入るため)。これを拡張して、数列が円形の場合には周期GCD($N, K$)の数列であれば同じように条件を満たすことがわかる。よって、mod GCD($N, K$)で合同なindexをもつ要素をすべて同じ数字に揃えればよい。数直線上の複数の点からの距離の合計が最小になる座標は各点の座標の中央値なので、複数の要素を同じ数字に揃えるときには揃えたい要素の中央値に揃えるのがコスト最小となる。
自力AC。(円形でない)数列で長さ$K$の連続な部分列の和をすべて等しくする方法はTopCoder MM107をやっている最中に使ったのでそれを思い出した。距離の和の最小値が中央値になるのは最初忘れていたが途中で思い出した。
$N$個の電球があり、それぞれのON/OFF状態が与えられる。$i$番目の電球の状態を変えるためには$i+1$番目の電球がONかつ[$i+2, N$]番目の電球がすべてOFFである必要がある(ただし、$N$番目の電球だけはいつでも状態を変更できる)とき、すべての電球をOFFにするための最小の操作回数を出力せよ。
すべての電球がOFFの状態から$i$番目の電球のみをONにするための最小操作回数は、$2^{N-i+1}-1$である(実験や数学的帰納法からわかる)。ここで、DPテーブルを
$DP[i][0]$=[$i, N$]番目以降の電球をすべてOFFにするための最小操作回数
$DP[i][1]$=$i$番目の電球をONにして、$[$i+1, N$]$番目の電球をすべてOFFにするための最小操作回数
とすれば $$DP[N][state_N]=0\\DP[N][!state_N]=1$$ であり、更新は $$DP[i][state_i]=DP[i+1][0]\\ DP[i][!state_i]=DP[i+1][1]+1+2^{N-(i+1)+1}-1$$ となる。$DP[0][0]$が答えである。
自力AC。右から$i$番目の電球をつけるのに$2^i-1$回の操作が必要ということは、途中で$2^i$個の状態を経由することを意味する。さらに、一回の操作では1つの電球しか変化しないので、これはグレイコードの性質と同じである。ここで状態の遷移とグレイコードを照らし合わせると一致することがわかるので、与えられた状態をグレイコードと解釈して復号することでこの問題が解ける。解説を見る前に思いついた方法はこちらの方法で、ACしたあと解説を読んで想定解法(「解法」に書いた方法)でもACしておいた。DPを思いつく能力が低い気がする……。あとは再帰を使った貪欲でもACできるらしい。
$N$行$M$列のグリッドが存在し、最初すべてのマスは白である。すべてのマスが青または赤に塗られた$N\times M$グリッドが与えられるので、行または列を1つ選んで青もしくは赤に塗る操作を繰り返してその状態にするための最小の操作回数を出力せよ。不可能な場合は-1を出力せよ。
すべてのマスは赤もしくは青に塗られているので、すべてのマス($i,j$)に対して、行$i$もしくは列$j$が塗られていなくてはならない。このことから、ある行$r$を塗らないとしたとき、すべての列は行$r$と同じ配色で塗られなくてはならないことがわかる。また、塗られなかった行は自動的に$r$と同じ配色になる。よって、$r$と同じ配色の行も塗る必要がなくなる。
ある行を塗らないとしたとき、すべての列の配色は自動的に決まり、それに伴ってすべての行の配色も決まるはずである。たとえば列$j$が青のとき、マス($i,j$)が赤であれば行$i$は赤でなくてはならない、など。さらに、このような場合には列$j$は行$i$より先に塗られなくてはならないこともわかる。このようにして各行および列をノードとして塗る順番を有向辺として張ることでグラフを構築することができて、このグラフがDAGであれば解があることがわかる。同様に、グラフにサイクルがあれば解はない。
グラフにサイクルがある場合とはどういう場合かを考える。たとえばある列$a$が赤と決まったとする。その後、マス($b, a$)が青であれば行$b$は青となり、$a\rightarrow b$である。ここで、($b, c$)が赤、($c, d$)が青であれば$a\rightarrow b\rightarrow c\rightarrow d\rightarrow a$のサイクルができる。これを言い換えると、入力に $$\left( \begin{array}{rr} R & \cdots & B \\ \vdots & \ddots & \vdots \\ B & \cdots & R \end{array} \right)\; or \; \left( \begin{array}{rr} B & \cdots & R \\ \vdots & \ddots & \vdots \\ R & \cdots & B \end{array} \right) $$ のような部分行列がある場合に優先順位グラフにサイクルができるといえる。このような部分行列があるかどうかはどの行を塗らないことにするかどうかとは関係がないので、解が1つでも存在するならばどの行を塗らないことも可能であることがわかる。対称性より、これまでの議論は行と列を入れ替えても成り立つ。
そのような部分行列があるかどうかを愚直に判定しようとすると到底間に合わないが、逆にいえば解をひとつ見つければそのような部分行列がないことがいえる。これは簡単であって、すべての要素が同じ色になっている行/列を見つけて削除することを繰り返せば解があるかどうかはO(N+M)で判定できる。
このようにして解があることがわかれば、あとはすべての行/列に対して同じものがいくつあるかを数えて、その最大値を$N+M$から引いたものが答えとなる。
解説AC。解説を見る前は、操作列を逆順に決定していくことを考えていた。各行/列について青に塗られたマスの数でソートしてdequeに入れ、すでに塗った行/列の数を記録しながらdequeの前後から青もしくは赤で塗れるものを探して貪欲に塗る(例えば、すでに2つの行が青で塗られているときに列のdequeの先頭が2(青の数が2)だったらその列は赤で塗れる、など)を考えたが、操作の順番によって解が変わることに気付いて断念した。この方法は「解をひとつ見つける方法」に流用できた。優先順位グラフにサイクルが存在するとき、かならず長さ4のものが存在するかどうかは実際のところよくわからない。行列の形で決まることは変わらないと思うので大丈夫だとは思うが……。
$N$ノードの木が与えられる。Alexは、この木を構成するノードのなかから互いに隣接しないいくつかのノードを部分集合として選択する。その後、残ったノードの中からBenが別の部分集合をとりだし、それを削除する。Benが選ぶ部分集合は、これを削除したときにAlexが選んだ部分集合のなかで互いに接続されているものがなくなるようなもののなかでサイズが最小のものである。Alexが最適な部分集合を選択したときに、Benが選択する部分集合のサイズを最大でいくつにできるかを出力せよ。
Benがノードを選ぶ最適な方法は以下である。Benは根(適当にノード1としてよい)からDFSをして、ノード$x$がAlexによって選択されたノードであれば、$x$の子$y$のうち、$y$を根とする部分木にAlexによって選択されたノードを含み、かつそのノードから$y$までのパスがBenによって選択された別のノードによって切断されていないものをすべて選択する。$x$がAlexによって選択されたノードでないとき、$x$を根とする部分木にAlexによって選択されたノードが2つ以上存在し、そのうち2つ以上のLCAが$x$であれば$x$を選択する。
これを踏まえて、AlexがBenに選択させられる最大のノード数を求めるには、以下のようなDPを行えばよい。
適当に決めた根からDFSを行い、葉ノードを $$DP[leaf][0]=0\\ DP[leaf][1]=-\infty\\ DP[leaf][2]=0\\ DP[leaf][3]=0$$ で初期化して遡るように更新していく。ここで、$DP[leaf][1]=-\infty$とするのは、葉ノードをAlexが選択することなく部分木(葉ノード自身)からパスを出すことはできないからである(0にするとバグる)。
$DP[x][0]$の値は、以下の2つのもののうち大きい方である。
$DP[x][1]$の値は、$x$の子$y$のうち1つから$DP[x][3]$を、それ以外の子からは$DP[y][0]$を足し合わせたもののうち最大のものである。
$DP[x][2]$の値は、$x$の子$y$について${\rm max}(DP[y][0], DP[y][1]+1)$を足し合わせたものである。$DP[x][2]$では$x$がAlexによって選択されているので、$y$からのすべてのパスを切っておく必要があるためこのようになる。問題の制約と$DP[y][1]$の条件より、Benが$y$を選択することで常に切断が可能である。
最終的な答えは $${\rm max}(DP[root][0], DP[root][1], DP[root][2])$$ となる。
解説AC。難しいけど、もっとしっかり考えていればBenの最適な行動くらいは考察できたのでは？という感じもする。Summer Festival Contest 2018 Dと似ているなと思った。パスを切ったり繋げたりしているので、実質同じでは？(だったら考察できなきゃ駄目だろ)