Hatena::Grouptopcoder

ぷろこんメモ用紙

2013-09-02Typical DP Contest I - イウィ

DPが見えなかったので法則ゲーしたらあっけなく通ってしまった。


問題文

方針としては、文字列中にiiwiがあったらこのiwiは問答無用で消しても良いというもの。

なぜなら、

  • iwiの左はどうせiなのでこのままでは消えない
  • 右(iiwiの次の文字)から見た時は、iwiを消してもその直前がiであるという事実は変化せず、またこの文字はwを使った消し方には絡めないので、消し方を減らすことはない。

という2点が成立するため。iwiiについても同様のことが言える。

この方針で消せるだけ消すと、残ったiwiは全てwiwiwの形で出現していることになる。

こうなったら、左から貪欲に消していくと最も多く消せる。

たぶん正しいと思うんだけど、誰か反例を見つけたら教えてください。

#!/usr/bin/env ruby

# iwiを消せるパターンとして、まず見えるのが
# ・iiwi, iwii: iwiを消してiに置換しても等価
# これを可能な限り適用すると、残ったiwiは消しても新しくiwiが生成されることはない。
# (残ったiwiの両側は常にwであり、iwiを消すとwwが生成されるため。)
# したがって、左から順にiwiを消していけば最も多くiwiを消せる。

s = gets.chomp
cnt = 0
loop do
  cur = cnt
  s.gsub!(/iiwi/){cnt += 1; "i"}
  s.gsub!(/iwii/){cnt += 1; "i"}
  break if cur == cnt
end
s.gsub!(/iwi/){cnt += 1; ""}
puts cnt