実は伏線張ってましたっていうお話・作問の経緯
伏線というのはこのツイートことです。
寿司取るなツイ消ししとるな
— 寿司取るにゃ 🙀 (@sushitoruna1) March 19, 2021
はい。それだけです。。
僕はツイ廃(ツブ廃)ではないので、5000ツイートに行かないように頻繁にツイ消ししているので()それを題材にした問題を作ろう！→ツブ消ししとるなっていう感じです。
はい。それだけです。。この記事を書いている時点では炎上しないことをただただ願っています。
ツブ消ししとるなEasy解説
問題内容
寿司取るな君は Tbutter という SNS を利用しています.
現在, 寿司取るな君のツブート数は N です. また, 寿司取るな君の i ツブート目のいいね数は A_i です. ツブ廃になりたくない寿司取るな君は, ツブ消しをすることでツブート数を M 以下にすることにしました.
ただツブ消しするだけではつまらないので, 寿司取るな君は残ったツブートのいいね数の和を最大化しようと思いました.
寿司取るな君は, いいね数が Y 以下のツブートはつまらないので必ず消します. いいね数が X 以上のツブートは面白いので消すことはできません. その他のツブートについては, 消すか消さないかを自由に決められます.
残ったツブートのいいね数の和の最大値を求めてください. ただし, どのようにツブ消しをしてもツブート数を M 以下にできない場合はHandicappedと出力してください.
制約
1 ≤ M ≤ N ≤ 10^5
0 ≤ Y < X ≤ 10^5
0 ≤ A_i ≤ 10^5
入力は全て整数
出力
寿司取るなくんがツブート数を M 以下に
・できない場合はHandicappedを
・できる場合は残ったツブートのいいね数の合計の最大値を
それぞれ 1 行に出力してください.最後に改行してください.
要約すると、いいね数の和が大きくなるようなツイートの消し方を考えなさい。というわけです。
解法
まず、ツブート数を M 以下にできない場合について考えましょう。
これは必ず残さないといけないツブートが M ツイートより多くある場合。つまり、いいね数が X 以上のツブートが M ツイートより多くある場合であることがわかります。この場合はHandicapped と出力してください。
次に、ツブート数を M 以下にできる場合について、どのようにすれば最大化できるか考えましょう。
基本的にはいいね数が多いツブートを残したいので、降順ソートするなどしていいね数の多いツブートから順番に残していけばいいでしょう。いいね数が Y 以下のツブートは消さなくてはならないことに注意してください。
また、オーバフローに注意してください。
実装
C++での実装例：https://yukicoder.me/submissions/630362
Pythonでの実装例：https://yukicoder.me/submissions/632916
ツブ消ししとるなHard解説
問題内容
寿司取るな君は Tbutter という SNS を利用しています.
現在, 寿司取るな君のツブート数は N です. また, 寿司取るな君の i ツブート目のいいね数は A_i です. ツブ廃になりたくない寿司取るな君は, ツブ消しをすることでツブート数を M 以下にすることにしました.
ただツブ消しするだけではつまらないので, 寿司取るな君はいいね数の平均を Z にしようと思いました.
寿司取るな君は, いいね数が Y 以下のツブートはつまらないので必ず消します. いいね数が X 以上のツブートは面白いので消すことはできません. その他のツブートについては, 消すか消さないかを自由に決められます. ただし, ツブートは 1 つ以上残すものとします. 残ったツブート数が M 以下かつ, いいね数の平均が Z になる場合の通り数を出力してください. ただし, どのようにツブ消しをしてもツブート数を 以下にできない場合はHandicappedと出力してください.
制約
1 ≤ M ≤ N ≤ 50
0 ≤ Y < X ≤ 50
0 ≤ Z ≤ 50
0 ≤ A_i ≤ 10^5
入力は全て整数
出力
寿司取るなくんがツブート数を M 以下に
・できない場合はHandicappedを
・できる場合は残ったツブート数が M 以下かつ,いいね数の平均が Z になる場合の通り数を
それぞれ 1 行に出力してください.最後に改行してください.
ツブ消ししとるなEasyとほぼ同じ問題文ですが、平均値の通り数を求めろという問題です。
解法
まず、ツブート数を M 以下にできない場合について考えましょう。
これは必ず残さないといけないツブートが M ツイートより多くある場合。つまり、いいね数が X 以上のツブートが M ツイートより多くある場合であることがわかります。この場合はHandicapped と出力してください。(Easyのコピペです。すみません())
次に、ツブート数を M 以下にできる場合について考えましょう。
まず、いいね数の平均が Z のときというのは、いいね数の合計が、 Z × ツブート数 であるといえます。よって、いいね数の合計を持ったDPをすれば良いと検討がつきます。具体的には次のようなDPです。
dp[ i ][ j ][ k ]： i ツブート目までの中から、 j ツブートを残したとき、いいね数の合計が k となるときの通り数
ただし、いいね数が Y 以下のツブートは削除しなくてはならないことや、いいね数が X 以上のツブートは残さなくてはいけないことの処理には注意してください。詳しくは実装を参考にしてください。(色々な対処方法はあると思います＞＜)オーバーフローにも気をつけてください。
