AtCoder-ABC219 C - Neo-lexicographic Ordering【Python解答例】

サイシードプログラミングコンテスト2021(AtCoder Beginner Contest219)のC問題についてPythonの解答例を記事にしていきます。
Sciseed Programming Contest 2021（AtCoder Beginner Contest 219） - AtCoder

AtCoder Beginner Contest219 C - Neo-lexicographic Ordering

C - Neo-lexicographic Ordering

問題文

AtCoder 王国を治める高橋君は、英小文字のアルファベット順を変更することにしました。

新たなアルファベット順はa , b ,…, z を並べ替えて得られる文字列 X を用いて表されます。X の i(1≤i≤26) 文字目は、新たな順番において i 番目に小さい英小文字を表します。

AtCoder 王国には N 人の国民がおり、それぞれの国民の名前は S 1​ ,S 2​ ,…,S N​ です。ここで、S i​ (1≤i≤N) は英小文字からなります。
これらの名前を、高橋君の定めたアルファベット順に基づく辞書順に従って並べ替えてください。

制約

・X は a , b ,…, z を並べ替えて得られる
・2 ≤ N ≤ 50000
・N は整数
・1≤∣S i​ ∣≤10 (1 ≤ i ≤ N)
・S i​ は英小文字からなる (1 ≤ i ≤ N)
・S i​ ≠ S j​ (1 ≤ i < j ≤ N)

解答例

x = input()

n = int(input())

S = []
for _ in range(n):
    S.append(input())

res = []
for i in range(n):
    tmp = ""
    for j in range(10):
        if j < len(S[i]):
            for k in range(26):
                if x[k] == S[i][j] and k <= 8:
                    tmp += "0"
                    tmp += str(k+1)
                    break
                elif x[k] == S[i][j] and k > 8:
                    tmp += str(k+1)
                    break
        else:
            tmp += "00"
    res.append([tmp,i])

res.sort()

for i in range(n):
    print(S[res[i][1]])

解説

アルファベット順をXに変更したときに、N人の名前を変更したアルファベット順に並び替える問題です。

新しいアルファベット順に並び替えるために、i番目の名前Siをアルファベット順に基づいた数字に変換しました。

名前のj文字目が、Xのk(1～9)番目の文字の場合は2桁分の0kをtmpに、それ以外ならそのままkを付け加えます。

名前の長さがばらばらでも10文字分まで処理して 配列resにtmpとインデックスを格納しました。

つぎにresをソートすることで辞書順に並び替えます。

並び替えたresのインデックスをもとにSを出力していくことでACできました。

ABC219の関連記事はこちら
ebisuke33.hatenablog.com

AtCoder-ABC219 A - AtCoder Quiz 2 / B - Maritozzo【Python解答例】

サイシードプログラミングコンテスト2021(AtCoder Beginner Contest219)のA とB問題についてPythonの解答例を記事にしていきます。
Sciseed Programming Contest 2021（AtCoder Beginner Contest 219） - AtCoder

AtCoder Beginner Contest219 A - AtCoder Quiz 2

A - AtCoder Quiz 2

問題文

AtCoder 王国では、競技プログラミングの実力を測る検定試験が実施されています。

試験は 100 点満点であり、点数が高ければ高いほど、高いランクが認定されます。
ランクは以下のように定められています。

0 点以上 40 点未満のとき、初級
40 点以上 70 点未満のとき、中級
70 点以上 90 点未満のとき、上級
90 点以上のとき、エキスパート
高橋君は、この検定試験を受験し、X 点を取りました。

高橋君が認定されたランクより一つ高いランクとなるためには最低であと何点必要か求めてください。ただし、高橋君がエキスパートと認定された場合、それより高いランクは存在しないため expert と出力してください。

制約

・0≤X≤100
・X は整数

解答例

x = int(input())

if x >= 90:
    print("expert")
elif x >= 70:
    print(90-x)
elif x >= 40:
    print(70-x)
else:
    print(40-x)

解説

高橋君が次のランクにあがるために必要な点数を答える問題です。

高橋君の点数をxで受け取ります。

