AtCoder Beginner Contest 217

39568 ワード
Python 競技プログラミング AtCoder tech テキストリンク

A - Lexicographic Order

import sys
import heapq, math, itertools
from collections import defaultdict, deque
from bisect import bisect_left, bisect_right
inputs = sys.stdin.readline
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
inputs = sys.stdin.readline
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
inputs = sys.stdin.readline
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
inputs = sys.stdin.readline
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
inputs = sys.stdin.readline
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型を用いることで、愚直な二分探索でも間に合うそうです。参考記事
本番中に色々なデータ型を試すのはリスクが高いので、BinaryTrieの解法で答えられるようにした方がよさそうです。

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
inputs = sys.stdin.readline
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になるのは明白なので、効率的にデータを持つ必要がありそうです。
結論としてはソート済みの配列aと、ソートしていない配列bを保持します。
これによって操作1では最後尾に要素xを追加するので、絶対にaがbより前方に位置することとなります。
ソート済みの配列aから出力するのは先頭の要素、すなわち最小の要素なので、heapqを使えばよさそうです。
一方操作2に関してaが空の時にはbの先頭を出力するのですが、この操作をO(1)で行うためにdequeを使いましょう。(dequeを使わず、この操作をx = b[0], b = b[1:]などとするとTLEします)

[Rust] nannou のベクトルライブラリ glam の作り込みがやばかった
Vite + React + TypeScriptで構築したアプリにCognitoの認証機能を追加する（React 18対応も）