289.1

IE7が一度中途半端なところで落ちて、それから頻繁に落ちるようになったのでIE8のBeta2を入れてみたら、はてなのJavaScriptにけちつけるようになった。うっとおしい。

そしてJavaのArrayListはメモリくうし遅いよ、というだけのセット。いかがなものかと。基本的な解法は全部同じ。DPというかメモ付き探索というか。(メモ付き探索のことをDPと呼んでいるケースもあるけど気にしないことにしよう。)

250

正三角形の頂点から、左下か右下に一つずつ移動することで、底辺まで移動することを考える。途中経由しないといけない点が複数個指定されるので、可能なパスは何通りあるか答えよ、という問題。

単純なDPをするだけ。ある行の点が指定されたならば、その行の他の点ではDPによる更新をしないようにフラグを立てておく。

500

無限に長いピアノがある。現在のキーからの相対的な移動で弾くキーが指定される。黒いキーを叩かないようにして、指定されたシーケンスを高々一回ずつ演奏するとき、最長で演奏できるシーケンスの数を答えよ、という問題。

現在のキーと、あるシーケンスを実行したときに遷移するキーの位置をメモしておく。実行不可能なシーケンスについてはその旨メモ。既に使用したシーケンスと、現在のキー位置を状態としてメモ付き探索すれば良い。

1000

自分の身長を操作する薬と、徐々に閉じていくドアがある状況で、迷路から出るのにかかる時間を答えよ、という問題。ドアはすべて一定速度で閉まる。薬は複数個あり、効果の発動していない状態で飲むと、身長が0以下になるまで一定の速度で縮み、0以下になると最初の身長に戻る。

現在位置と現在の身長と薬の残数を状態にメモ付き探索。メモ付きBFSをするだけの問題なのだけれど、2Mちょっとの状態になるので整数配列をArrayListに入れるとメモリが足りなくなる。普通に配列を持てば足りると思いつつ、Queueの大きさを適当に見積もって、その分くらいのBoundedBufferみたくしておいた。ちなみにBoundedBufferをArrayListで代用しようとすると終わらない。C++のSTLの適当なデータ構造なら問題なく終わると思う。