ABC268のD問題をRustで解きました

# はじめに

[ABC268](https://atcoder.jp/contests/abc268)は弊社が主催したプログラミングコンテストです。

せっかくなのでコンテスト中に解くことができたD問題を振り返りついでに記事にしてみました。

# 問題

[D問題](https://atcoder.jp/contests/abc268/tasks/abc268_d)

水色Diffの問題で、D問題としては難しめです。

単語とアンダーバーを組み合わせた文字列で、指定された文字列と重複しない文字列を見つける問題です。

# 方針を考える

## （A） 単語の順番について
単語数$N$についての制約が$N\leq8$と小さいので、順列全探索でよさそうです。

## (B) 単語間を埋めるアンダーバーの個数について
$N$単語の隙間は$N-1$箇所あり、最大文字数が16の制約から、使えるアンダーバーの個数は$16-\sum|S_i|$です。このパターンの個数は$\displaystyle_{16-\sum|S_i|+N-1}C_{N-1}$です。
$16-\sum|S_i|+N-1\leq15$であることを考えると、パターンを列挙することはできそうです。

$X$の探索として上記の順列全探索と組み合わせると間に合いませんが、$M$種類の文字列に重複しない$X$が出てきたら打ち切ってよくて、探索回数を高々$M+1$回にできるので問題なさそうです。

## (C) 文字列の重複判定について
重複してはいけない文字列の個数$M$についての制約は$M\leq10^5$なので、上記の探索それぞれについて$M$通り全て調べると間に合わなさそうです。重複判定は完全一致なので、$M$個の文字列を`HashSet`に入れることで重複判定を$O(\log M)$でできるようにすればよさそうです。

# 実装する

まず以下のようにして入力をもらいます。先に出力するところも作っておきます。

```rust
use proconio::input;

fn main() {
    input!{
        n: usize,
        m: usize,
        s: [String; n],
        t: [String; m]
    }

    let mut result = None;

    // TODO: 条件を満たす文字列があればresultに入れる

    match result {
        Some(x) => {
            println!("{}", x);
        }
        None => {
            println!("-1");
        }
    }
}
```

## （A） 単語の順番を全探索する

[itertools](https://docs.rs/itertools/latest/itertools/)というcrateが便利です。

```diff
use proconio::input;
+ use itertools::Itertools;

fn main() {
    input!{
        n: usize,
        m: usize,
        s: [String; n],
        t: [String; m]
    }

    let mut result = None;
 
-   // TODO: 条件を満たす文字列があればresultに入れる
+   // (A) 単語の順序を全探索する
+   for shuffled_s in s.iter().permutations(n) {
+       // TODO
+   }

    match result {
        Some(x) => {
            println!("{}", x);
        }
        None => {
            println!("-1");
        }
    }
}
```

## (B) アンダーバーの埋め方を列挙する

再帰関数で実装します。引数で隙間の個数`len`と使用できるアンダーバーの個数`underbar_count`を受け取り、"それぞれの隙間に使うアンダーバーの個数のベクタ"を列挙したベクタを返します。

* `len = 1`のとき
  隙間が1箇所なので、そこに`underbar_count`まで使うことができます。
* `len > 1`のとき
  * `len`番目に`i`文字使うとすると、`len-1`番目までで`underbar_count-i`文字まで使うことができます。それぞれの隙間に少なくとも1文字使わないといけないので、`len-1 <= underbar_count-i`を満たす範囲で探索します。

```diff
use proconio::input;
use itertools::Itertools;

fn main() {
    input!{
        n: usize,
        m: usize,
        s: [String; n],
        t: [String; m]
    }

    let mut result = None;
 
+   // (B) アンダーバーの個数の組み合わせパターンを列挙する
+   let max_underbar_count = 16 - (0..n).map(|i| s[i].len()).sum::<usize>();
+   let underbar_patterns = get_underbar_patterns(n-1, max_underbar_count);
 
    // (A) 単語の順序を全探索する
    for shuffled_s in s.iter().permutations(n) {
        // TODO
    }

    match result {
        Some(x) => {
            println!("{}", x);
        }
        None => {
            println!("-1");
        }
    }
}
 
+ // (B) アンダーバーの個数の組み合わせパターンを列挙する
+ fn get_underbar_patterns(len: usize, underbar_count: usize) -> Vec<Vec<usize>> + {
+     let mut result = vec![];
+     if len == 1 {
+         for i in 1..=underbar_count {
+             result.push(vec![i]);
+         }
+         return result;
+     }
+
+     for i in 1..=underbar_count-len+1  {
+         for mut v in get_underbar_patterns(len-1, underbar_count-i) {
+             v.push(i);
+             result.push(v);
+         }
+     }
+
+     result
+ }
```

これで文字列の順序、アンダーバーの個数を列挙することができたので、文字列$X$を構築できます。

（Rustの文字列操作に慣れていないので、もっといい方法があれば教えていただきたいです。）

```diff
use proconio::input;
use itertools::Itertools;

fn main() {
    input!{
        n: usize,
        m: usize,
        s: [String; n],
        t: [String; m]
    }

    let mut result = None;
 
    // (B) アンダーバーの個数の組み合わせパターンを列挙する
    let max_underbar_count = 16 - (0..n).map(|i| s[i].len()).sum::<usize>();
    let underbar_patterns = get_underbar_patterns(n-1, max_underbar_count);
 
    // TODO: 条件を満たす文字列があればresultに入れる
    // (A) 単語の順序を全探索する
    for shuffled_s in s.iter().permutations(n) {
-       // TODO
+       for underbar_pattern in &underbar_patterns {
+           let mut x = shuffled_s[0].clone();
+           for i in 1..n {
+               for _j in 0..underbar_pattern[i-1] {
+                   x += "_";
+               }
+               x += shuffled_s[i];
+           }
+
+           // TODO: tとの重複判定、resultへの代入
+       }
    }

    match result {
        Some(x) => {
            println!("{}", x);
        }
        None => {
            println!("-1");
        }
    }
}
 
// (B) アンダーバーの個数の組み合わせパターンを列挙する
fn get_underbar_patterns(len: usize, underbar_count: usize) -> Vec<Vec<usize>> {
    let mut result = vec![];
    if len == 1 {
        for i in 1..=underbar_count {
            result.push(vec![i]);
        }
        return result;
    }
 
    for i in 1..=underbar_count-len+1  {
        for mut v in get_underbar_patterns(len-1, underbar_count-i) {
            v.push(i);
            result.push(v);
        }
    }
 
    result
}
```

## (C) 重複判定をする

`t`を`HashSet`にした`t_set`をつくります。

`t_set`にない文字列であれば`result`に入れてループを打ち切ります。

```diff
use proconio::input;
use itertools::Itertools;
+ use std::collections::HashSet;

fn main() {
    input!{
        n: usize,
        m: usize,
        s: [String; n],
        t: [String; m]
    }

    let mut result = None;
 
+   // (C): tの要素でHashSetをつくる
+   let t_set: HashSet<String> = t.into_iter().collect();
 
    // (B) アンダーバーの個数の組み合わせパターンを列挙する
    let max_underbar_count = 16 - (0..n).map(|i| s[i].len()).sum::<usize>();
    let underbar_patterns = get_underbar_patterns(n-1, max_underbar_count);
 
    // (A) 単語の順序を全探索する
-    for shuffled_s in s.iter().permutations(n) {
+    'search: for shuffled_s in s.iter().permutations(n) {
        for underbar_pattern in &underbar_patterns {
            let mut x = shuffled_s[0].clone();
            for i in 1..n {
                for _j in 0..underbar_pattern[i-1] {
                    x += "_";
                }
                x += shuffled_s[i];
            }
 
-           // TODO: tとの重複判定、resultへの代入
+           // (C) tになければresultにいれる
+           if !t_set.contains(&x) {
+               result = Some(x);
+               break 'search;
+           }
        }
    }

    match result {
        Some(x) => {
            println!("{}", x);
        }
        None => {
            println!("-1");
        }
    }
}
 
// (B) アンダーバーの個数の組み合わせパターンを列挙する
fn get_underbar_patterns(len: usize, underbar_count: usize) -> Vec<Vec<usize>> {
    let mut result = vec![];
    if len == 1 {
        for i in 1..=underbar_count {
            result.push(vec![i]);
        }
        return result;
    }
 
    for i in 1..=underbar_count-len+1  {
        for mut v in get_underbar_patterns(len-1, underbar_count-i) {
            v.push(i);
            result.push(v);
        }
    }
 
    result
}
```

# エッジケースに対処する

上記のコードで入力例を試してみると、入力例1で早速panicしてしまいます。

$N=1$のときはアンダーバーを入れる隙間がないので、これに対応しないといけません。

このときは`s[0]`の文字列しか作れないので、これが条件を満たすかどうかを判定して出力する処理を追加します。

そういえば今まで$X$の文字数を気にしていませんでしたが、$N>1$のときは文字列、アンダーバー、文字列で3文字以上あることは保証されています。

```diff
use proconio::input;
use itertools::Itertools;
use std::collections::HashSet;

fn main() {
    input!{
        n: usize,
        m: usize,
        s: [String; n],
        t: [String; m]
    }

    let mut result = None;
 
    // (C): tの要素でHashSetをつくる
    let t_set: HashSet<String> = t.into_iter().collect();
 
+   // (エッジケース) n=1のときはアンダーバーとの探索ができないのでここで対応する
+   if n == 1 {
+       if !t_set.contains(&s[0]) && 3 <= s[0].len() {
+           println!("{}", s[0]);
+       } else {
+           println!("-1");
+       }
+       return;
+   }
 
    // (B) アンダーバーの個数の組み合わせパターンを列挙する
    let max_underbar_count = 16 - (0..n).map(|i| s[i].len()).sum::<usize>();
    let underbar_patterns = get_underbar_patterns(n-1, max_underbar_count);
 
    // (A) 単語の順序を全探索する
     'search: for shuffled_s in s.iter().permutations(n) {
        for underbar_pattern in &underbar_patterns {
            let mut x = shuffled_s[0].clone();
            for i in 1..n {
                for _j in 0..underbar_pattern[i-1] {
                    x += "_";
                }
                x += shuffled_s[i];
            }
 
            // (C) tになければresultにいれる
            if !t_set.contains(&x) {
                result = Some(x);
                break 'search;
            }
        }
    }

    match result {
        Some(x) => {
            println!("{}", x);
        }
        None => {
            println!("-1");
        }
    }
}
 
// (B) アンダーバーの個数の組み合わせパターンを列挙する
fn get_underbar_patterns(len: usize, underbar_count: usize) -> Vec<Vec<usize>> {
    let mut result = vec![];
    if len == 1 {
        for i in 1..=underbar_count {
            result.push(vec![i]);
        }
        return result;
    }
 
    for i in 1..=underbar_count-len+1  {
        for mut v in get_underbar_patterns(len-1, underbar_count-i) {
            v.push(i);
            result.push(v);
        }
    }
 
    result
}
```

# 提出する

これでACできます。お疲れ様でした。

[実際の提出](https://atcoder.jp/contests/abc268/submissions/34771849)