GCJ Japan Qualification

なんか同じカテゴリの問題というか、ひらめきが共有できる。

A

カードの山をA番目からB枚抜いて、一番上に、という操作を繰り返す。最後C枚目にあるカードは最初何枚目にあったか答えよ、という問題。

C枚目のカードは一つ前のステップでどこにあったかを考える。Cが上からB枚以内にあれば、A枚目のところから移動してきたし、A+B枚目以内にあれば、B枚上に乗っかったし、そうでなければ移動していないし、という感じにやる。

B

賞味期限が指定されたものの、満足度と分量が与えられるので、期限内にできるだけ多くの満足度になるように消費せよ、という問題。

後ろから順にその時に最適なものを割り当てていく。時間を見て、賞味期限内のもので一番満足度の高いものを選び、他のどれかの賞味期限にぶつかるか、それを全部消費する時間にだけ、それを消費していくだけ。

C

整数Aを二つの整数の和に分解することを考えるとき、分解した二つの数のビットカウントの合計を最大化せよ、という問題。

上の桁で一個立てるくらいならその隣の桁で2個立てる方が良いはずなので、キャリーは貪欲に発生させて良い。ということで下の桁から順番に決めていけば良い。