219.1

1000の方が500よりも簡単な気がしてならない問題セット。というか1000のはまりポイントが分からない...。

250

ある規則に従って、一番良いメニューを答えよという問題。規則は、Aをできるだけ(大きく|小さく)する、同点ならBについて...、というのが与えられる。

規則に従った実装をするだけ。良くあるソート問題の、ソートじゃなくて最小要素を答える問題。

500

N人の人がそれぞれ好きな食べ物がある状態で、回転する円卓に座っている。好きな食べ物を取ることができるように円卓を回すとき、全員に好きな食べ物が一品行き渡るための最小の時間を答えよ、という問題。目の前にある食事を取るのに15秒かかり、円卓を回すのにはK人分回すときにK+1秒かかる。

テーブルを初期状態から見て、A人分動かす状態のそれぞれをやるかやらないかを全探索。N個動かし方があるので、それぞれやるかやらないかなので、2^N通りの可能性がある。これらのうち、やった動作によって、目の前に好きな食べ物がある人の集合を求める。(ある程度最適化しないと間に合わないけれど割愛。)

全員が好きな食べ物を得られる状態について、回転をより早く実現する方法を考える。これは、右に回すか左に回すかを、実行する状態の数だけ判断する。要は、実現しないといけない回転状態Mの数だけ、右に回すか左に回すかを全通り試す。これまた2^M通り試す。単純に全部列挙すると当然ながら終わらないけれど、大抵Mの個数が小さい方が良い結果になるので、途中経過とM*15との比較でフィルタなどすれば終わる。

実装が非常に面倒だったけれど、他にもやりようがあるのかも知れない。

1000

N人の人がそれぞれ好きな食べ物がある状態で、すべての人が必ずちょうど二品好きなものにありつけるように注文する時の、最小の値段を答えよ、という問題。

好きなものが多い人から順にソートして、今までに選んだ食べ物と好きなものとの重なりを調べる。2品より多かったらバックトラック。2品ちょうどだったら、その人が好きな他のものは選べないようにして次の人へ。2品より少なければ、足りない分を今までに選んでなくて既に決定した人の好きな食べ物ではない食べ物から追加することを全パターン試す。こういう探索をやるだけ。

好きな食べ物が多い人から始めるので、かなりの勢いで枝が狩られるような気がしたし、実際それでSYSTEMのTESTは通った。悪い例は作れそうな気もするけれども...。