a = 3 2 1 4 ave = 2.5
最も近いのは 3(i=0) と 2(i=1) なので、小さい方である0が答え
平均値を求めればよい。$N$が小さいのでそのまま計算しても演算誤差の心配は無いが、不安なら$a_i$の方を$N$倍して、合計と比べればよい。
n = int(input()) aaa = list(map(int, input().split())) ave = sum(aaa) / n bbb = [(abs(a - ave), i) for i, a in enumerate(aaa)] bbb.sort() print(bbb[0][1])
a : 2 5 2 5
部分列: 2 7 9 14 -> 0010 0111 1001 1110
の和 5 7 12 0101 0111 1100
2 7 0010 0111
5 0101
K=2
12と14を選ぶと、1110 AND 1100 = 1100 → 12 が答え
以下、○桁目というと、2進数表記で上位(左)から数えた桁とする。
ANDなので、選んだ $K$ 個の内に $i$ 桁目が'0'の数が1つでも含まれると、答えも $i$ 桁目を '1' にはできない。
最大値を求めるので上位のbitを優先的に'1'にした方がよい。
よって、上の桁から使える値を絞ってサバイバルバトルを繰り広げればよい。
'1'である数の個数を数える'1'にできないので、そのまま'1'にできるのでする'0' である数は使わないので候補から除くK=3 部分列の和: 1111 ----> 1111 ----> 1111 ----> 1111 ----> 1111 1100 1桁目 1100 2桁目 1100 3桁目 1100 4桁目 x 1001 '1' 1001 '1' 1001 '1' 1001 '1' 1001 1010 1010 1010 1010 x 1001 K=3個 1001 K個 1001 K個 1001 K個 1001 0111 以上 x ない x ない x ある x 0100 ある x →残す x →残す x x -------------------------------------------------------- 答え 1 0 0 1 → 1001 = 9
計算量を見積もると、$N \le 1000$ なので、ひとまず全ての部分列の和は計算してメモリ上に確保できる。
また、$a_i \le 10^9$ なので、部分列の和の最大値は $10^{12} \simeq 2^{40}$。40bitほど考えればよい。
from collections import defaultdict
from itertools import accumulate
n, k = map(int, input().split())
aaa = list(map(int, input().split()))
acc = [0] + list(accumulate(aaa))
subs = defaultdict(lambda: 0)
for l in range(n):
acl = acc[l]
for r in range(l + 1, n + 1):
beu = acc[r] - acl
subs[beu] += 1
ans = 0
for i in range(40):
bit = 1 << (39 - i)
new_subs = {}
remain = 0
for sub, cnt in subs.items():
if sub & bit > 0:
new_subs[sub] = cnt
remain += cnt
if remain >= k:
subs = new_subs
ans |= bit
print(ans)
'D','M','C'が連続で無くてもよいのでこの順で並ぶ）'D'～'C'の文字数は$k$文字以下）12345678 S = DDoMoCCC k = 4 ... k-DMC = 0 4文字以下で、D,M,Cをこの順で含む文字列は取れない k = 5 ... k-DMC = 1 2～6文字目を取ると、条件を満たす文字列が1個取れる k = 8 ... k-DMC = 6
$k$の制約を考えないで、単にDMCがこの順で並ぶ個数を考えると、これは簡単に求められる。先頭から順に見ていって、
Dカウント を1増やすDMカウント を、自分より左のDの数＝その時のDカウントの値だけ増やすDMCカウント を、自分より左のDMの数＝その時のDMカウントの値だけ増やすDMCカウントが答えkなし
D M D D M M C
Dcnt 1 2 3
DMcnt +1 +3 +3
Total 1 4 7
DMCcnt +7
で、$k$の制約を追加したときに、何を数えすぎているかというと、
DMカウントDMカウントを求める際に、$k$個以上左のDによって加算されたDカウントk=4 _____________
D M D D M M C
| ^ ^
| これらのMのDMcntのうち、左2つのDによって加算された分は余分
このMのDMcntは余分
Dcnt 1
DMcnt +1 +1
Total 1 2
DMCcnt +2
ある'C'に注目中の時、その'C'を右端とするk-DMCの条件を満たす組の個数は以下の式で求められる
$(範囲内のMによるDMcnt)-(範囲内のMの個数)\times(範囲より左のDの個数)$
これは、3つの累積和と1つのデータを事前計算しておくことで、高速に求められる。
注目中の'C'の位置を$r$とし、$l=r-k$（範囲外の一番右、はみ出る場合は0）とすると、以下のようになる。
$Acc_{DM}[r] - Acc_{DM}[l] - Acc_D[l] \times (Acc_M[r] - Acc_M[l])$
7 - 1 - 2 * 2 = 2
~~~ ~~~~~
| 範囲内のMの個数×範囲より左のDの個数
範囲外のMによって加算されたDMcnt
Pythonだと時間的に厳しく、PyPyでぎりぎりというところ。また、Pythonなら累積和の計算にitertools.accumulate()など便利な関数があるのだが、PyPyの場合は使わないで1つずつ代入する書き方の方が速かったりする？（言うて0.1～0.2秒だが）
n = int(input())
s = input()
acc_cnt_a = [0] * (n + 1)
acc_cnt_b = [0] * (n + 1)
acc_cnt_ab = [0] * (n + 1)
c_loc = []
cnt_a = 0
cnt_b = 0
cnt_ab = 0
for i, c in enumerate(s):
i += 1
if c == 'D':
cnt_a += 1
elif c == 'M':
cnt_b += 1
cnt_ab += cnt_a
elif c == 'C':
c_loc.append(i)
acc_cnt_a[i] = cnt_a
acc_cnt_b[i] = cnt_b
acc_cnt_ab[i] = cnt_ab
q = int(input())
buf = []
for k in map(int, input().split()):
ans = 0
for r in c_loc:
l = r - k
if l > 0:
rejected_a = acc_cnt_a[l]
cnt_internal_b = acc_cnt_b[r] - acc_cnt_b[l]
cnt_internal_ab = acc_cnt_ab[r] - acc_cnt_ab[l]
ans += cnt_internal_ab - rejected_a * cnt_internal_b
else:
ans += acc_cnt_ab[r]
buf.append(ans)
print('\n'.join(map(str, buf)))