−目次

ARC 098
- C - Attention
  - 問題
  - 例
  - 解法
- D - Xor Sum 2
  - 問題
  - 例
  - 解法
- E - Range Minimum Queries
  - 問題
  - 例
  - 解法

ARC 098

C - Attention

問題

$N$ 人の人が、西か東のいずれかを向いて東西方向に1列に並ぶ
リーダーを1人決めると、その他の人は一斉にリーダーの方を向く
- リーダー自身はどちらを向いていてもよい
リーダーは自由に選べるとすると、向きを変える最小の人数は何人か

例

初期状態
←→→→←→←→

リーダーを決める
←→Ｌ→←→←→

リーダーの方を向く
→→Ｌ←←←←←

この場合、向きを変えたのは4人。

解法

西から $i$ 番目の人をリーダーとした時、向きを変えるのは、以下の合計。

$1$ ～ $i-1$ 番目にいて、西を向いている人数
$i+1$ ～ $N$ 番目にいて、東を向いている人数

累積和を使ってそれぞれを求め、合算した結果から、最小値を取ればよい。

        
              from itertools import accumulate
 
n = int(input())
s = [c == 'W' for c in input()]
l = accumulate([0] + s[:-1])
r = accumulate([0] + [not c for c in reversed(s[1:])])
print(min(e + w for e, w in zip(l, reversed(list(r)))))

D - Xor Sum 2

問題

長さ $N$ の正整数列 $A$
左端 $l$ と右端 $r$ の組 $(l \le r)$ で、以下の等式を満たす個数を求めよ
$A_l+A_{l+1}+...+A_{r-1}+A_r = A_l \oplus A_{l+1} \oplus ... \oplus A_{r-1} \oplus A_r$
- $\oplus$ は排他的論理和（xor）を表す

例

まず、 $l=r$ の組は必ず条件を満たす。(1,1) (2,2) (3,3) (4,4)

また、 $2+1+4 = 2 \oplus 1 \oplus 4 = 7$ なので、(1,3)も条件を満たす。同様に (1,2) (2,3)も条件を満たす。

解法

問題を言い換えると、 $A$ の連続した部分列で「どの2つを取っても、2進数表記した時に同じ場所に'1'が立っていない」のはいくつ取れますか、ということになる。

2数のxorは、ある桁で、少なくともどちらか一方が'0'なら足し算と同等になるが、両方が'1'だと打ち消される。

a	b	a+b	a xor b	+とxorの結果
0	0	0	0	同じ
0	1	1	1	同じ
1	0	1	1	同じ
1	1	2	0	違う

    19        10011          10011
xor  6 → xor 00110        + 00110
------    ---------        -------
              10101 = 21     11001 = 25
 打ち消される→  ~

どの要素も正なので、 $a+b \ge a \oplus b$ となり、 $a \& b = 0$ の時しか等しくならない。

これは、尺取法で実装できる。

しゃくとり法 (尺取り法) の解説と、それを用いる問題のまとめ - Qiita

空の計算用配列を用意して、「条件を満たさなくなるまでAの要素を順に配列末尾に追加する」「条件を満たさなくなったら、満たすようになるまで配列の頭から要素を取り除く」ことを繰り返して求めていく。

計算用配列が伸びたり縮んだりして進んでいくので、尺取り虫みたい。といいつつ尺取り虫とか最近見ない。

        
              from collections import deque
 
n = int(input())
aaa = list(map(int, input().split()))
 
buf = deque()  # 計算用配列
tmp = 0        # 計算用配列の全要素のxor値
ans = 0
 
for a in aaa:
    while tmp & a:
        rm = buf.popleft()
        tmp ^= rm
    buf.append(a)
    tmp ^= a
    ans += len(buf)
print(ans)

E - Range Minimum Queries

問題

