https://csacademy.com/contest/beta-round-5/summary/
各要素が0もしくは1で構成された$N\times N$行列$A$が与えられる。もとの行列とこれを$90^\circ,180^\circ,270^\circ$回転した3つの行列のうち、すべての行列で0となっている要素は0、そうでない要素は1であるような$N\times N$行列$B$を出力せよ。
$$B_{ij}=\max{(A_{i, j}, A_{N-j-1, i}, A_{j, N-i-1}, A_{N-i-1, N-j-1})}$$ とすればよい。
自力AC。簡単。
$N$頂点$M$辺の無向グラフが与えられる。AlexとBenはともに頂点$S$からスタートし、Alexは頂点$A$に、Benは頂点$B$に移動する。ここで、AlexとBenはそれぞれの目的地に最短経路で向かうが、できるだけ長く一緒に旅をしたいと思っている。よって、$A,B$に向かう最短経路のうち、できるだけ多くの辺を共有する2つの経路を計算し、2つの経路が共有する辺の数の最大値を出力せよ。
AlexとBenは常に最短経路を通るので、一度別れたらもう出会うことはない（もう一度出会うのであれば、そこまで一度も別れずにいけるはずである）。よって、$S, A, B$からすべての頂点に対しての最短経路をダイクストラ法で求めて、($S$からの最短経路)＋($A, B$からの最短経路)＝($S$から$A, B$への最短経路)であるような頂点のうち$S$からの最短経路が一番長い頂点まで一緒に旅行するのがよい。
自力AC。自然な発想でACできた。解説を見るとダイクストラではなくてBFSを使っていた。それはそう。
$N$要素の数列$v$と$M$要素の数列$u$が与えられ、最初$v[i]=i$である。この数列に対して、偶数番目の要素を抜き出して順番を変えずに数列の最初に持ってくる操作(例: $a,b,c,d \rightarrow b,d,a,c$)を行い、その後、操作後の数列のprefix(元々偶数番目だった要素)とsuffix(元々奇数番目だった要素)にそれぞれ同様の操作を行うことを考える。この一連の操作が終了したあと、数列$v$が$u$を(連続な)部分列として含む場合は1を、含まない場合は0を出力せよ。
数列$v$に操作を行ったあと、要素$i$が何番目にあるかということは再帰関数を使ってO($\log{N}$)で求められるので、これを$u$のすべての要素に対して行えば$u$が操作後の$v$の連続な部分列であるかどうかがわかる。
解説AC。操作後の$v$に明らかに法則性があるのでそれをうまく取り出す問題かと思ったら、思ったより愚直だった……。簡単なのに思いつかなかったのは悔しい。
$N$頂点$M$辺のグラフが与えられる。また、グラフの各頂点が存在する座標が与えられる。各頂点間には反発力がはたらいており、その大きさは辺で結ばれている頂点間では$F_1*dist$、辺で結ばれていない頂点間では$F_2*dist$である。すべての力が独立かつ同時にはたらくとき、各頂点にはたらいている力の合力を出力せよ。
点$i$の座標を$\vec{x}_i$とすると、辺が1つもない場合に点$i$にはたらく力はすべての点から$i$に伸びるベクトルの和の$F_2$倍であるから \begin{align*} \vec{F}_{2i}&=F_2\sum_j \left( \vec{x}_i-\vec{x}_j \right)\\ &=NF_2\vec{x}_i-\sum_j \vec{x}_j \end{align*} と表せる。$\sum_j \vec{x}_j$をあらかじめ求めておくと、この計算は点全体でO($N$)となる。
辺がある場合には、上述の力に加えて力 $$\vec{F}_{1a}=\left( F_1-F_2 \right)\sum_{edges} \left( \vec{x}_a-\vec{x}_b \right)$$ がはたらくと考えることができる。ここで、$a, b$は各辺の両端の点のindexである。以上のことから、時間計算量は全体でO($N+M$)となる。
解説AC。普通に感心したが、よく考えたらわかったのではと思わなくもない。解説を見る前はBITとかを使って左や上から掃引していくのは無理っぽいな〜などと考えていた。
0と1のみで構成された2つの文字列$Text, Pattern$が与えられる。ここで、$Text$の中で隣り合う2つの文字を入れ替える操作を繰り返すことで$Pattern$とのマッチング回数($Text[i..(i+Pattern.length-1)]=Pattern$となるような$i$の数)を最大にすることを考える。可能な最大のマッチング回数と、それを実現するために必要な操作の最小回数を出力せよ。
$Text$の中で隣り合う2文字を入れ替えることによって作れる文字列は、0, 1の数が$Text$とそれぞれ一致する文字列すべてである。ここで、ある文字列を作るために必要な操作回数は転倒数と同様の方法で計算できて、最初に前計算として$Text$での$i$番目の0/1の前にある1/0の数を記録しておき、操作後の文字列の各桁について転倒しているペアの数を足し合わせることで求められる。よって、DPテーブルを
$DP[i][j][k]=$操作後の文字列を$i$番目まで決めたときに0が$j$個あり、後ろから$k$文字が$Pattern$の前から$k$文字と一致している場合の(最大マッチング回数, 最小操作回数)
とすればよい。ここで、$k$の遷移が多少特殊である。1回$Pattern$とマッチングが完了したとき、その瞬間に後ろから何文字かが$Pattern$と一致している可能性があるからである。これは前計算で求めておけば良い。また、途中で一致が切れた場合にも同じことが言えて、これも$k$文字目で一致が切れた場合をそれぞれ前計算しておく必要がある。DPの遷移自体がO($|S|^3$)なので、愚直に前計算をしても間に合う。また、メモリ制限が少なくDPテーブルをそのまま取るとMLEになるので、実際には$DP[2][j][k]$のようにとり、$i$の代わりに$i$%2を更新することでメモリ制限を回避できる。
自力AC。典型の詰め合わせみたいな問題。本番で3人にしか解かれていない問題だったので、解けたのは嬉しい。
cycle treeとは、以下のうち1つを満たす無向グラフである。
cycle treeが与えられるので、その最大独立点集合のサイズを出力せよ。
cycle treeでは次数が2の頂点が必ず存在していて、「次数2の頂点を削除する→削除した頂点と接続されていた2点間に辺がない場合は辺で結ぶ」という操作を繰り返すことで最終的に必ず2つの頂点とその間を結ぶ辺のみが残る。このことを利用して、以下のようなDPテーブルを考えることができる。
$DP[0/1][0/1][u][v]=$頂点$u, v$と、辺($u, v$)に所有される頂点の集合での最大独立点集合のサイズ。ここで、最初の2変数はそれぞれ頂点$u, v$を最大独立点集合に使用するかどうかを表している。
このDPテーブルを、上述の操作を行いながら更新していけばよい。以下に「各辺が所有する頂点」という概念を定義する。はじめ、どの辺も頂点を所有していない。ここで、DPの遷移に伴って頂点$a$を削除したとき、$a$が頂点$b, c$に接続されていたとする。操作によって頂点$b, c$間には辺が作られる(元からある場合もある)が、このとき削除された頂点$a$はこの辺($b, c$)に所有される。同時に辺($a, b$), ($a, c$)も削除されるが、これらのうちどちらかが所有する頂点が存在したならば、その頂点もまた辺($b, c$)に所有される。
DPテーブルの遷移は以下のように行う。最初から辺で結ばれていた頂点を両方とも独立点集合に含めることはできないので、そのような2点$u, v$について $$DP[1][1][u][v]=-\infty$$ とする。また、すべての辺(途中でできた辺も含む)について、辺が作成された時点で $$DP[0][0][u][v]=0\\ DP[0][1][u][v]=1\\ DP[1][0][u][v]=1$$ である。
頂点$a$を削除したとき、$a$と接続されていた頂点$b, c$について $$DP[i][j][b][c]+=\max{\left( 0,\; DP[i][0][b][a]+DP[j][0][c][a]-(i+j),\; DP[i][1][b][a]+DP[j][1][c][a]-(i+j+1) \right)}$$ のように遷移する($a$を使う場合と使わない場合の最大独立点集合の和からダブルカウントされた頂点を引いている)。ここで、$i,j\in\{0, 1\}$である。
頂点を削除する順番は関係なく、その次数が2であればよい。この操作を続けていけば、最後には次数が1の2点が残り、その2点を結ぶ辺は$N-2$個の頂点を所有しているという状態になる。このときのDPテーブルの4つの値のうち最大のものが解となる。
テクニックとして、上記のDPテーブルを配列で持とうとすればそのサイズは$2\times2\times N\times N$となりMLEとなるが、std::mapを利用すれば実質$2\times2\times M$程度ですむ。頂点の管理にはstd::queueが便利である。
解説AC。cycle treeも最大独立点集合も初見だったので全く歯が立たなかったが、DPの遷移の仕方が特殊で面白いと思った。解説ではDPテーブルを$DP[edge][0/1][0/1]$のように持っていたが、これは辺の番号を管理したり頂点の順序を守ったりしなくてはならない点で少し不便か。ただし、std::mapを使わないぶん時間計算量では多少優れているはず。