Code Forces 30

今回からDiv.1だそうで。(実際にはDiv.2の大会に参加できないという制約があるだけだけど。)

A

整数A,B,Nが与えられるので、A*X^N=Bなる整数Xが存在すれば、それを答えよ、という問題。

Xの絶対値はBの絶対値以下であることと、Xをかけていく過程で絶対値が大きくなってはいけないことから、全部探索するだけ。場合分けも特にいらないはず。

B

生年月日が順不同(どの数字が年、月、日に相当するか分からない状態)で与えられるので、目的の日に18歳以上である可能性はあるかどうか答えよ、という問題。

年に一番小さい数字を割り当てて...、とやりたくなるところをこらえて全通り試す問題。(日付として不適切なものを切り捨てないといけないので。)後は18年差分があるかどうかを判断する。辞書順なので、厳密な比較は必要ないので、重み付けを適当にやって比較する方が楽かも？

C

N個のものから、できるだけ多くの価値になるように選択したいが、ものには場所と時間が指定されていて、その時間にその場所にいないと選択できない。つまり、あるものを選択した後に別のものを選択するには、その二つの間の距離を時間の差分の間に移動できないといけない。このとき最大の価値を答えよ、という問題。

単純に時間の早いものから順に選択していくDPなので、一番簡単な問題のはず。

D

それぞれの間に道が存在するN都市が与えられる。一つを除き同一直線上に並んでいる状況の配置で、初期位置が与えられるので、すべての都市を巡回する際の最小距離を求めよ、という問題。

同一直線上に並んでいるのではない点のときは、直線上に降りる位置を決めれば後は直線を最短にスイープするだけ。同一直線状に並んでいるときはどの点にいるときに直線から抜け出すかを考慮すればいいはずなんだけれど、その時に可能なパスが二通りあるので、それをうまく拾わないとダメそう。...という感じで場合分けが必要な面倒系問題。

E

文字列が与えられるので、部分文字列A,B,Cを重複がないようにしつつ、Bが回文でAを反転させるとCになるというものを取り出したい。このとき、三つ組の長さの合計が一番長くなるものを答えよ、という問題。

元の文字列がとても長いので、高速に文字列探索できるアルゴリズムを使いつつ、真ん中の回文の長さの最大値を効率良く求めるとか？良く分からない。