【Atcoder】競プロ典型90問に挑戦

競プロ典型問題90問に挑戦していきます

002 – Encyclopedia of Parentheses（★3）
1. 方針
2. 解答
007 – CP Classes（★3）
004 – Cross Sum（★2）
014 – We Used to Sing a Song Together（★3）
016 – Minimum Coins（★3）
020 – Log Inequality（★3）
022 – Cubic Cake（★2）
024 – Select +／- One（★2）
027 – Sign Up Requests （★2）
033 – Not Too Bright（★2）
038 – Large LCM（★3）
044 – Shift and Swapping（★3）
055 – Select 5（★2）
061 – Deck（★2）
078 – Easy Graph Problem（★2）

002 – Encyclopedia of Parentheses（★3）

方針

Nの数が小さく、制約が小さいので全探索を考える
bit全探索で考える

解答

n = int(input())

ans = []
count=0
for bit in range(2**n):
    _=''
    count = 0
    for i in range(n):
        if (bit >> i) & 1:
            _ += "("
            count += 1
        else:
            _ += ")"
            count -= 1
        if count < 0:
            break
    if count == 0:
        ans.append(_)

ans.sort()

for i in range(len(ans)):
    print(ans[i])

n = int(input())

ans = []

count=0

for bit in range(2**n):

_=''

count = 0

for i in range(n):

if (bit >> i) & 1:

_ += "("

count += 1

else:

_ += ")"

count -= 1

if count < 0:

break

if count == 0:

ans.append(_)

ans.sort()

for i in range(len(ans)):

print(ans[i])

007 – CP Classes（★3）

方針

①探索で検索する

②二分探索には探索対象のリストはソートされている必要があるので、クラスのレーティングを昇順にソートする(ソート時の計算量は要確認)

③二分探索後のインデックスの値に応じて不満度を計算する

解答

import bisect

n = int(input())
#A=map(int,input().split())
A=input().split()
q=int(input())
Q=[]                        #[1]各生徒のレーティングをリストQに入れる
for i in range(q):
  Q.append(int(input()))

a=0
b=0

for i in range(len(A)):     #[2]各クラスのレーティングをソート
  A[i]=int(A[i])
A.sort()
for i in range(q):
  idx=bisect.bisect_left(A,Q[i]) #bisectライブラリで二分探索
  if idx==0:                     #[3]★1
    print(abs(A[0]-Q[i]))        
  elif idx==len(A):              #[3]★2
    print((abs(A[-1]-Q[i])))
  else:                          #[3]★3
    a=abs(A[idx-1]-Q[i])
    b=abs(A[idx]-Q[i])
    print(min(a,b))

import bisect

n = int(input())

#A=map(int,input().split())

A=input().split()

q=int(input())

Q=[] #[1]各生徒のレーティングをリストQに入れる

for i in range(q):

Q.append(int(input()))

a=0

b=0

for i in range(len(A)): #[2]各クラスのレーティングをソート

A[i]=int(A[i])

A.sort()

for i in range(q):

idx=bisect.bisect_left(A,Q[i]) #bisectライブラリで二分探索

if idx==0: #[3]★1

print(abs(A[0]-Q[i]))

elif idx==len(A): #[3]★2

print((abs(A[-1]-Q[i])))

else: #[3]★3

a=abs(A[idx-1]-Q[i])

b=abs(A[idx]-Q[i])

print(min(a,b))

[2]各クラスのレーティングをソート

リストAには文字列で各クラスのレーティングが入っています。

mapを使うとソートができなかったので、いったん文字列でリストAに入れて、各要素をintにしてからソートするという無駄なことをしています。

“list(map(・・・))”とすることで初めからintでリストを作れました。

[3]二分探索の結果に応じて計算

bisectは探索対象のリストの何番目に当たるかをインデックスで返してくれます。

例えば、[1,2,4,5]というリストがあり、x=3を何番目に入れたいかbisectで調べると、インデックスである2を返します。

もし、x=0ならインデックスは0となるので、リストAの0番目の要素と各生徒のレーティングを引き算して不満度を計算します。(★1)

