📚
【競技プログラミング】AtCoder Beginner Contest 353_C問題
問題
要約
-
変数
- N: 正整数列Aの長さ
- A = (A₁, ..., Aₙ): 正整数列
-
関数 f(x,y) の定義
f(x,y) = (x + y) mod 10^8
ここで、mod は剰余演算（割り算の余り）を表します。 -
求めるべき式:
Σ(i=1からN-1まで) Σ(j=i+1からNまで) f(Aᵢ, Aⱼ)
正整数列Aの全ての異なる2つの要素の組み合わせに対して、f(x,y)を適用し、その結果を合計する。
- 最初の要素から順に、その要素より後ろにある全ての要素との組み合わせを考えます。
- それぞれの組み合わせに対して f(x,y) を計算します。
- 全ての計算結果を合計します。
既存投稿一覧ページへのリンク
アプローチ
正整数列Aの全ての異なる2つの要素の組み合わせに対して f(x,y) を計算し、その合計を求める。
解法手順
-
入力を受け取り、正整数列Aをソートする。
-
10^8以上になる組み合わせの数を効率的に数える
- 配列の両端から走査を始め、和が10^8以上になる組み合わせを見つける。
- これにより、10^8以上になる組み合わせの数（biggersum）を効率的に計算できる。
-
全ての組み合わせの単純な和を計算する
- sum(An) * (N - 1) で、全ての組み合わせの和が得られる。
-
最終的な答えを計算する：
- 全ての組み合わせの和から、10^8以上になる組み合わせの数に10^8を掛けたものを引く。
- これにより、f(x,y)の定義に従った正確な合計が得られる。
-
結果を出力する。
ACコード
ac.py
def io_func():
# 入力を受け取る
N = int(input()) # 正整数列Aの要素数
An = list(map(int, input().split())) # 正整数列A
return N, An
def solve(N, An):
# 正整数列Aをソートする
An.sort()
# 10^8以上になる組み合わせの数を数える
biggersum = 0
j = N - 1
for i in range(N):
while i < j:
if An[i] + An[j] >= 100000000: # 10^8
j -= 1
else:
break
if i < j:
biggersum += N - j - 1
elif i < N - 1:
biggersum += N - i - 1
# 全ての組み合わせの単純な和を計算
total_sum = sum(An) * (N - 1)
# 最終的な答えを計算
ans = total_sum - biggersum * 100000000 # 10^8
return ans
if __name__=="__main__":
# メイン処理
N, An = io_func()
result = solve(N, An)
print(result)
###
# N: 正整数列Aの要素数
# An: 正整数列A
# biggersum: 10^8以上になる組み合わせの数
# j: 配列の後ろから走査するためのインデックス
# total_sum: 全ての組み合わせの単純な和
# ans: 最終的な答え（f(x,y)の合計）
# 1. io_func関数:
# - 標準入力から正整数列Aの要素数Nと正整数列Anを読み込む
# 2. solve関数:
# - 正整数列Aをソートする
# - 10^8以上になる組み合わせの数を効率的に数える
# - 全ての組み合わせの単純な和を計算する
# - 最終的な答えを計算する
# 3. メイン処理:
# - io_func関数を呼び出して入力を受け取る
# - solve関数を呼び出して結果を計算する
# - 結果を出力する
Discussion