本記事は、AtCoder Beginner Contest 458 (SMBCプログラミングコンテスト #1) に参加した際の、A〜D問題の復習と解答の備忘録です。コンテスト中に考えた解法の方針や、提出したPythonのコードについて整理しています。

A - Chompers /

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 :
100 点

問題文

英小文字からなる文字列 $S$ と正の整数 $N$ が与えられます。 $S$ の長さは $2N+1$ 以上です。

$S$ の先頭と末尾から $N$ 文字ずつ取り除いて得られる文字列を求めてください。

制約

• $S$ は英小文字からなる文字列
• $N$ は整数
• $2N+1 \le |S| \le 30$
• $1 \le N \le 10$

自分の解答の方針

リストのスライスを利用する

提出したコード

S = list(input())
N = int(input())
print("".join(S[N:len(S)-N]))

B - Count Adjacent Cells /

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 :
200 点

問題文

$H$ 行 $W$ 列のグリッドがあります。上から $i$ 行目、左から $j$ 列目のマスをマス $(i,j)$ と表します。

マス $(x_1, y_1)$ とマス $(x_2, y_2)$ が辺で隣接するとは、 $|x_1 - x_2| + |y_1 - y_2| = 1$ が成り立つことをいいます。

すべてのマスについて、そのマスに辺で隣接するマスの個数を求めてください。

制約

• $1 \le H, W \le 50$
• 入力される値はすべて整数

自分の解答の方針

二重ループですべてのマスに対して、四方向を調べてカウント

提出したコード

H,W = map(int,input().split())
S = [[0 for _ in range(W)] for _ in range(H)]
for i in range(H):
    for j in range(W):
        count = 0
        for (x,y) in [(1,0),(0,1),(-1,0),(0,-1)]:
            if 0<=i+x<=H-1 and 0 <= j+y <= W-1:
                count += 1
        S[i][j] = count
for i in range(H):
    print(" ".join(map(str,S[i])))

C - C Stands for Center /

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 :
300 点

問題文

英大文字からなる文字列 $S$ が与えられます。以下の条件を全て満たす $S$ の部分文字列 (連続する部分列) がいくつあるか求めてください。

• 奇数個の文字からなる。
• 中央の文字が C である。厳密には、抜き出した部分文字列が $l$ 文字からなるとき、その $(l+1)/2$ 文字目が C である。

ただし、部分文字列が文字列として一致していても、抜き出した文字の位置が異なる場合、それぞれ別に数えます。

制約

• $S$ は英大文字からなる長さ 1 以上 $5 \times 10^5$ 以下の文字列

自分の解答の方針

前から順番に一文字づつ見ていき、Cを発見したらその位置から先頭と末尾の近いほうまでの長さを調べ、その分をカウントに足す

提出したコード

S = list(input())
count = 0
for i in range(len(S)):
    if S[i] == "C":
        count += min(i+1,len(S)-i)
print(count)

D - Chalkboard Median /

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 :
400 点

問題文

黒板に整数 $X$ が 1 つ書かれています。

$Q$ 個のクエリが与えられるので、順に処理してください。 $i$ 個目 $(1 \le i \le Q)$ のクエリは以下の通りです。

• 2 つの整数 $A_i, B_i$ が与えられる。黒板に新たに 2 つの整数 $A_i, B_i$ を書く。
• その後、黒板に書かれた $2i+1$ 個の整数の中央値を出力する。

制約

• $1 \le X \le 10^9$
• $1 \le Q \le 2 \times 10^5$
• $1 \le A_i, B_i \le 10^9$
• 入力される値は全て整数

自分の解答の方針

中央値を境に大小二つのリストを優先度付きキューとして持ち、毎回小さいほうのリストの最大値と大きいほうのリストの最小値を取り出す
それぞれの大小関係を調べて、それが変わらないように大小二つのリストに追加する。
Aを追加するときは小さいリストが一つ多くなるようにする。

提出したコード

import heapq

X = int(input())
Q = int(input())
left = []
right = []
heapq.heappush(left,float('inf'))
heapq.heappush(right, float('inf'))
heapq.heappush(left, -X)
# center = X
for _ in range(Q):
    A,B = map(int,input().split())
    left_max = -heapq.heappop(left)
    right_min = heapq.heappop(right)
    if A < left_max:
        heapq.heappush(right, right_min)
        heapq.heappush(right, left_max)
        heapq.heappush(left, -A)
    else:
        heapq.heappush(right, right_min)
        heapq.heappush(right, A)
        heapq.heappush(left, -left_max)
    left_max = -heapq.heappop(left)
    right_min = heapq.heappop(right)
    if B > right_min:
        heapq.heappush(left, -left_max)
        heapq.heappush(left, -right_min)
        heapq.heappush(right, B)
    else:
        heapq.heappush(left, -left_max)
        heapq.heappush(left, -B)
        heapq.heappush(right, right_min)

    left_max = -heapq.heappop(left)
    right_min = heapq.heappop(right)
    if len(left) > len(right):
        print(left_max)
    else:
        print((left_max + right_min) // 2)
    heapq.heappush(left,-left_max)
    heapq.heappush(right, right_min)