長さ $N$ の整数列 $A$
$A$ に対し「任意の長さ $K$ の区間を決め、その中の最小値を除く」という操作を $Q$ 回行う
取り除いた数字の最小値 $X$ と最大値 $Y$ の差 $Y-X$ をできるだけ小さくする時、その値を求めよ

例

A: 4 3 1 2 5 1 3
K: 3   Q: 3

1回目: 4 3 [1 2 5] 1 3  → 1を除外
2回目: [4 3 2] 5 1 3    → 2を除外
3回目: 4 [3 5 1] 3      → 1を除外

最大値と最小値の差は 2 - 1 = 1

解法

取り除く最小値 $X$ を決めると、対応する最小の $Y$ を決めることができる。

$X$ が最小値なのだから、長さ $K$ の区間を決める時、 $X$ 未満の数字を含む区間は取れない。

なので、 $A$ を $X$ 未満の数字で区切って部分列に分割してやる。

A: 9 7 8 6 9 8 1 7 6 8 9 2 8 9 8 3
K: 3  Q: 3

X: 3とすると
   9 7 8 6 9 8 | 7 6 8 9 | 8 9 8 3
3つに分割される

この敷居をまたがないように区間を取る。でも、1回の操作毎に長さは短くなっていき、 $K$ 未満になるとそこからは取れなくなる。

[9  7  8] 6  9  8
[9  8  6] 9  8
[9  8  9] 8
[9  9  8]
 9  9

1つの部分列から取り除ける数字は、部分列の長さを $L$ とすると、最大で $L-K+1$ 個。最小値から取っていくので「小さい方から $L-K+1$ 個」の数字を（取り除こうと思えば）取り除ける。

区間 9 7 8 6 9 8 から取り除ける数字 → 6 7 8 8

これを全部分列について求め、取り除ける数字の候補を集める。候補の中から、最終的に $Q$ 個の数字が取り除かれる。区間は好きに選べるので、候補の小さい方から順番に取り除いていくことが可能である。

なので、候補を昇順ソートして、 $Q$ 番目の数字が、 $X$ を決めた時に取り得る $Y$ の最小値である。

なお、 $X$ は、 $A$ に存在する小さい方の数字から順に探索していくのが効率的である。

例えば $X=3$ の時に分割された箇所が、 $X=7$ の時に分割されずひとつながりの部分列となることは無い。（ $X$ 未満の数字で分割しているので）

A  :  9 7 8 6 9 8 1 7 6 8 9 2 8 9 8 3
X=3:  9 7 8 6 9 8 | 7 6 8 9 | 8 9 8 3
X=7:  9 7 8 | 9 8 | 7 | 8 9 | 8 9 8 |

Xを昇順で探索すると、既存の分割箇所が消えることは無い

なので、計算の途中で長さが $K$ 未満になった部分列は次からは考慮しなくていいし、部分列から最大限除いても $Q$ 個の数字を取り除けなくなったらその時点で打ち切ってよい。

        
          
          
              
              from heapq import nsmallest
 
 
def get_add_list():
    cache = {}
 
    def add_list(s, t):
        global new_lists, removables
        l = t - s
        if l >= k:
            new_lists.append((s, t))
 
            if (s, t) in cache:
                removables.extend(cache[s, t])
                return
 
            cache[s, t] = nsmallest(l - k + 1, aaa[s:t])
            removables.extend(cache[s, t])
 
    return add_list
 
 
n, k, q = map(int, input().split())
aaa = list(map(int, input().split()))
srt = sorted(set(aaa))
lists = [(0, n)]
ans = float('inf')
add_list = get_add_list()
for a in srt:
    new_lists = []
    removables = []
    for s, t in lists:
        r = s
        for i, b in enumerate(aaa[s:t]):
            if a > b:
                add_list(r, s + i)
                r = s + i + 1
        add_list(r, t)
    if len(removables) < q:
        break
    removables.sort()
    ans = min(ans, removables[q - 1] - a)
    lists = new_lists
 
print(ans)

            

        
      