AtCoderBeginnerContestXXX 問題 点 「」

問題リンク

問題概要

制約

  • $2 \le N \le 10^5$
  • $1 \le X,\ Y \le 10^9$
  • $1 \le P_i \le 8$
  • $1 \le T_i \le 10^9$
  • $1 \le Q \le 2 \times 10^5$
  • $1 \le q_i \le 10^9$
  • 入力はすべて整数

解法

バスに乗る時刻によって，各バス停での待機時間が変わり，N 番目のバス停に到着する時刻が変化することが予想される。ここで，各バス停から$P_i$分ごとの周期でバスが発車することと，その周期は高々$1 \le P_i \le 8$であることに注目する。

バス停 $i,\ i+1$ での待ち時間はのパターンは$|P_i - P_{i+1} |$個で，これが各バス停で考えられることから，1 番目のバス停から N 番目のバス停までにかかる時間のパターンは$8! = 840$通りしかない。出発時刻 $\%$ 840 で割った値が該当する時刻なので，これに前後の徒歩時間を足すことで$\mathcal{O}(1)$で計算することができる。（ちょっと微妙。よくわかってないかも）

お気持ち

AC コード

この回答例では最初の歩行時間 + バスに乗っている時間で 840 通り作った後にクエリに答えている

#![allow(non_snake_case)]
#![allow(unused_imports)]
#![allow(unused_macros)]
#![allow(clippy::needless_range_loop)]
#![allow(clippy::comparison_chain)]
#![allow(clippy::nonminimal_bool)]
#![allow(clippy::neg_multiply)]
use std::collections::{BTreeSet, BinaryHeap, HashMap, HashSet, VecDeque};
use std::f64::consts::PI;
use std::hash::Hash;
use std::mem::swap;
use std::ops::Index;
use std::ops::Mul;

use itertools::{CombinationsWithReplacement, Itertools};
use libm::{ceil, log};
use num::{integer::Roots, traits::Pow, ToPrimitive};
use num_integer::{div_ceil, Integer};
use num_traits::{abs_sub, AsPrimitive, Float};
use permutohedron::Heap;
use proconio::input;
use proconio::marker::{Chars, Usize1};
use std::convert::From;
use std::io::*;

fn solve() {
    #[rustfmt::skip]
    input! {
        N : usize, X:usize, Y:usize,
        PT:[(usize,usize); N-1],
        Q:usize
    }
    let mut V = vec![];
    for i in 0..840 {
        let mut tmp = i;
        for &(p, t) in PT.iter() {
            tmp = div_ceil(tmp, p) * p;
            tmp += t;
        }
        V.push(tmp + Y);
    }
    let mut ans = vec![];
    for _ in 0..Q {
        input! {q:usize}
        let s = q + X;
        let v = V[s % 840] + s - s % 840;
        ans.push(v);
    }
    println!("{}", ans.iter().join("\n"));
}

fn main() {
    // input! {N:usize}
    // for _ in 0..N {
    //     solve();
    // }
    solve();
}