−目次

第5回ドワンゴからの挑戦状予選 A～C
- A - Thumbnail
  - 問題
  - 例
  - 解法
- B - Sum AND Subarrays
  - 問題
  - 例
  - 解法
- C - k-DMC
  - 問題
  - 例
  - 解法

第5回ドワンゴからの挑戦状予選 A～C

Dwango Programming Contest V / 第5回ドワンゴからの挑戦状予選

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)))

            

        
      

−目次

第5回 ドワンゴからの挑戦状 予選 A～C

A - Thumbnail

問題

例

解法

B - Sum AND Subarrays

問題

例

解法

C - k-DMC

問題

例

解法

第5回ドワンゴからの挑戦状予選 A～C