#969564 (Rust) No.2715 Unique Chimatagram

• 問題: No.2715 Unique Chimatagram
• ユーザー: atcoder8
• 提出日時: 2024-04-05 21:43:31
• 言語: Rust (1.77.0 + proconio)
• 結果: TLE
• 実行時間: -
• コード長: 1,356 bytes
• コンパイル時間: 14,259 ms
• コンパイル使用メモリ: 400,076 KB
• 実行使用メモリ: 6,940 KB
• 最終ジャッジ日時: 2024-10-01 01:58:09
• 合計ジャッジ時間: 17,686 ms
• ジャッジサーバーID （参考情報）: judge3 / judge4

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	1 ms; 5,248 KB
testcase_01	AC	1 ms; 5,248 KB
testcase_02	AC	0 ms; 5,248 KB
testcase_03	AC	0 ms; 5,248 KB
testcase_04	AC	1 ms; 5,248 KB
testcase_05	AC	1 ms; 5,248 KB
testcase_06	AC	1 ms; 5,248 KB
testcase_07	AC	1 ms; 5,248 KB
testcase_08	AC	1 ms; 5,248 KB
testcase_09	AC	1 ms; 5,248 KB
testcase_10	AC	1 ms; 5,248 KB
testcase_11	AC	1 ms; 5,248 KB
testcase_12	AC	1 ms; 5,248 KB
testcase_13	AC	1 ms; 5,248 KB
testcase_14	AC	1 ms; 5,248 KB
testcase_15	AC	1 ms; 5,248 KB
testcase_16	AC	1 ms; 5,248 KB
testcase_17	AC	2 ms; 5,248 KB
testcase_18	AC	1 ms; 5,248 KB
testcase_19	AC	1 ms; 5,248 KB
testcase_20	AC	2 ms; 5,248 KB
testcase_21	AC	1 ms; 5,248 KB
testcase_22	AC	1 ms; 5,248 KB
testcase_23	AC	1 ms; 5,248 KB
testcase_24	AC	1 ms; 5,248 KB
testcase_25	AC	1 ms; 5,248 KB
testcase_26	AC	1 ms; 5,248 KB
testcase_27	AC	1 ms; 5,248 KB
testcase_28	AC	42 ms; 5,248 KB
testcase_29	AC	11 ms; 5,248 KB
testcase_30	AC	26 ms; 5,248 KB
testcase_31	AC	4 ms; 5,248 KB
testcase_32	AC	102 ms; 5,248 KB
testcase_33	AC	1 ms; 5,248 KB
testcase_34	AC	1 ms; 5,248 KB
testcase_35	AC	1 ms; 5,248 KB
testcase_36	AC	1 ms; 5,248 KB
testcase_37	AC	0 ms; 5,248 KB
testcase_38	AC	2 ms; 5,248 KB
testcase_39	AC	1,130 ms; 5,248 KB
testcase_40	AC	68 ms; 5,248 KB
testcase_41	AC	249 ms; 5,248 KB
testcase_42	TLE	-

ソースコード

fn main() {
    match solve() {
        Some(ans) => println!("{}", ans),
        None => println!("-1"),
    }
}

fn solve() -> Option<String> {
    let n = {
        let mut line = String::new();
        std::io::stdin().read_line(&mut line).unwrap();
        line.trim().parse::<usize>().unwrap()
    };
    let ss: Vec<Vec<char>> = (0..n)
        .map(|_| {
            let mut line = String::new();
            std::io::stdin().read_line(&mut line).unwrap();
            line.trim().chars().collect()
        })
        .collect();

    for s in &ss {
        for c in 'a'..='z' {
            let mut t = s.clone();
            t.push(c);

            if ss.iter().filter(|s| is_match(&s, &t)).count() == 1 {
                return Some(t.iter().collect());
            }
        }
    }

    None
}

fn is_match(s: &[char], t: &[char]) -> bool {
    if s.len() + 1 != t.len() {
        return false;
    }

    let mut counts1 = vec![0; 26];
    for &c1 in s {
        counts1[char_to_number(c1)] += 1;
    }

    let mut counts2 = vec![0; 26];
    for &c2 in t {
        counts2[char_to_number(c2)] += 1;
    }

    counts1
        .iter()
        .zip(&counts2)
        .all(|(cnt1, cnt2)| cnt1 <= cnt2)
}

/// Converts the character `c` to the corresponding numeric value.
pub fn char_to_number(c: char) -> usize {
    (c as u8 - b'a') as usize
}