AtCoder Beginner Contest 268 D

https://atcoder.jp/contests/abc268/tasks/abc268_d

Sの間にアンダースコアを挟みますが、例えば、Sが4個で合わせて11文字だったら、最大5個のアンダースコアを3つに分配することになります。これは意外と簡単です。最初は、

1 1 1

これに1ずつ加えていけばよいです。例えば、

2 1 1

です。しかし、うまく加えてあげないと重複することになります。自由に加えられたら、

1 2 1

からも、

2 1 1

からも、

2 2 1

とすることができます。こういうときは逆から考えます。

2 2 1

から1個減らすには、

2 1 1

が自然でしょう。要するに、1より大きい右端から減らすのです。逆に戻すと、追加できるのは、右から辿っていって、1が続く間はどこでも追加できる、1より大きい数に出合ったらそこには追加できてもう左には追加できない、とすればよいです。
場合によっては複数追加できる箇所があるので、Queueを使います。QueueはVecDequeを使います。
permutationsもそんなに難しくないので実装しました。

// Unique Username
#![allow(non_snake_case)]

use std::collections::{VecDeque, HashSet};


//////////////////// library ////////////////////

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

fn read_vec<T: std::str::FromStr>() -> Vec<T> {
    read::<String>().split_whitespace()
            .map(|e| e.parse().ok().unwrap()).collect()
}


//////////////////// Distribute ////////////////////

struct Distribute {
    n: usize,
    m: usize,
    queue: VecDeque<Vec<usize>>,
}

impl Iterator for Distribute {
    type Item = Vec<usize>;
    
    fn next(& mut self) -> Option<Vec<usize>> {
        let v_ = self.queue.pop_front();
        if v_ == None {
            return None
        }
        
        let v0 = v_.unwrap();
        if v0.iter().sum::<usize>() == self.n {
            return Some(v0)
        }
        
        for i in (0..self.m).rev() {
            if i == self.m - 1 {
                // 右端なら積める
                let v = Distribute::add(&v0, i);
                self.queue.push_back(v);
                if v0[i] > 1 {
                    break
                }
            }
            else if v0[i] > 1 {
                // 1でない最も右に積める
                let v = Distribute::add(&v0, i);
                self.queue.push_back(v);
                break
            }
            else {
                // 1でも積める
                let v = Distribute::add(&v0, i);
                self.queue.push_back(v);
            }
        }
        return Some(v0)
    }
}

impl Distribute {
    fn add(v: &Vec<usize>, i: usize) -> Vec<usize> {
        let mut v1 = v.to_vec();
        v1[i] += 1;
        v1
    }
    
    fn create(n: usize, m: usize) -> Distribute {
        let mut q = VecDeque::<Vec<usize>>::new();
        let v = (0..m).map(|_| 1).collect::<Vec<usize>>();
        q.push_back(v);
        Distribute { n, m, queue: q }
    }
}


//////////////////// Permutations ////////////////////

struct Permutations {
    a: Vec<usize>
}

impl Iterator for Permutations {
    type Item = Vec<usize>;
    
    fn next(&mut self) -> Option<Vec<usize>> {
        if self.a.is_empty() {
            return None
        }
        
        let ret = Some(self.a.to_vec());
        for i in (1..self.a.len()).rev() {
            if self.a[i-1] < self.a[i] {
                self.change(i);
                return ret
            }
        }
        self.a.clear();
        ret
    }
}

impl Permutations {
    fn swap(&mut self, i: usize, j: usize) {
        let tmp = self.a[i];
        self.a[i] = self.a[j];
        self.a[j] = tmp;
    }
    
    fn find_neighbor_index(&mut self, i: usize) -> usize {
        for j in i..self.a.len() {
            if self.a[i-1] > self.a[j] {
                return j - 1
            }
        }
        self.a.len() - 1
    }
    
    fn change(&mut self, i: usize) {
        let k = self.find_neighbor_index(i);
        self.swap(i - 1, k);
        for j in i..(i+(self.a.len()-i)/2) {
            self.swap(j, self.a.len() - j + i - 1)
        }
    }
    
    fn create(n: usize) -> Permutations {
        let a = (0..n).collect::<Vec<usize>>();
        Permutations { a }
    }
}


//////////////////// process ////////////////////

fn read_input() -> (Vec<String>, Vec<String>) {
    let v: Vec<usize> = read_vec();
    let N = v[0];
    let M = v[1];
    let S: Vec<String> = (0..N).map(|_| read()).collect();
    let T: Vec<String> = (0..M).map(|_| read()).collect();
    (S, T)
}

fn shuffle(a: &Vec<usize>, v: &Vec<String>) -> Vec<String> {
    a.iter().map(|i| v[*i].to_string()).collect::<Vec<String>>()
}

fn join(v: &Vec<String>, ds: Vec<usize>) -> String {
    let mut w = Vec::<String>::new();
    w.push(v[0].to_string());
    for i in 0..ds.len() {
        w.push((0..ds[i]).map(|_| '_').collect::<String>());
        w.push(v[i+1].to_string())
    }
    w.join("")
}

fn f(S: Vec<String>, T: Vec<String>) -> String {
    let total_len = S.iter().map(|s| s.len()).sum::<usize>();
    let res = 16 - total_len;
    let set_T: HashSet<String> = T.iter().map(|t| t.to_string()).collect();
    for a in Permutations::create(S.len()) {
        let v = shuffle(&a, &S);
        for ds in Distribute::create(res, S.len() - 1) {
            let user_name = join(&v, ds);
            if user_name.len() < 3 {
                continue
            }
            if !set_T.contains(&user_name) {
                return user_name
            }
        }
    }
    "-1".to_string()
}

fn main() {
    let (S, T) = read_input();
    println!("{}", f(S, T))
}