#1166248 (Rust) No.3554 Rurumaru Function Problem 2

• 問題: No.3554 Rurumaru Function Problem 2
• ユーザー: akakimidori
• 提出日時: 2026-05-22 23:45:27
• 言語: Rust (1.94.0 + proconio + num + itertools)
• 結果: AC
• 実行時間: 2 ms / 2,000 ms
• コード長: 4,105 bytes
• コンパイル時間: 18,548 ms
• コンパイル使用メモリ: 199,456 KB
• 実行使用メモリ: 6,400 KB
• 最終ジャッジ日時: 2026-05-22 23:46:06
• 合計ジャッジ時間: 7,039 ms
• ジャッジサーバーID （参考情報）: judge2_1 / judge3_1

ファイルパターン	結果
sample	AC * 3
other	AC * 12

コンパイルメッセージ

warning: unused import: `std::io::Write`
 --> src/main.rs:6:5
  |
6 | use std::io::Write;
  |     ^^^^^^^^^^^^^^
  |
  = note: `#[warn(unused_imports)]` (part of `#[warn(unused)]`) on by default

warning: type alias `Set` is never used
 --> src/main.rs:9:6
  |
9 | type Set<T> = BTreeSet<T>;
  |      ^^^
  |
  = note: `#[warn(dead_code)]` (part of `#[warn(unused)]`) on by default

warning: type alias `Deque` is never used
  --> src/main.rs:10:6
   |
10 | type Deque<T> = VecDeque<T>;
   |      ^^^^^

warning: function `test` is never used
  --> src/main.rs:71:4
   |
71 | fn test() {
   |    ^^^^

ソースコード

// 実験するとgの値は強い性質ありそう
// 切り替わるnはようわからん
// 単調っぽいから毎度二分探索すればいい？

use std::collections::*;
use std::io::Write;

type Map<K, V> = BTreeMap<K, V>;
type Set<T> = BTreeSet<T>;
type Deque<T> = VecDeque<T>;

fn main() {
    input!(n: usize);
    let mut v = 0;
    let mut a = vec![];
    while v < n {
        a.push(v);
        v = 4 * v + 2;
    }
    let calc = |n: usize, v: usize| -> u64 {
        let mut dp = Map::new();
        dp.insert((false, false), 1u64);
        for i in 0..30 {
            let n = n >> i & 1;
            let v = v >> i & 1;
            let mut ndp = Map::new();
            for (less, w) in dp.iter() {
                for x in 0..2 {
                    for y in 0..2 {
                        let z = if i % 2 == 0 { x & y } else { x | y };
                        if z != v {
                            continue;
                        }
                        let a = x < n || (x == n && less.0);
                        let b = y < n || (y == n && less.1);
                        *ndp.entry((a, b)).or_insert(0) += w;
                    }
                }
            }
            dp = ndp;
        }
        dp.get(&(true, true)).cloned().unwrap_or(0)
    };
    let mut part = vec![0];
    for a in a.windows(2) {
        let (x, y) = (a[0], a[1]);
        let mut ng = y;
        let mut ok = 2 * y;
        while ok - ng > 1 {
            let mid = (ok + ng) / 2;
            if calc(mid, y) > calc(mid, x) {
                ok = mid;
            } else {
                ng = mid;
            }
        }
        part.push(ok);
    }
    part.push(n + 1);
    let mut ans = 0;
    for (a, part) in a.iter().zip(part.windows(2)) {
        if part[0] >= part[1].min(n + 1) {
            continue;
        }
        let c = part[1].min(n + 1) - part[0];
        ans += c * *a;
    }
    println!("{}", ans);
}

fn test() {
    let and = (0..30).step_by(2).fold(0, |s, a| s | (1 << a));
    let or = (1..30).step_by(2).fold(0, |s, a| s | (1 << a));
    let mut map = Map::new();
    let mut pre = 1;
    for n in 1..100000 {
        for x in 0..n {
            let y = n - 1;
            let f = (x & y & and) | ((x | y) & or);
            *map.entry(f).or_insert(0) += if x == y { 1 } else { 2 };
        }
        let c = *map.values().max().unwrap();
        let g = map
            .iter()
            .filter(|(_, v)| **v == c)
            .map(|(k, _)| *k)
            .next()
            .unwrap();
        if pre != g {
            println!("{n}: {g} {g:b} {n:b}");
        }
        pre = g;
    }
}

// ---------- begin input macro ----------
// reference: https://qiita.com/tanakh/items/0ba42c7ca36cd29d0ac8
#[macro_export]
macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        input_inner!{iter, $($r)*}
    };
    ($($r:tt)*) => {
        let s = {
            use std::io::Read;
            let mut s = String::new();
            std::io::stdin().read_to_string(&mut s).unwrap();
            s
        };
        let mut iter = s.split_whitespace();
        input_inner!{iter, $($r)*}
    };
}

#[macro_export]
macro_rules! input_inner {
    ($iter:expr) => {};
    ($iter:expr, ) => {};
    ($iter:expr, $var:ident : $t:tt $($r:tt)*) => {
        let $var = read_value!($iter, $t);
        input_inner!{$iter $($r)*}
    };
}

#[macro_export]
macro_rules! read_value {
    ($iter:expr, ( $($t:tt),* )) => {
        ( $(read_value!($iter, $t)),* )
    };
    ($iter:expr, [ $t:tt ; $len:expr ]) => {
        (0..$len).map(|_| read_value!($iter, $t)).collect::<Vec<_>>()
    };
    ($iter:expr, chars) => {
        read_value!($iter, String).chars().collect::<Vec<char>>()
    };
    ($iter:expr, bytes) => {
        read_value!($iter, String).bytes().collect::<Vec<u8>>()
    };
    ($iter:expr, usize1) => {
        read_value!($iter, usize) - 1
    };
    ($iter:expr, $t:ty) => {
        $iter.next().unwrap().parse::<$t>().expect("Parse error")
    };
}
// ---------- end input macro ----------