Atcoder ABS ABC049C 白昼夢

こんにちは、ナナオです。

前回に引き続き競プロを実施していきたいと思います。

今回の問題は以下です。

実装

最初はシンプルに…（と思ったんですが結構行数使ってしまいました）

文字の長さとそれぞれの文字列が一致しているかどうかを見て、一致していたら渡された文字列から文字数だけ削除するという実装になっています。

use proconio::input;

fn rmstr(mut s: String, n: usize) -> String {
    for _ in 0..n {
        s.remove(0);
    }
    s
}

fn main() {
    input! {
        mut s: String,
    }
    let c = 0;
    loop {
        if s.len() < 5 {
            println!("NO");
            return;
        }
        let a = &s[c..c + 5];
        if a == "dream" || a == "erase" {
            s = rmstr(s, 5);
        } else if s.len() >= 6 && &s[c..c + 6] == "eraser" {
            s = rmstr(s, 6);
        } else if s.len() >= 7 && &s[c..c + 7] == "dreamer" {
            s = rmstr(s, 7);
        } else {
            println!("NO");
            return;
        }
        if s.len() == 0 {
            println!("YES");
            return;
        }
    }
}

これで実装できた！…と思ったんですが、通りませんでした。

普通に考慮不足がありました。

dreamerはdreamと、eraserはeraseと一部一致しているので、この実装だと判定するのが早すぎてdreameraserのような文字列の場合だと最後にrだけ残って正常に判定できません。

ということで判定順を早めます。

use proconio::input;

fn rmstr(mut s: String, n: usize) -> String {
    for _ in 0..n {
        s.remove(0);
    }
    s
}

fn main() {
    input! {
        mut s: String,
    }
    let c = 0;
    loop {
        if s.len() < 5 {
            println!("NO {}", s);
            return;
        }
        let a = &s[c..c + 5];
        if s.len() >= 7 && &s[c..c + 7] == "dreamer" {
            s = rmstr(s, 7);
        } else if s.len() >= 6 && &s[c..c + 6] == "eraser" {
            s = rmstr(s, 6);
        } else if a == "dream" || a == "erase" {
            s = rmstr(s, 5);
        } else {
            println!("NO");
            return;
        }
        if s.len() == 0 {
            println!("YES");
            return;
        }
    }
}

と、このように実装しましたが、先ほどのdreameraserの場合dreamerの判定が先にされ、aserという謎の文字列が残ることになります。

さて、こうなるとわからなくなってきました。

単純な文字列置換でも解決できないのです。

ということでAIと壁打ちします。

文字列を逆にして判定すればいいと助言をもらいました。

ついでに、s.remove(0)は文字列の長さに応じてO(N^2)という結構無視できない計算量が発生するようなので、これも削除します。

ということで修正したコードは以下の通りです。

use proconio::input;

const WORDS: [&str; 4] = ["maerd", "remaerd", "esare", "resare"];

fn main() {
    input! {
        s: String,
    }
    let rs = s.chars().rev().collect::<String>();
    let mut i = 0;
    'outer: while s.len() < i {
        for word in WORDS {
            if rs[i..].starts_with(word) {
                i += word.len();
                continue 'outer;
            }
        }
        println!("NO");
        return;
    }

    println!("YES");
}

これで出来たと思ったんですが、while文の条件が間違っていて、常にYESを出力するようになってしまっていたので、そこだけ修正しました。

use proconio::input;

const WORDS: [&str; 4] = ["maerd", "remaerd", "esare", "resare"];

fn main() {
    input! {
        s: String,
    }
    let rs = s.chars().rev().collect::<String>();
    let mut i = 0;
    'outer: while i < s.len() {
        for word in WORDS {
            if rs[i..].starts_with(word) {
                i += word.len();
                continue 'outer;
            }
        }
        println!("NO");
        return;
    }

    println!("YES");
}

これで実装できました！

ということで今回はこれで👍

実装#

実装