Sushi

この問題を解こうとしたときに、はじめに思いつく解法は、『選ぶ寿司ネタを全通り試して、得られる「満足度」の最大値を求める』というものだと思います。これは、以下のように三重ループと適切な条件分岐を用いて書くことができますが、これでは TLE(実行制限時間超過)、となり正解することはできません。 (計算量としては $O(N^3)$ となります。)

TLE となる Python の実装例です。

xxxxxxxxxx

N = int(input())

A = list(map(int, input().split()))

# 答えをマイナス無限大で初期化

ans = -float("inf")

# 三重ループを回して、全通りを試す。

for i in range(N):

    for j in range(N):

        for k in range(N):

            # 最大値の更新

            ans = max(ans, (A[i] + A[j] + A[k]) * len({i, j, k}))

print(ans)

​

では、どうすればこの問題を正解することができるでしょうか？

寿司ネタを $3$ つ選ぶとき、選び方は以下の三種類があります。

• 一つの同じ寿司ネタを $3$ つ選ぶ。
• 一つの同じ寿司ネタを $2$ つ、それとは異なる寿司ネタを $1$ つ選ぶ。
• 相異なる寿司ネタを $1$ つずつ、計 $3$ つ選ぶ。

それぞれの場合について、どのように寿司ネタを選ぶのが「満足度」を最大化できるかについて考えてみましょう。

• 一つの同じ寿司ネタを $3$ つ選ぶ場合
  この場合、最も美味しさの大きい寿司ネタを選ぶべきです。証明は省略します。

• 一つの同じ寿司ネタを $2$ つ、それとは異なる寿司ネタを $1$ つ選ぶ場合
  この場合、最も美味しさの大きい寿司ネタを $2$ つ、二番目に美味しさの大きい寿司ネタを $1$ つ選ぶべきです。 証明は省略します。

• 相異なる寿司ネタを $1$ つずつ、計 $3$ つ選ぶ場合
  この場合、最も美味しさの大きい寿司ネタを $1$ つ、二番目に美味しさの大きい寿司ネタを $1$ つ、三番目に美味しさの大きい寿司ネタを $1$ つ選ぶべきです。 証明は省略します。

上の三種類の選び方において、それぞれ選ぶ寿司ネタは一意に定まるため、「満足度」を最大化するときの選び方の候補は実質三通りしかありません。その三通りの選び方を全て試して最大値を出力すればこの問題に正解出来ます。
$i \, (1 \leq i \leq N)$ 番目に美味しい寿司ネタの美味しさを求めるには、 $A$ を降順にソートして $A[i]$ を参照すれば良いです。
計算量としてはソートがボトルネックとなり、 $O(NlogN)$ となりますが、この問題の制約において、十分高速です。

以下は Python の実装例です。

xxxxxxxxxx

N = int(input())

A = list(map(int, input().split()))

​

# 降順にソート

A.sort(reverse=True)

​

# 最大値を求めたいので、答えをマイナス無限大で初期化

ans = -float("inf")

​

# 美味しさが最大の寿司ネタを 3 つ選ぶ場合

ans = max(ans, (A[0] + A[0] + A[0]) * 1)

​

# 美味しさが最大の寿司ネタを 2 つ、二番目に美味しい寿司ネタを 1 つ選ぶ場合

if N >= 2:

    ans = max(ans, (A[0] + A[0] + A[1]) * 2)

​

# 美味しさが最大の寿司ネタを 1 つ、二番目に美味しい寿司ネタを 1 つ、三番目に美味しい寿司ネタを 1 つ選ぶ場合

if N >= 3:

    ans = max(ans, (A[0] + A[1] + A[2]) * 3)

​

print(ans)