もし90点以上なら問題文通りexpertを出力します。
70 ～ 89点なら90 - xがエキスパートにあがるために必要な点数です。
40 ～69点なら70 - x が上級にあがるのに必要な点数、40点未満のとき40 - xが中級にあがるのに必要な点数になります。

必要な点数を出力すればOKでした。

AtCoder Beginner Contest219 B - Maritozzo

B - Maritozzo

問題文

英小文字からなる 3 つの文字列 S 1​ ,S 2​ ,S 3​ と、1、2、3 のみからなる文字列 T が与えられます。

T の各文字に対応する文字列を連結してできる文字列を出力してください。より厳密には、以下の指示にしたがって文字列を出力してください。

・1≤i≤∣T∣ を満たす整数 i に対し、文字列 s i​ を次のように定める。
・T の i 文字目が 1 のとき、S 1
・T の i 文字目が 2 のとき、S 2
・T の i 文字目が 3 のとき、S 3​
・s 1​ ,s 2​ ,…,s ∣T∣​ をこの順に連結してできる文字列を出力する。

制約

・1≤∣S 1​ ∣,∣S 2​ ∣,∣S 3​ ∣≤10
・1≤∣T∣≤1000
・S 1​ ,S 2​ ,S 3​ は英小文字からなる。
・T は 1、2、3 のみからなる。

解答例

s1 = input()
s2 = input()
s3 = input()
t = input()

ans = ""

for i in range(len(t)):
    if t[i] == "1":
        ans += s1
    elif t[i] == "2":
        ans += s2
    else:
        ans += s3

print(ans)

解説

Tの各文字に対応する文字列を連結した文字列を出力する問題です。

Tの文字列の長さ分だけループさせていきます。
Tのi文字目が1のときはansにS1を、2のときはS2、3のときはS3を足し合わせていきます。

すべて足し合わせたあとにansを出力すればACでした。

AtCoder-ABC218 C - Shapes【Python解答例】

AtCoder Beginner Contest218のC問題についてPythonの解答例を記事にしていきます。
AtCoder Beginner Contest 218 - AtCoder

AtCoder Beginner Contest218 C - Shapes

C - Shapes

問題文

2 次元グリッド上に 2 つの図形 S と T があります。グリッドは正方形のマスからなります。

S は N 行 N 列のグリッド内にあり、S i,j​ が # であるようなマス全体からなります。
T も N 行 N 列のグリッド内にあり、T i,j​ が # であるようなマス全体からなります。

S と T を 90 度回転及び平行移動の繰り返しによって一致させることができるか判定してください。

制約

・1≤N≤200
・S,T は # と . のみからなる
・S,T は 1 つ以上 # を含む

解答例

def rot(x):
    return list(zip(*x[::-1]))


def shift(x):
    for i in range(n):
        for j in range(n):
            if x[i][j] == "#":
                return i,j


def judge(x,y):
    xi, xj = shift(x)
    yi, yj = shift(y)
    offset_i = yi - xi
    offset_j = yj - xj
    for i in range(n):
        for j in range(n):
            ii = i + offset_i
            jj = j + offset_j
            if 0<=ii<n and 0<=jj<n:
                if x[i][j] != y[ii][jj]:
                    return False
            else:
                if x[i][j] == "#":
                    return False
    return True


n = int(input())

S = []
for _ in range(n):
    S.append(input())

T = []
for _ in range(n):
    T.append(input())

cntS = 0
for i in range(n):
    for j in range(n):
        if S[i][j] == "#":
            cntS += 1

cntT = 0
for i in range(n):
    for j in range(n):
        if T[i][j] =="#":
            cntT += 1

flag = False

if cntS == cntT:
    for _ in range(4):
        if judge(S,T):
            flag = True
        S = rot(S)

if flag:
    print("Yes")
else:
    print("No")

解説

公式解説をみてACでした。

SとTの#の個数が同じ場合においてＳを90°ずつ回転させ4通りを全探索します。
Sを回転させたあとSとTの最も左上の#の位置があうようにオフセット量を求め、平行移動させたあとでＳとＴが一致するかjudgeしました。

一致すればYesを、そうでなければNoを出力すればＯＫでした。

ABC218の関連記事はこちら
ebisuke33.hatenablog.com
ebisuke33.hatenablog.com

