ABC161 E - Yutori

問題原文

atcoder.jp

問題要旨

明日から 日間のうち、 日間を選んで働く。
ただし、 x がつけられた日と、最後に働いてから 日間は働けない。
日働くために必ず働かなければいけない日を全て求めよ。

• 

解法

まず問題を簡単にして、「できるだけ多く働くには？」を考える。これは貪欲的に働ける日に働くのが最適。 次に、 「 日目に働かなくても 日間働くことができるか？」を各 について考えたくなるが、これはまともにやると [tex: O(N²)] になってしまう。

よく考えると、 「 日目に働かなくても 日間働くことができるか？」は、 「 日目まで出来るだけ多く働く」+「 日目以降できるだけ多く働く」をして、 日以上働いているか？ と言い換えることができる。

ここまで見えると、ある点で２分される場合のdpが思い浮かぶので、 dpテーブル を二つ計算して各 について高速に答えを求めれば良い。

↓は僕が解説を書いた類題 at274.hatenablog.com

実装

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


dp1 = [0] * (N + 1)  # iまでで何回働けるか
dp1[0] = 0
for i, s in enumerate(S, start=1):
    if s == 'x':
        dp1[i] = dp1[i - 1]
        continue
    b = max(0, i - C - 1)
    dp1[i] = dp1[b] + 1


dp2 = [0] * (N + 1)  # i以降で何回働けるか
for i in reversed(range(N)):
    s = S[i]
    if s == 'x':
        dp2[i] = dp2[i + 1]
        continue
    b = min(N, i + C + 1)
    dp2[i] = dp2[b] + 1


ans = []
# i番目のやつを使わなくてもK個取れるか？
for i in range(1, N + 1):
    if dp1[i - 1] + dp2[i] < K:
        ans.append(i)

print(*ans, sep="\n")

感想

ACまで23分だけど、発想が出るのが少し遅かったので一瞬で出したいなぁと。
想定は前と後ろから貪欲をして結果をマージするらしいです（やったこと似てるけど届かない壁を感じる）