もしx=10ならインデックスは4となるので、リストAの最後の要素と各生徒のレーティングを引き算して不満度を計算します。(★2)

それ以外は、返されたインデックスの前後の要素と、各生徒のレーティングを計算して小さい方を選択して不満度を計算します。(★3)

別解

方針と実装がかなり似ている方のコードがありました。

私と異なるのは、★の部分のコードがより短くてわかりやすいです。

実装はできるだけシンプルにするべきだと感じました。

また、リストを多く使うと要素の指定時にミスのもととなるので、単なる変数で指定できるのであればそちらを採用すべきだと思います。

from bisect import bisect_left
N  = int(input())
A = list(map(int,input().split()))#★
A.sort()
Q = int(input())

for _ in range(Q):
    b = int(input())#★
    idx = bisect_left(A, b)
    if idx == 0:
        print(A[0]-b)
    elif idx == N:
        print(b-A[-1])
    else:
        print(min(abs(A[idx]-b), abs(A[idx-1]-b))) #★

from bisect import bisect_left

N = int(input())

A = list(map(int,input().split()))#★

A.sort()

Q = int(input())

for _ in range(Q):

b = int(input())#★

idx = bisect_left(A, b)

if idx == 0:

print(A[0]-b)

elif idx == N:

print(b-A[-1])

else:

print(min(abs(A[idx]-b), abs(A[idx-1]-b))) #★

また、このほかにもヒープソートで実装している方もいました。

ソートのアルゴリズムを使う問題でしたが、アルゴリズムを知っていると解法が増えるので、実装上詰まった時に別の方法を用いるといった選択肢も出てくると思います。

アルゴリズムとデータ構造の勉強は今後も続けていきたいと思います。

参考

Pythonにはbisectというライブラリがあり、二分探索を素早く使えます。

Pythonで二分探索する公式ライブラリ – Qiita

こちらは以前二分探索を勉強したときの記録としてこのサイトでまとめた記事です。

【Python】二分探索を実装する【アルゴリズム】

004 – Cross Sum（★2）

方針

h行w列のマス目のそれぞれの要素について、行の合計と列の合計を計算していくと計算量が多くなりそうでした。

そこで、行ごとの合計と列ごとの合計をあらかじめ計算しておき、それぞれの要素ごとに合計を求めることで計算量を削減できそうです。

このとき要素、(I,J)は行と列の両方で合計として使われているので、差し引く必要があります。

たとえば、以下のような場合

1,2

3,4

行の合計は3と7、列の合計は4と6です。

1行1列目の値である1は行と列の両方で合計を計算するために使われているので、行合計＋列合計 – 1とする必要がありました。

提出の際、Python3だとＴＬＥになりました。そのためPyPy3で提出しています。

解答

h,w = map(int,input().split())
X = []
for i in range(h):
  X.append(list(map(int, input().split())))

#[1]各行の合計を求める
gyo = []
for i in range(h):
  gyo.append(sum(X[i]))

#[2]各列の合計を求める
retsu = []
for i in range(w):
  sum = 0
  for j in range(h):
    sum += X[j][i]
  retsu.append(sum)

#行ごとにリストを作る
Y = []

#解答用のリスト
ans = []

#[3]1行ごとにリストを作り、ansに追加する。
for i in range(h):
  Y = []
  for j in range(w):
    Y.append(gyo[i]+retsu[j]-X[i][j]) #★それぞれの要素の値を計算
  ans.append(Y)
        

for i in range(h):
  print(*ans[i])

h,w = map(int,input().split())

X = []

for i in range(h):

X.append(list(map(int, input().split())))

#[1]各行の合計を求める

gyo = []

for i in range(h):

gyo.append(sum(X[i]))

#[2]各列の合計を求める

retsu = []

for i in range(w):

sum = 0

for j in range(h):

sum += X[j][i]

retsu.append(sum)

#行ごとにリストを作る

Y = []

#解答用のリスト

ans = []

#[3]1行ごとにリストを作り、ansに追加する。

for i in range(h):

Y = []

for j in range(w):

