atcoder練習(2024.11.19)

キーワード

問題

高橋君は歯が左右一列に
N 本生えています。現在の高橋君の歯の状態はある文字列
S によって表されます。

S の
i 文字目が O のとき、左から
i 番目の歯が丈夫であることを表します。
S の
i 文字目が X のとき、左から
i 番目の歯が虫歯にかかっていることを表します。丈夫である歯は虫歯にかかっていません。

高橋君はある連続する
K 本の歯が丈夫であるとき、その
K 本の歯を使ってイチゴを
1 個食べることができます。イチゴを食べると、その
K 本の歯が虫歯にかかり丈夫でなくなります。

このとき、高橋君は最大で何個のイチゴを食べることができるか求めてください。

制約
1≤K≤N≤100
N,K は整数
S は O と X からなる長さ
N の文字列
入力
入力は以下の形式で標準入力から与えられる。

N
K
S
出力
答えを出力せよ。

入力例 1
Copy
7 3
OOXOOOO
出力例 1
Copy
1
左から
4 本目の歯から左から
6 本目の歯までの連続する
3 本の丈夫な歯を使ってイチゴを
1 個食べることができます。これ以降、イチゴを食べることができません。また、他にどのような方法でイチゴを食べても
1 個以下しか食べることができません。よって、
1 を出力します。

入力例 2
Copy
12 2
OXXOOOXOOOOX
出力例 2
Copy
3
入力例 3
Copy
22 5
XXOOOOOOOOXXOOOOOXXXXX
出力例 3
Copy
2

回答

N , K = map(int, input().split())
S = input()

ans = 0
key = 0

for i in range(N):
  if S[i] == "O":
    key += 1
    if key == K:
      ans += 1
      key = 0
  else:
    key =0

print(ans)

参考

備考

• 比較的アルゴリズムが整理することができた。最初の段階では余計な部分があったけど、コードを書いたり、紙に書いたりする過程で整理することができた。やっぱりアルゴリズムを考えるのが大事。
• コードを書く力が不足しているのはもちろんだけど、それ以上にアルゴリズム力の方を鍛えたほうが良さそう。一方で鍛え方ってどうするの？
• 他の人のコードを見る限り同じようなことをしているのが大半。