ABC312 C - Invisible Hand (Diff:727 茶)の解説 [AtCoder][Python]

8/2: 修正、図の追加を行いました。

問題へのリンク https://atcoder.jp/contests/abc312/tasks/abc312_c

問題概要

りんご市場に N 人の売り手と M 人の買い手がいる。
i 番目の売り手は、A[i]円以上でならりんごを売ってもよいと考えている。
i 番目の買い手は、B[i]円以下でならりんごを買ってもよいと考えている。

この時、次の条件を満たすような最小の整数Xを求めよ。

条件: りんごを X 円で売ってもよいと考える売り手の人数が、りんごを X 円で買ってもよいと考える買い手の人数以上である。

問題要約

(配列Aに含まれるX以上の数の個数) ≧ (配列Bに含まれるX以下の数の個数)となる最小のXを求めよ。

制約

1 ≦ N, M ≦ 2×10⁵
1 ≦ A[i], B[i] ≦ 2×10⁹

解説

下図は、入力例1をグラフにしたものである。緑は売る人の人数、オレンジは買う人の人数を表している。重なったところは少し濃くなっている。

この図では、X(リンゴの値段)を0から増やしていくと、売り手(緑)の人数は0人から徐々に増えていき、買い手(オレンジ)の人数は4人から減っていくことが分かる。途中で逆に減ったり増えたりすることはない。そのため、0円から値段を高くしていって売り手の人数が買い手の人数を上回ったその瞬間の値段が条件を満たす最小のXである。入力例1では110円が(売り手の人数)>=(買い手の人数)となる瞬間である。

(売り手)≧(買い手)となる瞬間のみが分かればよいので、人数が増減するタイミング(A[i]とB[i])だけに注目する。まず、それを知るためにAとBの要素を入れる空のリストLを作る。そのリストに、AとBの要素を、元々AとBのどちらにあったか分かるようにした上で入れていく。この時、Bに含まれる要素には全て1を足す。

これは、0円から値段を上げていった時、買い手は値段がB[i]円の時はまだ買うことができ、(B[i]+1)円になると買えなくなるので、人数が切り替わるタイミングはB[i]+1の時だからだ。一方、売り手は値段がA[i]円になった時に買えるようになり、そのタイミングで人数が切り替わるから変更する必要はない。

そして、その新しいリストLを昇順(小さい順)にソートする。 また、AとBのカウント用の変数 cnt_a ,cnt_bを用意し、cnt_a = 0, cnt_b = Mとする。

そして、新しいリストを左から見ていく。

• もし、要素がAに入っていたものだったら、売る人が1人増えたのでcnt_a += 1
• もし、要素がBに入っていたものだったら、買う人が1人減ったのでcnt_b -= 1
• もし、cnt_a ≧ cnt_bになったならその時の要素が答え

例:入力例1

上の動作は入力例1では下表のようになり、初めて a_cnt ≧ b_cnt となる110が答えである。 ※Bの要素には1を足してある。「A or B」は要素がAとBどちらに含まれているかを指す。

i	始め	0	1	2	3	4	5	6
要素	-	81	90	101	110	120	121	10001
A or B	-	B	A	B	A	A	B	B
a_cnt	0	0	1	1	2	3	3	3
b_cnt	4	3	3	2	2	2	1	0

実際は3以降は行わないので、110を出力したらその場でbreakまたはexit()を使って終了する。

実装例(Python)

N,M = map(int,input().split())
A = list(map(int,input().split()))
B = list(map(int,input().split()))

L = []
for i in range(N):
    L.append((A[i], 0)) # 0はAに入っていたことを表す
for i in range(M):
    L.append((B[i]+1, 1)) # 1はBに入っていたことを表す

L.sort() # Lを要素の大きさでソート
cnt_a,cnt_b = 0, M

#eは要素、gはどちらに含まれるか(0ならA,1ならB)
for e, g in L:
    # Aに含まれているのなら
    if g == 0:
        cnt_a += 1
    # Bに含まれているのなら
    else:
        cnt_b -= 1

    #cnt_aがcnt_b以上になったら
    if cnt_a >= cnt_b:
        print(e) # 要素を出力
        exit() # その場で終了

おまけ…問題名の由来

「Invisible Hand」=見えざる手。Adam Smithが『国富論』で用いた語。経済は各個人の利益追求に任せておいても「見えざる手」に導かれ社会全体の利益につながると説いた。