Y.append(gyo[i]+retsu[j]-X[i][j]) #★それぞれの要素の値を計算

ans.append(Y)

for i in range(h):

print(*ans[i])

[1]行ごとの合計を求める

gyoリストを作り、行ごとの合計を求めています。

[2]行ごとの合計を求める

[1]と同様に、列ごとの合計を求めています。

numpyを使えば列ごとの計算ができるのでもう少し簡単かもしれません。

[3]1行ごとにリストを作り、ansに追加する

ansはこのようなリストにしました。

[[5,5,5],

[5,5,5],

[5,5,5]]

Yは各行の[5,5,5]にあたります。

当初は[5,5,5,5,5,5,5,5,5]とシンプルなリストにしていたのですが、それだと最後のprintでエラーになってしまったのでこのような形にしています。

★の部分は方針で記載した通りにそれぞれの要素の値を計算しています。

参考

【競プロ典型90問】004の解説（python） – Qiita

014 – We Used to Sing a Song Together（★3）

方針

①各小学生の家と各小学校の位置を昇順か降順にソートする

②順番に家と学校の差の合計を求める

解答

n=int(input())
A=list(map(int,input().split()))
B=list(map(int,input().split()))

A.sort()
B.sort()
ans=0
for i in range(n):
  ans+=abs(A[i]-B[i])

print(ans)

n=int(input())

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

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

A.sort()

B.sort()

ans=0

for i in range(n):

ans+=abs(A[i]-B[i])

print(ans)

参考：貪欲法について

今回は貪欲法について知ることが目的の問題だと思います。

簡単で部分的な問題に絞り、その正解を積み重ねていくものだと思っています。

今回の問題だと、1番目の小学生と一番近い小学校の家、2番目の小学生と一番近い小学校の家と一部分に注目し、その差を積み重ねて合計したものが答えということなのかなと。

ただ、いくつかのサイトで説明を読んでもこの理解であっているとは到底思えないです。改めて勉強しようと思います。

貪欲法 – Wikipedia

そのアルゴリズム、貪欲につき――貪欲法のススメ：最強最速アルゴリズマー養成講座（1/3 ページ） – ITmedia エンタープライズ

簡単な貪欲法を解いてみた – Qiita

また、リストを扱う時は計算量を気にしたほうが良いかと思っています。こちらの記事で解説頂いていますが、Python3のリストでsortを使って並べ替えすると、計算量はO(NlonN)となるようです。

Pythonistaなら知らないと恥ずかしい計算量のはなし – Qiita

016 – Minimum Coins（★3）

方針

NとA,B,Cの関係を式にする
式をA,Bの全探索で済む形に変形する

解答

n=int(input())
a,b,c=map(int,input().split())

ans=9999
for i in range(ans):     #[1]
  for j in range(ans-i): 
    k=(n-(a*i+b*j))//c
    if n==a*i+b*j+c*k and k>=0: 
      ans=min(ans,i+j+k) #[2]
print(ans)

n=int(input())

a,b,c=map(int,input().split())

ans=9999

for i in range(ans): #[1]

for j in range(ans-i):

k=(n-(a*i+b*j))//c

if n==a*i+b*j+c*k and k>=0:

ans=min(ans,i+j+k) #[2]

print(ans)

[1]式を変形してA,Bの全探索にする

今回の問題は”N円＝A円硬貨＊i枚＋B円硬貨＊k枚＋C円硬貨＊k枚”という式にすることができます。

→N=A*i+B*j+C*k

これをkを求める式に変形します。

k=N-(A*i+B*j)/C

N,A,B,Cは入力として与えられるので、i,jを全探索で求めることでkが求まります。

i,j,kの合計がN円を払いきることができる各硬貨の枚数になります。

ただし、i,j,kの組み合わせは一つではないので、すべての組み合わせの中でi+j+kの合計が最小のものを探す必要があります。

[1]の二十ループでは、ひとまずk=N-(A*i+B*j)/Cを満たす組み合わせを全探索しています。

見つかった組み合わせに対して、現状の最小値であるansと比較して、小さい方をansに代入します。

★ansに最小値を代入して探索回数を減らす

