オセロでたとえられているが、要はバブルソートの交換回数の簡易版で、各白につき、左にある黒の個数分だけ操作を行うことになる。
よって「黒カウント変数」を持ち、左から以下を繰り返すことで求められる。
s = input()
ans = 0
tmp = 0
for c in s:
if c == 'B':
tmp += 1
else:
ans += tmp
print(ans)
3 5 8 11 13
間違ったペアを先に作ってしまうと最大に出来ないというところが厄介。
グラフ理論の最大マッチングっぽさはあるのだが、普通の実装では $O(N^3)$ とかになるので $N \le 2 \times 10^5$ の本問ではとても間に合わない。
処理順序をちゃんと考えれば貪欲で解ける。大きい数からペアを決定していくとよい。
$a_k$ とペアに出来る数を考える。
大きい方から貪欲に確定していくので、$a_k$ まで来た時点で、$a_k$ より大きい数が含まれる未確定ペアはもう残っていない。相方は $a_k$ 以下の数の中から探すことになる。
「$a_k+(a_k以下の数)$」の答えは、$a_k$ より大きいが、$2a_k$ より大きくはなり得ない。その中に2の冪乗は1つしかなく「$a_k$ より大きい最小の2の冪乗」一意に決定する。よって相方も一意に決定する。
その相方とペアを作れるだけ作る。
もし相方が、他のもっと小さい数ともペアが作れたとしても、それを作るためには $a_k$ とのペアを必ず解散しなければならないので、差し引きゼロとなる。
上記の例の (3, 5) は、1組を解散することでペアの両方が新たなペアを作れるからダメだったが、この方法では $a_k$ が必ずペアを作れなくなってしまうため、問題ない。
PythonのCounterなどで同じ数字をまとめて計算してしまうと、同じ数字が沢山出てくるようなテストケースでは速く処理できる。
奇数は奇数同士、偶数は偶数同士としかペアにならないため、グループ分けして探すと少し速いかも？（ほとんど変わらない）
from collections import defaultdict
n = int(input())
aaa = list(map(int, input().split()))
def solve(count):
ans = 0
for a in sorted(count, reverse=True):
cnt = count[a]
if cnt <= 0:
continue
ma = 1 << (a.bit_length())
b = ma - a
if b in count and count[b] > 0:
if a == b:
pair = cnt // 2
else:
pair = min(cnt, count[b])
count[b] -= pair
ans += pair
return ans
count_e = defaultdict(lambda: 0)
count_o = defaultdict(lambda: 0)
for a in aaa:
if a % 2 == 0:
count_e[a] += 1
else:
count_o[a] += 1
print(solve(count_e) + solve(count_o))
この場合、辞書式順序を満たし、使われている文字種は2つ
長さ 中身(一例) S1 3 aab S2 4 aabb S3 2 ba
以下の場合は、文字種2つでは構築できず、3つ目が必要
長さ 中身(一例) S1 2 aa S2 1 b S3 2 ba S4 2 bb S5 2 ca
「$k$ 個の文字を使って構築することは可能か？」で $k$ を二分探索する。
$a_i$ が大きいのでシミュレーションは無理……と思いきや、できてしまう。
というのも、$10^9$ 個の文字が並んでいても、ほとんどは'a'（辞書順最小の文字）が並ぶだけで、実際に必要な「辞書順最小以外の文字」の数は限られるから。
$N=2 \times 10^5$ 個の文字列を区別するのは、文字数 $k=2$ であっても、$2^{18} \gt 2 \times 10^5$ より18文字程度でできてしまう。（もちろん途中で文字数がそれ以下になることもあるのでシミュレーションは必要だが、概算として）
使う文字数 $k$ を二分探索に基づいて決める。決まったら、以下の方法で可能か試す。
スタック型のデータ構造で文字列を管理する。格納するアイテムは、[位置, 文字の辞書順] とし、辞書順最小の文字は省略する。文字の辞書順は、1から始まる整数として表現する。
位置: 0 1 2 3 4 5
現在の文字列: a a b c a d
↓
データ構造: [[2, 2], [3, 3], [5, 4]]
各 $a_i$ につき、前の文字列より辞書順が後となる中で最も近い文字列を求めていく。
$S_{i-1}$ の末尾に辞書順最小の文字を繰り返し繋げるのが最適。（'abc'→'abcaaaa…'）
今回のデータ構造的には何もすることはない。
$S_{i-1}$ の $a_i$ 文字目より後を切り落とし、$a_i$ 文字目を辞書順で次の文字にするのが最適
繰り上がったときに桁あふれが発生すれば、$k$ 文字での構築は不可能（$k=4$ で 'dddd' を辞書順で次にしようとしてもできない）。二分探索に従い次の$k$を試す。
たとえば以下のように実装する。
def solve(aaa):
l = 1
r = 200000
while l < r:
m = (l + r) // 2
if check(m, aaa):
r = m
else:
l = m + 1
return r
def check(d, aaa):
if d == 1:
return all(a1 < a2 for a1, a2 in zip(aaa, aaa[1:]))
l = 0
word = [[0, 0]]
for a in aaa:
if l >= a:
if not carry(d, word, a):
return False
l = a
return True
def carry(d, word, a):
while word[-1][0] > a:
word.pop()
while word[-1] == [a, d]:
word.pop()
a -= 1
if a == 0:
return False
if word[-1][0] == a:
word[-1][1] += 1
else:
word.append([a, 2])
return True
n = int(input())
aaa = list(map(int, input().split()))
print(solve(aaa))
何でお前800点問題なんだ……コンテスト中は点数に惑わされずちゃんと一通り問題に目を通さないとダメですね。（一般的な直交座標グラフとx,yが逆という罠はあったようだが）
求めるのは高橋君の行動回数だが、ゲームの支配者は青木君である。
たった2回連続で駒が動かされなかっただけで終わるので、高橋君が動かさなかったら、青木君は自分の手番でも動かさずにゲームを終了できる。よって高橋君は動かし続けるしかなく、選択の余地はない。
逆に青木君は、次に高橋君が動かそうとしても障害物に妨げられるような状況で高橋君に手番を回すのがよい。誘導する障害物は左下半分（後述）の中で自由に選べるので、最も $x$ 座標が小さいものを選ぶのが早く終わる。
→y ↓駒・・・・・ 駒は●で示した範囲なら x ●●・・・・ 青木君が希む任意のマスに行ける ●●●・・・ （障害物が無い場合） ●●●●・・ ●●●●●・
→y ↓駒・・・・・ ある行で、動かせる範囲の最も右端のマスに障害物（×）があると x ●●・・・・ 青木君が動かせないので、以降、動かせる範囲は1つずつ減る ●●×・・・ （右端以外にあるのは大丈夫、その下に行く前にゲームが終わる） ●●●・・・ ●●●●・・
→y ↓駒・・・・・ 青木君は、行ける範囲の中で最も上にある x └┐・・・・ 「障害物の1つ上のマス」に動かして、高橋君にターンを渡す ●│×・・・ ●└┐・・・ 範囲内に障害物が存在しなければ、 ●●×●・・ 一番下の外壁にぶつけるしかなく、答えはHとなる
import sys
def solve(obstacles):
offset = 0
obstacles.sort()
for x, y in obstacles:
if x > y + offset:
return x - 1
if x == y + offset:
offset += 1
return h
h, w, n = map(int, input().split())
obstacles = [tuple(map(int, line.split())) for line in sys.stdin.readlines()]
print(solve(obstacles))