385.1

なんとも...。やるだけ？

250

文字列配列が与えられるので、幅Wの領域に適切に配置せよ、という問題。

配置方法は配列長Nに対して高々2^N通りくらいしかないので、全部試してやるだけ。

500

二次元盤面上に配置された部屋の連結状態が与えられる。現在の部屋と同じ行の部屋を90度回転させ、同じ列の部屋を90度回転させるという操作を移動と同じコストで行うことができる。左上から右下までの移動にかかる最小時間を答えよ、という問題。

現在位置と回転させた行と列の状態を覚えておいてBFSするだけ。

1100

A=B+Cとなるような三つの無限整数配列を考える。それぞれの配列について繰り返しが検出されるまでの最小の長さが与えられるので、そのときのA,B,Cとして可能なものを答えよ、という問題。可能なものが複数ある場合はA,B,Cの順で辞書順に最初のものを答える。

それぞれの繰り返しの長さから、理論上可能かどうかが計算できる。後は貪欲に埋めてみれば取り敢えず答えがあるはず。なるべく頭の方から決めていくこととする。決めないと行けない長さはA,B,Cのうち一番繰り返しが長いもの。他のは繰り返しになるので、該当する位置のものを引っ張ってくる。

まず、Aの先頭を辞書順で最初になるように決めてやる。こうするとB,Cの該当する位置のものも必然的に決まる。(ここではBが辞書順で最初になるように決めてやる。)これによって、A,B,Cの長さが違えば、他の場所がいくつか埋まる。(同じだったら、最後の文字以外は同様に決めていってやればいい。面倒なら場合分けして追い出しても良さそう。)

できるだけAを辞書順で最初にしたいので、埋まってないAの位置を順番に見ていく。もしそのAの位置に該当するB,Cに決まっているものがあれば、それを考慮してAを決定する。(必然的にBまたはCの決まっていないものも決まる。)これにより影響が出る部分も埋めてやる。もし途中で、B,Cの両方が決まっていないことがあれば、それは無視する。(Aが決まってもB,Cで帳尻合わせできるので、保留にしておいて、後ろのAを先に決めてやって、それから派生させる。)というのを適当に優先順序決めてやれば良さそう。

本当はAを辞書順で最初になるように決めていく過程で、B,Cとして可能なものがあるかどうかを適当に判定する方法があれば、それを使うべきなんだろうけれど...。かなり自由度が高いので、よほどのことがない限り、解がなくならなさそうなので、余り考えてない...。