iとjの二十ループになっており、計算量は多いですが、range(ans)として各ループの最後でansに最小値を代入することで、どんどん探索回数を減らしていくことができます。

今回のように最小値を求める場合や、最大値を求めるときにも上限が決まっていれば応用できるのではないかと思いました。

参考

020 – Log Inequality（★3）

方針

整数での式に変形する

解答

import math
a,b,c=map(int,input().split())

if a<c**b:
  print('Yes')
else:
  print('No')

import math

a,b,c=map(int,input().split())

if a<c**b:

print('Yes')

else:

print('No')

参考

公式の解説が一番わかりやすかったです。理系選択ながら数学が一番苦手な教科でしたが、数式を見たら拒否反応がでないだけマシだと考えることにします。

浮動小数点型の計算は誤差が発生する可能性があるため、整数での計算に置き換えるのが良いという解説でした。

公式解説

Pythonに慣れてきたら、公式ドキュメントでより詳細な仕様に触れて言語の理解を進める必要があると思いました。

math — 数学関数 — Python 3.9.4 ドキュメント

022 – Cubic Cake（★2）

方針

幅A、奥行きB、高さCの直方体を何回切るとすべてが立方体になるかという問題です。

それぞれの長さがcm単位だとすると、ケーキを切るときは1cm単位で切って良いです。

最初、問題文に書かれていないのに必ず半分に切らなければならないと勘違いしていました。

幅A、奥行きB、高さCの直方体を切り、全てが立方体になるのはA,B,Cが同じ長さになる時です。

そのため、A,B,Cの最大公約数を求める問題と言いかえられます。

解答1

import math 
a,b,c = map(int, input().split())
d = math.gcd(c,math.gcd(a,b)) #[1]
ans = a//d+b//d+c//d-3 #[2]
print(ans)

import math

a,b,c = map(int, input().split())

d = math.gcd(c,math.gcd(a,b)) #[1]

ans = a//d+b//d+c//d-3 #[2]

print(ans)

[1]最大公約数を求める

最大公約数を求めるにはユークリッドの互除法がありますが、mathモジュールのgcd関数が簡単なのでそちらを用います。math.gcdは最大公約数を求める関数です。

参考記事によると、python3.9からは引数(カッコ内の数字)を3つにして最大公約数を求めることができますが、3.9よりも前の版では引数は2つまでです。

そのため、今回はaとbの最大公約数を求めてから、さらにcとの最大公約数を求めています。

解答の作成

最大公約数でA,B,Cを割った数を合計し、3を引いています。

なぜ3を引くのか、問題の入力例2を例にして考えます。

入力例2：2 2 4

高さCが4なので、高さCを半分に切ることで全て(2つ)のピースが立方体にになります。

今回の実装の流れで言えば、奥行きBと高さCの最大公約数は2であり、これと幅Aは長さ2なので最大公約数は2になります。

A,B,Cを最大公約数で割り算して1になった場合はケーキを切る必要がなかったことになります。入力例2で言えば幅Aと奥行きBです。

ケーキを切る必要がなかった部分は最大公約数で割り算すると1になります。

ケーキを切る必要があった部分は最大公約数で割り算すると2以上になります。

A,B,Cのそれぞれから1を引き、合計することでケーキを切る回数になります。

解答2：ユークリッドの互除法

def gcd(x,y):
  if y==0:
    return x
  else:
    return gcd(y,x%y)

  
a,b,c = map(int,input().split())

