301.1

250

4つの状態を取るものについて、状態遷移が与えられる。状態遷移を圧縮して記述するとき、辞書順で先頭のものを答えよ、という問題。ただし長過ぎるなら途中で打ち切る。

状態遷移はユニークに決まるので、貪欲に選択するだけ。同じ状態が続くのをC??のようにコマンドCが??回続く、という表記をするので、辞書順で先頭になるようにするには、99が後ろに付くようにする。このとき0を書かないように注意する必要があるくらい。(というか0を書いてしまった。)ただ実装が面倒なだけの問題ともいう。

450

N人の囚人について、各二人のペアをつなぐ鎖の長さが与えられる。このとき任意の二人の囚人の間の距離の最大値を求めよ、という問題。

ある囚人ペアi,jについて、他の囚人kが存在し、d(i,j)>d(i,k)+d(j,k)ならば、d(i,j)を実現することはできない。このような規則を収束するまで適用していく。Warshall-Floydと同じ要領なので、N回やれば停止すると思う。後は一番長い距離を答えておけば良い。

1000

文脈自由文法が与えられるので、目的の文字列を生成するパターンがいくつあるか答えよ、という問題。

メモ付き探索するだけだと思う。もちろん単純にやると効率が悪いので、終端文字列を含むならそこで分割してやる必要がある。なお、非終端文字一つからなるような規則は存在しない。すべての非終端文字が1文字以上の終端文字を生成するのを考慮に入れれば多少ましになるかも知れない。時間がないし専門外なので実装していない。