AtCoder Beginner Contest 161 E
AtCoder Beginner Contest 161 E を Python で解説していきます。初見のときは，いつもの問題よりも問題設定が簡単めかなぁと思いましたが，実際にコーディングしようとすると全然手が出ませんでした。(笑)
ただ，問題設定自体は理解しやすい問題だと思います！😀
AtCoder の解説を見てじっくり考えてから自力でコーディングして AC できましたので，これを基に解説していきたいと思います。
それでは早速いきましょう！まずは問題文から。
E – Yutori
実行時間制限: 2 sec / メモリ制限: 1024 MB
配点 : 500 点
問題文
高橋君は明日からの N 日間のうち K 日を選んで働くことにしました。
整数 C と文字列 S が与えられるので、次の 2 つの条件を満たすようにして働く日を選びます。
- ある日働いたら、その直後の C 日間は働かない
- S の i 文字目が 'x' のとき、今日から i 日後には働かない
高橋君が必ず働く日をすべて求めてください。
制約
- 1≤N≤2×10^5
- 1≤K≤N
- 0≤C≤N
- S の長さは N
- S の各文字は 'o' か 'x'
- 問題文中の条件を満たすように働く日を選ぶことが可能
入力
入力は以下の形式で標準入力から与えられる。
N K C
S
出力
高橋君が必ず働く日を昇順に改行区切りですべて出力せよ。
解説
1つ目の設定は，j 日目に働くと次に働けるのは C 日間の休暇を挟んだ j + (C+1) 日目になるというもので，2つ目の設定は文字列 S が与えられて，その i 番目が i 日目に働けるかどうかを表しており，’o’ なら働け，’x’ なら働けないということです。
まずは入力例１を見てどういう思考過程を経ればいいか考えてみましょう。入力例１は以下です。
11 3 2
ooxxxoxxxoo
１１日間のうち３日働き，それぞれ２日のインターバルが必要という設定ですね。実際に出力を考えるときは S を見ながら１日目から可能なものを考えて，
(１，６，１０），（１，６，１１），（２，６，１０），（２，６，１１）
この４パターンが考えられます。よって全てに共通している６を出力します。
この思考から，もし働く日数を最大にしたいのなら，１日目から貪欲に設定に当てはまるものを考えればいいことが分かります。上記の例の場合，これは（１，６，１０）がこれに当てはまりますね。これを L = [1, 6, 10]としておきます。
働く日数が最大の場合とは結局どういうことなのでしょうか。これはつまるところ i 回目に働くのはL[i-1]日目以降ということになりますよね。どういうことかというと，L の場合が最大限に働く場合なのだから，例えば１回目に働くのは１日目以降，２回目に働くのは６日目以降でなければなりませんよね？
つまり，左から貪欲に働く日数を出していき，それを L という配列にすると，L は i 番目に働く日が L[i-1] 日目以降になるということが分かります。同様に今度は右から貪欲に働く日数を出していき，それを R という配列にすると， i 番目に働く日が R[i-1] 日目以前になるということが分かります。先ほどの例では (２，６，１１) がこれにあたります。
ではこの L と R を求めたら何が分かるのか？についてです。
L[x] と R[x] はそれぞれ x 回目に働くのが L[x] 日目以降，R[x]日目以前ということなので，もし L[x] = R[x] = i となるような x があるなら，その x 回目に働くのは i 日目以降，i 日目以前，ということはつまり i 日目ということになって，x 回目に働くのは必ず i 日目であるということになります。
従って，実装すべきは貪欲に L と R を出して，その後条件分岐を設定して L[x] = R[x] = i となるような i を出力するというものです。ここまでくればコーディング自体はそこまで難しくはないと思います。
では，解答例を載せます。
解答例では S の最初に 'x’ を加えることで，S のインデックス番号と日にちを同じ値にしました。
また，R を出すときに後ろから貪欲でリストに追加していくと降順で追加されてしまうので，L と対応させるために R[::-1] で順序を逆にしました。
解答例
n,k,c = map(int,input().split())
s = "x" + input()
l = []
i = 1
# 前から貪欲
while len(l) < k:
if s[i] == "o":
l.append(i)
# i日目に働くと次に働けるのはc+1日目
i += c+1
else:
# その日働けないなら次の日に回す
i += 1
# 後ろから貪欲
r = []
i = n
while len(r) < k:
if s[i] == "o":
r.append(i)
i -= (c+1)
else:
i -= 1
# rを降順から昇順に
r = r[::-1]
for i in range(len(l)):
if l[i] == r[i]:
print(l[i])やはり E 問題になると難しいですね。😅
ただ，発想自体はかなり面白いなと思いました！
それでは！
