Red and Green Apples
ABC160-E "Red and Green Apples"
だいぶ沼にハマっていました....
提出コード
考察1(WA解法)
赤色,緑色,無色のりんごを美味しい順にソートしておきます.
それぞれのりんごを先頭から見るためのindexを合計3つ用意します.
先頭の赤と緑の美味しさを比較して,もし赤の方が美味しければ次は赤と無色で比較.
緑も同様です.
無色を着色した事実も含めて,合計で赤と緑のりんごを何個食べたかを持っておいてX,Yを超えないように見ていく.
考察はこんなところですが,index操作がわからず無事死亡.
以上です,AC解法にいきます()
考察2(AC解法)
赤色,緑色,無色のりんごを美味しい順にソートするのは同じです.
赤はX個まで,緑はY個までしか食べないので,赤色のりんごのうち美味しさランキングが(X+1)位以降のりんごは食べません.
緑も同様です.
そこで,「食べるかもリスト」を以下のように構成します.
・赤色のりんごのうち美味しさランキングがトップX位のりんごを「食べるかもリスト」に追加.
・緑色のりんごのうち美味しさランキングがトップY位のりんごを「食べるかもリスト」に追加.
・無色のりんごはC個全て「食べるかもリスト」に追加.
このとき,「食べるかもリスト」にはX個の赤色のりんご,Y個の緑色のりんご,C個の無色のりんごがあります.
「食べるかもリスト」のりんごを美味しい順にX+Y個食べればOK.
無色のりんごがあれば赤色か緑色か適切に着色してあげればよいです.
よって,美味しい順にソートして美味しさを足し込んでいけば答えが出ます.
感想
考察1の方法でも頑張れば通せるのかなーと思います.
実装力がなさすぎた.