Regionals 2010 :: Asia - Fuzhou

Live Archive 練習会

なんかcoutでACのものがprintfだとWAになった。　→　LiveArchiveの仕様変更に起因する何かっぽい
上記の件を除けば、それなりに色々詰まっていて良いセットだった。
https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&category=384

A - 5098 - Knight's Problem

問題

無限に広い平面でナイトを(fx,fy)から(tx,ty)に動かす最小手数を求めよ。
ただしナイトは(x,y)から(x+mxi,y+myi)に動くことが出来る。

制約

-5000 <= fx, fy, tx, ty <= 5000
mxi,myiの数 <= 10
-10 <= mxi, myi <= 10

mxi + myi > 0
解法

(fx,fy)から(tx,ty)に行くとき、直線(fx,fy)-(tx,ty)から極端に離れるところを経由する意味は無い。
具体的には、-10 <= mxi, myi <= 10という制約から、直線(fx,fy)-(tx,ty)からマンハッタン距離で30くらい以上離れることを考える必要がない。
これにより探索空間が減るので、普通にBFS出来る。

B - 5099 - Nubulsa Expo

問題

無向グラフが与えられる。
ソースが決まっていてシンクが決まってないとき最大流の最小を求めよ。

制約

頂点数<=300
辺数<=50000

解法

無向グラフの全域最小カット。
使ったのはUAPC以来。

C - 5100 - Shade of Hallelujah Mountain

問題

三次元空間に、平面と点光源、凸多面体が与えられる。
このとき、平面に出来る影の面積を求めよ。
ただし、無限に影が出来るときはInfiを出力せよ。

制約

多面体の頂点<=100

解法

ヒントにもあるように平面がz=0、点光源と凸多面体がz>0になるように座標変換（平行移動と回転と鏡像変換）する。
そうしたら凸多面体の各頂点をz=0に射影して凸包取って面積を求める。
このとき点光源よりz座標が大きい頂点と小さい頂点があったらInfiになる。

D - 5101 - Math teacher's homework

問題

m1~mnまでのn個の整数と整数kが与えられる。

  • x1 ^ ... ^ xn = k
  • 0 <= xi <= mi

となるような整数xiの組み合わせ数を求めよ。

制約

n<=50
0 <= k, m1, ...mn　<= 2^31 - 1

解法

解けなかったので先輩に解法を教えてもらった。感動した。

solve(m, k)という関数を作る。
mの中で一番多きなものをm1とすると、m1の最上位ビット(ビットaとする)を使うか使わないかで場合分けする。
使わない場合、m1においてaより下位のビットは自由に決めることができるので、m1以外のmでビットaだけを気にしながらDPすることで答えを求めることが出来る。
使う場合、m1におけるaより下位のビットにまだ制約があるので、m1とkのビットaを反転させ、solveを使って答えを求める。
solveの答えはこの2つの場合の和になる。
mとkが全て0のときはsolveは1を返す。
solveが呼ばれるごとにm[]において立っているビットが1個少なくなっているので、solveは最大でも32*50回しか呼ばれない。

E - 5102 - Fermat Point in Quadrangle

問題

四角形が与えられるので、ある点をPとしたときPと四角形の各頂点との距離の和の最小値を求めよ。

制約

0<=座標<=1000

解法

四角形のフェルマー点は対角線上にあるようなので、対角線上で三分探索。

F - 5103 - Computer Virus on Planet Pandora Description

問題

ABDDEKKKKKKKG
が
AB[2D]E[7K]G
というふうにランレングス風に文字列（プログラムと呼ばれる）が与えられる。
また、パターン文字列として、n個の文字列が（普通に）与えられる。
このとき、プログラムに現れているパターン文字列の数を求めよ。
現れているとは、パターンがプログラムの部分文字列もしくは逆順にしたプログラムの部分文字列になっていることを言う。

制約

n<=250
パターンの長さ<=1,000
プログラムの長さ<=5,100,000

解法

Aho-Corasick
計算量が微妙なので、少し高速化する必要がある。
プログラムを逆順にするのではなく、逆順にしたパターンをパターンに加えるという工夫が考えられる。

G - 5104 - Farm Game Description

問題

N個の製品があり、1ポンドあたりの価値と、今何ポンド持っているかが与えられる。
また、ある製品をある製品に変換することが出来る場合もあり、その規則も与えられる。
規則は1ポンドのa(i-1)をb(i)ポンドのa(i)に変換することが出来るというような形式で与えられる。
ただし、aからa'に変換することができるときa'からaに直接もしくは間接的に変換できることはない。
このとき、持っている製品の価値の合計を最大いくらにできるか。

制約

N<=10000
規則の数<=50000

解法

dp[i] = 1ポンドの製品iを変換して（もしくは変換しないで）得られる価値の最大
規則のグラフはDAGになる。
よってトポロジカルソートが出来て、DAGの先のほうからdp[i]を更新することが出来る。

H - 5105 - Selecting courses

問題

N個のコースをできるだけ登録したい。
各コースは(Ai,Bi)の時間だけ登録をすることが出来る。（単位は分、開区間）
また、ある時間に登録をしたらその時間から5分おきにしか登録ができない。
例えば、1分10秒に登録したら、6分10秒、11分10秒、・・・というタイミングで登録をするチャンスを得る。
このとき、最大で何個のコースを登録できるか。

制約

N<=300
0<=Ai

解法

登録をはじめる時間として、１分1秒で試したとき、1分2秒とかで試しても結果は変わらないので、5回試せばいいことになる。
それぞれ、貪欲や二部マッチングで最大で何個のコースを登録できるか調べることができるので、それらの最大を求める。

I - 5106 - Let the light guide us

問題

N×Mのマスがある。
各マスはt[i][j]とf[i][j]が設定されている。（どちらも整数）
各行から1つのマスを選んで、選んだマスのt[i][j]の和（コスト）を最小にしたい。
ただし、i行目で(i,j)を選んだ場合、i+1行目では、

j-k <=f[i][j]+f[i+1][k]

を満たす(i+1,k)しか選ぶことができない。

制約

1<=N<=100
1<=M<=5000

解法

dp[i][j] = i行まで見て、(i,j)を選んだときのコストの最小値
として
dp[i][j] = min{dp[i-1][k] + t[i][j] | |k-j|<=f[i-1][k]+f[i][j]}
で解けるが、O(NM^2)となる。
よく考えるとMの部分をSegTreeを使うことによりlog(M)に落とすことが出来る。
以下のように考える。

  • dp[i][j]を求めるとき、i-1行目のSegTreeの[max(0,j-f[i][j]), min(M-1,j+f[i][j])]部分の最小値を求め、それにt[i][j]を足した値をdp[i][j]とする。
  • dp[i][j]が求まったとき、i行目のSegTreeの[max(0,j-f[i][j]), min(M-1,j+f[i][j])]部分をdp[i][j]で更新する。

これを実現するには、区間のminの更新と、区間のminの取得が可能なSegTreeを作る必要がある。
これには蟻本にも載っている区間に加算するSegTreeを参考にすることが出来る。

J - 5107 - A hard Aoshu Problem

問題

A~Eで構成された文字列が3つ与えられる。
A~Eにはある1桁の数字を割り当てる。
同じ文字には同じ数字を割り当てる必要がある。
また演算子opを+,-,*,/から一つ選ぶ。
このとき、３つの文字列をS1,S2,S3としたとき、
S1 op S2 = S3
という等式を作る。
こうして作られる等式のうち、等式が成り立っているものの個数を求めよ。

制約

文字列の長さ　<= 8

解法

全部試すだけ。