Regionals 2011 :: Asia - Daejeon

Live Archive

会津の練習会
http://rhodon.u-aizu.ac.jp:8080/arena/room.jsp?id=625
http://livearchive.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=513
最大流自力で解きたかった…（本番はほとんど考えなかった）
CとIのDPが面白かった

5839 - Block Compaction

下に動かすときはy座標でソートして下の方から動かせるだけ動かす
左に動かすときはx座標でソートして左の方から動かせるだけ動かす
これを普通に繰り返す。
ソートすることによりO(n^3)に収まりそうだけど、どうだろう。

5840 - Chemical Products

ABとBCを決め打ちすればCAを最大どれだけ作れるか分かるので全部試す。

5841 - Color Length

dp[i][j] = １つ目の文字列をi文字目、２つ目の文字列をj文字目まで見たときのコストの最小
ある文字についてのコストは、
最後に現れた位置 - 最初に現れた位置
となる。
そこで、今加えようとしている文字が最初に現れているなら、その位置をマイナスし、
最後に現れているなら、その位置をプラスするという処理をする。

5842 - Equipment

Kが5以上なら全てのパラメータについて最良のものを選ぶことが出来る。
4以下のとき、O(N*K*3^5*5)のDPをした。
DPとかしない別の方法でも出来るっぽい。

5843 - Furniture Factory

最大流。
グラフはソースとシンクと時間ノード、注文ノードを持つ。
ソースから時間ノードに容量mのエッジを張る。（各時間にはm人が働くことが出来る）
時間ノードから注文ノードに、対応する時間に処理できるなら容量1のエッジを張る。（１つの仕事は単位時間に１人で処理する）
注文ノードからシンクに容量w[i]のエッジを張る。（w[i]流れたらその注文は成功）

5844 - Leet

Standard Englishの各文字について、Leetを1文字~ｋ文字対応させることを全部試してもk^n。
ということで、適度に枝狩りしつつ全探索。

5845 - Laptop

Komakiさんのソースを見て解きました。感謝。
rもしくはdの値でソートする。
すると、制約(2)からこの順番でタスクをこなせばいいことが分かる。
まず、後ろからループを回して出来るだけ遅い時間にタスクを配置したときどの時間になるか求めておく。
制約(3)からこのようにしたとき必ず区間の制約を満たすスケジュールとなる。
次に、前からループを回して出来るだけ前のタスクと繋がるようにタスクを配置する。
もしそれが出来ない（置こうとするとrより前に置くことになる）場合、先ほど求めた出来るだけ遅い時間にタスクを配置する。このとき答えをインクリメントする。
この貪欲の考え方は、

  • タスクを繋げられるなら繋げる
  • 繋げられないなら出来るだけ遅く置くことにより、後で出来るだけ繋げられるようにする

というもの。

5846 - Neon Sign

bitsetを使ったO(N^3)で通った。
以下O(N^2)の解法。
各頂点について、そこから伸びる赤い辺の数と青い辺の数の積を求める。
この積は、その頂点から見たとき明らかに２色で構成される三角形の数に等しい。
各頂点で積を考えた場合、２色で構成される三角形はそれぞれちょうど２回ずつカウントされることになる。
よってこの積の和を２で割ったものを全体の三角形の数から引けば良い。

5847 - Pizza Delivery

中国語のブログにあったコードを解読した。
問題は、Taipei2008H[id:sune2:20120912:1347459032]とほぼ同じ。
この問題の場合は、Taipeiのときのように家を左側と右側に分けてソートするとやりやすい。
ただし、Taipeiのほうは時間を1000まで考えればよかったのに対し、こちらは100000まで考えなければならない。
よって時間をキーにできない。
そこで、後いくつの家を訪れるかという値を状態に加える。
後k個の家を訪れるとき、距離dを移動するとする。
このとき、この移動によって生じるペナルティは結局k*dとなる。
このアイディアを用いることにより、DPの遷移のコストを上手く求めることが出来る。
以上より、
dp[i][j][k][0/1] = 左にi個、右にj個の家に配達し、あとk個の家に訪れ、[左端/右端]にいるときの最大利益
でDPする。

5848 - Soju

分割統治した。
まずICとPCそれぞれy座標でソート。
ICの点のy座標の中央値で分けることと、PCの点のy座標の中央値で分けることを交互に繰り返す。
ここで、２つに分けたものをAとBで表す。
求める最小値は、

  • Aの中での答え
  • Bの中での答え
  • AのICの点とBのPCの点の最小距離
  • AのPCの点とBのICの点の最小距離

のどれかになる。
3つ目と4つ目については、ICとPCそれぞれの点と、ある適切な点Oとの最小距離を考えることで求めることが出来る。

5849 - Traveling Spiders

5850 - Turtle

やるだけ