AtCoder-ABC218 D - Rectangles【Python解答例】

AtCoder Beginner Contest218のD問題についてPythonの解答例を記事にしていきます。
AtCoder Beginner Contest 218 - AtCoder

AtCoder Beginner Contest218 D - Rectangles

D - Rectangles

問題文

2 次元平面上に N 個の相異なる点があり、1,2,…,N の番号がついています。点 i(1≤i≤N) の座標は (x i​ ,y i​ ) です。

これらの点のうち 4 つを頂点とし、全ての辺が x 軸または y 軸に平行であるような長方形はいくつありますか？

制約

・4≤N≤2000
・0≤x i​ ,y i​ ≤10 ^9
・(x i​ ,y i​ ) ≠ (x j​ ,y j​ ) ( i ≠ j )
・入力は全て整数である。

解答例

import bisect

n = int(input())

XY = []
X = []
for _ in range(n):
    x, y = map(int, input().split())
    XY.append((x, y))
    X.append(x)

XY.sort()
X.sort()

ans = 0
for i in range(n-1):
    for j in range(i+1,n):
        if XY[i][0] >= XY[j][0] or XY[i][1] >= XY[j][1]:
            continue
        tmp1 = bisect.bisect_left(X,XY[i][0])
        tmp2 = bisect.bisect_left(X,XY[j][0])
        flag = 0
        while XY[tmp1][0] == XY[i][0]:
            if XY[tmp1][1] == XY[j][1] and i < tmp1 < j:
                flag += 1
                break
            tmp1 += 1
            if tmp1 > n-1:
                break
        while XY[tmp2][0] == XY[j][0]  and i < tmp2 < j:
            if XY[tmp2][1] == XY[i][1]:
                flag += 1
                break
            tmp2 += 1
            if tmp2 > n-1:
                break
        if flag == 2:
            ans += 1

print(ans)

解説

N個の点があり、このうち4個の頂点を選んだ時にX軸やY軸に平行な長方形がいくつあるか答える問題です。

配列XYにはX座標とY座標を、配列XにはX座標のみ格納していき、ソートします。

左下の頂点をi、右上の頂点をjとして全探索しました。

長方形のときだけ調べるために頂点iが頂点jより左かつ下でなければスキップします。

頂点i , j のX座標を二分探索でしらべtmp1,2としました。

頂点iと同じX座標で、頂点jと同じY座標の頂点があればflagに1を足します。

同様に頂点jと同じX座標で、頂点iと同じY座標の頂点があればさらにflagに1を足しました。

最終的にflagが2になれば、求める長方形なのでans変数に1を足してカウントします。

すべての頂点の探索を終えた後にansを出力すればＯＫです。

ABC218の関連記事はこちら
ebisuke33.hatenablog.com
ebisuke33.hatenablog.com

AtCoder-ABC218 A - Weather Forecast / B - qwerty【Python解答例】

AtCoder Beginner Contest218のA とB問題についてPythonの解答例を記事にしていきます。
AtCoder Beginner Contest 218 - AtCoder

AtCoder Beginner Contest218 A - Weather Forecast

A - Weather Forecast

問題文

明日からの 7 日間の天気予報を表す文字列 S が与えられます。
i 日後の予報は S の i 文字目が o であるとき晴れ、x であるとき雨です。

N 日後の天気予報が晴れかどうかを教えてください。

制約

・N は 1 以上 7 以下の整数
・S は長さ 7 の文字列であり、o と x のみからなる

解答例

n = int(input())

s = input()

if s[n-1] == "o":
    print("Yes")
else:
    print("No")

解説

文字列SのN文字目がoかxかを答える問題です。

Ｎは整数なのでint型で、Sは文字列なのでstr型で入力を受け取ります。

SのN文字目はS[N-1]なのでS[N-1]がoならYesを出力し、oでないならNoを出力すればOKです。

AtCoder Beginner Contest218 B - qwerty

B - qwerty

問題文

1 以上 26 以下の整数からなる長さ 26 の数列 P=(P 1​ ,P 2​ ,…,P 26​ ) が与えられます。ここで、P の要素は相異なることが保証されます。

以下の条件を満たす長さ 26 の文字列 S を出力してください。

