Regionals 2010 :: Asia - ChengDu
https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&category=381
A - Balanced Number
問題
[x,y]に含まれるbalanced numberの数を求めよ。
Balanced Numberとは、ある桁を中心として他の桁の値を重さと見たときのモーメントが吊り合っている数である。
制約
0<=x<=y<=10^18
解法
もちろんsolve(y)-solve(x-1)として解く。
桁DP。
dp[桁][中心の桁][合計][less][zero]
0が少し曲者で、00000とかのとき、どこを中心としても吊り合ってしまうことからどうにかしなければならない。
dpのときzeroフラグを利用して全て0みたいなのはカウントしないようにした。
ただ、普通に桁の数だけ引けばよかったような気もする。
ここで合計は多くとも2000くらいで抑えられるはずなので状態数は18*18*2000*2*2くらい。
B - Battle over Cities
C - Binary Number
やるだけ
D - Detector Placement
問題
レーザーの発信源、レーザーが通る他の場所、三角形のプリズムの頂点、プリズムの屈折率が与えられる。
このとき、レーザーがx軸にぶつかるならそのときのx座標、ぶつからないならErrorをチュス直せよ。
ただし、レーザーの発信源、プリズムはy>0に位置し、発信源はプリズムの外に位置する。
またプリズムの頂点にレーザーが当たることはなく、全反射も起こらない。
また、空気の屈折率は1.0とする。
制約
座標は1000とか
解法
実装するだけ。
屈折は入ってくる角度に注意して場合分けする。
レーザーの半直線を表現するのに、INFに飛ばして線分として扱うとかしてたら誤差で死亡した。
ここで半直線ライブラリを作った。
E - Double Maze
問題
6*6の迷路があり、スタート、ゴール、穴、壁がある。
最初ボールがスタートにあり、ゴールに持っていくことが目標。
ボールに上下左右いずれかのコマンドを送ると、その方向に動く。
ただし、壁があったら動かず、穴に落ちたり外側に出たりしたら駄目。
２つの迷路が与えられるので、両方を同時に解く最短コマンド列を求めよ。
コマンドは２つの迷路に同時に送られ、ボールはそのコマンドに沿って独立に動く。
複数あれば辞書順最小。
制約
解法
BFSするだけ。
辞書順はDLRUの順に動かせば良いだけ。
注意点
- 壁の判定をしてから穴の判定や外側に出る判定を行う
- スタートとゴールが同じ場所にあることがある
F - Error Curves
問題
二次関数がn個与えられる。
それらのmaxをとった関数をFとするとき、
Fの最小値を求めよ。
制約
T<=100
n<=10000
解法
f,gが凸関数のときmax{f,g}が凸関数であることから三分探索。
立命合宿阪大セットの曲線の長さ求めるやつが頭から離れず思いつかなかった。
CF#82Eが関連っぽい。
http://codeforces.com/blog/entry/2493?locale=en
G - Go Deeper
問題
要素数mの数列a,b,cが与えられる
a[i],b[i]∈{0,1,...n-1}
c[i]∈{0,1,2}
であり、要素数nの{0,1}数列xをうまく決めて、以下を満たすz(<=m)を最大にしたい。
x[a[d]] + x[b[d]] != c[d] (for all d < z)
このときzの最大値を求めよ。
制約
0 < n ≤ 200, 0 < m ≤ 10000
解法
二分探索＋2SAT。
二分探索でzを決めて、
0~z-1の制約を用いて2SATを構築し、充足可能かどうかで分岐していく。
2SATの変数はn個でx[i]に対応する。
各制約はc[i]によって形が変わる。
- c[i]=0
- x[a[i]] or x[b[i]]
- c[i]=1
- not (x[a[i]] xor x[b[i]])
- c[i]=2
- ~x[a[i]] or ~x[b[i]]
H - Jenga
I - Rescue
制約
魔力がm1,...,mnな石が１列に並んでいる。
あるiを選んでスキルを発動すると、m1~miの石にダメージを与えることが出来る。
石j(j<=i)に与えられるダメージはmax(0, (j-i)*(j-i)*p)である。
与えられたダメージがmiを超えると石は破壊される。
k回のスキル発動で全ての石を壊したい。
このときpとして必要な値の最小値を求めよ。
解法
1 ≤ n ≤ 50000, 1 ≤ k ≤ 100000
制約
二分探索+貪欲+差分処理
二分探索でpを決め打ちする。
ここで、残っている石で最も右のものをiとすると、スキル発動ではiを選ぶべきである。
なぜなら、iより小さければ石が残ってしまうし、iより大きければダメージが弱くなるから。
そこで右から石についてループを回していき、現在与えられたダメージが魔力以下なら
その石を破壊できるまでスキル発動を繰り返すという処理を行う。
ここで、現在与えられたダメージの計算は普通にやるとO(n)かかってしまうが、
差分処理を行うとO(1)で行うことが出来る。
これはKUPCのAcceralation of SNSと似ている。
二次関数なので差分の差分は定数であることを利用する。
J - Similarity
問題
大文字アルファベットからなる要素数nの列Aがある。
同様の列Bがm個与えられる。
このとき、Bのアルファベットを適切に入れ替える（例えばXをYに変えたならYは別のアルファベットに変えなければならない）ことにより、AとBのsimilarityを最小にしたい。
ただし、AとBのsimilarityはsum(Ai==Bi)/nで定義される。
このときsimilarityの最小値を求めよ。
制約
0 < n < 10000
0 < m < 30
解法
アルファベットの変換は、アルファベットをアルファベットにマッチングさせるイメージ。
そしてあるアルファベットをあるアルファベットに変換させることによって類似度がどれだけ大きくなるかは事前に求めることができる。
よって最大重み最大二部マッチングで解ける。
