読者です 読者をやめる 読者になる 読者になる

2014JAG夏合宿4日目 D問題:夕食 解説

原案、解答、問題文を担当していました。とこはるさんが解法、解答。

まずこの問題、一番辛いところは自炊パワーが自炊でも食堂でも変動する事なのでなんとかします。

自炊パワーは
自炊で+1、食堂で-1ですが、コレを自炊で+2、食堂で変動無し(±0)にしたと考えます。

仮にこのようにすると、i日目、自炊パワーは本来よりi-1高いです。
なので、自炊した場合本来より(i-1)*P高い幸福度を得ます。
このままだと答えはおかしくなりますが、i日目の食堂に事前に(i-1)*Pを足しておきます。
すると、本来より自炊しても食堂に行っても(i-1)*P高い幸福度を得るので、必ず本来より
1*P+2*P+3*P+..+(N-1)*P高い幸福度を得るので、この仮定での幸福度のMaxからコレを引けば正しい答えになります。

自炊パワーが自炊で+2、食堂で変動無しだとすると、どのように解けば良いでしょうか。
これは、自炊で得る幸福度の総和が自炊の回数だけに依存するので、自炊する日数を決めてしまえば残りは食堂を高い順に取ればOKです。
なので、自炊する日数KをK=0,1,2..と決めうちすればどこかで正しい答えが出ます。

色々雑なのでイミワカンナイ場合@yosupotまで