結果

問題 No.3392 Count 23578 Sequence
コンテスト
ユーザー LyricalMaestro
提出日時 2026-05-25 23:33:47
言語 Rust
(1.94.0 + proconio + num + itertools)
コンパイル:
/usr/bin/rustc_custom
実行:
./target/release/main
結果
AC  
実行時間 673 ms / 2,000 ms
コード長 3,541 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 1,325 ms
コンパイル使用メモリ 207,720 KB
実行使用メモリ 126,044 KB
最終ジャッジ日時 2026-05-25 23:34:24
合計ジャッジ時間 32,891 ms
ジャッジサーバーID
（参考情報） 		judge1_0 / judge3_0
純コード判定待ち
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 48
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

use proconio::input;
use std::collections::BTreeMap;

const H: u128 = 9007199254740997u128;

fn main() {
    input! {
        n: usize,
        a: [i64; n],
    }

    let mut answer: usize = n;

    if n == 1 {
        println!("{}", answer);
        return;
    }

    let m = n - 1;

    let mut diff_a = Vec::with_capacity(m);
    for i in 0..m {
        diff_a.push(a[i + 1] - a[i]);
    }

    // 座標圧縮
    let mut vals = diff_a.clone();
    vals.sort();
    vals.dedup();

    let mut mp = BTreeMap::new();
    for (i, &v) in vals.iter().enumerate() {
        mp.insert(v, i + 1usize);
    }

    let diff_a2: Vec<usize> = diff_a.iter().map(|x| mp[x]).collect();

    let max_a = *diff_a2.iter().max().unwrap();
    let b_base: u128 = (max_a + 1) as u128;

    // forward hash
    let mut forward_hash = vec![0u128; m];
    let mut h = 0u128;
    for i in 0..m {
        h *= b_base;
        h %= H;
        h += diff_a2[i] as u128;
        h %= H;
        forward_hash[i] = h;
    }

    // backward hash
    let mut backward_hash = vec![0u128; m];
    h = 0;
    for i in (0..m).rev() {
        h *= b_base;
        h %= H;
        h += diff_a2[i] as u128;
        h %= H;
        backward_hash[i] = h;
    }

    // pow_b
    let mut pow_b = vec![0u128; n];
    let mut p = 1u128;
    for i in 0..n {
        pow_b[i] = p;
        p *= b_base;
        p %= H;
    }

    let solve = |forward_hash: &Vec<u128>,
                 backward_hash: &Vec<u128>,
                 pow_b: &Vec<u128>,
                 i: usize,
                 l: usize| -> bool {
        let b = (backward_hash[i - l] + H - ((backward_hash[i] * pow_b[l]) % H)) % H;
        let f = (forward_hash[i + l] + H - ((forward_hash[i] * pow_b[l]) % H)) % H;
        b == f
    };

    // 奇数長
    for i in 0..m {
        let left = i;
        let right = m - 1 - i;
        let max_length = left.min(right);

        let mut low = 0usize;
        let mut high = max_length;

        while high > low + 1 {
            let mid = (high + low) / 2;
            if solve(&forward_hash, &backward_hash, &pow_b, i, mid) {
                low = mid;
            } else {
                high = mid;
            }
        }

        if solve(&forward_hash, &backward_hash, &pow_b, i, high) {
            answer += 1 + high;
        } else {
            answer += 1 + low;
        }
    }

    let solve2 = |forward_hash: &Vec<u128>,
                  backward_hash: &Vec<u128>,
                  pow_b: &Vec<u128>,
                  i: usize,
                  l: usize| -> bool {
        let b = (backward_hash[i - l] + H
            - ((backward_hash[i + 1] * pow_b[l + 1]) % H))
            % H;

        let f = (forward_hash[i + 1 + l] + H
            - ((forward_hash[i] * pow_b[l + 1]) % H))
            % H;

        b == f
    };

    // 偶数長
    for i in 0..m - 1 {
        if diff_a2[i] != diff_a2[i + 1] {
            continue;
        }

        let left = i;
        let right = m - 1 - (i + 1);
        let max_length = left.min(right);

        let mut low = 0usize;
        let mut high = max_length;

        while high > low + 1 {
            let mid = (high + low) / 2;
            if solve2(&forward_hash, &backward_hash, &pow_b, i, mid) {
                low = mid;
            } else {
                high = mid;
            }
        }

        if solve2(&forward_hash, &backward_hash, &pow_b, i, high) {
            answer += 1 + high;
        } else {
            answer += 1 + low;
        }
    }

    println!("{}", answer);
}
0