🙄
アルゴリズム勉強の反省日記 4/25-5/9
4/26 HackerRank Strings: Abbreviation
二つの文字列AとBがあたえられる。Aには小文字がふくまれ、それらを消去あるいは大文字に変換するとBに一致するかどうかを判定する。ちなみに大文字は消去できない(これを見落としていた)。
解法としては、まず
- Aの一文字目が大文字か判定、大文字ならBの一文字目と一致しているかを判定する。一致してない場合はおわり、一致していればAの二文字目以降を検討。
- Aの一文字目が小文字の場合、大文字にした場合にBの一文字目と一致するか判定。一致すればA,Bそれぞれ次の文字を考える。一致しなければAの次の文字とBの一文字目を繰り返し検討する。
4/27 HackerRank Queues: A Tale of Two Stacks
キューの問題。そもそも問題文を理解するのが難しかった…
class MyQueue(object):
def __init__(self):
self.inward = []
self.outward = []
def peek(self):
if not self.outward:
self.outward = list(reversed(self.inward))
self.inward = []
return self.outward[-1]
def pop(self):
head = self.peek()
del self.outward[-1]
return head
def put(self, value):
self.inward.append(value)
queue = MyQueue()
t = int(input())
for line in range(t):
values = map(int, input().split())
values = list(values)
if values[0] == 1:
queue.put(values[1])
elif values[0] == 2:
queue.pop()
else:
print(queue.peek())
5/1 AtCorder D問題
反転するか否かをrevで表し、文字を追加する時に前から追加するか後ろから追加するか決める。
単純にリストを反転すると、遅くなっちゃう。
リストとdequeの計算量の違い・使い分け
- 要素の追加・取り出し（削除）・アクセス（取得）が両端のみ → deque
- 両端以外の要素に頻繁にアクセス → リスト
from collections import deque
s = deque()
rev = False
for i in input():
if i == 'R':
rev = not rev
elif rev:
if s and s[0] == i:
s.popleft()
else:
s.appendleft(i)
else:
if s and s[-1] == i:
s.pop()
else:
s.append(i)
if rev:
s = reversed(s)
print("".join(s))
[参考]https://note.nkmk.me/python-collections-deque/
5/8 AtCoder Beginner Contest 200
差を200で割ったあまりが同じになるような整数の組みの個数を求める問題。
・200で割った余りが一致する整数の組み合わせというとこに気付けなかった
・今回の場合、長さ２００の０のリストをつくり、余りの分をカウントしていく
・その中かから、nC2の組み合わせを計算していく
n = int(input())
a_list = list((map(int, input().split())))
a_num = 0
arrc = [0]*200
for i in a_list:
arrc[i%200] += 1
for j in arrc:
a_num += (j * (j - 1))/2
print(int(float(a_num)))
Discussion