AtCoder ABC173
2020-07-05(日)に行われたAtCoderBeginnerContest173の問題をA問題から順に考察も踏まえてまとめたものとなります．
後半ではDEの問題を扱います．前半はこちら．
問題は引用して記載していますが，詳しくはコンテストページの方で確認してください．
コンテストページはこちら
公式解説PDF
D問題 Chat in a Circle
問題文
あなたはオンラインゲーム「ATChat」のチュートリアルを終え、その場に居合わせたプレイヤー$N$人で早速とある場所を訪ねることにしました。この$N$人には$1$から$N$の番号が振られており、人$i(1 \leq i \leq N)$のフレンドリーさは$A_i$です。
訪ねる際、$N$人は好きな順番で$1$人ずつ到着します。あなたたちは迷子にならないために、既に到着した人たちで環状に並び、新たに到着した人は好きな位置に割り込んで加わるというルールを決めました。
最初に到着した人以外の各人は、割り込んだ位置から到着した時点で「時計回りで最も近い人」と「反時計回りで最も近い人」のフレンドリーさのうち小さい方に等しい 心地よさ を感じます。最初に到着した人の心地よさは$0$です。
$N$人が到着する順番や割り込む位置を適切に決めたとき、$N$人の心地よさの合計の最大値はいくらになるでしょう？
正直，ちゃんと考えれば良かったなと思いました．
何となく問題見て難しい気がしてしまったのと，差をつけるためにE問題を解くために飛ばしてしまいました．
n = int(input())
a_list = list(map(int, input().split()))
a_list.sort(reverse=True)
ans = 0
for i in range(0, n - 1):
ans += a_list[(i + 1) // 2]
print(ans)
E問題 Multiplication 4
問題文
$N$個の整数$A_1,…,A_N$が与えられます。
このなかからちょうど$K$個の要素を選ぶとき、選んだ要素の積としてありえる最大値を求めてください。
そして、答えを$(10^9+7)$で割った余りを$0$以上$10^9+6$以下の整数として出力してください。
正の数と負の数と0の数に分けて，問題を考えていましたが，$K=N$の結果が負になるときと正のときとをなぜか必死に場合分け書いてたら，タイムオーバーでした．
よくよく考えれば，全部使うときは，貪欲に計算すれば，済む話でしたね(反省)
ただ，勉強のために提出されたコード見てみると，
4 3
-1 -2 3 4
のような入力例に対応できていないものが"AC"通っていて何だかなーと思いました．
こういった場合の処理をどうしないといけないかなど，いろいろ考えている人が結局時間が足りず通せず，入力に対してあまり深く考えず，限定された，テストにある入力を運よく通って得点できている人がいるような場合，後からrateの調整とかしてほしいところですが，無料のコンテストにあまり多く求めてもしょうがないですよね（汗）
現在は，after_contest_01.txtがチェックに追加されていて，そういったコードは"WA"になります．
n, k = map(int, input().split())
a_list = list(map(int, input().split()))
mod = 10**9+7
a_list.sort()
ans = 1
if k % 2 == 1 and a_list[-1] < 0:
for i in range(k):
ans *= a_list[n - 1 - i]
ans %= mod
else:
l = 0
r = -1
mlt1 = a_list[0] * a_list[1]
mlt2 = a_list[-2] * a_list[-1]
count = 0
while True:
if count == k:
break
elif count == k - 1:
ans *= a_list[r] % mod
ans %= mod
break
if mlt1 >= mlt2:
ans *= mlt1 % mod
l += 2
count += 2
if l <= n - 2:
mlt1 = a_list[l + 1] * a_list[l]
else:
ans *= a_list[r] % mod
r -= 1
count += 1
if r >= - n + 1:
mlt2 = a_list[r - 1] * a_list[r]
ans %= mod
print(ans)
後半も最後まで読んでいただきありがとうございました．