211.1

中途半端にストーリーを作ろうとして問題が無駄に長くなっているひどいセット...。読解力のテストと実装力のテストともいう。得るものは非常に少ないので、お勧めはしません。

250

辞書の中の単語のうち、与えられた単語と一番近いもので、最初のものを答えよという問題。同じ場所の文字が一致している数で距離を計算し、どれも一致しない場合には-1を返す。

マッチ数が増大する場合にはその単語を記憶する、という処理をやるだけ。初期値を-1にしておけば例外処理もいらない。

500

長方形内部に、長方形の通れない場所がいくつか存在する。通れる場所の面積のリストを小さい順にソートして答えよ、という問題。

400x600の長方形で、通れない部分は50個までなので、その大きさのboolean配列を用意するだけ。最後に残った通れる場所をBFSなりDFSなりすれば良い。

ArrayListのcontainsで判定をするようなBFSをやったらひどいことになった。チェックした場所を通れない場所に追加してまわればただの配列アクセス一回になるので、そうやるだけ。世間の人はこういう頭の悪いはまりはないだろうなぁ...。

900

コの字型をフラクタルで拡張して、N*Nの大きさを作成せよという問題。(実際には拡張したフラクタルの軌跡をたどるような配列アクセスをして処理をする問題だけれど、処理がdiv2の250点問題程度なので割愛。)

2*2の図形を定義して、4*4を作成して...、という風に拡張していく。各マスが2*2の大きさになるので、どのマスから開始するのか、次に進むのはどの方向か、というのを計算しながら実装するだけ。サンプルが通る程度に実装すれば多分終わる。手動で32*32の配列まで作ればそれでもいいけれど、さすがにそれは終わらないだろうなぁ、という感じ。