d = gcd(gcd(a,b),c)
print(a//d+b//d+c//d-3)

def gcd(x,y):

if y==0:

return x

else:

return gcd(y,x%y)

a,b,c = map(int,input().split())

d = gcd(gcd(a,b),c)

print(a//d+b//d+c//d-3)

最大公約数を求めるユークリッドの互除法を使ってみました。

xとyの2つを引数として受け取ります。

yが0ならxを返し、それ以外はyとx%yを新たな引数として再帰的に処理します。

参考

Pythonで最大公約数と最小公倍数を算出・取得 | note.nkmk.me

024 – Select +／- One（★2）

方針

①数列Aと数列Bの各要素の差の絶対値の合計を求める

②指定された操作回数であるKと①で求めた値の差を求める

③条件分岐を使って解答を作成する

解答

"""
K-(Ai-Biの合計)が偶数ならYes
それ以外はNo
"""

n,k = map(int,input().split())
A=list(map(int, input().split()))   
B=list(map(int, input().split()))

sum = 0
for i in range(n):
  sum += abs(A[i]-B[i]) #[1]　①

if k<sum:               #[2] パターン1
  print('No')
elif abs(k-sum)%2==0:   #[2] パターン2
  print('Yes')
else:
  print('No')　　　　　　#[2] パターン3

"""

K-(Ai-Biの合計)が偶数ならYes

それ以外はNo

"""

n,k = map(int,input().split())

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

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

sum = 0

for i in range(n):

sum += abs(A[i]-B[i]) #[1]　①

if k<sum: #[2] パターン1

print('No')

elif abs(k-sum)%2==0: #[2] パターン2

print('Yes')

else:

print('No')　　　　　　#[2] パターン3

[1]数列AとBの差の絶対値の合計を求める

AとBはそれぞれ長さnの数列なので”A[i]-B[i]”とする操作を、forループでn回繰り返すことで各要素の差を求めることができます。その合計をsumに代入しました。

さらに”abs(A[i]-B[i])”とすることで絶対を求めることができます。

[2]Kとsumの関係に応じて解答する

・パターン1：Kよりもsumが大きい

操作回数がK回という指定があるので、sumがKよりも大きい場合、AとBは一致しません。

例）K=1の場合

A＝[1,3,5]

B=[2,3,4]

①AとBの差の絶対値の合計は1+0+1=2であり、Kよりも大きいです

1回の操作だけではAとBは一致させることができず、Noとなります。

・パターン2：Kよりもsumが小さく、Kとsumの差が偶数の場合

K回以内にAとBを一致させ、さらに残り操作回数が偶数の場合、どれかの要素に1を足し、1を引く操作を繰り返せばよいのでYesとなります。

・パターン3：Kよりもsumが小さく、Kとsumの差が奇数の場合

K回以内にAとBを一致させることができたものの、残り操作回数が奇数の場合、どれかの要素に1を足し引きするとAとBが不一致になるため、Noとなります。

参考

Atcoder Beginners Selectionに類題がありました。

このサイトでも挑戦しています。

AtCoder Beginners SelectionにPythonで挑戦

後半にあるABC086C – Travelingという問題です。

こちらは座標上で考えます。指定された時刻に指定された場所にいられるかという問題で、指定時間内に目的地に到着できたら、あとは隣の場所と行ったり来たりを1秒ごとに繰り返します。

027 – Sign Up Requests （★2）

方針

①入力されたデータをSetオブジェクトに保存する

②各データがSetオブジェクトに保存されていない(まだユーザー名として登録されていない)時に番号を出力する

解答

n=int(input())
s=[]
for i in range(n):
  s.append(input())

list=set() #[1]Set型を利用


for i in range(n):
  if not s[i] in list:
    print(i+1)
  list.add(s[i]) #Setの場合はadd

n=int(input())

s=[]

for i in range(n):

s.append(input())

list=set() #[1]Set型を利用

for i in range(n):

if not s[i] in list:

print(i+1)

list.add(s[i]) #Setの場合はadd

[1]Set型を利用

Set型を利用すると早くなります。

リスト型で組んで提出したところＴＬＥになりました。

なぜSet型だと早くなるかについては正直理解できていないので参考記事をご覧ください。

リストで組んだ場合、同じ文字列がリストに複数含まれている場合でも端から順に全て合致するか確認していきます。これは無駄なのはわかります。

Set型だと重複をなくしてデータが保存されているので、今回の問題の場合は入力データに同じ文字列があるほどに計算量が少なくなると理解しています。

単純な全探索から方針を変えた後の計算量がわかるようにならなければ出力が正しくできるコードでもTLEを繰り返すだけになるので、計算量についてもう少しチェックしてみようと思います。

参考

なるべく公式ドキュメントを見る癖をつけたいです。

Set オブジェクト — Python 3.9.4 ドキュメント

なぜSetだと早くなるのかはこちらを参照。

Pythonで”in list”から”in set”に変えただけで爆速になった件とその理由 – Qiita

pythonの高速化のために、用途別にcollection型(list/tuple/dictionary/set)の計算量をまとめる – Qiita

033 – Not Too Bright（★2）

方針

①HかWが1の場合とH,Wが両方とも2以上の場合で分ける

②H,Wがどちらも2以上の時に、奇数と偶数の場合で分ける

解答

h,w = map(int, input().split())
if h==1:
  ans=w
elif w==1:
  ans=h 
else:
  ans = ((h+1)//2) * ((w+1)//2)
print(ans)

h,w = map(int, input().split())

if h==1:

ans=w

elif w==1:

ans=h

else:

ans = ((h+1)//2) * ((w+1)//2)

print(ans)

①HかWのどちらか一方でも1の場合は特別なケースです。

不適切になる条件は「2×2のマスの中で2つ以上LEDが点灯している」というものです。

どちらかが1なら、2×2のマス自体が存在しないので、すべてのLEDが点灯していても不適切にはなりません。

そのため、1ではない方の数が答えになります。

②HとWのそれぞれについて、偶数ならその半分の値、奇数なら1を足して半分にした値を掛け算すると答えになります。

Wが4の場合は1つおきに点灯していればOKです。(！は点灯しているという意味です。)

！・！・

Wが5の場合も1つおきに点灯していればOKです。

！・！・！

縦の場合も同様です。式にするとこのようになります。

点灯できるLEDの数＝(n+1)÷2

横と縦とそれぞれあるので、掛け算した値が答えになります。

公式ではH,Wが1の場合のようなコーナーケースに注意しようという解説されています。

問題文の条件をよく読む必要があることを再認識しました。

参考

公式解説

038 – Large LCM（★3）

方針

math.gcd関数で最大公約数を求める
a*bを最大公約数で割り算する
値の大きさに応じて解答する

解答

import math
a,b=map(int,input().split())


ans=a*b//math.gcd(a,b)
if ans > 10**18:
  print('Large')
else:
  print(ans)

import math

a,b=map(int,input().split())

ans=a*b//math.gcd(a,b)

if ans > 10**18:

print('Large')

else:

print(ans)

a*bを最大公約数で割ることで最小公倍数を求められます。

解説ではオーバーフローに注意とあり、この問題の趣旨はそちらだと思います。

C++ではlong long型には最大値が存在します。

今回の問題で言えば、上記のPythonのコードをＣ＋＋の文法に則って書くと計算途中でlong long型で決められている最大値よりも大きな値になります。

これが解説で記載されているオーバーフローに当たりますが、このために計算結果が狂って不正解となってしまうことに注意しなければならないようです。

そのため、計算の順序を変えるなど工夫することで正解できるというものでした。

参考記事を読むとPython2の頃は注意しなければならなかったように見えますが、Python3のint型には最大値がないため、オーバーフローによる不正解は心配しなくてもよさそうです。

ただ、計算方法を工夫をすることで、制限時間内に実行できなかったはずが間に合うようになったという問題(055 – Select 5（★2))もあるので、知っておいて損はしないと思います。

また、PythonよりもC++の方が計算速度が早いこともあり、お勧めされている数々の書籍もC++で記載されていることが多いです。いずれPython以外の言語を使うことがあるかもしれないですし、こうした言語による違いを知ることは重要かもしれません。

参考

公式ドキュメント

math — 数学関数 — Python 3.9.4 ドキュメント

最大公約数を求めるアルゴリズムについて書いています。

ユークリッドの互除法で最大公約数を求める

今回のオーバーフローに関連がありそうな記事

Python3の整数int型に最大値はない（上限なし） | note.nkmk.me

C++ における整数型の怪と “移植性のある” オーバーフローチェッカー (第1回 : 整数型の怪と対策の不足) – Qiita

044 – Shift and Swapping（★3）

方針

dequeをインポートしてキューを作成する
t=1では素直に要素を入れ替える
t=2ではpop()とappendleft()でローテーションする
t=3では素直にprintする

解答

from collections import deque
n,q=map(int,input().split())
Q=deque(map(int,input().split()))

for i in range(q):
  t,x,y=map(int,input().split()) 
  if t==1:
    Q[x-1],Q[y-1]=Q[y-1],Q[x-1]  #Q[x-1]にQ[y-1]の値を代入し、Q[y-1]にQ[x-1]の値を代入
  if t==2:
    _=Q.pop()                    #キューから、キューの最後の要素を削除し、_に代入
    Q.appendleft(_)              #キューの先頭に_の値を代入
  if t==3:    
    print(Q[x-1])

from collections import deque

n,q=map(int,input().split())

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

for i in range(q):

t,x,y=map(int,input().split())

if t==1:

Q[x-1],Q[y-1]=Q[y-1],Q[x-1] #Q[x-1]にQ[y-1]の値を代入し、Q[y-1]にQ[x-1]の値を代入

if t==2:

_=Q.pop() #キューから、キューの最後の要素を削除し、_に代入

Q.appendleft(_) #キューの先頭に_の値を代入

if t==3:

print(Q[x-1])

pythonのdequeにはrotate()関数があるので使っていたのですが、rotate()関数はキュー内の全要素を動かすので、計算量がO(N)となります。これをQ回ループさせるので計算量が大きくなりすぎてしまい、TLEになってしまいました。

しかし、popとappendleftを使えば左端と右端の要素を操作はO(1)でできるので計算量が小さくなります。

今回はキューの両端を操作するので問題ないのですが、キューの中央部分の要素を複数操作する場合は間に合わないかもしれません。

なので、公式解説で説明されているようにローテーションした回数をメモしておくという方法を確認したほうが良いかと思います。

・・・思うのですが、この部分の解説が簡素すぎて理解に困っています。

参考

dequeのpopとappendleftの計算量の項目はこちらで記載されています。

Pythonistaなら知らないと恥ずかしい計算量のはなし – Qiita

dequeの公式ドキュメント

collections — コンテナデータ型 — Python 3.9.4 ドキュメント

055 – Select 5（★2）

方針

・計算途中で値が小さくなる定数倍を挟むことで、処理時間を短くしながら全探索する

解答

from itertools import combinations
n,p,q=map(int,input().split())
list = list(map(int, input().split()))          

count = 0
for a,b,c,d,e in combinations(list,5):
  if a%p * b%p * c%p * d%p * e%p == q: #(a*b*c*d*e)%pだとTLEになる
    count +=1
print(count)

from itertools import combinations

n,p,q=map(int,input().split())

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

count = 0

for a,b,c,d,e in combinations(list,5):

if a%p * b%p * c%p * d%p * e%p == q: #(a*b*c*d*e)%pだとTLEになる

count +=1

print(count)

計算途中の値が大きくなると計算が遅くなりますが、途中で計算結果が小さくなる定数倍があれば、

10^5のような計算でも時間切れとならず、正解するとのことでした。

Python3ではTLEになったのでPyPyで提出したところACとなりました。

Python3とPyPyの違いを確認しようと思います。

今後、全探索しか解法が思いつかない問題にあたったときは、forループの中で定数倍することにより値を小さくすることができないか考えてみるのがよさそうです。

参考

公式解説

061 – Deck（★2）

方針

①i番目のtが1ならリストの最後尾に、i番目のtが2ならリストの最初に追加する

②Qの数だけループを行い、i番目のtが3ならリストから(i番目のxの値-1)のインデックスの値を出力する

解答

q = int(input())
t=[]
x=[]
for i in range(q):
  a,b = map(int, input().split())
  t.append(a)
  x.append(b)

list=[]
for i in range(q):
  if t[i]==3:
    print(list[x[i]-1])
  elif t[i]==1:
    list.insert(0,x[i])
  elif t[i]==2:
    list.append(x[i])

q = int(input())

t=[]

x=[]

for i in range(q):

a,b = map(int, input().split())

t.append(a)

x.append(b)

list=[]

for i in range(q):

if t[i]==3:

print(list[x[i]-1])

elif t[i]==1:

list.insert(0,x[i])

elif t[i]==2:

list.append(x[i])

別解

from collections import deque
q = int(input())
t=deque()
x=deque()

for i in range(q):
  a,b = map(int, input().split())
  t.append(a)
  x.append(b)

Q=deque()
for i in range(q):
  if t[i]==3:
    print(Q[x[i]-1])
  elif t[i]==1:
    Q.appendleft(x[i])
  elif t[i]==2:
    Q.append(x[i])

from collections import deque

q = int(input())

t=deque()

x=deque()

for i in range(q):

a,b = map(int, input().split())

t.append(a)

x.append(b)

Q=deque()

for i in range(q):

if t[i]==3:

print(Q[x[i]-1])

elif t[i]==1:

Q.appendleft(x[i])

elif t[i]==2:

Q.append(x[i])

今回の問題は実装自体は難しくないものの、キューやスタックといったデータ構造を理解するためのきっかけとして作成されたのではないかと思います。

pythonだとリストよりもdequeをインポートして使って検証した結果、早くなったという記事が多く見られます。問題によっては制限時間内に間に合わない場合は、dequeを使ってみることを忘れないようにしたいと思います。

データ構造を知るには以下の2冊がよくお勧めされていたので購入して読みました。

個人的には2冊目の方が読みやすかったです。

・プログラミングコンテスト攻略のためのデータ構造

・問題解決力を鍛える！アルゴリズムとデータ構造

078 – Easy Graph Problem（★2）

方針

①1]a,b大きい方をキーに、小さい方を値として辞書を作る

②辞書の値が0でないキーの数を数える

解答

n,m = map(int,input().split())
dict={}

#[1]a,bの大きい方をキーに、小さい方を値として辞書を作る
for i in range(m):
  a,b=map(int,input().split())
  if not max(a,b) in dict:   #辞書にa,bの大きい方がない場合
    dict[max(a,b)]=min(a,b)  #a,bの小さい方を追加
  else:                      #辞書にa,bの大きい方の値がある場合
    dict[max(a,b)]=0         #そのキーの値を0に変更

#[2]辞書の値が0でないキーの数を数える
ans=0
for i in dict:
  if dict[i]!=0:
    ans+=1
print(ans)

n,m = map(int,input().split())

dict={}

#[1]a,bの大きい方をキーに、小さい方を値として辞書を作る

for i in range(m):

a,b=map(int,input().split())

if not max(a,b) in dict: #辞書にa,bの大きい方がない場合

dict[max(a,b)]=min(a,b) #a,bの小さい方を追加

else: #辞書にa,bの大きい方の値がある場合

dict[max(a,b)]=0 #そのキーの値を0に変更

#[2]辞書の値が0でないキーの数を数える

ans=0

for i in dict:

if dict[i]!=0:

ans+=1

print(ans)

[1]a,bの大きい方をキーに、小さい方を値として辞書を作る

aとbが複数回入力されます。

“max(a,b)”　つまりa,bの大きい方の値が辞書のキーとして存在していなければ要素を追加します。

“min(a,b)”　つまりaとbの小さい方は値として辞書に追加します。

また、もし”max(a,b)”がキーとして辞書に存在していた場合は、その値を0にします。

自分自身より値が小さい頂点が2つ以上あること示すことを意図しています。

[2]辞書の値が0でないキーの数を数える

“dict[i]!=0″は、iをキーとしたときの値ですが、その値0以外のキーは、自分よりも小さい頂点が1つのみということなので、その数が解答になります。

所感

はじめは辞書ではなくリストを使って解いていたのですが、提出するとTLEとなったので、ちょこちょこと使い方を調べつつ辞書を使ってみたところACになりました。

辞書やSetオブジェクトの使い方に慣れておく方が有利になりそうです。

時間のある時にリファレンスをチェックしておこうと思いました。

参考

辞書オブジェクト (dictionary object) — Python 3.9.4 ドキュメント