👌

2022/03/31に公開

# A - Lexicographic Order

import sys
import heapq, math, itertools
from collections import defaultdict, deque
from bisect import bisect_left, bisect_right
mod = 10**9+7
inf = float('inf')
#sys.setrecursionlimit(10**7)

def main():
s,t = input().split()
print('Yes' if s<t else 'No')

if __name__ == '__main__':
main()


pythonは文字列でも比較演算子による辞書順比較が可能です

# B - AtCoder Quiz

import sys
import heapq, math, itertools
from collections import defaultdict, deque
from bisect import bisect_left, bisect_right
mod = 10**9+7
inf = float('inf')
#sys.setrecursionlimit(10**7)

def main():
s = [input() for _ in range(3)]
t = ['A{}C'.format(c) for c in ['B', 'R', 'G', 'H']]
print(list(set(t).difference(set(s)))[0])

if __name__ == '__main__':
main()


ABC,ARC,AGC,AHCの中で入力されていないものが答えです。
4個程度ならリストによる管理でも問題ないですが、数が多いときには集合型を使う方が高速です

# C - Inverse of Permutation

import sys
import heapq, math, itertools
from collections import defaultdict, deque
from bisect import bisect_left, bisect_right
mod = 10**9+7
inf = float('inf')
#sys.setrecursionlimit(10**7)

def main():
n = int(input())
p = list(map(int, inputs().split()))
ans = [-1]*(n+1)
for i in range(n):
ans[p[i]] = i+1
print(*ans[1:])

if __name__ == '__main__':
main()


ans[p[i]] = i+1 としているのは、0-indexなので格納する数字を1つ増やすためです

# D - Cutting Woods

import sys
import heapq, math, itertools
from collections import defaultdict, deque
from bisect import bisect_left, bisect_right, insort_left, insort_right
mod = 10**9+7
inf = float('inf')
#sys.setrecursionlimit(10**7)

class BinaryTrie:
def __init__(self, max_query=2*10**5, bitlen=30):
n = max_query * bitlen
self.nodes = [-1] * (2 * n)
self.cnt = [0] * n
self.id = 0
self.bitlen = bitlen

# xの挿入
def insert(self,x):
pt = 0
for i in range(self.bitlen-1,-1,-1):
y = x>>i&1
if self.nodes[2*pt+y] == -1:
self.id += 1
self.nodes[2*pt+y] = self.id
self.cnt[pt] += 1
pt = self.nodes[2*pt+y]
self.cnt[pt] += 1

# 昇順x番目の値
def kth_elm(self,x):
pt, ans = 0, 0
for i in range(self.bitlen-1,-1,-1):
ans <<= 1
if self.nodes[2*pt] != -1 and self.cnt[self.nodes[2*pt]] > 0:
if self.cnt[self.nodes[2*pt]] >= x:
pt = self.nodes[2*pt]
else:
x -= self.cnt[self.nodes[2*pt]]
pt = self.nodes[2*pt+1]
ans += 1
else:
pt = self.nodes[2*pt+1]
ans += 1
return ans

# x以上の最小要素が昇順何番目か
def lower_bound(self,x):
pt, ans = 0, 1
for i in range(self.bitlen-1,-1,-1):
if pt == -1: break
if x>>i&1 and self.nodes[2*pt] != -1:
ans += self.cnt[self.nodes[2*pt]]
pt = self.nodes[2*pt+(x>>i&1)]
return ans

def main():
l,q = map(int, inputs().split())
bt = BinaryTrie()
bt.insert(0)
bt.insert(l)
ans = []
for _ in range(q):
c,x = map(int, inputs().split())
if c==1:
bt.insert(x)
else:
p = bt.lower_bound(x)
ans.append(bt.kth_elm(p)-bt.kth_elm(p-1))
print(*ans, sep='\n')

if __name__ == '__main__':
main()


BinaryTrieのデータ構造を用いることで解決できます。

## 追記

import sys
import heapq, math, itertools
from array import array
from collections import defaultdict, deque
from bisect import bisect_left, bisect_right, insort_left, insort_right
mod = 10**9+7
inf = float('inf')
#sys.setrecursionlimit(10**7)

def main():
l,q = map(int, inputs().split())
pos = array('i',[0, l])
ans = []
for _ in range(q):
c,x = map(int, inputs().split())
if c==1:
insort_left(pos, x)
else:
idx = bisect_left(pos, x)
if idx==0:
ans.append(pos[0])
elif idx==len(pos):
ans.append(l-pos[-1])
else:
ans.append(pos[idx]-pos[idx-1])
print(*ans, sep='\n')

if __name__ == '__main__':
main()


array型を用いることで、愚直な二分探索でも間に合うそうです。参考記事

# E - Sorting Queries

import sys
import heapq, math, itertools
from collections import defaultdict, deque
from bisect import bisect_left, bisect_right, insort_left, insort_right
mod = 10**9+7
inf = float('inf')
#sys.setrecursionlimit(10**7)

def main():
q = int(inputs())
a = []
heapq.heapify(a)
b = deque([])
ans = []
for _ in range(q):
l = input().split()
if l[0]=='1':
x = int(l[1])
b.append(x)
elif l[0]=='2':
if a:
x = heapq.heappop(a)
ans.append(x)
else:
x = b.popleft()
ans.append(x)
else:
while b:
x = b.popleft()
heapq.heappush(a, x)
b = deque([])
print(*ans, sep='\n')

if __name__ == '__main__':
main()


Aを毎回ソートしていてはTLEになるのは明白なので、効率的にデータを持つ必要がありそうです。

これによって操作1では最後尾に要素xを追加するので、絶対にaがbより前方に位置することとなります。
ソート済みの配列aから出力するのは先頭の要素、すなわち最小の要素なので、heapqを使えばよさそうです。

ログインするとコメントできます