2023/8/21 解説を大幅に修正
問題へのリンク: https://atcoder.jp/contests/abc315/tasks/abc315_c
問題概要
Nカップのアイスがある。i番目のアイスの味は F_i, 美味しさは S_i (S_iは偶数)である。 この中から2つを選んで食べる。この時の満足度は次のように定義される。
2つのアイスの美味しさをs, t(s≧t)とすると、
- 味が異なれば、満足度は s + t
- 味が同じなら、満足度は s + (t / 2)
満足度の最大値を求めよ。
解説
forループで2つの組を調べていると間に合わない。どのようにして求められるか考える。
N個のアイスのうち最も美味しさが大きいアイスをアイスmとする。(ただし、同じ美味しさのアイスが複数存在するなら、アイスmはそのうちの1つとする。)
すると、アイスmは必ず選ばれる。
理由は、アイスmよりも美味しさが小さいアイスから2つ選んだ時、そのどちらかをアイスmに置き換えることによって、必ず前よりも満足度を高くすることができるからだ。
入力例を見て考える。下の図は、入力例1を示している。同じ色のアイスは同じ種類である。この場合、最も美味しさが大きいアイスmは図の上にあるアイス2である。
例えば、アイス1とアイス3を選んだ時の満足度は4+8=12だが、アイス3をアイス2(アイスm)に置き換えることによって満足度が4+10=14に上昇する。
また、アイス1とアイス3を選んだ時の満足度は4+6=10だが、アイス1をアイス2(アイスm)に置き換えることによって満足度は10+6=16に上昇する。
このように、アイスmと同色のものがあればその中で美味しさが小さいもの、無ければ美味しさが小さいものに置き換えることによって、必ず満足度を大きくできる。よって、満足度が最も高いアイスの1つであるアイスmは必ず使わなくてはならないことが分かった。
これが分かれば後は簡単で、アイスmと、アイスm以外の全てのアイスの組を全て試せば良い。計算量はO(N)。実際は全てを試す必要はないが、計算量は変わらない。
実装例(Python)
N = int(input()) I_L = [list(map(int,input().split())) for _ in range(N)] # idx_x: 最も美味しいアイス(アイスm)のindex idx_x = 0 # max_d: ここまでの最大の美味しさ max_d = 0 for i in range(N): # もしこれまでで一番美味しかったら更新 if I_L[i][1] > max_d: idx_x = i max_d = I_L[i][1] # アイスmの味f1、美味しさd1 f1, d1 = I_L[idx_x] # 答え(美味しさの最大値) ans = 0 #アイスm以外のもう1つのアイスとの組を調べる for i in range(N): # アイスxは既に選択済み if idx_x == i: continue # i番目のアイスの味f2、美味しさd2 f2, d2 = I_L[i] # 味が同じ if f1 == f2: ans = max(ans, d1 + d2 // 2) # 味が異なる else: ans = max(ans, d1 + d2) print(ans)
