https://csacademy.com/contest/beta-round-3/summary/
$N$要素の数列が与えられる。数列内の最小値と最大値をそれぞれ1つ以上含む連続な部分列のなかで、最も短いものの長さを出力せよ。
数列を前から見て、最大値/最小値が出てきたらその時点で一番最後に出た最小値/最大値との距離を比べればよい。
自力AC。難しくない。
$N$要素の数列が与えられる。任意の2要素を取り出したときに必ず片方がもう片方で割り切れるような部分列の最大のサイズを出力せよ。
数列から任意の2要素を取り出したときに必ず片方がもう片方で割り切れるためには、数列をソートしたときに$i+1$番目の要素が必ず$i$番目の要素で割り切れればよい。このような部分列のなかで最大のものの長さはLISと同じ要領で求められて
$DP[i]=i$番目の要素が一番最後になるような部分列の中で最も長いものの長さ
とすればよい。
解説AC。DPを用いた(通常の)LISの求め方には大きく分けて2つあり、ひとつは今回の問題の解法となるO($N^2$)の方法、もうひとつは
$DP[i]=$長さ$i$の部分列が作れるような最小の要素の値
として二分探索で更新するO($NlogN$)の方法である。2つあるなら速いほうだけ覚えておけばいいだろうと思って後者だけ覚えていたら、すべての要素のペア間に順序が定義できる場合にしか使えないことに気付いて終了してしまった。とはいえ、こんなDPはLISを知らなかったとしても解けるべきなので言い訳のしようはない。反省。
$x$軸に平行な$N$個の区間が与えられる。各区間は$x$軸に平行に移動させることができて、そのコストは区間の移動距離に等しい。すべての区間と交差する垂直線が少なくとも1本引けるように各区間を移動させるとき、その最小コストを求めよ。
ある区間を座標$x$を含むように動かすためのコストはこんな形→(\_/)のグラフになっている。これをすべての区間について足し合わせると必ず下に凸な折れ線グラフになり、この関数の最小値が答えとなる。
区間[$l,r$]に対するコスト関数を足すと、全体のコスト関数の傾きが変化する点の集合に$l$と$r$が追加される。傾きが変化する点を1つ通るごとに全体のコスト関数の傾きは1ずつ増え、その2つの中央値の間で傾きが0となる。つまり、これまでに足し合わせた区間の$(l, r)$をすべて集めた集合の中央の2つを$(c_l, c_r)$とすると、区間[$c_l, c_r$]で傾きが0となる(最小値をとる)ことがいえる。
priority_queueなどを利用して座標$c_l, c_r$の値を保持することで、全体のコスト関数の最小値を求めることができる。1つの区間のコスト関数を考えるたびに$l$と$r$の2つの座標を集合に追加しながら、前半の座標が1つめのpriority_queueに、後半の座標が2つめのpriority_queueに常に入っているように調整する。たとえば$[1,4],[5,6],[7,8]$の3つの区間を考えたとき、2つのpriority_queueの状態は $$[1,4,5)\;(6,7,8]$$ のようになる(丸括弧がqueueの出口)。ここで、2つのpriority_queueのtop(この場合は5と6)がそれぞれ$c_l, c_r$となる。区間[$c_l, c_r$]での値は区間を足すたびに容易に更新できて、全体でO($NlogN$)となる。
自力AC。ARC070Eと非常に似ていて、ほぼ同じ問題なのでやり方を知っていた。後から気付いたが、普通に$2N$個の座標をソートして中央値に合わせるシミュレートをするだけでよかった(そして後から解説を読んだらそう書いてた)
'A'と'B'のみからなる長さ$N$の文字列$S$が与えられ、AlexとBenがこれを使ってゲームをする。AlexとBenは、自分の手番で$S$からこれまでに選択された部分文字列のどれとも被らない部分文字列を選ぶ。$S$のすべての要素が選択されるまでこれを繰り返して、最終的に選んだ文字列に含まれる'A'の数の合計が少ないプレイヤーの勝ちである。Alexから行動し、お互いが最適にプレイするとき、どちらが勝利するかを出力せよ。
文字列に'A'しかなければ一度に2つ以上の'A'を取るのは明らかに損であるので、お互いに1つずつ取り合うことになる。文字列に'A'と'B'が両方あるときには'B'があるのに'A'をとる意味はないので、'B'のみからなる区間を選択することになる。文字列中の'B'は'A'によって区切られたいくつかの塊として考えることができて、各プレイヤーは1つの塊の中から好きな数の'B'を取ることができる。最終的に'B'がない状態で手番が回ってきたプレイヤーから'A'を取りはじめることになる。
自分の手番が回ってきたときに'B'の塊が偶数個あるときお互いに1つの塊すべてをとることを繰り返せば自分が最初に'A'を取らされてしまうが、'B'の塊のなかからいくつか残して取る(例えば右半分だけ、など)ことで手番の偶奇をずらすことができる。
このようにして、すべての塊が0になった状態で自分にターンが回ってくることを回避しようとするゲームはNimそのものであって、勝敗は簡単にわかる。'B'を取るフェイズでどちらが勝つかわかれば、後は敗者から順に'A'をひとつずつ取ったときに勝敗がどうなるか(Nimパートの敗者がそのまま負けるか、もしくは引き分けになる)を出力すればよい。
なお、'B'の塊からいくつかの'B'を削除するとき、削除する区間に塊の端を含めない場合には塊が2つに分裂する。これは通常のNimにはない挙動だが、このことによって勝敗に影響が出ることはない。なぜなら、非負整数$x, y, z$について $$x \oplus y = x+y+z$$ が成立するのは$z=0$の場合に限られるためである($x\oplus y \leq x+y$より) 。よって、塊から$z\;(\gt0)$個の石を取り除いた結果$x$個と$y$個に分裂しても、すべての塊の総xorを変えないことは不可能なので、Nimの勝敗に影響はないことがいえる。
解説AC。解説を読んで、それはそうだなあとなってしまった。
$N$個のノードをもつ木が与えられ、すべてのノードは赤か青に塗られている。この木の任意の辺に対して、辺が結ぶノードの色を入れ替える操作を行うことを考える。この操作を繰り返すことで、すべての辺が赤と青のノードを結ぶようにすることができるかどうかを調べ、できる場合には最小の操作数を出力せよ。
前提として、距離が$d$であるような任意の2つのノードのswapは必ず$d$回の操作でできて、$d$回未満ではできない。たとえば $$BBBBRRRR$$ のようなパスがあったとき、 $$BBBBRRRR \rightarrow RBBBBRRR \rightarrow RBBBRRRB$$ のようにして7回の操作で端どうしのswapができる。パスの中の配色がどのようであっても、このような左右で色が別れた領域に分割することで同様にパスの長さ-1回で両端のswapが可能であることがいえる。
これを踏まえて、適当に決めた根(1でよい)からDFSをしながら以下のようなDPを行う。
ノード$x$を根とする部分木のなかに赤が多いときは、赤にしたいノードはすべて部分木内のswapのみで赤にできるはずである。その場合には、青になるはずのノードのうち$delta[x]$個は赤になっている。
テーブルの更新は以下のように行う。 $$delta[x]=sum(delta[y])+wrong[x]\\ cost[x]=sum(cost[y]+|delta[y]|)$$ ここで、$y$は$x$の子ノードであり、$wrong[x]$は$x$を青にしたいが赤になっているときに$+1$、赤にしたいが青になっているときに$-1$となる。そのどちらでもないときは$wrong[x]=0$である。
$delta[x]$は部分木内で赤と青どちらが多いかという意味なので、子ノードについてすべて足し合わせて最後に自分の分を足せばよい。
$x$の2つの子ノード$y_1, y_2$に属するノードどうしをswapするとき、swapしたいノードを$y_1, y_2$に持ってきてから$x$を通して入れ替えることになり、そのコストはそれぞれのノードと$y_1, y_2$との距離の合計＋2である。 $cost[y]$には$y$を根とする部分木内で目的の配色と異なるノードと$y$との距離がすでに含まれているので、結局入れ替えたいノード1つあたり1の追加コストがかかる。余ったノードについても$x$との距離は$y$との距離＋1なので、$cost$の更新は「部分木それぞれの$cost$の合計＋各部分木で配色が誤っているノードの数の合計」となる。
木は二部グラフなので、可能な配色は二通りしかなく、それぞれでの根の$cost$のminが最終的な答えとなる。
解説AC。DFSして根か葉から順番に色を合わせていくんだろうなぁということは分かっていたが、パスの両端swapなどは考察できていなかった。DPの状態の持ち方はどうやったら思いつくのだろうか。