380.1

SRM

250

右方向に進まないといけないナイトのコマが、4通りの移動を少なくとも一回ずつする状況で、二次元盤面上を最長移動するときの移動回数を答えよ、という問題。移動回数が少ないときはすべての移動をする必要はない。


めんどくさい条件分岐するだけ。多分4回移動する範囲を全探索して、4通り移動ができるのであれば以降は1マスずつ右に行く処理を繰り返す。それ以外は最長のを答えれば良い。実際には探索書くのがめんどくさいので、適当な条件分岐に落としてやるだけ。

500

何種類かのカードがあって、全部のカードを一枚ずつ使いたい。ただし一つだけワイルドカードで代用することが許可されており、ワイルドカードの使用上限が与えられる。このとき全部で何回全部のカードを一枚ずつ使えるか答えよ、という問題。


できる回数を決めればワイルドカードの使用枚数が分かる。これが上限に引っかからないことと、ワイルドカードが同時に二枚使われない(つまりワイルドカードの使用枚数が全体の回数を越えない)ことが満たされている最大値を二分探索で求めてやれば良い。

1000

N本の棒が与えられる。最初の棒は45度よりも浅く傾けて、次の棒は45度以上になるように傾けて...というのを交互にやる。ちょうど45度の場合は次の棒の傾きを好きなようにして良い。このとき最初の棒の高さの最小値を答えよ、という問題。


どこかの棒が45度でちょうどになるケースか、0度や90度になるケースが最小値を与えることになるので、全パターン試せば良さそう。なお、できるだけ最初の棒の傾きを浅くしたいので、それぞれの棒は片方の端が接触しているはず。(漏れてるケースあるかも。)