・任意の i(1≤i≤26) について、S の i 文字目は辞書順で小さい方から P i​ 番目の英小文字である。

制約

・1 ≤ P i​ ≤ 26
・P i​ ≠ P j​ (i ≠ j)
・入力は全て整数である。

解答例

P = list(map(int, input().split()))

ans = ""

for i in range(26):
    tmp = chr(P[i] + 96)
    ans += tmp

print(ans)

解説

Pythonの場合、chr(値)で数値を文字列に変換できます。

asciiコードの97がaに該当するので、chr(P[i] + 96)においてP[i] = 1なら a 、P[i]= 26ならzに変換できます。

これで26個の整数を英子文字に置き換えて、ansに足しあわせていきました。

最後にansを出力すればACでした。

ABC218の関連記事はこちら
ebisuke33.hatenablog.com
ebisuke33.hatenablog.com

dequeの使い方【Python】

Pythonの標準ライブラリcollectionsのdeque型による両端キューの使い方を記事にしていきます。

深さ優先探索や幅優先探索など様々な場面で活用できるので、しっかり覚えたいですね。

dequeの特徴

リストとdeque比較した場合、操作する要素の位置によって速度に大きな違いが出てきます。

リストの場合

先頭の要素を取り出すpop(0)や、先頭に要素を追加するinsert(0,x)でO(n)のコストが必要になります。

dequeの場合

先頭と末尾の要素の追加や削除を行うappend()、appendleft()、pop()、popleftがO(1)のコストで実行できます。

一方で中央部分ではO(n)と遅くなります。

したがって普段はリストを使用すればよいですが、幅優先探索などアクセスが両端のみの場合にdequeを使用することで高速に処理することができます。

dequeの使い方

dequeオブジェクトの作成

from collections import deque

que = deque()

print(type(que))

# <class 'collections.deque'>

deque()でdequeオブジェクトが作成できます。

両端への要素の追加

from collections import deque

que = deque()

que.append(1)
que.append(2)
que.append(3)

que.appendleft(4)
que.appendleft(5)
que.appendleft(6)


print(que)

# deque([6, 5, 4, 1, 2, 3])

append()で末尾へ、appendleft()で先頭へ要素を追加できます。

両端の要素の削除

from collections import deque

que = deque([1, 2, 3, 4, 5])

print(que.pop())

# 5

print(que)

# deque([1, 2, 3, 4])

print(que.popleft())

# 1

print(que)

# deque([2, 3, 4])

pop()で末尾の要素を取り出し、popleft()で先頭の要素を取り出すことができます。

そのほかの要素追加方法[extend / extendleft]

from collections import deque

que = deque([1, 2, 3, 4, 5])

que.extend([6, 7])

print(que)

# deque([1, 2, 3, 4, 5, 6, 7])

que.extendleft([8, 9])

print(que)

# deque([9, 8, 1, 2, 3, 4, 5, 6, 7])

複数の要素を追加するときはextend/leftを使用します。

extend()で末尾に、extendleft()で先頭に要素を追加します。

extendleftでは追加される順番に注意が必要です。

その他 要素削除方法[remove / clear]

from collections import deque

que = deque([1, 2, 3, 4, 5, 3])

que.remove(3)

print(que)

# deque([1, 2, 4, 5, 3])

que.clear()

print(que)

# deque([])

remove()では引数とおなじ要素を削除します。

該当する値が複数ある場合は初めの要素だけ削除されます。

clear()はすべての要素を削除し空のキューになります。

要素のローテーション

from collections import deque

que = deque([1, 2, 3, 4, 5])

que.rotate()

print(que)

# deque([5, 1, 2, 3, 4])

que.rotate(-1)

print(que)

# deque([1, 2, 3, 4, 5])

que.rotate(3)

print(que)

# deque([3, 4, 5, 1, 2])

rotate()で右に1個ずつ要素が動きます。

引数をマイナスの値にすると左側に、引数を整数とすると その値分だけローテーションします。

dequeの特徴をしっかり理解し、適切なデータ構造を活用していきたいですね！

AtCoder-ABC217 E - Sorting Queries【Python解答例】

