L
なら西を、R
なら東を向いているオセロの石を使った問題でもそうだが、状態が2値で、同じ色/方向の連続が重要な問題において、「区間を反転させる」操作は「境界を最大2つ無くす」操作として捉えられる。
今回の問題も、$S$ を同じ文字の連続毎に区切って
LLLRRRRLLRLRR ↓ LLL RRRR LL R L RR Are you happy? xoo ooox xo x x ox Happiness is Mandatory. Citizen, are you happy? ooo oooo oo o o oo
グループをまたいで幸福な人の数に影響し合ったりしないので、独立に考えてよい。各グループ、先頭以外の全員が、そのグループにおける幸福な人となる。
なので、グループに1人ずつ幸福で無い人がいるので、この時に幸福な人の数は $N-グループ数$ となる。
これを増やすには、グループ数を減らすことがいいし、逆にどこでグループを減らしても変わらない。
1回操作を行う毎に、最大2つまでグループ数を減らせる。(当然だが)1つより少なくはできない。
LLLRRRRLL R L RR ↓ ~~~~ LLLLLLLLL R L RR
よって、$N-\max(1, 初期のグループ数 - 2K)$ が答えとなる。
n, k = list(map(int, input().split())) s = input() group = 1 for c, d in zip(s, s[1:]): if c != d: group += 1 print(n - max(1, group - 2 * k))
C++ のsetを使うことが想定解の問題は、Pythonではそれに値するデータ構造が無く、自力実装しても遅いため、なかなか厳しい。
setとは要素を昇順に保ったまま追加・削除を行えるデータ構造で、「ある値を追加するとしたらその直前の値は何か」も $O(\log{N})$ で求められる。
Pythonでは、bisectで二分探索により何番目に追加できるかは求められるものの、値を挿入するには $O(N)$ かかる。
一応、ごり押しで一度に2要素を管理するセグ木を工夫すれば、PyPyで通ったので、その解法をメモ。
まず、答えを求めるのに必要な情報を考える。
区間を主軸に考えるよりも、各 $P_i$ に注目して「その数が何組の $L,R$ で $X_{L,R}$ になるか」を考える。
自分より左/右に2つ以上、自分より大きな数があると、もうその数はXになり得ない。 「自分より左に1個、右に0個」と「左に0個、右に1個」に分けるとよさそう。
それには、「左にある自分より大きい数のindex」「右にある自分より大きい数のindex」を得たい。
直近のindexだけではそれを越えた範囲がわからないので、直近と、その次の2つまでのindexが分かればよい。
8 2 7 3 ④ 5 6 1 |<----|<----| |->|-->| ~~~~ ~~ 左に1個、右に0個の時に、左右端になり得る範囲 2 × 1 ~~~~~ ~~ 左に0個、右に1個の時に、左右端になり得る範囲 2 × 1 2x1 + 2x1 = 4 が、4がXになる区間の数
それ以上左/右に大きい数が無い時は、1つ範囲外のindex(-1 と 8)で埋めておく。これは後の計算で楽になる。
i 0 1 2 3 4 5 6 7 8 2 7 3 4 5 6 1 ------------------------------------ 左1st index -1 0 0 2 2 2 2 6 (x_i) 左2nd index -1 -1 -1 0 0 0 0 5 (w_i) 右1st index 8 2 8 4 5 6 8 8 (y_i) 左2nd index 8 3 8 5 6 8 8 8 (z_i)
こうすると、各 $i$ につき、$P_i \times ((x_i - w_i)(y_i-i) + (i-x_i)(z_i-y_i))$ を求め、合計すると答えとなる。
左,右のそれぞれから、直近2要素のindexを管理するセグメント木を構築する。
説明のため数字を変更して、$P$ を $\{0,1,2,...,N-1\}$ の順列とし、添え字も $\{P_0,P_1,...,P_{N-1}\}$ とする。
左のindexを求めるなら、全要素 [-1, -1] で初期化し、$P_0$ から順に以下を処理する。
P = {2,0,3,1} [0,4) [-1,-1] / \ [0,2) [2,4) [-1,-1] [-1,-1] / \ / \ [0,1) [1,2) [2,3) [3,4) [-1,-1] [-1,-1] [-1,-1] [-1,-1] i=0, Pi=2 get(3,4) = [-1, -1] update(2,0) [ 0,-1] / \ [-1,-1] [ 0,-1] / \ / \ [-1,-1] [-1,-1] [ 0,-1] [-1,-1] i=1, Pi=0 get(1,4) = [0,-1] update(0,1) [ 1, 0] / \ [ 1,-1] [ 0,-1] / \ / \ [ 1,-1] [-1,-1] [ 0,-1] [-1,-1] i=2, Pi=3 get(4,4) = [-1,-1] update(3,2) [ 2, 1] / \ [ 1,-1] [ 2, 0] / \ / \ [ 1,-1] [-1,-1] [ 0,-1] [2,-1] i=3, Pi=1 get(2,4) = [ 2, 0] update(1,3) [ 3, 2] / \ [ 3, 1] [ 2, 0] / \ / \ [ 1,-1] [ 3,-1] [ 0,-1] [2,-1]
こうやってget()で順に得た2つの数が、それぞれ左の1st,2nd indexとなっている。
i 0 1 2 3 2 0 3 1 ------------------------ 左1st index -1 0 -1 2 左2nd index -1 -1 -1 0
同じことを右から、今度は最小の2要素を保ちつつ求めると、右側の自分より大きい数のindexがわかる。
class SegmentTree: def __init__(self, n, init_value): self.n = n n2 = 1 # nより大きい2の冪数 while n2 < n: n2 <<= 1 self.n2 = n2 self.tree = [[init_value, init_value] for _ in range(n2 << 1)] self.ini = init_value def update(self, i, x): # 注: 同じiへのクエリは複数来ないことを利用して単純化 i += self.n2 self.tree[i][0] = x while i > 1: i >>= 1 sti = self.tree[i] if sti[0] > x: sti[1] = sti[0] sti[0] = x elif sti[1] > x: sti[1] = x def get(self, a, b): result = [self.ini, self.ini] q = [(1, 0, self.n2)] while q: k, l, r = q.pop() if a <= l and r <= b: stk = self.tree[k] if result[0] > stk[0]: result[1] = min(result[0], stk[1]) result[0] = stk[0] elif result[1] > stk[0]: result[1] = stk[0] continue m = (l + r) // 2 k <<= 1 if a < m and l < b: q.append((k, l, m)) if a < r and l < m: q.append((k + 1, m, r)) return result def solve(n, ppp): str = SegmentTree(n, n) right = [] for i in range(n - 1, -1, -1): p = ppp[i] right.append(str.get(p, n)) str.update(p - 1, i) right.reverse() ans = 0 stl = SegmentTree(n, 1) for i in range(n): p = ppp[i] l1, l2 = stl.get(p, n) l1, l2 = -l1, -l2 r1, r2 = right[i] ans += p * ((l1 - l2) * (r1 - i) + (r2 - r1) * (i - l1)) stl.update(p - 1, -i) return ans n = int(input()) ppp = list(map(int, input().split())) print(solve(n, ppp))
C++ のstd::setを用いる問題は、たとえば この問題(ネタバレ注意)なんかもそうだが、setを使えないPythonでは「次に見るべきindexを保持して、何らかの順番で処理する上でスキップできるとわかったindexは張り替える」ことで、高速に実装できるケースがある。
各 $i$ につき、「暫定、自分より大きな左/右にある直近の数のindex」をリストで保持すると、2つ目の自分より大きな数のindexは、リストを2回辿ればよい。
i 0 1 2 3 4 5 6 7 8 2 7 3 4 5 6 1 ------------------------------ 左1st -1 0 0 2 2 2 2 6 ↖___/ 4にとって、左1st indexは2, 左2nd indexは0
ただし、よく見るとたとえば $P_i=1$ にとっては正しく成り立っていない。 これは上記の左1stリストが最終更新済みのものだからで、実際は $P_i$ の小さい方から順に更新しながら求めていくことで、正しく求まるようになる。
左と右を同時に求める。 まず、リストをすぐ左/右のindexで初期化する。 範囲外の値に対応するため、便宜的に末尾に-1/8を2つずつ付け足しておく i 0 1 2 3 4 5 6 7 (8 9 = -1) P 8 2 7 3 4 5 6 1 ------------------------------------ L -1 0 1 2 3 4 5 6 -1 -1 R 1 2 3 4 5 6 7 8 8 8 i=7, Pi=1 左1st = L[7] = 6 左2nd = L[L[7]] = 5 右1st = R[7] = 8 右2nd = R[R[7]] = 8 Piの小さい順に処理しているため、次のループ以降に処理される数字にとっては、 ・Piより右の要素にとって、Piはもはや大きい要素では無くなる = Lにおいてスキップしてよい ・Piより左の要素にとって、Piはもはや大きい要素では無くなる = Rにおいてスキップしてよい これを表現するため、 L[R[7]] = L[7] R[L[7]] = R[7] で更新する L -1 0 1 2 3 4 5 6 ⑥ -1 R 1 2 3 4 5 6 ⑧ 8 8 8 以下、同様に処理する i=1, Pi=2 左1st = L[1] = 0 左2nd = L[L[1]] = -1 右1st = R[1] = 2 右2nd = R[R[1]] = 3 L -1 0 ⓪ 2 3 4 5 6 6 -1 R ② 2 3 4 5 6 8 8 8 8 i=3, Pi=3 左1st = L[3] = 2 左2nd = L[L[1]] = 0 右1st = R[1] = 4 右2nd = R[R[1]] = 5 L -1 0 0 2 ② 4 5 6 6 -1 R 2 2 ④ 4 5 6 8 8 8 8 ...
これで左右の1st,2nd indexが求まる。
from operator import itemgetter def solve(n, ppp): qqq = sorted(enumerate(ppp), key=itemgetter(1)) left_next_index = list(range(-1, n - 1)) + [-1, -1] right_next_index = list(range(1, n + 1)) + [n, n] ans = 0 for i, p in qqq: l1 = left_next_index[i] l2 = left_next_index[l1] r1 = right_next_index[i] r2 = right_next_index[r1] ans += p * ((l1 - l2) * (r1 - i) + (r2 - r1) * (i - l1)) left_next_index[r1] = l1 right_next_index[l1] = r1 return ans n = int(input()) ppp = list(map(int, input().split())) print(solve(n, ppp))
$S$ で最大の要素を、最初のスライムにする。
何らかの基準を決めて貪欲に、体力の大きい順に割り振っていって最後まで矛盾無く決まるか調べることを考える。
N=3 t 0 1 2 3 ○→○→○→○ | `----→○ |----→○→○ `--------→○ S = {4, 3, 3, 3, 2, 2, 2, 1} ↓ t 0 1 2 3 4→3→2→1 | `----→2 |----→3→2 `--------→3
早めに生まれた子にはそれから沢山の子を生んでもらわにゃならんので、体力は大きく保った方が良さそうだが、単純に時刻で埋めていくと、同じ数字が多くある時に矛盾する。
S = {4, 3, 3, 3, 2, 2, 2, 1} t 0 1 2 3 4→3→3→○ | `----→○ |----→3→○ `--------→○
体力の大きなスライムは、より体力の大きなスライムからしか生まれないので、親が大きい方から当てはめていく? しかし、それでは今度は下の方に同じ数字が沢山ある時に矛盾する。
S = {4, 3, 2, 2, 1, 1, 1, 1} t 0 1 2 3 4→3→○→○ | `----→○ |----→2→○ `--------→2 ↓ 4→3→1→1 | `----→1 |----→2→1 `--------→2
時刻が早い方から割り当てていく考え方で基本はよくて、ただし同じ体力のスライムの更新はまとめて同時に行うようにする。
スライム毎に「次にそのスライムが子を生める時刻」を優先付きキューに入れる。
体力が大きいスライムから順に○への割り当てを確定していく(時刻が重要であって、同時刻ならどの○か、というのは特に区別しなくて良い)。
同じ体力のスライムが何匹いるかはあらかじめ数えておき、優先キューへ突っ込むのは、同体力のスライムの割り当てを全て確定し終えた後とする。
どこかの体力のスライムで、優先キューにそのスライムを生めるスライムが残ってない、という状況になれば不可能。最後まで行けば可能。
S = {4, 3, 3, 3, 2, 2, 2, 2} s = 4 t 0 1 2 3 優先キュー(時刻) 4→○→○→○ [0] | `----→○ |----→○→○ `--------→○ s = 3 x 3 t 0 1 2 3 [1] 1匹目を生んだ直後 4→3→○→○ [2] 2匹目を生んだ直後 | `----→○ [ ] 3匹目を生んだら、時刻的にもう生めないので除外 |----→3→○ [1, 2] 体力3のスライムが子を埋める時刻をまとめて入れる `--------→3 s = 2 x 4 t 0 1 2 3 [2, 2] 1匹目を生んだ直後 4→3→2→○ [2] 2匹目を生んだ直後 | `----→2 [ ] 3匹目を生んだ直後 |----→3→2 [ ] 4匹目は生めない!不可能 `--------→3
まず、スライムの家系図は自己相似形(?)になる。
例えば下図で、時刻0のスライムから生まれた子たちの $t=3$ までの親子関係と、時刻1に生まれたスライムが $t=4$ までに生む子たちの親子関係は同じ構造となる。
t 0 1 2 3 ○→○→○→○ | `----→○ |----→○→○ `--------→○ ↓1秒後 ○→●→●→●→● | | `----→● | |----→●→● | `--------→● |----→○→○→○ | `----→○ |--------→○→○ `------------→○
これを踏まえて、「体力の大きい順に、その時に生める最も早い時刻に割り当てる」のが良いことを言う。
「体力の大きなスライムをより早い時間に生めるのに、生まなかった場合でも、矛盾無く割り当てできた」とする。
S = {5, 4, 3, 3, 2, 2, 2, 1} 5→③→2→1 | `----→2 |----→④→3 `--------→2
この時、「④以下の構造」と「③以下のうち、④以下の構造と一致する部分」を、矛盾無く入れ替えられる方法が存在する。
5→④→3→1 「④→3」 | `----→2 「③→2」を入れ替え |----→③→2 `--------→2
もし、こんな割り当てだと、入れ替えると矛盾が発生するが、
5→③→2→1 5→④→1→1 | `----→2 → | `----→2 |----→④→1 |----→③→2 `--------→2 `--------→2
④から子の方面に辿って、あるスライムで、③で同じ箇所に相当するスライムの体力が等しいか大きくなったら、そこで入れ替えるのを止めるとよい。
↓2と1を比較して、2の方が大きいので、それ以下の入れ替えは停止 5→③→❷→1 5→④→2→1 | `----→2 → | `----→2 |----→④→❶ |----→③→1 `--------→2 `--------→2
各箇所が、成立の状態を保ったまま入れ替えられることを整理する。
全ての箇所で、成立を保ったまま入れ替えが可能であると言える。
「体力の高いスライムから、割り当て可能な最も早い時刻に割り当てる」という方針に当てはまらないで成功する割り当てが存在しても、必ず当てはまるような割り当てに変換することが出来るので、この方針に従って割り当てていって不可能なら、不可能と判定してよい。
from collections import Counter from heapq import heappop, heappush def solve(n, sss): ccc = Counter(sss) keys = sorted(ccc.keys(), reverse=True) if ccc[keys[0]] != 1: return False q = [0] for k in keys[1:]: nq = [] for _ in range(ccc[k]): try: t = heappop(q) except IndexError: return False if t < n - 1: nq.append(t + 1) heappush(q, t + 1) for item in nq: heappush(q, item) return True n = int(input()) sss = list(map(int, input().split())) print('Yes' if solve(n, sss) else 'No')