2019-06-13に投稿

AtCoder Beginner Contest 122cをPythonで解く

GeT AC

  1. GeT AC

問題

A, C, G, T からなる長さNの文字列 Sが与えられます。以下の Q個の問いに答えてください。問 i (1≤i≤Q): 整数 li,ri (1≤li
Sの先頭から li 文字目から ri 文字目までの (両端含む) 部分文字列を考える。この文字列に AC は部分文字列として何回現れるか。

こう考えた

  • countでACの数を計算して出力する。

書いたコード

N,Q=map(int,input().split())
S=input()
for q in range(Q):
  l,r=map(int,input().split())
  s=S[l-1:r]
  print(s.count("AC"))

🐍これでいけんちゃうかな?

結果

TLE

🐍計算量の問題か

Atcoderの標準回答

N,Q=map(int,input().split())
S=input()
t = [0] * (N + 1)
for i in range(N):
  t[i + 1] = t[i] + (1 if S[i : i + 2] == 'AC' else 0)
for q in range(Q):
  l,r=map(int,input().split())
  print(t[r-1] - t[l-1])

🐍ACのカウントの配列をつくるんやな。

結果

AC

🐍文字列検索って結構時間喰うねんな。。

Originally published at www.coderecipe.org

view_list Pythonで競プロ
第9回 AtCoder Beginner Contest 090BをPythonで解く
第10回 AtCoder Beginner Contest 129DをPythonで解く
第11回 AtCoder Beginner Contest 122cをPythonで解く
第12回 AtCoder Beginner Contest 063bをPythonで解く
第13回 # AtCoder Beginner Contest 123CをPythonで解く

aocory

Crieitは個人で開発中です。 興味がある方は是非記事の投稿をお願いします! どんな軽い内容でも嬉しいです。
なぜCrieitを作ろうと思ったか

また、「こんな記事が読みたいけど見つからない!」という方は是非記事投稿リクエストボードへ!

こじんまりと作業ログやメモ、進捗を書き残しておきたい方はボード機能をご利用ください!

ボードとは?

関連記事

コメント