atcoder ABC 323 C - World Tour Finalsの説明

atcoder.jp

・説明
　'o'の問題は再び使えないので、累積和とbisectだと無理。xのものを抽出して、それをmaxのものと引き算してマイナスになるまでやる。

・失敗例

def II(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
def LS(): return list(map(str, input().split()))

n,m=MI()
a=LI()
s=[input() for _ in range(n)]

import bisect

cnt=[i+1 for i in range(n)]
#print(s)
for i in range(n):
    for j in range(m):
        if s[i][j]=='o':
            cnt[i]+=a[j]

a.sort(reverse=True)
ruiseki=[0]
for i in range(m):
    tmp=a[i]+ruiseki[i]
    ruiseki.append(tmp)

ma=max(cnt)
for i in range(n):
    if cnt[i]==ma:
        print(0)
        continue
    sa=abs(cnt[i]-ma)
    bir=bisect.bisect_right(ruiseki,sa)
    print(bir)

・AC例

def II(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
def LS(): return list(map(str, input().split()))

n,m=MI()
a=LI()
s=[input() for _ in range(n)]

cnt=[i+1 for i in range(n)]  #点数
flag=[[] for _ in range(n)]  #xのものを入れる

#'x'のものを抽出する。
for i in range(n):
    for j in range(m):
        if s[i][j]=='o':
            cnt[i]+=a[j]
        if s[i][j]=='x':
            flag[i].append(a[j])


ma=max(cnt)
for i in range(n):
    if cnt[i]==ma:
        print(0)
        continue

    sa=abs(cnt[i]-ma)  #これがマイナスになるまで'x'のものを引き算する。
    flag[i].sort(reverse=True)

    ans=0
    for f in flag[i]:
        if sa<0:
            break
        sa-=f
        ans+=1
    print(ans)