Codeforces 124

正答者数で配点が変動するシステム。補正としては適切な気もするけれど、順位変動が凄く気持ち悪い。

A

ある文字列の部分文字列(連続である必要はないが順番を変えてはいけない)のうち、辞書順で一番後ろのものを答えよ、という問題。

後ろから見ていって、直前に追加した文字以上の文字があれば追加していき、最後に反転して出力する。基本的には、できるだけ辞書順で遅い文字を探索して、追加して、その最後からは辞書順で次に遅い文字を...とやれば同じ。

B

ある迷路を上下左右に無限に連結してできる無限迷路について、開始地点から無限に遠くまでいけるか否かを答えよ、という問題。

座標を幅と高さで法をとりながらBFSするだけ。ただし、到達した点については、そのときの実際の座標を覚えておいて、それと違う値で到達するかどうかを吟味する。違う値で到達できるということは、その差分の移動を無限に繰り返すことができることを意味している。

C

二次元空間上にある点に木のノードをマップして線分でつなぐとき、交差が発生しないようなレイアウトを答えよ、という問題。

適当な点を選び、木のルートを割り当てる。次に任意の点を最初の子に割り当て、時計回りに子のノードを割り当てるという操作を繰り返す。親から子への角度を覚えておかないと、親から子への線分をまたぐので注意が必要。後はやるだけ...。

D

連続な部分文字列に長さD以上の回文を含まない文字列のうち、ある文字列よりも辞書順で後ろのもののうち最初のものを答えよ、という問題。

辞書順でダメな位置が決まれば、それ以降はかなり貪欲に作れそう？まじめな回文判定を入れると大変なので...。

E

到達せず。