C. Cow and Message

Quiz

https://codeforces.com/contest/1307/problem/C

解法

https://codeforces.com/blog/entry/73953

補足

• indexの関係は「arithmetic progression（等差数列）」になっていなければいけない
• なので、s=aaabbcccの場合の答えは9が正しい
  • 3x2x3=18ではない
• indexのセットを選ぶたびに等差は変わってもよい

例題

abcabcbopqrsc

ans = 6

わかりやすく分割すると

abc abc b opqrs c

• abcを3つ取れるようにsを設定した
• しかし答えは6
• bcの組が6個取れる
• abの組は5個
• もしsの後端にcが大量にあったとしても、abcの組はabの組以上にはならない

abcabcbopqrsccccccccccccccccccccccccc

• この場合の答えは351
• ccが大量に作れるため

振り返り

• 「長さ3以上は考える必要がない」と気づけるか
• 英語をちゃんと読まないと制約を見逃す

プログラミングコンテストチャレンジブック [第2版]　～問題解決のアルゴリズム活用力とコーディングテクニックを鍛える～