CODE FESTIVAL 2017 Final E - Combination Lock

解法

方針としては、

  1. 区間を整理しやすいように文字列の長さを偶数にする。
  2. 区間の整理をめっちゃ頑張る
  3. 端から区間を見ていけば良いだけの状態になったら imos 法で順番に処理していき、ダメだったら NO

文字列の長さを偶数にする

文字列の長さが奇数だった場合、中央の文字に対する操作が何回行われても結果に影響はないので、中央の文字とそれに対する操作を削除して考えても変わりません。よって、入力を整理して、文字列の長さは必ず偶数であるとして考えます。

中央を覆う区間に対する操作

例えば、長さ 8 の文字列の [1, 5] 文字目に対する操作があった時、回分にするためには 4 文字目と 5 文字目を同じ文字にする必要がありますが、この操作によって 4 文字目と 5 文字目の差は変わらないため、この操作による 4 文字目と 5 文字目への影響は無視できます。よって、長さ 8 の文字列の [1, 5] 文字目に対する操作は [1, 3] 文字目に対する操作と考えることができます。

f:id:kenkoooo:20171215222547p:plain

このように中央を越える区間に対する操作は、中央を挟んだ無視できる区間への影響を無視することで、より小さい区間への操作に置き換えることができます。これによって全ての操作を、中央から見て右側か左側のどちらかに収まるものとして考えることができます。

片側に寄せる

ある区間に対する操作を 26 回行うのと 0 回行うのは同じです。よってある区間に対する操作を 25 回行うのと -1 回行うのは同じことがわかります。中央から見て右側にある区間に対する操作は、中央から見て対称な左側の区間に対する操作に置き換えられます。例えば、長さ 8 の文字列について、 [6, 8] 文字目に対する操作を 1 回行うことは、 [1, 3] 文字目に対する操作を -1 回行うのと同じです。

このことから、全ての区間を左側に集め、左側に対して操作を行うことで右側の文字列を作って行く問題と考えることができます。

区間の整理

片方の端が同じ値である2つの区間に対する各操作は、区間が被らない操作として考えることが出来ます。例えば、区間 [a, b] に対する操作 1 と、区間 [a, b+k] に対する操作 2 があって操作 1 を m 回行って操作 2 を n 回行うのは、区間 [a, b] に対する操作を 2m 回行って、区間 [b+1, b+k] に対する操作を n 回行うのと同じです。

f:id:kenkoooo:20171215215746p:plain

よって上の図のように 4 つの区間がある時、下の図のようにそれぞれが被らない区間の操作に置き換えることができます。

f:id:kenkoooo:20171215220442p:plain

累積和

imos 法

コード

use std::io;
use std::cmp;
use std::collections::BTreeMap;
use std::collections::VecDeque;
use std::collections::BTreeSet;

fn main() {
    let s = read_line().trim().to_owned();
    let n = s.len();
    let methods = read_values::<usize>()[0];
    let mut segments = Vec::new();
    for _ in 0..methods {
        let input = read_values::<usize>();
        let mut l: usize = input[0] - 1;
        let mut r: usize = input[1] - 1;
        let half = n >> 1;

        if (n & 1) == 1 {
            // 文字列の長さが奇数の時、中央の文字を削除するために区間を整理する
            if l == half && r == half {
                // 中央の 1 文字のみに対する操作は意味がないので無視する
                continue;
            }

            // 中央の文字を削除する分だけ 1 文字分ずらす
            if half < l {
                l -= 1;
            }
            if half <= r {
                r -= 1;
            }
        }
        segments.push((l, r));
    }

    // 長さが奇数の時、中央の文字を削除する
    let s = {
        let t = s.bytes().map(|c| {
            c - "a".bytes().next().unwrap()
        }).collect::<Vec<_>>();
        let mut polished = Vec::new();
        for i in 0..n {
            if (n & 1) != 1 || (n >> 1) != i {
                polished.push(t[i]);
            }
        }
        polished
    };

    // 新しい文字列の長さ
    let n = s.len();

    // 区間の左端をキーにして、左端の値の set を持つ
    let mut right_map: BTreeMap<usize, BTreeSet<usize>> = BTreeMap::new();
    for x in segments.iter() {
        let (l, r) = *x;

        let half = n >> 1;
        let (l, r) = if r < half {
            // 中央から見て左側の区間はそのまま使う
            (l, r)
        } else if l >= half {
            // 中央から見て右側の区間は左側に移す
            (n - 1 - r, n - 1 - l)
        } else {
            // 中央を越える区間を整理する
            let right_side = r - (half - 1);
            let left_side = half - l;

            if right_side > left_side {
                // 中央から見て右のほうが大きい区間
                let tmp_l = half + left_side;
                (n - 1 - r, n - 1 - tmp_l)
            } else if right_side == left_side {
                // 中央から見て対称な区間に対する操作は結果に影響がないので無視する
                continue;
            } else {
                // 中央から見て左のほうが大きい区間
                (l, half - 1 - right_side)
            }
        };

        if !right_map.contains_key(&l) {
            right_map.insert(l, BTreeSet::new());
        }
        right_map.get_mut(&l).unwrap().insert(r);
    }

    // 区間の右端をキーとした map も作る
    let mut left_map = BTreeMap::new();
    for (left, rights) in right_map.iter() {
        for r in rights.iter() {
            if !left_map.contains_key(&(r + 1)) {
                left_map.insert(r + 1, BTreeSet::new());
            }
            left_map.get_mut(&(r + 1)).unwrap().insert(*left);
        }
    }

    // 区間を整理する
    let mut merged_map = BTreeMap::new();
    for left in 0..n {
        // left を左端に持つ区間がなければスルー
        if !right_map.contains_key(&left) {
            continue;
        }

        let mut lefts = BTreeSet::new();

        let mut queue = VecDeque::new();
        queue.push_back(left);
        let mut right = left;
        while !queue.is_empty() {
            let v = queue.pop_front().unwrap();
            lefts.insert(v);

            if let Some(set) = right_map.remove(&v) {
                for r in set.iter() {
                    queue.push_back(*r + 1);
                    right = cmp::max(right, *r + 1);
                }
            }

            if let Some(set) = left_map.remove(&v) {
                for l in set.iter() {
                    queue.push_back(*l);
                }
            }
        }
        lefts.insert(right);

        let list = lefts.iter().map(|x| x.clone()).collect::<Vec<_>>();
        for i in 0..(list.len() - 1) {
            let cur = list[i];
            let next = list[i + 1];
            merged_map.insert(cur, next);
        }
    }

    let mut sum = vec![0; n / 2 + 1];
    let mut cur = 0;
    for i in 0..(n / 2) {
        cur += sum[i];
        let from = (s[i] as i64 + cur) % 26;
        let to = (s[n - 1 - i] as i64) % 26;
        let add = (to + 26 - from) % 26;
        if add == 0 {
            continue;
        }
        if !merged_map.contains_key(&i) {
            println!("NO");
            return;
        }
        let x = *merged_map.get(&i).unwrap();
        cur += add;
        sum[x] -= add;
    }
    println!("YES");
}

fn read_line() -> String {
    let stdin = io::stdin();
    let mut buf = String::new();
    stdin.read_line(&mut buf).unwrap();
    buf
}

fn read_values<T>() -> Vec<T> where T: std::str::FromStr, T::Err: std::fmt::Debug {
    read_line()
        .split(' ')
        .map(|a| a.trim().parse().unwrap())
        .collect()
}