AtCoder Beginner Contest 353 - あるぱかのブログ

久々にrated参加

atcoder.jp

A - Buildings
B - AtCoder Amusement Park
C - Sigma Problem

A - Buildings

リンク：A - Buildings (atcoder.jp)

概要：配列 $H$ で先頭より大きな値が初めて出る場所を出力してね

問題文の解読に手間取りました。

最大値ではなく、初めて $H_1$ を越える場所を出力します。

$H$ を順番に見ていって $H_i \gt H_1$ になる $i$ が存在すれば $i$ を、そうでなければ $-1$ を出力します。

#ABC353 A - Buildings
N = int(input())
H = list(map(int, input().split()))
idx = 0
for i in range(1, N):
    if H[i] > H[0]:
        idx = i
        break
if idx == 0:
    print(-1)
else:
    print(idx+1)

提出リンク：提出 #53326606 - AtCoder Beginner Contest 353

B - AtCoder Amusement Park

リンク：B - AtCoder Amusement Park

概要：グループの人数 $A_i$ がアトラクションの空席 $K$ 以内なら乗せる、越えたら出発させるを繰り返して出発した回数を出力してね

問題文の解読に略

$A_i$ を順番に足していって $K$ を越える直前にアトラクションを出発させることを繰り返します。

乗った/乗ってないを管理する配列 $go$ を作っていますが別解のようにwhileの二重ループとしたほうがシンプルだと思います。

#ABC353 B - AtCoder Amusement Park
N, K = map(int, input().split())
A = list(map(int, input().split()))
count = 0
go = [False] * N
for i in range(N):
    if go[i]:
        continue
    else:
        member = 0
        j = i
        while j < N:
            if member + A[j] <= K:
                member += A[j]
                go[j] = True
                j += 1
            else:
                break
        count += 1
print(count)

提出リンク：提出 #53346465 - AtCoder Beginner Contest 353

#ABC353 B - AtCoder Amusement Park
N, K = map(int, input().split())
A = list(map(int, input().split()))
count = 0
i = 0
while i < N:
    member = A[i]
    j = i+1
    while j < N:
        if member + A[j] <= K:
            member += A[j]
            j += 1
        else:
            break
    count += 1
    i = j
print(count)

提出リンク：提出 #53387512 - AtCoder Beginner Contest 353

C - Sigma Problem

リンク：C - Sigma Problem (atcoder.jp)

概要： $A$ について $(A_i + A_j)\ mod\ 10^{8}$ の総和を出力してね

すべての $i,j$ の組で都度計算していては $_N C _2$ 回の試行回数が必要になりTLEします。

$sum(A) \times (N-1)$ に対して $mod\ 10^{8}$ を取りたくなりますが正しい答えではありません。

そこで $A_i+A_j \gt 10^{8}$ となった回数を記録しておき $sum(A) \times(N-1) \ -\ 10^{8} \times count$ とすることを考えます。

答えは $A$ をソートしても問題ないのでソートし、 $A_i+A_j \geq 10^{8}$ となる $j$ を二分探索します。

計算量はソートに $O(NlogN)$ 、二分探索1回につき $O(logN)$ （N回行うので $O(NlogN)$ ）なので十分高速です。

（公式解説のしゃくとり法なら探索パートが $O(N)$ になります）

14～17行目の $count$ の積み上げのところはもっと上手な処理の仕方がありそうですがACしたのでヨシ！

N = int(input())
A = sorted(list(map(int, input().split())))
mod = 10**8
count = 0
for i in range(N-1):
    left = i+1
    right = max(left, N-1)
    while right < N and left+1 < right:
        mid = (left + right) // 2
        if A[mid] + A[i] >= mod:
            right = mid
        else:
            left = mid
    if A[i] + A[left] >= mod:
        count += (N - left)
    elif A[i] + A[right] >= mod:
        count += (N - right)
ans = sum(A) * (N-1) - (mod * count)
print(ans)

提出リンク：提出 #53383604 - AtCoder Beginner Contest 353（時間オーバー）