読者です 読者をやめる 読者になる 読者になる

水面下の夢

競プロやイラストに興味があります.メインブログがここ.ソシャゲの話はこっち(http://ameblo.jp/0n0-yumechi/).ブログアイコンはYaQ(@8_9_00)さんから.

No.345 最小チワワ問題

Python yukicoder 競技プログラミング

No.345 最小チワワ問題 - yukicoder

yurahunaさんがすでに解説を書いているので、私が書く意味は殆ど無いのですが、まあ記録のために一応。

pakapa104.hatenablog.com


最短でc.*w.*wがでるようなパターンを求める問題。 あれ、これもしかして最短チワワ問題なのでは…。

多分私が書いたのはO(N^2)解法。長くなりすぎてしまった。(´・ω・`)
とにかくcを発見したら、次のwとその次のwを求めて距離を計算して最小値を更新していく、という方法。一応、c.*w.*wが見つからなかった場合に対して、番兵を設置しておく(114がそれ)

Python3での解答コードは以下のとおり。

#79791 No.345 最小チワワ問題 - yukicoder

s = input()
res = 114
while "c" in s:
    cidx = s.find("c")
    widx = s.find("w", cidx+1)
    if widx < 0:
        break
    w2idx = s.find("w", widx+1)
    if w2idx > 0:
        res = min(res, w2idx - cidx + 1)
    s = s[cidx+1:]
print(res if res != 114 else -1)

30/ 300