AtCoder Beginner Contest 157の復習, E問まで(Python)

競プロ初心者の復習用記事です。

ここで書く解は解説や他の人の提出を見ながら書いたものです。自分が実際に提出したものとは限りません。

A - Duplex Printing

ページ数Nを両面印刷すると何枚の紙が必要か答える問題です。

2で割って切り上げればよし。

n = int(input())
print((n+1)//2)

B - Bingo

与えられた番号とビンゴカードで列が揃っているか答える問題です。

二次元配列を探索して要素を探すのがめんどくさかったので、numpyを用いてnp.whereで置き換える操作を利用しました。ついでに縦軸、横軸にそってnp.sum()を利用することでビンゴの有無も調べました。

pypy3ではnumpyを読み込めないので注意。

import numpy as np
S = np.array([list(map(int, input().split())) for _ in range(3)])
n = int(input())
for _ in range(n):
    S = np.where(S==int(input()), 0, S)
HBingo = min(np.sum(S, axis=0)) == 0
WBingo = min(np.sum(S, axis=1)) == 0
SBingo = S[2][0] == 0 and S[1][1] == 0 and S[0][2] == 0
BSBingo = S[0][0] == 0 and S[1][1] == 0 and S[2][2] == 0
if HBingo or WBingo or SBingo or BSBingo:
    print('Yes')
    exit()
print('No')

ただし、numpyを使わずに素直に配列を探索する方がずっと早いようです。

C - Guess The Number

受け取った桁数と数値の条件を満たす最小の数値を返す問題です。

まずそれぞれの桁を-1を初期状態として作成します。そこから入力を受け取るごとに「書き換える数値が-1である」もしくは「書き換える数値が矛盾が生じない」どちらかの条件を満たしたとき書き換えます。矛盾が発生したときは-1を出力して終了。

最後に書き換えが発生しなかった桁(-1)を最小値取るように変換させれば完成です。左から1桁目なら1(N=1の時0が許されるのに注意)、それ以降なら0に変換。

$N\geq2$の時1桁目を0に変えられないことに注意(一敗)。

N, M = map(int, input().split())
ans = [-1] * N
for _ in range(M):
    i, n = map(int, input().split())
    if (ans[i-1] == -1 or ans[i-1] == n) and not(N > 1 and i == 1 and n == 0):
        ans[i-1] = n
    else:
        print(-1)
        exit()
ans = [n if n != -1 else 0 for n in ans]
if ans[0] == 0 and N > 1:
    ans[0] = 1

print(*ans, sep='')

D - Friend Suggestions

SNSの状態を与えられて、「友達の友達」であり、「友達でも敵でもない」関係が何人いるかを答える問題です。

繋がり合いっているかを探索する方法がわからず、諦めました。

解説を見ました。友達候補の数は、「自身が含まれるクラスター内の人数」から「自身の友達の数」と「自身の数（１）」と「クラスター内のブロックしている人数」を引いた数が答えになります。

よって配列として「それぞれの要素が所属しているクラスター」を格納する配列clusterI、「それぞれのクラスターの持つ人数」を格納する配列clusterN、後で引く「友達とブロックしている人数」outの三つの配列を作成します。

clusterIにはそのクラスター内の最も低いインデックスを格納します。ここが問題。インデックスを書き換える処理をforで回して雑に変えたのが以下のコード。

n, m, k = map(int, input().split())
clusterN = [1] * n
clusterI = list(range(n))
out = [0] * n

def unite(x, y):
  CX = clusterI[x]
  CY = clusterI[y]
  if CX != CY:
    if CX < CY:
      CX, CY = CY, CX
    clusterN[CX] += clusterN[CY]
    for i in range(n):
      if clusterI[i] == CY:
        clusterI[i] = CX

for _ in range(m):
  a, b = map(int, input().split())
  unite(a-1, b-1)
  out[a-1] -= 1
  out[b-1] -= 1

for _ in range(k):
  a, b = map(int, input().split())
  if clusterI[a-1] == clusterI[b-1]:
    out[a-1] -= 1
    out[b-1] -= 1
out = [out[i] + clusterN[clusterI[i]] - 1 for i in range(n)]
print(*out)

TLEです。

他の人のコードを参考に、再帰関数による書き換えにしました。これで通りました。探索についての知識を持ってないのが大きな課題ですね。

n, m, k = map(int, input().split())
clusterN = [1] * n
clusterI = list(range(n))
out = [0] * n
def find(x):
  if clusterI[x] != x:
    minI = find(clusterI[x])
    clusterI[x] = minI
    return minI
  else:
    return x

def unite(x, y):
  CX = find(x)
  CY = find(y)
  if CX != CY:
    if CX > CY:
      CX, CY = CY, CX
      x, y = y, x
    clusterN[CX] += clusterN[CY]
    clusterI[CY] = CX
    
for _ in range(m):
  a, b = map(int, input().split())
  unite(a-1, b-1)
  out[a-1] -= 1
  out[b-1] -= 1

for _ in range(k):
  a, b = map(int, input().split())
  if find(a-1) == find(b-1):
    out[a-1] -= 1
    out[b-1] -= 1
out = [out[i] + clusterN[find(i)] - 1 for i in range(n)]
print(*out)

E - Simple String Queries

入力に従って文字列を変換する操作を繰り返し、文字の種類数を調べる問題です。

いつものように愚直にやったのが以下のコードです。

import collections

N = int(input())
S = list(input())
Q = int(input())
for _ in range(Q):
    Q1, Q2, Q3 = input().split()
    if Q1 == '1':
        S[int(Q2)-1] = ord(Q3)
    else:
        print(len(collections.Counter(S[int(Q2)-1: int(Q3)])))

TLE出ました。

解説を見てみました。

AからZまでについての情報をもつ要素数26個の配列を作成します。要素内には、その文字が登場する位置を格納。数を数えるときは、26個の文字について指定範囲内にその文字の登場位置が含まれているかを調べます。

というのをそのまま実装したのが以下です。

N = int(input())
S = list(str(input()))

def ordN(x):
  return ord(x) - ord('a')

li = [[] for _ in range(26)]
for i,s in enumerate(S):
  li[ordN(s)].append(i)

for i in range(int(input())):
  Q1, Q2, Q3 = input().split()
  if Q1 == "1":
    Q2 = int(Q2) - 1
    if S[Q2] != Q3:
      li[ordN(S[Q2])] = [n for n in li[ordN(S[Q2])] if n != Q2]
      li[ordN(Q3)].append(Q2)
      S[Q2] = Q3
  else:
    Q2, Q3 = int(Q2)-1, int(Q3)-1
    count = 0
    for j in range(26):
      if [True for n in li[j] if Q2 <= n and n <= Q3]:
        count += 1
    print(count)

このままだとTLEがやはり出ます。他の人のコードを参考に書き換えます。文字の登場位置をソートした状態で保持。さらに二分探索によって置き換えや位置のチェックを行います。二分探索にはライブラリbisectを使用します。

使う関数は以下の二つ。
bisect.bisect_left(list, x)

a = [1, 2, 4, 6, 10]
print(bisect.bisect_left(a, 4)) # 3

第一引数のリストに対して第二引数をソート順を崩さず入れられる位置を返します。
bisect.insort(list, x)

a = [1, 2, 4, 6, 10]
bisect.insort(a, 4)
print(a)# [1, 2, 4, 4, 6, 10]

第一引数のリストに対してソート順を崩さず挿入を行います。

これを利用して書き換えたのが以下のコード。

import bisect

N = int(input())
S = list(str(input()))

def ordN(x):
  return ord(x) - ord('a')

li = [[] for _ in range(26)]
for i,s in enumerate(S):
  li[ordN(s)].append(i)

for i in range(int(input())):
  Q1, Q2, Q3 = input().split()
  if Q1 == "1":
    Q2 = int(Q2) - 1
    if S[Q2] != Q3:
      I = bisect.bisect_left(li[ordN(S[Q2])], Q2)
      li[ordN(S[Q2])].pop(I)
      bisect.insort(li[ordN(Q3)], Q2)
      S[Q2] = Q3
  else:
    Q2, Q3 = int(Q2)-1, int(Q3)-1
    count = 0
    for j in range(26):
      I = bisect.bisect_left(li[j], Q2)
      if I < len(li[j]) and li[j][I] <= Q3:
        count += 1
    print(count)

これで通りました。

この記事はここまでとします。