Regionals 2011 :: Asia - Chengdu

Live Archive

https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&category=520

A - Alice and Bob

B - Break the Chocolate

問題

N*M*Kの板？チョコレートがある。
これを1*1*1のピースに分けたい。
分け方には手を使う方法とナイフを使う方法がある。
手を使う方法はピースを１個ずつ折るしか無い。
ナイフを使う方法は何個でもピースを１回で切る事ができる。
ナイフを使える場合と使えない場合でチョコを分けるための最小回数を求めよ。

制約

1 ≤ N,M,K ≤ 1000

解法

ナイフを使えない場合は、N*M*K-1。
使える場合は、\lceil \log_2 N \rceil + \lceil \log_2 M \rceil + \lceil \log_2 K \rceil。

C - Construct the Great Wall

D - Disney's Fastpass

問題

ディズニーランドで、ファストパスをうまく使って興味のあるアトラクション全てに乗るのにかかる時間の最小を求めよ。
パークは頂点数N,変数Mのグラフで与えられる。
興味のあるアトラクションはK個。
i番目の興味のあるアトラクションはPiに位置し、普通はTi分、ファストパスがある場合はFTi分の時間がかかる。
ファストパスがある位置はNi個であり、それはFi1,...,FiNに位置する。
複数のアトラクションが同じ位置にある場合もある。
グラフは連結である。

制約

1 ≤ N ≤ 50
0 ≤ K ≤ 8

解法

まず全点対最短距離を求めてg[i][j]とする。
各アトラクションの状態を
0 -> 訪れてないし、ファストパスもとってない
1 -> 訪れてないが、ファストパスをとった
2 -> 訪れた
の３種類とする。
これをエンコードした整数をSとすれば、状態T(T

  • 普通に(S,j)に遷移
  • iでファストパスを取って(T,i)に遷移
  • iでアトラクションに乗って(T,i)に遷移

を実装すればいいだけ。
O(N^3 + 3^K * N^2)。
ちなみに3^8 * 50^2は16402500。

E - Eliminate the Conflict

問題

アリスとボブがN回じゃんけんする。
アリスはボブが何を出すか知っている。
アリスはA回目とB回目について

  • K=0 : 一緒の手を出さなければならない
  • K=1 : 違う手を出さなければならない

という制約をM個課せられる。
アリスは一回でも負けるか、制約を満たせなければ負けとなる。
このときアリスに勝つ見込みがあるか判定せよ。

制約

1 ≤ N,M ≤ 1000

解法

ボブの手から、アリスがi回目のじゃんけんで出すことが可能な手がどれか（２個）分かる。
そこでPiが真なら１個目の手を出し、~Piが真なら２個目の手を出すとみなすことで2SATを用いることが出来る。
M個の制約について、

  • K=0 : Piで出す手とPjで出す手が違う　→　~Pi∨~Pj　（他の組み合わせ(Piと~Pjとか)も同様）
  • K=0 : Piで出す手とPjで出す手が同じ　→　~Pi∨~Pj　（上と同じ）

という項を考えて2SATを解けば良い。

F - Fruit Ninja

問題

円がN個ある。
直線を引いたとき交差する円の数の最大値を求めよ。

制約

1 ≤ N ≤ 1000

解法

答えとなるような直線は、交差する円の数を変えないままある円に接するように移動することが出来る。
そこで各円について接線の角度で平面走査する。

G - GRE Words

問題

N個のワードが入った順序付き単語リストがある。
単語リストから単語をいくつか消して、全ての連続する単語について、1つ前の単語が次の単語の部分文字列になっているようにしたい。
また、各単語には価値w[i]が割り当てられているので合計価値の最大値を求めよ。

制約

1 ≤ N ≤ 2*10^4
文字列の長さの合計 ≤ 3*10^5

解法

dp[i] = max{ dp[j] + w[i] | (s[j]はs[i]の部分文字列) }
でmax{dp[i]}が答え。
部分文字列となるワードを見つけてくるのはAho-Corasickを使う。
初めに全部のワードでTrieを構成しておく。
現在のワードをマッチさせて、なんかの文字列とマッチしたらそのDPの値を見るという感じ。
計算量は多分O(N^2+sum_of_length)
あとcin使うとWAするっぽい？

H - Holiday's Accommodatio

問題

木があり、各頂点にひとりずつ住んでいる。
各人は、自分以外の頂点に移動する。
ここで、2人以上の人が同じ頂点に移動することは許されない。
このとき、全員の移動距離（最短距離）の合計の最大値を求めよ。

制約

2 ≤ N ≤ 10^5

解法

各辺に対して、一方の側にいる人の数をA,もう一方の側にいる人の数をBとすると、
min(A,B)人をスワップすることが出来る。
そこで、sum{min(A,B)*2*辺の長さ}が答え。

I - Isabella's Message

ただの実装問題

J - Ji-Tu Problem