結果
| 問題 |
No.2067 ±2^k operations
|
| コンテスト | |
| ユーザー |
 magurofly
|
| 提出日時 | 2022-09-02 22:00:46 |
| 言語 | Rust (1.83.0 + proconio) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 9,335 bytes |
| コンパイル時間 | 15,222 ms |
| コンパイル使用メモリ | 401,200 KB |
| 実行使用メモリ | 6,820 KB |
| 最終ジャッジ日時 | 2024-11-16 03:26:33 |
| 合計ジャッジ時間 | 22,782 ms |
|
ジャッジサーバーID （参考情報） |
judge3 / judge4 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | WA * 1 |
| other | AC * 2 WA * 21 |
ソースコード
fn read_line(stdin: &mut std::io::Stdin) -> String {
let mut str = String::new();
stdin.read_line(&mut str).unwrap();
str
}
/// 例: 桁DP
/// ## 問題文
/// 正整数 L, R, M が与えられます。 L, R は共に 10 進法表現の長さが N の整数です。
/// L, R をそれぞれ M/N 回繰り返したものを L', R' とします。
/// L' 以上 R' 以下の整数の総和を求めてください。
fn main() {
let digits = &[0, 1];
let mut stdin = std::io::stdin();
let t = read_line(&mut stdin).trim().parse::<usize>().unwrap();
for _ in 0 .. t {
let mut n = read_line(&mut stdin).trim().parse::<i64>().unwrap();
let mut ub = vec![];
while n > 0 {
ub.push(n % 2);
n /= 2;
}
ub.reverse();
let automaton = AutomatonDP::digit_lte(digits, &ub);
let ans = automaton.compute::<(i64, i64, i64, i64), _, _, _, _>(ub.len(),
|(x1, z1, o1, d1), (x2, z2, o2, d2)| (x1 + x2, z1 + z2, o1 + o2, d1 + d2),
|| (0, 0, 0, 0),
|&(x, z, o, d), c| if c == 0 { (x, z + o + d, 0, 0) } else { (x + z + o, 0, z, d + o) },
|| (0, 1, 0, 0));
println!("{}", ans.0);
}
}
use std::collections::*;
use std::hash::Hash;
/// オートマトン（DFA）が受理するすべての文字列に対して DP をする
/// - `Q`: 状態の型
/// - `C`: 入力の型
pub struct AutomatonDP<Q, C> {
transition: HashMap<Q, HashMap<C, Q>>,
init: Q,
accept: Vec<Q>,
}
impl<Q, C> AutomatonDP<Q, C>
where
Q: Copy + Eq + Hash,
C: Copy + Eq + Hash
{
/// 初期状態が `init` のオートマトンを作成する
pub fn new(init: Q) -> Self {
Self {
transition: HashMap::new(),
init,
accept: Vec::new(),
}
}
/// 遷移を追加する
/// `from` 状態のとき、 `input` が来ると `to` 状態に遷移する
pub fn add_transition(&mut self, from: Q, input: C, to: Q) {
self.transition.entry(from).or_insert_with(HashMap::new).insert(input, to);
}
/// 遷移を削除する
pub fn remove_transition(&mut self, from: Q, input: C) {
self.transition.entry(from).and_modify(|tr| {
tr.remove(&input);
});
}
/// 受理状態を追加する
pub fn accept(&mut self, state: Q) {
self.accept.push(state);
}
/// 受理状態を削除する
/// O(accept.len())
pub fn reject(&mut self, state: Q) {
let mut prev = 0;
while let Some(index) = (prev .. self.accept.len()).find(|&i| self.accept[i] == state) {
self.accept.swap_remove(index);
prev = index;
}
}
/// 受理状態をクリアする
pub fn reject_all(&mut self) {
self.accept.clear();
}
/// 状態を変換する
pub fn map<R, Map>(&self, map: Map) -> AutomatonDP<R, C>
where
R: Copy + Eq + Hash,
Map: Fn(Q) -> R,
{
let mut transition = HashMap::new();
for (&p, tr) in &self.transition {
let mut tr2 = HashMap::new();
for (&c, &q) in tr {
tr2.insert(c, (map)(q));
}
transition.insert((map)(p), tr2);
}
let accept = self.accept.iter().map(|&q| (map)(q)).collect();
let init = (map)(self.init);
AutomatonDP { transition, accept, init }
}
/// 長さ `n` のすべての文字列に対して DP をする
/// - `op`: 加法
/// - `e`: 加法単位元を返す
/// - `map`: 乗法っぽいやつ
/// - `empty`: 空列に対する結果を返す
///
/// ただし、乗せる値は半環（っぽいやつ）でないといけない
/// つまり:
/// ```
/// assert_eq!((op)(x, (op)(y, z)), (op)((op)(x, y), z));
/// assert_eq!((op)(x, (e)()), x);
/// assert_eq!((op)((e)(), x), x);
/// assert_eq!((op)(x, y), (op)(y, x));
/// assert_eq!((map)(c, (op)(x, y)), (op)((map)(c, x), (map)(c, y)));
/// ```
/// 計算量: O(n (状態数 + 遷移数))
pub fn compute<S, Op, E, Map, Empty>(&self, n: usize, op: Op, e: E, map: Map, empty: Empty) -> S
where
S: Clone + Sized,
Op: Fn(&S, &S) -> S,
E: Fn() -> S,
Map: Fn(&S, C) -> S,
Empty: Fn() -> S,
{
let mut dp = HashMap::new();
dp.insert(self.init, (empty)());
for _ in 0 .. n {
dp = self.dp_forward(&dp, &op, &e, &map);
}
let mut ans = (e)();
for &q in &self.accept {
ans = (op)(&ans, &dp.get(&q).cloned().unwrap_or_else(|| (e)()));
}
ans
}
pub fn dp_forward<S, Op, E, Map>(&self, dp: &HashMap<Q, S>, op: &Op, e: &E, map: &Map) -> HashMap<Q, S>
where
S: Clone + Sized,
Op: Fn(&S, &S) -> S,
E: Fn() -> S,
Map: Fn(&S, C) -> S,
{
let mut dp2 = HashMap::new();
for (&from, value) in dp {
for (&input, &to) in &self.transition[&from] {
let x = dp2.entry(to).or_insert_with(|| (e)());
let y = (op)(&x, &(map)(value, input));
*x = y;
}
}
dp2
}
/// 論理積をとる
pub fn intersection<R>(&self, other: &AutomatonDP<R, C>) -> AutomatonDP<(Q, R), C>
where
R: Copy + Eq + Hash
{
let mut transition = HashMap::new();
for (&p1, tr1) in &self.transition {
for (&c, &q1) in tr1 {
for (&p2, tr2) in &other.transition {
if let Some(&q2) = tr2.get(&c) {
transition.entry((p1, p2)).or_insert_with(HashMap::new).insert(c, (q1, q2));
}
}
}
}
let mut accept = Vec::new();
for &q1 in &self.accept {
for &q2 in &other.accept {
accept.push((q1, q2));
}
}
AutomatonDP {
init: (self.init, other.init),
transition,
accept,
}
}
}
#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
pub enum DigitDPState {
BothBounded(usize),
LowerBounded(usize),
UpperBounded(usize),
Unbounded(usize),
}
impl<C> AutomatonDP<DigitDPState, C>
where
C: Copy + Eq + Hash
{
/// 辞書順で upper_bound 以下の数列を受理するオートマトンを作成
/// 頂点数 O(upper_bound.len())
/// 辺数 O(upper_bound.len() * digits.len())
pub fn digit_lte(digits: &[C], upper_bound: &[C]) -> Self {
use DigitDPState::*;
let n = upper_bound.len();
let mut automaton = AutomatonDP::new(UpperBounded(0));
automaton.accept(UpperBounded(n));
automaton.accept(Unbounded(n));
for i in 0 ..= n {
let r = upper_bound[i % n];
for &c in digits {
automaton.add_transition(Unbounded(i), c, Unbounded(i % n + 1));
}
for &c in digits {
if c == r {
automaton.add_transition(UpperBounded(i), c, UpperBounded(i % n + 1));
break;
}
automaton.add_transition(UpperBounded(i), c, Unbounded(i % n + 1));
}
}
automaton
}
/// 辞書順で lower_bound 以上の数列を受理するオートマトンを作成
/// 頂点数 O(lower_bound.len())
/// 辺数 O(lower_bound.len() * digits.len())
pub fn digit_gte(digits: &[C], lower_bound: &[C]) -> Self {
use DigitDPState::*;
let n = lower_bound.len();
let mut automaton = AutomatonDP::new(LowerBounded(0));
automaton.accept(LowerBounded(n));
automaton.accept(Unbounded(n));
for i in 0 ..= n {
let l = lower_bound[i % n];
for &c in digits {
automaton.add_transition(Unbounded(i), c, Unbounded(i % n + 1));
}
for &c in digits.into_iter().rev() {
if c == l {
automaton.add_transition(LowerBounded(i), c, LowerBounded(i % n + 1));
break;
}
automaton.add_transition(LowerBounded(i), c, Unbounded(i % n + 1));
}
}
automaton
}
/// 辞書順で lower_bound 以上 upper_bound 以下の数列を受理するオートマトンを作成
pub fn digit_between(digits: &[C], lower_bound: &[C], upper_bound: &[C]) -> Self {
use DigitDPState::*;
assert_eq!(upper_bound.len(), lower_bound.len());
let n = lower_bound.len();
let s = digits.len();
let mut automaton = AutomatonDP::new(BothBounded(0));
automaton.accept(BothBounded(n));
automaton.accept(LowerBounded(n));
automaton.accept(UpperBounded(n));
automaton.accept(Unbounded(n));
for i in 0 ..= n {
let (l, r) = (lower_bound[i % n], upper_bound[i % n]);
for &c in digits {
automaton.add_transition(Unbounded(i), c, Unbounded(i % n + 1));
}
for &c in digits.into_iter().rev() {
if c == l {
automaton.add_transition(LowerBounded(i), c, LowerBounded(i % n + 1));
break;
}
automaton.add_transition(LowerBounded(i), c, Unbounded(i % n + 1));
}
for &c in digits {
if c == r {
automaton.add_transition(UpperBounded(i), c, UpperBounded(i % n + 1));
break;
}
automaton.add_transition(UpperBounded(i), c, Unbounded(i % n + 1));
}
let lower = (0 .. s).find(|&j| digits[j] == l).unwrap();
let upper = (0 .. s).find(|&j| digits[j] == r).unwrap();
if lower == upper {
automaton.add_transition(BothBounded(i), digits[lower], BothBounded(i % n + 1));
} else if lower < upper {
automaton.add_transition(BothBounded(i), digits[lower], LowerBounded(i % n + 1));
automaton.add_transition(BothBounded(i), digits[upper], UpperBounded(i % n + 1));
for &c in &digits[lower + 1 .. upper] {
automaton.add_transition(BothBounded(i), c, Unbounded(i % n + 1));
}
}
}
automaton
}
}