https://csacademy.com/contest/beta-round-8/summary/
$N$要素の円形配列$A$が与えられる。各要素を隣接する2つの要素の和で置き換えた配列を出力せよ。
各$i$について、$A[(i-1+N)\% N]+A[(i+1)\% N]$を順番に出力していけばよい。
自力AC。簡単。
英小文字のみからなる文字列が$N$個与えられる。各文字列について、その文字列を構成する英小文字を同じ数だけrotationすることによって自分以外の$N-1$個の文字列のうちどれかと同じにできるかどうかを出力せよ。
各文字列を先頭の文字が'a'になるようにrotationさせて、同じものが存在するかどうかをstd::mapなどでカウントすればよい。
自力AC。典型っぽい問題。
$N$要素からなる数列が与えられる。この数列の好きな場所に好きな整数を1つだけ挿入することができるとき、公差が1であるような増加部分列の長さを最大化し、その長さを出力せよ。
$DP[a][0/1]=$現時点ですでに整数の挿入を 行っていない / 行っている 場合の、整数$a$を終点とする増加部分列の最大長さ
遷移は、$i$番目の整数を$a$として
となる。最終的にDPテーブルの中で一番大きい整数が答え。
自力AC。こういう問題は1分くらいで解けるようになりたい。
平面上の点が$N$個与えられる。2点$(x_1, y_1), (x_2, y_2)$の距離を$\min(|x_1-x_2|, |y_1-y_2|)$と定義するとき、すべてのペアの距離の中で$K$番目に短いものを出力せよ。
全点対の距離のなかで$K$番目に短いものを求めるには、距離が$D$以下のペアが$K$個以上あるような$D$の最小値を二分探索によって求めればよい。以下のような方法で距離$D$以下のペアがいくつあるかを高速に数えられる。
すべての点を$x$座標によってソートして、前から順番に見ていくことを考える。ここで、ある点$(x_i, y_i)$を見ているとき、すでに見た点のなかから以下のどちらかの条件を満たす点$(x_j, y_j)$を数えればよい。ここで、$x_j\leq x_i$である。
前者はqueueを使ったしゃくとり法によって求められる。すなわち、点をqueueに入れながら$x_i-x_j\gt D$となる点をpopしていけばよい。また、$y_i$と$y$座標の差が$D$以下の点はBITを使ってカウントできて、$y$座標が$y_j$であるような点が現れたら$y_j$のカウントを1増やし、$[y_i-D, y_i+D]$の総和を数えればよい。queueからpopした点の$y$座標だけをBITで記録していけば、$x_i-x_j\leq D$である点を2回カウントせずにすむ。
解説AC。二分探索もBITによる掃引も思いついたが、ダブルカウントを防ぐ方法を思いつかなかった。もう少し考察を詰められるようになりたい。問題自体はかなり面白いと思った。
$N$頂点からなる木と、$N$要素の配列$score$が与えられる。与えられた木に対して以下の操作を好きな回数行うことを考える。
木のスコアは$\sum_{nodes} score[degree]$で定義される。適切に操作を行ったあとのスコアの最大値を出力せよ。
適当な頂点を根として、以下のようなDPテーブルをDFSを使って更新することを考える。
$DP[i]=$すべての操作を行ったあとに頂点$i$とその親が残っている場合の、$i$を根とする部分木内のスコアの最大値
最終的に頂点$i$とその親が残っているとき、$i$の次数としてありうる値は[1, 初期状態での$i$の次数]である。$i$の次数が$k$であるとき、$i$に接続されている頂点は親と$k-1$個の子となっているはずである。ここで、子のなかから$k-1$個を選ぶにあたって$DP[son]$の大きい順に貪欲に選んでよい。よって、$DP[i]$は $$DP[i]={\rm chmax}(score[k]+DP[son_1]+DP[son_2]+...+DP[son_{k-1}])$$ となる。これをあり得る$k$すべてについて試せばよい。事前に$DP[son]$をソートしておけば計算量は全体でO($N\log N$)となる。
根以外のすべての頂点について$DP[i]$が求められたら、操作後の木で根となる頂点を全探索する。これは最後に残っている頂点のなかでもっとも(最初に決めた)根に近い頂点である。頂点$i$がそのような点であり、かつその次数が$k$であるとき、スコアの最大値は $$score[k]+DP[son_1]+DP[son_2]+...+DP[son_k]$$ となる。これをすべての$i, k$について調べたとき、その最大値が答えとなる。
解説AC。こういう問題は木DPに決まっていると思いつつも、やり方がわからなかった。答えを見てみるとこのくらいの工夫は思いついても良さそうに思うが、実際は難しい。
$N$種類のペンキで立方体の6面を塗り分けることを考える。$N$要素の数列$A$が与えられ、色$i$のペンキが$A_i$枚の面を塗れるだけの量があることを表すとき、ありうる塗り分け方の数を出力せよ。ただし、隣り合う面(辺を共有する面)は異なる色で塗られていなくてはならず、立方体を回転させて一致する塗り分け方は同じものであるとみなす。
隣り合う面は同じ色で塗ることができないので、ペンキの量は1面しか塗れないか2面塗れるかしか関係がない。ここで、1面しか塗れないペンキの数を$n_1$、2面しか塗れないペンキの数を$n_2$とする。この条件下で立方体の各面を塗るとき、使う色の種類は3種類から6種類のうちのどれかである。
3種類のペンキを使う場合、3色それぞれが向かい合う2面を塗ることになる。使う3色が決まればあとはどのように塗っても回転で一致するので、3色で立方体を塗る方法の数は $$_{n_2}C_3$$ となる。
4種類のペンキを使う場合、向かい合う2面を塗るペンキが2色あり、残りの2色が最後の2面を塗ることになる。この場合にも使う4色が決まれば塗り方は1通りしかないので、4色で立方体を塗る方法の数は $$_{n_2}C_2\times _{N-2}C_2$$ となる。
5種類のペンキを使う場合、向かい合う2面を塗るペンキが1色あり、残りの4色が残りの面を1面ずつ塗ることになる。1面を塗る4色のうち1色を固定すると残りの3色の塗り方が$\frac{3!}{2}$通りある(裏返して一致するものは除かなくてはならないため)ので、5色で立方体を塗る方法の数は $$\frac{3!}{2}\times _{n_2}C_1\times _{N-1}C_4$$ となる。
6種類のペンキを使う場合、6種類のペンキが1面ずつ塗ることになる。使う6色が決まれば1面を固定して、固定した面の裏側を塗る色が5通り、あとは残りの4面を塗る場合の数が$3!$通りある(5色の場合と違って裏返しを考慮する必要がないため)ので、6色で立方体を塗る方法の数は $$3!\times _NC_6$$ となる。
これらをすべて足し合わせたものが答えである。
自力AC。前の2問と比べて簡単じゃないですか……？
$N$頂点$M$辺の有向グラフが与えられる。ここで、グラフは以下の性質を満たす。
辺の部分集合を選んでその向きを反転することができるとき、グラフを強連結にするために反転すべき辺の集合の大きさの最小値を出力せよ。不可能な場合は-1を出力せよ。
与えられたグラフに存在する強連結成分の内部は最初から自由に行き来できるので、中身の辺をflipしても意味がない。よって、以降は与えられたグラフを強連結成分分解し、各強連結成分をノードとするDAGを考える。一般のDAGでは入次数が0のノード(トポロジカル順序が最初になりうるノード)が複数あってもよいが、この問題ではパスA~>C, B~>Cが存在するときA~>BもしくはB~>Aが存在するという制約より、(グラフが連結であれば)DAG上で入次数が0のノードは必ず1つであることがいえる。
入次数が0の点を根とすれば、DAG上の辺を取り出してすべての頂点を使った有向木を作ることができる。さらに、適切にtree edgeを選べば、それ以外の辺をすべてforward edgeとすることが可能である。その理由は以下である。
具体的には、DAG上の各頂点について根からの最長距離$depth$を求め、$depth[a]=depth[b]+1$を満たすような頂点($a, b$)間の辺A->Bをtree edgeとすればよい。根からの最長距離を求めるには、$depth$を頂点のトポロジカル順序で更新すればよい。
以上のようにしてDAG上の辺をtree edgeとforward edgeに分けることができれば、適切にforward edgeをひっくり返すことでグラフ全体を強連結にすることができる。ひっくり返す辺は貪欲に選択することができて、作った木の上でDFSを行い、葉から順に現在の頂点から(すでにひっくり返した辺を使って)自分より上の頂点にたどり着けないとき、自分を根とする部分木へと伸びるforward edgeのなかから、もっとも$depth$が小さい頂点から伸びているものをひっくり返せばよい。これを繰り返して根まで遡ることができなかったとき、解がないことがいえる。
解説AC。全く解けず、解説を理解するのもそこそこ時間を要したが、面白い問題だと思った。グラフに少し詳しくなった気がする(本当か？)