195.1

気を取り直して...。

250

Div2の500と同じ問題。基本的に。

500

状態iから状態i+1への遷移をボタンを押すたびに行う機械がある。最後の状態からは最初の状態に戻るようになっている。また各状態に到達した時に音が鳴るか鳴らないかの情報が与えられる。このとき、目的の状態に到達するまでに何回ボタンを押す必要があるかを最悪の場合について答えよ、という問題。

ある状態を先頭に考えたとき、それからN回ボタンを押した時点で他の状態と識別できるとする。その時から目的の状態までの移動回数+Nの最大値を計算すれば良い。Nの求め方は、すべての状態と違う音の鳴り方をするまでの回数なので、その状態から音の鳴り方を他の状態すべてと比較して、一番似ているものとの差分の出る場所を求めれば良い。

950

Div2の1100と同じような問題。ただしコインの使う数を最小にせよという問題。

使用するコインが最小になる時のパスをどうやって計算するか、という問題。取り敢えず各ステップごとに使用する最大のコインを取得するようにやったら、最悪の場合でTLEした。単純に実現したい額でメモするようにしたら、時間内に終了。というか、一回の演算で求める方式でもTLEしそうな気はする。

この問題に限ったことではないけれど、状態遷移をどうやって保存するかは重要だと思う。とりわけ一回の演算で保存しておくことは重要だろうなぁ。この問題は同じ演算を繰り返しても、メモさえしてあれば問題ないだろうけれど。