GCJ 2012 Round 2

相変わらず...。

A

ロープを使って、ある位置から目的の位置まで移動することを考える。ロープは途中に何本かあり、ロープの支点と長さが与えられる。現在の位置と支点を挟んで反対側までロープを使って移動することができ、途中にある任意のロープを一本掴むことができる。使っているロープと掴んだロープの二本をうまく巻き取ることで、使っているロープの支点と掴んだロープの支点の間の点に移動することができる。(もちろん新たに掴んだロープが短い場合は、掴んだロープの支点側に移動することになる。)現在位置を更新して、新たに掴んだロープで同様に移動していくとき、目的地に到達できるか答えよ、という問題。

結局、あるロープについて、開始地点をどれだけ支点から遠ざけて使うことができるかについて考えれば良い。やるだけ。

B

いくつかの円を、指定された矩形の中に中心が来るように配置したい。任意の二円が衝突しないような配置を求めよ、という問題。

かなり制約が緩いので、正方形とみなして敷き詰めても通る模様。

C

N本の柱が並んでいる。一番上から見たときに、一番大きく見える柱の番号が与えられる。(同じ高さの場合は手前のものが与えられる。)このような柱の高さとして考えられるものを一つ答えよ、という問題。

一番奥の柱を一番高くする。その柱が一番高く見える柱を子にして、木構造を作る。遠い方から順に傾きを1ずつ大きくして配置してやれば、親子間で制約は満たされる。一番遠い子には親よりと同じ傾きを与えて良い。木構造が作れない場合は矛盾があるので、例外処理してやる。

D

現在位置が分からない状況で、二次元盤面上を下右左に移動することを考える。目的地に到達可能な点すべてについて、ある移動シーケンスで目的地に到達できるか否かを答えよ、という問題。

左右に移動して、適切な位置を決め、下に移動する、という処理を延々と繰り返す。なので、到達可能な点を横方向に連続な区間ごとに分けて考える。後は、右端からK個左、あるいは左端からK個右、といった状況で移動することで、縦方向のマージを進めていくことを考えて、最終的に目的地に移動できるかどうかを判定する。(コードになるかどうかは分からない...。)