https://eow.alc.co.jp/search?q=invisible+hand#resultsList-sectionより

「需要曲線」と「供給曲線」をイメージさせられる問題だった。

CodeForces Round 889 Div. 2 A Dalton the Teacher の解説 [Python]

2023/8/21 文章を修正しました。

問題文(英語) https://codeforces.com/contest/1855/problem/A

問題概要

N人の生徒が1列に並んでおり、生徒 i (1≦i≦N)は椅子 p[i](1≦p[i]≦N)に座っている。先生は生徒を2人選んで交換する動作を行える。この時、すべての生徒と椅子の番号が異なるようにするために必要な最小の交換回数を求めよ。

知っている方向け: 2つの数を選んで入れ替え、完全順列にする時の最小回数を求めよ。

条件

• 1 ≦ (テストケース数) ≦ 1000
• 2 ≦ N ≦ 10⁵
• pは[1, 2,…N]の並び替え
• (全てのテストケースのNの総和)≦10⁵
• 答えは必ず存在する

例:テストケース3

5
1 2 5 4 3

出力例:
2

最初は下図のような状態。

例えば、人1と人2を入れ替え、さらに人2と人4を入れ替えることで2回で椅子の番号と人の番号が異なるようにできる。

解説

まず、「どの人を入れ替えるべきか」を考える。すると、人と席の番号が同じになっている人は入れ替える必要がある。(先ほどの例では人1, 2, 4)
この条件を満たしている人を今後は単に「条件を満たす人」と呼ぶことにする。

もし、「条件を満たす人」が2人いた場合、2人の場所を交換すれば、2人とも人と席の番号が異なるものになる。そのため、「条件を満たす人」から2人組のペアを作っていき、ペア同士でそれぞれ1回交換すれば良いから、ペアの個数が答えになることが分かる。

問題は「条件を満たす人」が奇数人存在する時で、この時は2人ペアを作っていくと1人余ってしまう。しかし、この1人も全てのペアを交換し終わった後に誰とでも交換可能である。それは、条件を満たす人は交換すると番号が変わり、満たさない人も交換先の席と同じ番号は満たす人が持っているため、確実に移動先の席と同じ人の番号ではないからである。

よって、出力すべき答えは、条件を満たす人の人数をa人とすると、

• aが偶数の時、a/2個のペアができるから、a/2
• aが奇数の時、a-1個でペアを作り、残りの1人で1回交換するから、(a-1)/2+1 = (a+1)/2

これをif文で場合分けして出力しても良いが、aが偶数の時 a//2 と (a+1)//2 の値は変わらない。( // は切り捨て除算の記号)。よって、aの値に関わらず (a+1)//2 が答えとなる。

計算量はO(N)。

実装例(Python)

T = int(input()) #テストケースの数

