パナソニックプログラミングコンテスト2020 E Three Substrings 感想戦

今回のABCは恐ろしい回だった。 嘘解法が通るなど幸運もあり黄パフォだったが、コンディションによっては緑あたりが出てもおかしくない感じだ。

りんごさん御自ら作門した回ということで、なんらかのメッセージを出してくるんじゃないかなとは思っていたが。

「Bにはコーナーケースはないだろう」と思ったら『H == 1で角がまったく動けない』、 「Cあたりは全探索あるかもしれないけど、Eまで来たらDPとか文字列ならローリングハッシュ」と思ってたら『Eが全探索』、 とまあ「いつものABC」を過学習してしまった僕達に意識の外からZガンを直撃させてくる感じのコンテストであった。

E - Three Substrings

本家解説が丁寧なので、ブログはあっさり目で。

本番での方針

a->b->c、b->a->cのpermutaionをすべて調べさらにそれらについて、a->bのずらし幅とb->cのずらし幅を調べる。 愚直にやると間に合わない。ここで、貪欲にa->bのもっとも短いずらし幅のみを調べると、全体が最短になる回を見逃すことがあるのは公式の解説の通り。

前計算によってオーダーを落とすのが想定解だったようだ。

しかし、自力では全く思い浮かばず計算量の削減に苦戦。

ここで、貪欲法を少し改良し、「a->bのベスト10の短いありうるずらし幅に対しb->cの最短のずらし幅を探す」という貪欲法を少しだけマシにしたような精度改善を思いつく。

ためしに提出してみると、

1ケースのみ落ちてる。

「あれ、これもうちょっと頑張ればいけるんじゃない？」と思いベスト10->ベスト50にして投げ込む。

Submission #10878091 - Panasonic Programming Contest 2020

通った。こうして、高度嘘解法人材として黄パフォ獲得に成功しました。めでたし。

正しい方針

概ね公式の通りの方針です。 https://img.atcoder.jp/panasonic2020/editorial.pdf

fn is_ok(a: &Vec<char>, b: &Vec<char>) -> Vec<bool> {
    let mut ret = vec![true; a.len()];
    for i in 0..a.len() {
        if (0..b.len())
            .any(|j| i + j < a.len() && b[j] != '?' && a[i + j] != '?' && b[j] != a[i + j])
        {
            ret[i] = false;
        }
    }
    ret
}

fn main() {
    let a = read::<String>().chars().collect::<Vec<_>>();
    let b = read::<String>().chars().collect::<Vec<_>>();
    let c = read::<String>().chars().collect::<Vec<_>>();
    // ２つの文字列をiずらしたときに矛盾しないかどうか。
    // [0]a->b, [1]b->a, [2]b->c, [3]c->b, [4]a->c, [5]c->aの関係を表す。
    let mut ok = vec![vec![]; 6];
    for (i, &(ref a, ref b)) in [(&a, &b), (&b, &a), (&b, &c), (&c, &b), (&a, &c), (&c, &a)]
        .iter()
        .enumerate()
    {
        ok[i] = is_ok(&a, &b);
    }

    let mut ans = a.len() + b.len() + c.len();
    let criterion = |ok: &Vec<bool>, i| i >= ok.len() || ok[i];
    for &(ref ok0, ref ok1, ref ok2, l1, l2, l3) in &[
        (&ok[0], &ok[2], &ok[4], a.len(), b.len(), c.len()), // a -> b -> c
        (&ok[4], &ok[3], &ok[0], a.len(), c.len(), b.len()), // a -> c -> b
        (&ok[1], &ok[4], &ok[2], b.len(), a.len(), c.len()), // b -> a -> c
        (&ok[2], &ok[5], &ok[1], b.len(), c.len(), a.len()), // b -> c -> a
        (&ok[5], &ok[0], &ok[3], c.len(), a.len(), b.len()), // c -> a -> b
        (&ok[3], &ok[1], &ok[5], c.len(), b.len(), a.len()), // c -> b -> a
    ] {
        for i in 0..ok0.len() {
            if !criterion(ok0, i) {
                continue;
            }
            // a->bのずらし幅がi、b->cのずらし幅がj-i、こうするとa->bはjずれている。i, jは非負
            let j = (i..ok0.len() + ok1.len())
                .find(|&j| criterion(ok1, j - i) && criterion(ok2, j))
                .unwrap();
            let cur_length = *[l1, i + l2, j + l3].iter().max().unwrap();
            ans = std::cmp::min(ans, cur_length);
        }
    }
    println!("{}", ans);
}

fn read<T: std::str::FromStr>() -> T {
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).ok();
    s.trim().parse().ok().unwrap()
}

a, b, cあたりでこんもりになってしまったfor文がつらいがそこだけ気をつければなんとかなる。 permutationとか使えばもっと賢い書き方ができるかもしれないが、かえってバグりそうなのでやめた。

ところで、最近はforとかifを使うよりなるべく、any()とかall()とかfind()を使うようにしている。 これらを使ったほうがバグりづらく、読みやすい。

ただし、is_okはcollectを使えば残っているfor文を消すこともできるが、そこまでやると逆にわかりづらくなるので、この辺が自分にとっては一番わかりやすい落とし所。