385.1

SRM納め。不完全燃焼。

250

複数の単語を_を間に入れて整形する。作成したい文字幅が与えられるので、_が偏らないように整形したとき、アルファベット順で最初のものを答えよという問題。_が連続する回数の最大値と最小値の差は高々1である。

_の入れられる数を計算して、全パターン試す問題。あるいは、_を入れるとアルファベット順で前になる箇所に順次入れていく問題。

500

十字路か上下・左右の道からなる迷路を、今自分がいる点とx座標が同じ点、y座標が同じ点を90度回転させるという操作をしながら移動するとき、左上から右下まで移動するのにかかる時間を答えよという問題。

各行・列について、90度回転しているかどうかという状態を覚えておくと、N行M列で、2^(N+M)状態になる。これに現在の座標を追加した状態について、DPすればいいらしい。状態の計算時に、毎回盤面を生成したところTLEだった。

1100

ある循環しない文字列の、無限回数繰り返しからなる文字列を考える。また、アルファベットの加算をmod26で行うとき、二つの無限文字列の和から、新たな無限文字列を作成することができる。このとき、特定の長さの二つの無限文字列から、指定された長さの無限文字列を作成し、アルファベット順で最初のものを答えよという問題。答えがない時はその旨答える。

二つの元の無限文字列から、i番目の文字とj番目の文字の和が一致するとかしないとかで制約を列挙して、それを解くといいんじゃないかなぁと漠然と思ったり。単純にこういうアプローチだとTLEしそうだけれども。