AtCoder Beginner Contest217のE問題についてPythonの解答例を記事にしていきます。
AtCoder Beginner Contest 217 - AtCoder

AtCoder Beginner Contest217 E - Sorting Queries

E - Sorting Queries

問題文

空の列 A があります。クエリが Q 個与えられるので、与えられた順番に処理してください。
クエリは次の 3 種類のいずれかです。

・1 x : A の最後尾に x を追加する。
・2 : A の最初の要素を出力する。その後、その要素を削除する。このクエリが与えられるとき、A は空でないことが保証される。
・3 : A を昇順にソートする。

制約

・1≤Q≤2×10 ^5
・0≤x≤10 ^9
・クエリ 2 が与えられるとき、A は空でない。
・入力は全て整数である。

解答例

from collections import deque
import heapq

Q = int(input())

que = deque()
hq = []

for i in range(Q):
    query = input()
    if query[0] == "1":
        q, x = query.split(" ")
        que.append(int(x))
    elif query[0] == "2":
        if len(hq) > 0:
            print(heapq.heappop(hq))
        else:
            print(que.popleft())
    else:
        while que:
            heapq.heappush(hq, que.pop())

解説

公式解説を読んで解くことができました。

queと優先度付きキューを使って取り組みました。

クエリごとの方針は次の通りです。
・クエリ1：que.append(int(x))でqueの最後尾にxを追加する。
・クエリ2：優先度付きキューが空なら、que.popleft()でqueの最初の要素を出力する。
空でなければheapq.heappop(hq)で優先度付きキューから最小値を取り出し出力する。
・クエリ3：queが空になるまで、heapq.heappush(hq, que.pop())で優先度付きキューにqueの要素を追加する。

この操作を該当するクエリごとに実行することでACできました。

優先度付きキューでソートの計算量を削減することがポイントでした。

ABC217の関連記事はこちら
ebisuke33.hatenablog.com
ebisuke33.hatenablog.com
ebisuke33.hatenablog.com

AtCoder-ABC217 D - Cutting Woods【Python解答例】

AtCoder Beginner Contest217のD問題についてPythonの解答例を記事にしていきます。
AtCoder Beginner Contest 217 - AtCoder

AtCoder Beginner Contest217 D - Cutting Woods

D - Cutting Woods

問題文

長さ L メートルの直線状の木材があります。
x=1,2,…,L−1 に対して、木材の左端から x メートルの地点には目印として線 x が引かれています。

Q 個のクエリが与えられます。 i 番目のクエリは数の組 (c i​ ,x i​ ) によって表されます。
以下の説明に従ってクエリを i の昇順に処理してください。

・c i​ =1 のとき : 線 x i​ がある地点で木材を 2 つに切る。
・c i​ =2 のとき : 線 x i​ を含む木材を選び、その長さを出力する。
ただし c i​ =1,2 の両方に対して、線 x i​ はクエリを処理する時点で切られていないことが保証されます。

制約

・1≤L≤10 ^9
・1≤Q≤2×10 ^5
・c i​ =1,2 (1≤i≤Q)
・1≤x i​ ≤L−1 (1≤i≤Q)
・全ての i (1≤i≤Q) に対して次が成り立つ: 1≤j

解答例

import bisect
import array

l, Q = map(int,input().split())

L = array.array("i",[0,l])
for i in range(Q):
    c, x = map(int,input().split())
    if c == 1:
        bisect.insort(L,x)
    else:
        point = bisect.bisect(L,x)
        res = L[point] - L[point-1]
        print(res)

解説

こちらの記事を読むことでACできました。
ありがとうございました。
【AtCoder】ABC217をPython3で解説（ABCD） - Qiita

ci =1 のときの配列への要素の追加や、ci = 2 のときの出力で二分探索ライブラリbisectを使い高速化しました。
ebisuke33.hatenablog.com

詳しい説明ができませんが、今回の配列Ｌはリスト型を使うとTLEしてしまいます。
arrayをインポートしてarray型を使用すると時間内で問題を解くことができました。
理由はわかりませんが、かなり差がつくポイントでした。

このような方針でもACすることができました。

ABC217の関連記事はこちら
ebisuke33.hatenablog.com
ebisuke33.hatenablog.com
ebisuke33.hatenablog.com