備忘録代わりに精進記録を載せていくつもりです。提出コード解法ある程度までは貪欲にとっていき、その後一部入れ替えてみて探索していく、という形になります。全ての寿司を美味しさの降順でソートします。個を食べたときのスコアを計算します。寿司をいくつ食べたか、も記録しておきます。解の候補の1つになります。個目以降の寿司についてみていきます。番目の寿司を見ているとします。個の寿司の種類と被っていない場合、以下のような操作をします。今食べることにしている寿司のうち、同じ種類で2個以上存在する寿司の中から、最もおいしさが少ないものと交換する。結局やりたいことは、種類ボーナスの獲得をするために、種類が増えるようにかつ、一番美味しさの総和が減らないようにしながら食べる寿司を交換する、ということです。番目以降のすべての寿司について行います。番目のお寿司を食べることにする。番号を若くしていき、同じことを繰り返す(もしすべて1個ずつしかなければ、その時点で全ての操作は終了します)。すると、おいしさの総和の減少を最小限に抑えつつ、種類のみを増やすことができます。あとは、これを繰り返し、食べる寿司を交換するたびに最大値をとっていけば答えが求まります。このような貪欲法で通るのでしょうか。以下になるような食べ方では、絶対にスコアが最大になることはありません。美味しさの総和でも、種類ボーナスでも最初の値を超えることができないからです。番目以降のお寿司を採用する際は、種類が増えるように選択しなければなりません。個の寿司の中で、1個しか存在していない種類の採用をとりやめることはありえなくなります。番目の寿司のみを採用するパターンがあるかどうか、です。どちらの場合も、その寿司を採用したことで増える寿司の種類は1種類です。番目の寿司を採用する方が、スコアは当然高くなります。採用するパターンはありえません。番目からは、順番に種類が増えるようにお寿司を採用(交換)していけば、最大値を探索することができます。感想この手の問題はとっつきにくい気がします。苦手意識があるのですが、わりとはやいスピードで解くことができたのでよかったです。このような問題では、とりあえずDPか貪欲が自分の中では思い浮かぶのですが、評価値が複雑なため、何か貪欲できる部分がありそう、という考えに至ります。そこで、まずは種類数を決め打ちした場合についてを考えましたが、どの種類を選ぶかがよくわからないため断念しました。個選んだパターンは割と高スコアになりそうなので、次にそこからスコアを伸ばせるとしたらどうすればいいか、という部分について考えます。すると、おいしい順に選んでしまっているので、あとは種類数を伸ばすしかありません。個の中から交換、という操作を行うのが最善ということがわかります。あとは、これをバグがないように実装すればいいのですが、無理でした。(1)注目記事はてなブログをはじめよう!emtubasaさんは、はてなブログを使っています。ブログを報告するスターをつけました引用をストックしましたストック一覧を見る閉じる引用するにはまずログインしてくださいログイン閉じる引用をストックできませんでした。再度お試しください閉じる限定公開記事のため引用できません。