283.1

結構いいセットのような気がする。600>>>1000なのはさておき。関係ないけどフォントがおかしいのでスタイル作るか...。

300

N個の点がある状況で、できるだけ多くの点が距離D以内にあるような直線を引くとき、その点数を答えよ、という問題。直線は任意の位置を通るが、傾きは45度か90度のみ。

すべての点について、-Dと+Dで区間グラフを作り、一番重なりが多い所を求める。(45度傾いた直線だと区間の幅はルート2倍になる。)

600

整数列AとMが与えられるので、A[0]!^(A[1]!^(....))%Mの値を求めよ、という問題。

A%Mがループすることを利用する。小さい範囲ではループしなかったりするので、明らかにその範囲にないことを確認すれば、再帰的に適用できる。その範囲にある場合には小さい値なので計算できる。なお、A[i]が1または0ならばそれ以降は見ないで問題ない。(見ると挙動がおかしくなった。)

綺麗にサックリ書ける気がしない。

1000

禁止文字列がいくつか提示されるので、それを含むようなN文字以下の文字列は何通りあるか答えよ、という問題。

取り敢えず禁止文字列のうち、他の禁止文字列を含むものは無視する。(その文字列にマッチするときには、もう一方が必ずマッチしているので。)このとき同一の文字列があることに注意する。

後は禁止文字列群の接頭辞集合を状態として、状態遷移行列を作成する。終了状態からは外に出ないようにして、後は行列乗算を行うだけ。

すっきり綺麗に書ければ簡単なのだけれども...。