第5回 ドワンゴからの挑戦状 予選 A～C
A - Thumbnail
問題
- 長さ$N$の整数列 $a=\{a_0,a_1,...,a_{N-1}\}$
- $a$の平均値に最も近い項を$a_i$として、$i$を求めよ
- 複数ある場合は最も小さいものを求めよ
例
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])
B - Sum AND Subarrays
問題
- 長さ$N$の整数列$a=\{a_1,a_2,...,a_N\}$
- 空でない連続した部分列の取り出し方は$N(N+1)/2$通り。これらの部分列の和を考える
- 和を$K$個、上手く選んだ時の、ビット演算の論理積(AND)の最大値を求めよ
- 選ぶ部分列同士の区間は重なっていてもよい
- 全く同じ区間を2回以上選ぶことは出来ない
- 数の並びや合計は同じでも、区間が異なる部分列は同時に選べる
- $1 \le N \le 1000$
- $1 \le a_i \le 10^9$
例
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'にした方がよい。
よって、上の桁から使える値を絞ってサバイバルバトルを繰り広げればよい。
- まずは$N(N+1)/2$個、全ての和を計算し、候補とする
- $i=$最上位の桁とする
- 残っている候補の中で、$i$ 桁目が
'1'である数の個数を数える - $K$個未満なら、答えの$i$桁目を
'1'にできないので、そのまま - $K$個以上なら、
- 答えの$i$桁目を
'1'にできるのでする - それ以降は $i$ 桁目が
'0' である数は使わないので候補から除く
- $i$を1つ下位の桁に移して繰り返す
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)
C - k-DMC
問題
- 英大文字から成る長さ$N$の文字列$S$
- この文字列の「k-DMC」数を求める
- 「k-DMC」数とは、$3 \le k \le N$ である$k$があって、以下を満たす$(a,b,c)$の個数
- $a \lt b \lt c$
- $S[a]='D', S[b]='M', S[c]='C'$（
'D','M','C'が連続で無くてもよいのでこの順で並ぶ） - $c-a \lt k$（
'D'～'C'の文字数は$k$文字以下）
- クエリが$Q$個与えられる
- それぞれのクエリで与えられる$k$に対し、k-DMC数を求めよ
例
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なら
Dカウントを1増やす - Mなら
DMカウントを、自分より左のDの数＝その時のDカウントの値だけ増やす - Cなら
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$の制約を追加したときに、何を数えすぎているかというと、
- Cより $k$ 個以上左のMによって加算された
DMカウント - Cより $k$ 個以内のMの
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つのデータを事前計算しておくことで、高速に求められる。
- $Acc_D[i]=i$文字目までのDの個数の累積和
- $Acc_M[i]=i$文字目までのMの個数の累積和
- $Acc_{DM}[i]=i$文字目までのMによるDMcntの累積和
- $Loc_C[]=$Cが出てくる位置を記録
注目中の'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)))
