薄々感づいてた(or確信してた)人もいると思いますが、SRM570のwriterをやっておりました。
問題を調整してるうちに変則セットになりました。すみません・・・ CF頑張ってください！
まあまあ、とりあえず簡単な解説でもどーぞ
Div2easy
N本の箸の長さが与えられるので、同じ長さの箸のセットを何個作れるか。
ソートしてペアを取っていくなど。
Div2medium
N個のコマンド「a[i]歩進んでa[i]*90度右に回る」からなるメソッドAをT回繰り返したときの座標を求めよ。
各コマンドをO(1)くらいで処理しながら露骨にシミュレーションすれば良い。
最近はD2mを簡単にしようという動きがあるらしく、簡単にした。
Div2hard
Div1mediumの簡単バージョン(設定わりと違うけど)。サーバがどうとか書いてあるけど要するに、
ある木の部分木の個数を求めよ。
典型問題っぽい雰囲気。適当に根を選んで根付き木にして、
dp[i]: 頂点 i 以下の頂点からなる、頂点 i を含む部分木の個数
という木DPをすればいい。
Div1easy
Div2mediumのTが大きいバージョン。周期が４なことを利用して頑張る。元ネタは当然HOJ。H言語にするとこんな感じ。
f(X):sf(X-1)r g(X):f(a[0])f(a[1])...f(a[N-1])g(X-1) g(T)
ちなみに"Herb"は"Herbert(男性名)の略称"らしいです。
Div1medium
木構造をしたネットワーク上のサーバを２グループに分けて、各グループ内のサーバだけで通信できるようにケーブルを増やす。 各サーバにはケーブルをさすための空きスロットが１つずつあり、空きスロットをひとつ増やすためにはコストが１かかる。 全てのサーバの分け方が同じ確率な時、必要なコストの期待値を求めよ。
最初もっと簡単だったんですが、一行で解けることが発覚してこうなりました。
１ステップずつやっていけば解ける系(超能力はいらない)の問題だと思います。
まず、全ての分け方は等確率なので、１つのグループにおけるコストの期待値だけを求めて最後に２倍すれば良いです。
次に、サーバの分け方を固定してそのときに必要なコストがどうなっているかを考えます。で、調べてみると
あるグループ内の 頂点数をv、辺数をe、連結成分の個数をc (=v-e) とすると必要なコストは、 max(0,2*(c-1)-v) ( = max(0,v-2e-2))
となっています。ということは連結成分が i 個、頂点の数が j 個となるような分け方の個数が分かればいいです。これは木DPをすれば求まります。
やり方によってO(N^2) ~ O(N^5) くらいまであります。(全部間に合います)
O(N^5)は「連結成分の数」「頂点の数」「頂点 i を使うかどうか」でDPすれば良くて、
O(N^3)は「2*(c-1)-v」の値と「頂点 i を使うかどうか」でDPすれば良いです。
O(N^3)のDPをちゃんと書いたら、頂点 v における計算量は、部分木のサイズをa,b,c,d...とすると、
a*b+(a+b)*c+(a+b+c)*d..... = a*b+a*c+a*d+...b*c+b*d........
みたいになっていて、これはLCAが頂点 v である頂点のペアの個数です。だから、全ての頂点での更新回数を足し合わせると結局O(N^2)となっています。(りんごさんに教えてもらった)
O(N^5)のDPもちゃんと書けば多分O(N^4)になっています。
O(N^2)のwriter解をpracticeに上げました。状態の値が負になるとDPしにくいので50を足してあります。
木DPの計算量の見積もりといえばBuilding 2が面白いです。
Div1hard
問題文はtopcoderの方でお願いします。
各セルをまずチェス盤みたいに黒白に色分けします。
(説明のために番号を付けました。)
で、セル i の中心から縦向きに線路を敷くことを表す頂点を「i 縦」、横向きを「i 横」とすると、
こんなグラフの最小費用流を求めれば良いです。
辺の最大流量は全て1で、コストは基本的に0(Curvyがいるセルのところの赤い辺は1)です。