# 各テストケースごとに
for t in range(T):

    # 生徒の数 N
    N = int(input())
    #1始まりなので、先頭に適当な値を入れる
    P = [None] + list(map(int,input().split()))

    # 条件を満たす人をカウントする変数
    a = 0

    # 各iについて、条件を満たすならカウント
    for i in range(1, N+1):
        if i == P[i]:
            a += 1
    # 答えを出力
    print((a+1)//2)

ABC312 B - TaK Code (Diff:216 灰) の解説[AtCoder][Python]

最近AtCoderでよく見る、「実装の重いB問題」でしたね。

問題概要

• 9x9マスの領域で、左上と右下の3x3マスがそれぞれ黒('#')、その周りを囲う部分が白('.')になっているものをTaK Codeと呼ぶ。

• 縦Nマス、横Mマスのグリッドがある。そこに含まれる9x9マスの領域のうち、「TaK Code」の部分の左上の座標を全て出力せよ。

• 下図がTaK Code('#'が黒、'.'が白、'?'はどちらでも良い)

###.?????
###.?????
###.?????
....?????
?????????
?????....
?????.###
?????.###
?????.###

解説

親切にもTaK Codeが出ているので、これをコピー&ペーストして調べたい部分と比較する。

比較の方法については、調べたい9x9マスの左上のマスを引数として受け取る関数を作り、9x9の範囲全てをTaK Codeと比べていく。実際は '?' である部分まで見る必要はないが、細かい範囲を考えるよりはすべて見たほうが楽。もし '?' でない部分で異なるならその場でFalseを返し、最後まで間違いがなかったらTrueを返すようにする。

あとは二重for文でfor i in range(N): for j in range(M):if (判定関数(i,j)…のようにしていき、結果がTrueなら(i,j)を出力すると、自然と辞書順になり条件を満たす。

なお、右下の一部のマスではそもそも(i,j)を左上にして正方形を作ることができないが、関数側でもし範囲をオーバーしそうになったらFalseを返す実装にすると、条件を満たさないi・jの範囲を考える手間を省ける。

実装

実装では、左上のマスを(0, 0)として考える。

#TaK Codeはコピペして、少し改造してリストにする
tak = ["###.?????",
"###.?????",
"###.?????",
"....?????",
"?????????",
"?????....",
"?????.###",
"?????.###",
"?????.###"]

# Sの(i, j)を左上とする9x9がTaKであるかを判定する関数
def takcheck(i, j):
    global N, M # N, Mが関数内でも使えるようにする

    # Sの調べている部分の座標(i+a, j+b)とTaKの(a, b)を比較
    for a in range(9):
        for b in range(9):

            #もしi+aまたはj+bが範囲外(9x9が作れない)ならばFalseを返す
            if not (0 <= i+a < N and 0 <= j+b < M):
                return False

            # もしTaKが?なら調べない
            if tak[a][b] == "?": continue

            # もし異なるならFalseを返す
            if S[i+a][j+b] != tak[a][b]: return False

    # もし最後まで異なるものがなければTrueを返す
    return True

N,M = map(int, input().split())
S = [input() for _ in range(N)]

# (i, j)全ての組において
for i in range(N):
    for j in range(M):

        # もしtakcheck(i,j)がTrueなら
        if takcheck(i,j):
            # 実際は左上は(1,1)であるため1を足して出力
            print(i+1, j+1)

Pythonのソート自由自在 ～初歩から関数を用いた複雑なソートまで～ [reverse, key, lambda, cmp_to_key]

当記事は、ソートを自由自在に使いこなすための方法を、具体例を多く用いて解説した記事です。

外部ライブラリ(NumPy, pandasなど)に関しては扱っていませんのでご了承ください。

目次

sort()とsorted()

Pythonには、数値や文字列を小さい順/大きい順(文字は早い順/遅い順)で並び替える(=ソートする)関数が用意されています。
それが、sort() と sorted() です。

sort()はリストそのものを直接ソートする処理で、

(リスト名).sort()

といった形で使います。

一方で、sorted()は元のリストをソートした新しいリストを作る処理で、基本的に、

sorted(リスト名)

といった形で使います。

sort(), sorted()ともに、引数を指定しないと昇順(小さい順)に並び替えられます。sort()・sorted()の引数はreverseとkeyがあり、降順で並べたい時はreverseを、ある条件に沿って並べたいときはkeyを指定します(詳しくは後程解説します)。

下はsort()、sorted()を利用した例です。リストAにsort()を、リストBにsorted()を適用しています。

sort()

A = [2, 4, 5, 3, 1]

A.sort() #A自体をソート
print(A)

# 出力
[1, 2, 3, 4, 5] # ←A Aそのものがソートされている

sorted

B = [2, 4, 5, 3, 1]

C = sorted(B) # Bをソートした新しいリストCを生成
print(C) #新しいリスト
print(B) #元のリスト

# 出力
[1, 2, 3, 4, 5] # ←C Bを基に新しく作られ、ソートされている
[2, 4, 5, 3, 1] # ←B Bそのものは変更されていない

また、二次元リストをソートすることも可能で、デフォルトでは各要素の1番目の要素を基にソートされ、同じだった場合は2番目の要素…というように並び替えられます。

L = [[1, 1], [2, 2], [0, 2], [1, 0], [1, 2], [0, 1], [2, 1]]
L.sort()
print(L)

# 出力
# [[0, 1], [0, 2], [1, 0], [1, 1], [1, 2], [2, 1], [2, 2]]

引数reverseを指定する

sort()、sorted()ともに、reverseという引数を指定することができます。()の中に「reverse=True」と書くことで、降順に並べることができます。(デフォルトではFalseが指定されています。)

L = [3, 5, 4, 2, 1]
L.sort(reverse=True)
print(L)

# 出力
# [5, 4, 3, 2, 1]

引数keyに関数を渡す

sort()関数・sorted()関数には、引数keyに関数を指定し、並び替える基準を設定することができます。
例えば、整数から成るリストを、絶対値(マイナスを外した数)が小さい順にソートしたいとします。その時は、keyとして絶対値を返す関数absを渡します。

L = [-3, 1, 4, -7, 0]
L.sort(key = abs)
print(L)

# 出力
# [0, 1, -3, 4, -7]
# 絶対値は0, 1, 3, 4, 7なので、正しくソートできている

絶対値が小さい順で出力されています。リストのそれぞれの要素がabsの引数として代入され、その返り値を基にソートされている感じです。

そして、この部分には組み込み関数だけでなく、自作の関数を使用することもできます。abs()と全く同じ動作をする関数myfunc()を作って渡してみます。この時、myfuncには1つ引数を用意してください。リストの各要素がその引数に代入され、その返り値をもとにソートが行われます。

def myfunc(x):
    if x >= 0: return x
    return -x

L = [-3, 1, 4, -7, 0]
L.sort(key = myfunc)
print(L)

# 出力
# [0, 1, -3, 4, -7]

また、これらは二次元リストでも利用することができます。たとえば、[[1,2],[3,4]…]のような、2つペアのリストを要素として持つ二次元リストを考えます。 この時、1つ目の要素ではなく2つ目の要素でソートしたいとします。

def myfunc2(x):
    return x[1]

L = [[5, 2], [7, 1], [9, 5], [2, 4]]
L.sort(key = myfunc2)
print(L)

# 出力
# [[7, 1], [5, 2], [2, 4], [9, 5]]
# 2番目の要素は1, 2, 4, 5になっているので正しくソートできている。

lambda式(ラムダ式、無名関数)を使う

とはいえ、def ～: return ～ のような一行で書けるような処理でも関数を作っていると管理が面倒です。そこで、Pythonにはlambda式(ラムダ式)という物が用意されています。lambda式とはいわば「使い捨て」の関数を簡潔に定義できる記法です。名前を付けることも可能ですが、基本付けません。

Pythonでは次のように記述できます。

lambda (関数名) (引数1), (引数2)… : (返り値)

これだけだと分かりにくいですが、実際に先ほどのmyfunc2()をlambda式で書いてみます。

#先ほどのmyfunc2
def myfunc2(x):
    return x[1]

# myfunc2と同じ機能
lambda x: x[1] #←これ

xを受け取って、x[1]をreturnしています。これだけです。
この関数をsortのkeyに入れれば良いのです。

L = [[5, 2], [7, 1], [9, 5], [2, 1]]
#myfunc2だった部分にlambdaを入れる
L.sort(key = lambda x: x[1])
print(L)

# 出力
# [[7, 1], [5, 2], [2, 4], [9, 5]]
# 先ほどと同じ

複数の関数を用いたソート

先ほどでは評価する関数に数値を指定していましたが、もし異なる要素が同じ数値だった場合にはどうなるでしょうか。

例えば、文字数で判断するとき、下のリストに含まれる要素の文字数は全て同じ5文字です。keyに文字数の長さを返すlen関数を渡して実行してみます。

color_list = ["white", "green", "black", "brown"]
color_list.sort(key = len)

# 出力
# ['white', 'green', 'black', 'brown']
# 変化せず

変化しませんでした。Pythonの仕様では、評価の結果が同じなら元の順序を維持するようになっています。(安定性)

もし同じ長さなのであれば、これまでのソート同様、辞書順(アルファベット順)に出力したいとします。

その場合、(一つ目の関数の結果,二つ目の関数の結果)のようなタプルを返す関数をkeyにすると良いです。ソートの順序はまず1つ目の要素で判断され、同点だったら2つ目、それも同点だったら3つ目…のように並び替えられます。
今回は、第二引数にxをそのまま渡せば文字列が評価され昇順に並び替えられます。

color_list = ["white", "green", "black", "brown"]
color_list.sort(key = lambda x: (len(x), x))

また、二次元リストにも適用することができます。例えば、数字のペアのうち1つ目は昇順、2つ目は降順に並べ替えたいとします。
「降順」を表すために、降順にしたい部分が入る所にマイナスをつけます。ソートされたリストの要素は
1<2<3…
のように並んでいますが、全ての要素に-1をかけると
-1>-2>-3…
のようになり大小関係が逆転するからです。

L = [[1,1],[2,2],[0,2],[1,0],[1,2],[0,1],[2,1]]
# x[1]にマイナスが付いている
L.sort(key = lambda x: (x[0], -x[1]))
print(L)

# 結果
# [[0, 2], [0, 1], [1, 2], [1, 1], [1, 0], [2, 2], [2, 1]]

まずタプルの1つ目のx[0]で1つ目の要素が昇順に並び替えられ、1つ目の要素が等しいペア同士が2つ目の-x[1]で降順に並び替えられています。

functools.cmp_to_key()を用いた、要素同士を比較するソート

先ほどの関数では関数の返り値の数値や文字列を基にリストをソートしました。しかし、時には全ての要素を返り値のみで比較することが難しい場合があります。要素を2個の大小が比較できる場合は、functools.cmp_to_key()関数を用いることができます。

手順としては、まず比較するために「x,yを引数として受け取り、yと比べてxが小さいなら-1、等しいなら0、大きいなら1を返す関数」を作ります。そしてfunctools.cmp_to_key(関数名)をソートのキーに渡します。

1つ、設定を考えてみます。

• 整数に「強さ」があるとします。
• 偶数は奇数より強く、奇数同士、偶数同士では大きい数のほうが強いとします。

これらの条件を基に、リストの数値を弱い順に並べたいとします。

import functools

# nが偶数ならTrue,奇数ならFalseを返す関数
def iseven(n):
    if n % 2 == 0:
        return True
    return False

# yよりxが小さければ-1、
# 等しいなら0、
# 大きいなら1を返す関数
def myfunc3(x, y):
    # もし、xとyがどちらも偶数、
    # またはどちらも偶数でない(奇数)ならば
    # x、yの大きさで判断
    if iseven(x) == iseven(y):
        if x < y: return -1
        elif x == y: return 0
        else: return 1

    # そうでないなら、x、yの大きさに関わらず偶数の方が強い
    else:
        if iseven(x):
            return 1
        else:
            return -1

L = [1, 2, 3, 4, 6, 6, 99, 100]

# cmp_to_keyの引数にmyfunc3を指定
L.sort(key = functools.cmp_to_key(myfunc3))
print(L)

# 出力
# [1, 3, 99, 2, 4, 6, 6, 100]

cmp_to_key()を用いて並べることができました。

おわりに

ここまで読んでくださりありがとうございました。 誤字、誤っている情報などありましたらコメント欄にお願いします。

参考文献

• Python公式ドキュメント

  • https://docs.python.org/ja/3/library/stdtypes.html

  • https://docs.python.org/ja/3/library/functions.html

  • https://docs.python.org/ja/3/library/functools.html

  • https://docs.python.org/ja/3/howto/sorting.html

ABC311 C - Find it! (Diff:448 茶) の解説 [AtCoder][Python]

問題へのリンク https://atcoder.jp/contests/abc311/tasks/abc311_c

問題概要

N頂点N辺の有向グラフがあり、i番目の頂点からはA[i]に伸びている。
この時、有向閉路を1つ求めよ。

入力例1

N = 7, A = [6, 7, 2, 1, 3, 4, 5]

画像:https://img.atcoder.jp/abc311/0ab396c54e276edb27de02ad3b20cf7f.png

出力例1

4
7 5 3 2

他の解答例
4
5 3 2 7

---

3
1 6 4

など

解き方

閉路とは、何度も同じ頂点をループする部分のこと。

入力例1では、試しに頂点1から辿ってみると、
1→6→4 → 1→6→4 → 1…と、何度も同じ頂点を回っていることがわかる。そして、この頂点の繰り返し(1, 6, 4)は求めたい閉路である。そのため、繰り返しが求められれば良い。

しかし、必ずしも最初から繰り返しになっているとは限らない。入力例3では、

入力例3のグラフ

画像:https://img.atcoder.jp/abc311/c31a7153e0ca36e8c0e1dd4c7bfe5329.png

1→3→4→ 7→8→2→ 7→8→2→ 7→8…と、(7,8,2)が途中からループになっている。そのため、

• まず、訪れた頂点を管理する空のリストを作る
• ある頂点から移動をスタートする。移動先の頂点が
  • 初めて訪れた頂点であればそのリストに追加する
  • もし訪れた頂点がリスト内にある(=既に訪れている)のなら、1回目の頂点がリストのどこにあるか探す→そこ以降の部分が閉路

というのを実装すれば答えが求められる。 例えば入力例3では、リストに[1,3,4,7,8,2]と入れていき、その次の頂点は2回目の7で、その部分からはループになる。よって、閉路はリストにある1回目の7から、2回目の7が入る直前の2までであることが分かる。よって、答えはリストの1回目の7以降の部分[7,8,2]である。

ちなみに、開始する頂点はどこでもよく、必ずどこかの閉路に繋がっている。これは、頂点は必ずどこかに繋がっているので、頂点を移動する動作は無限に行われるが、頂点は有限個しかないので、最終的にはいずれかの閉路に繋がって無限ループしない限り動作を無限に行うことができないからである。

コード(Python)

N = int(input())
A = list(map(int,input().split()))
visited = [False] * (N+1) # 既に訪れたかを管理

L = []
x = A[1] # 今いる頂点を示すx
while not visited[x]: # xが訪れたことのある頂点になるまで
    L.append(x) # Lに追加
    visited[x] = True # 訪れた
    x = A[x-1] #次の頂点に移動

first_x = 0 #1つ目の頂点のindex
while L[first_x] != x:
    # xは2つ目の頂点を指す
    # 1つ目の頂点のindexを探す
    first_x += 1

ans_list = L[first_x:] # 答えはLのfirst_x以降
print(len(ans_list))
print(*ans_list)

8/2 文章を修正しました。

ABC307 D - Mismatched Parentheses (Diff:666 茶)の解説 [AtCoder][Python][C++]

問題へのリンク https://atcoder.jp/contests/abc307/tasks/abc307_d

問題概要

アルファベットと"("、")"から成るN文字の文字列Sが与えられる。 先頭が"("、最後が")"で囲まれ、中に"("、")"を含まない文字列を削除する動作を繰り返す。

例(入力例1)

N=8, S=a(b(d))c

a(b(d))c
→ a(b)c
→ ac

解き方

与えられた処理を愚直に実装していくと、最高2×10⁵の長さのSを何回も先頭から順に見ていき、途中の文字列を削除する必要があるので、間に合う見込みがない。

手順1 ペアを探す

最初に、削除されるときのかっこのペアを考える。 例えば、入力例1 a(b(d))c では、先頭を0文字目とすると

a(b(d))c

1文字目の"("と6文字目の")"、3文字目の"("と5文字目の")"がそれぞれペアになっている。1文字目から6文字目を削除すれば3文字目から5文字目も削除されるから、削除する文字列は中にかっこのペアのみを含む文字列でもよいことがわかる。

しかし、文字列Sによっては必ずしもペアが存在するとは限らない。例えば、S=)(() のとき、0文字目の"("はペアを作らず、1文字目と2文字目の"("と")"がペアになる。

どのようにかっこのペアを見つければよいだろうか。"("の右側にあって、最も近い")"がペアとは限らない。これはその間にほかの"("が含まれている可能性があるからで、先ほどの例 S=(()では、0文字目と2文字目がかっこのペアであることになってしまう。では、")"に注目してみるとどうだろう。")"の左側にあって、最も近く、かつ未だペアになっていない"("とはペアになりそうだ。 例えば S = (a))では、2文字目の")"は、左側にあって最も近い0文字目の"("とペアになる。3文字目の")"は、左側に未だペアになっていない"("が1つも存在しないのでペアを作らない。

そのため、次のような手順でかっこのペアを求められる。

• 左のまだペアになっていない(を入れる配列[リスト]left, ペアを記録するpair_listを用意する
• [iを0~Nまで1ずつ増やしていく]
  • もし、Sのi文字目が"("なら、leftにi["("のindex]を追加する。
  • もし、Sのi文字目が")"で、leftが空でないならば、配列の一番後ろの値[すなわち、")"の左にあって一番近いもの]とiがペアになる。→leftの一番後ろの値を取り出してpとし、leftからは削除する。pair_listに[p,i]を入れる。

このようにして、すべてのかっこのペアを求められる。 例えば入力例1だとこのようになる。

S = a(b(d))c
最初.left = [], pair_list = []
i=0: S[i] == "a" (アルファベットの時は何も起こらない)
i=1: S[i] == "(" → leftに1(i)を追加 left = [1]
i=2: S[i] == "b"
i=3: S[i] == "(" → leftに3(i)を追加 left = [1,3]
i=4: S[i] == "d"
i=5: S[i] == ")" → leftの末尾3と5(i)がペア pair_list = [[3,5]] leftから3を消去 left = [1]
i=6: S[i] == ")" → leftの末尾1と6(i)がペア pair_list = [[3,5],[1,6]] leftから1を消去 left = []
i=7: S[i] == "c"
結果: pair_list = [[3,5],[1,6]]

手順2 削除される文字とされない文字を判断する

手順1で、全てのかっこのペアを求め、削除されるかっこのペアを求められた。あとはpair_listの要素[l,r]それぞれについて範囲を合わせればよい。ただ、ここが少し難しい。

まず、実際に削除するわけにはいかないので、Sのi文字目は削除されているかを示す長さNのリスト「isdeleted」(初期値は全てfalse)を作って、先ほどのかっこのペアのリストの各要素について、[3,5]で3～5をTrueに、[1,6]なら1~6をTrueに…としていくのだが、これだと"("が10⁵個続き、")"が10⁵個続くSでは[0,199999],[1,199998],[2,199997]…と続いてしまうので計算回数が200000+199998+199996…+2 ≒ 10¹⁰となり厳しそうだ。(基本間に合うラインは10⁸くらい)

そこで、無駄なかっこのペアを見ないように工夫する。実は、かっこのペア同士は範囲が一部分だけ重なっているということはない。例えば、[0,2]、[1,3]となることはなく、これは0,2の間に"("のみ含まれていることになるが、かっこのペアの中に含められるかっこはペアのみであるから矛盾が生じる。

そのため、もし[1,3]をチェックしたときに既にisdeletedの1がTrueになっていたら、既に1~3全体はより広い範囲のかっこのペアによってチェックされているので確認の必要がないということだ。だから、pair_listを[")"のindex-(のindex]が広い順にソートして、もし(の位置が確認されていなければ全体をチェック、確認されていれば次のペア、という感じで、少ない計算回数で確認が可能になる。

ちなみに、ソートに関してはlambda式を用いている。関数を作るより短くかけて楽。 Python,C++ともにr-lの大きさで判断している。Pythonでは-をかけて昇順に、C++では不等号の向きで降順(大きい順)にソートしている。

コード(Python, C++)

Python

N = int(input())
S = list(input())
left = []
pair_list = []

for i in range(N):
    if S[i] == "(":
        left.append(i) # leftにiを追加
    elif S[i]==")":
        if not left: continue # leftが空ならば何もしない
        pair_list.append((left.pop(), i)) #leftから末尾の要素をpopし、pair_listに追加

pair_list.sort(key=lambda x: -(x[1]-x[0])) #r-lの差が大きい順にソート
is_deleted = [False] * N #is_deletedを用意

for l, r in pair_list:
    if is_deleted[l]:continue # 削除済みなら処理しない
    for i in range(l, r+1):
        is_deleted[i] = True # l以上r以下について、is_deleted[i]をTrueに更新

for i in range(N):
    if not is_deleted[i]:
        print(S[i], end = " ") # もしS[i]が削除されていなければ出力
print() # 改行

C++

#include <bits/stdc++.h>
using namespace std;

int main(){
    int N;
    string S;
    cin >> N;
    cin >> S;
    vector<int> left;
    vector<pair<int, int>> pair_list;

    for (int i=0;i<N;i++){
        if (S[i]=='(') left.push_back(i); // leftにiを追加
        else if (S[i] == ')'){
            if (left.empty()) continue; // 空なら何もしない
            else{
                int p = left.back();
                left.pop_back(); // leftの末尾を取得し削除
                pair_list.push_back({p, i}); // {p,i}をpair_listに追加
            }
        }
    }

    // lambda式を用いたソート
    sort(pair_list.begin(), pair_list.end(), [](pair<int,int> &a, pair<int,int> &b){
        return (a.first-a.second) < (b.first-b.second);
    });

    vector<bool> is_deleted(N, false);

    for (pair<int,int> &p: pair_list){ // 範囲for
        int l,r;
        tie(l, r) = p;
        if (is_deleted[l]) continue; // チェック済みなら何もしない
        for (int j=l; j<r+1; j++){
            is_deleted[j] = true; // l以上r以下について、is_deleted[i]をtrueに
        }
    }

    for (int i=0; i<N; i++){
        if (!is_deleted[i]){
            cout << S[i]; // もし削除されていないのならS[i]を出力
        }
    }

    cout << endl; // 改行
}