競技プログラミング精進記録
FFABC 126 A - Changing a Character
問題
考察
ASCIIからなる大文字を小文字に変換する場合char::to_lowercase()より，char::to_ascii_lowercase()を使った方が，charをダイ レクトに変換できる．
to_lowercase()のほうは出力が独自の構造体なのでいちいちStringに交換しないといけなくめんどくさい．
またproconioには1-originのusizeを入力として受け取って0-originに変換したものを変数に代入するUsize1というenumがある．少 しコード量がへる．
解答
#![allow(unused_imports)]
use proconio::{input, fastout, marker::*};
use std::cmp::*;
#[fastout]
fn main() {
input!(_n: usize, k: Usize1, s: Chars);
println!("{}",
s
.iter()
.enumerate()
.map(|(i, &c)| if i == k { c.to_ascii_lowercase() } else { c })
.collect::<String>()
);
}
ABC 143 E - Travel by Car
問題
考察
まずは全点対間での最短経路をワーシャルフロイド法で構築する．
その後，全ての点のペアのうち経路が
そのグラフに対してもう一度ワーシャルフロイド法を使えば始点終点間での燃料補給回数が各クエリ
解答
#![allow(unused_imports)]
use proconio::{input, fastout};
use std::cmp::*;
use warshall_floyd::*;
#[fastout]
fn main() {
input!(n: usize, m: usize, l: i64);
let mut g = WarshallFloyd::new(n);
for _ in 0..m {
input!(a: usize, b: usize, c: i64);
g.add_edge_undirected(a-1, b-1, c);
}
g.build_graph();
let mut h = WarshallFloyd::new(n);
for i in 0..n-1 {
for j in i+1..n {
if g[i][j] <= l {
h.add_edge_undirected(i, j, 1);
}
}
}
h.build_graph();
input!(q: usize);
for _ in 0..q {
input!(mut c: usize, mut d: usize);
c -= 1; d -= 1;
println!("{}", if h[c][d] > 100000 { -1 } else { h[c][d] - 1 });
}
}
使用自作ライブラリ
FFABC 164 E - Two Currencies
問題
通行のための銀貨は金貨と交換することで発行できる．それぞれの町ごとに為替が決まっており
金貨が尽きることはないとし，はじめに銀貨を
考察
制約を見ると町の数と通行に必要な銀貨がそれぞれ
すなわち，銀貨は高々
銀貨の制約がなければ通常のダイクストラなどの方法で最短経路が分かるが今回の場合は通行に必要な銀貨を予め通行前に持っておく必要がある．
そこで，ダイクストラ法では頂点
このような，頂点遷移の際に状態として「現在の頂点」以外を考慮して行うダイクストラ法は「拡張ダイクストラ法」などと呼ばれる．(ダイクストラ法自体が拡張されているわけではない)
解答
#![allow(unused_imports)]
use proconio::{input, fastout};
use std::cmp::*;
use std::collections::BinaryHeap;
#[derive(Debug, Clone)]
struct Vertex { index: usize, sliver: i64, time: i64 }
#[derive(Debug, Clone)]
struct Edge { to: usize, time: i64, cost: i64 }
#[fastout]
fn main() {
//! 銀貨をs'枚持ってる時の頂点を動的に生やせば
//! ダイクストラ法が使える
//!
//! (銀貨はN*max(A) (高々2500)で足りる)
input!(n: usize, m: usize, mut s: i64);
let mut times = vec![vec![1<<60; 2501]; n];
chmin!(s, 2500);
let mut graph = vec![vec![]; n];
for _ in 0..m {
input!(u: usize, v: usize, a: i64, b: i64);
let u = u - 1;
let v = v - 1;
graph[u].push(Edge { to: v, time: b, cost: a });
graph[v].push(Edge { to: u, time: b, cost: a });
}
let mut vertices = Vec::with_capacity(n);
for i in 0..n {
input!(c: i64, d: i64);
vertices.push(Vertex { index: i, sliver: c, time: d });
}
let mut heap = BinaryHeap::<Reverse<(i64, usize, i64)>>::new();
heap.push(Reverse((0, 0, s))); // time, index, silver
times[0][s as usize] = 0;
while !heap.is_empty() {
let Reverse((time, index, silver)) = heap.pop().unwrap();
if time > times[index][silver as usize] { continue; }
// 銀を取得
if silver + vertices[index].sliver <= 2500 {
let n_silver = vertices[index].sliver + silver;
let n_time = vertices[index].time + time;
if chmin!(times[index][n_silver as usize], n_time) {
heap.push(Reverse((n_time, index, n_silver)));
}
}
// 辺を辿る
for edge in graph[index].iter() {
if silver < edge.cost { continue; }
let u = edge.to;
let n_silver = silver - edge.cost;
let n_time = time + edge.time;
if chmin!(times[u][n_silver as usize], n_time) {
heap.push(Reverse((n_time, u, n_silver)));
}
}
}
for v in 1..n {
println!("{}", times[v].iter().min().unwrap());
}
}
#[macro_export]
macro_rules! min {
($a: expr) => { $a };
($a: expr, $b: expr) => { std::cmp::min($a, $b) };
($a: expr, $($rest: expr),+) => { std::cmp::min($a, min!($($rest),+)) };
}
#[macro_export]
macro_rules! chmin {
($a: expr, $($rest: expr),+) => {{
let cmp_min = min!($($rest),+);
if $a > cmp_min { $a = cmp_min; true } else { false }
}};
}
ABC 164 D - Multiple of 2019
問題
考察
右側から累積和をとる．すると区間
よって，
解答
#![allow(unused_imports)]
use proconio::{input, fastout, marker::Chars};
use std::cmp::*;
#[fastout]
fn main() {
input!(mut s: Chars);
s.reverse();
let mut v = 0;
let mut b = 1;
let mut ctr = vec![0; 2019];
ctr[0] = 1;
let mut ans = 0;
for c in s.iter() {
v += c.to_digit(10).unwrap() as i64 * b;
v %= 2019;
ans += ctr[v as usize];
ctr[v as usize] += 1;
b *= 10;
b %= 2019;
}
println!("{}", ans);
}
ABC 187 D - Choose Me
問題
ある町
高橋氏がある町で演説を行うと青木派，高橋派の両方が高橋派に投票するが，演説をしなかった町では青木派は青木氏に投票し，高橋派は誰にも投票を行わない．
高橋派の得票数が青木派を上回るには最小でいくつの町で演説を行えばよいか．
考察
ある町で演説をすると，高橋派は
だが，
しかし，実は最初に2番目の町で演説を行えば
このような二属性を上手く扱う方法としては，差を考察すると良い．
青木派と高橋派の得票数の差はある町で演説を行えば
よってこの差が大きい順に演説を行い，差が0を下回ればそこで高橋派の得票数が青木派を上回ることになる．
解答
#![allow(unused_imports)]
use proconio::{input, fastout};
use std::cmp::*;
#[fastout]
fn main() {
input!(n: usize, mut ab: [(i64, i64); n]);
ab.sort_by_key(|(a, b)| 2 * a + b);
ab.reverse();
let mut diff = ab.iter().fold(0, |acc, (a, _)| acc + a);
for i in 0..n {
diff -= ab[i].0 * 2 + ab[i].1;
if diff < 0 {
println!("{}", i+1);
return
}
}
}
ABC 189 C - Mandarin Orange
問題
ヒストグラム中の最大矩形の面積を求めよ．
考察1
二乗解法でも間に合うけど色々考察できそう．蟻本にも全く同じのあった．
左端
解法1
#![allow(unused_imports)]
use proconio::{input, fastout};
use std::cmp::*;
#[fastout]
fn main() {
input!(n: usize, mut a: [usize; n]);
let mut ans = 0;
for l in 0..n {
let mut h = a[l];
for r in l..n {
chmin!(h, a[r]);
chmax!(ans, h * (r - l + 1));
}
}
println!("{}", ans);
}
考察2
ある区間
その区間の最小値を取る指数
再帰が深くなりそうで怖いが
区間の最小値の取得はセグメント木でもSparse Tableでもいいが
解答2
#![allow(unused_imports)]
use proconio::{input, fastout};
use std::cmp::*;
use sparse_table::*;
fn dfs(l: usize, r: usize, mut st: &mut SparseTable<usize>) -> usize {
if l > r {
return 0;
}
let i = st.query(l, r);
let h = st.data[i];
let mut a = h * (r + 1 - l);
if i > 0 {
a = max(a, dfs(l, i-1, &mut st));
}
a = max(a, dfs(i+1, r, &mut st));
a
}
#[fastout]
fn main() {
input!(n: usize, mut a: [usize; n]);
let mut st = SparseTable::new(&a, OperationType::Min);
println!("{}", dfs(0, n-1, &mut st));
}
使用自作ライブラリ
考察3
蟻本に載っている解法．
を参照するとわかりやすいかも．
(自分ではあまり理解できてない)
FFABC 146 E - Rem of Sum is Num ⭐
むずい......
問題
正の整数
長さ
考察
部分列の個数と聞かれたら取り敢えず累積和を取ってみる．
すると
-
(S_i-i)\%K (i, j) - 部分列の長さ(
j-i+1 K-1
部分列の個数を求めればよい
二乗の解法では間に合わないので
解答
#![allow(unused_imports)]
use proconio::{input, fastout};
use std::cmp::*;
use std::collections::*;
#[fastout]
fn main() {
input!(n: usize, k: usize, mut a: [i64; n]);
let mut s = vec![0];
for ai in a.iter() { s.push(s.last().unwrap() + ai); }
for i in 0..s.len() { s[i] -= i as i64; s[i] %= k as i64; }
let mut ans = 0;
let mut map: HashMap<i64, i64> = HashMap::new();
for j in 0..n+1 {
if j >= k {
*map.get_mut(&s[j-k]).unwrap() -= 1;
}
ans += map.get(&s[j]).unwrap_or(&0);
*map.entry(s[j]).or_insert(0) += 1;
}
println!("{}", ans);
}
ABC170 E - Smart Infants ⭐
問題
AtCoderに参戦している幼児が
幼稚園児は転園を
それぞれの転園の後の，AtCoderに参加している幼稚園のうちの最高レートを持つ幼稚園児の集合のうち最小値を出力しなさい．
考察
Setを使ってデータを管理すると高速化が見込める．ただC++の場合ではSetは二分木の実装(BTreeSet)なのでfirst()を使うと最小値が得られることを利用して高速処理するが，あいにくRustのBTreeSet.first()はnightly限定の機能らしい．(std::collections::BTreeSet - Rust )
仕方ないので妥協してbset.iter().rev().next().unwarp()とする必要がある．
速度的にはそこまで違いはないようだ．
#![feature(test)]
#![feature(map_first_last)]
extern crate test;
use once_cell::sync::Lazy;
use rand::{distributions::Uniform, Rng};
static RANDOM_VEC: Lazy<Vec<u32>> = Lazy::new(|| {
let range = Uniform::from(0..=1_000_000_000);
rand::thread_rng().sample_iter(&range).take(10_000_000).collect::<Vec<u32>>()
});
#[cfg(test)]
mod tests {
use super::*;
use std::collections::*;
use test::Bencher;
#[bench]
fn bench_1(b: &mut Bencher) {
let mut bts = BTreeSet::new();
RANDOM_VEC.iter().for_each(|&v| { bts.insert(v); });
b.iter(|| {
let v = bts.iter().rev().next().unwrap();
println!("{}", v);
})
}
#[bench]
fn bench_2(b: &mut Bencher) {
let mut bts = BTreeSet::new();
RANDOM_VEC.iter().for_each(|&v| { bts.insert(v); });
b.iter(|| {
let v = bts.last().unwrap();
println!("{}", v);
})
}
}
結果
> cargo bench [master]
..(中略)
test tests::bench_1 ... bench: 87 ns/iter (+/- 1)
test tests::bench_2 ... bench: 79 ns/iter (+/- 4)
test result: ok. 0 passed; 0 failed; 5 ignored; 2 measured; 0 filtered out; finished in 13.62s
このようにして高速に最大値を出せることが分かったので後は以下に基づいて構築する．
- 園ごとの園児を二分木セットで格納したgardens
- 園ごとの最強園児のレートを格納したセグ木highests
うえの性質から高速で園児が去った後の最強園児のレートを求めることができる．
解答
#![allow(unused_imports, dead_code)]
use proconio::{input, fastout};
use std::cmp::*;
use std::collections::*;
const MAX: usize = 200_000;
struct SegTree<T>
where
T: Copy,
{
size: usize,
seg: Vec<T>,
f: fn(&T, &T) -> T,
id: T,
}
impl<T> SegTree<T>
where
T: Copy,
{
fn new(n: usize, f: fn(&T, &T) -> T, id: T) -> SegTree<T> {
let mut size = 1;
while n > size {
size <<= 1;
}
let seg = vec![id; 2 * size];
Self { size, seg, f, id }
}
fn set(&mut self, k: usize, v: T) {
self.seg[k + self.size] = v;
}
fn get(&self, k: usize) -> T {
self.seg[k + self.size]
}
fn build(&mut self) {
for k in (1..self.size).rev() {
self.seg[k] = (self.f)(&self.seg[2 * k + 0], &self.seg[2 * k + 1]);
}
}
fn update(&mut self, k: usize, v: T) {
let mut k = k + self.size;
self.seg[k] = v;
while k > 1 {
self.seg[k >> 1] = (self.f)(&self.seg[k], &self.seg[k ^ 1]);
k >>= 1;
}
}
fn query(&self, i: usize, j: usize) -> T {
let mut s = self.id;
let mut l = i + self.size;
let mut r = j + self.size;
while l < r {
if (l & 1) > 0 {
s = (self.f)(&s, &self.seg[l]);
l += 1;
}
if (r & 1) > 0 {
s = (self.f)(&s, &self.seg[r - 1]);
}
l >>= 1;
r >>= 1;
}
s
}
}
#[fastout]
fn main() {
input!(n: usize, q: usize);
let mut a = Vec::new();
let mut b = Vec::new();
let mut gardens = vec![BTreeSet::<(u64, usize)>::new(); MAX];
let mut highests = SegTree::<u64>::new(
MAX, |&a, &b| min(a, b), std::u64::MAX
);
for i in 0..n {
input!(ai: u64, bi: usize);
a.push(ai);
b.push(bi-1);
gardens[bi-1].insert((ai, i));
highests.update(bi-1, gardens[bi-1].iter().rev().next().unwrap().0);
}
for _ in 0..q {
input!(ci: usize, di: usize);
let ci = ci - 1;
let to = di - 1;
// 出る方
let from = b[ci];
gardens[from].remove(&(a[ci], ci));
let v = {
if gardens[from].is_empty() {
std::u64::MAX
} else {
gardens[from].iter().rev().next().unwrap().0
}
};
highests.update(from, v);
// 入る方
b[ci] = to;
gardens[to].insert((a[ci], ci));
highests.update(to, gardens[to].iter().rev().next().unwrap().0);
println!("{}", highests.query(0, MAX+1));
}
}
ABC186 E - Throne
あまり，あまり慣れてない．
問題
はじめ，玉座から時計回りに-1を出力せよ．
方針
このような
-
拡張ユークリッドの互除法を使う方法
-
中国剰余定理を使う方法
がある． -
中国剰余定理の場合
座れない場合，中国剰余定理の実装上で(0, 0)を返すようにすれば中国剰余定理に座れるかどうかの判定を任せることができる．
- 拡張ユークリッドの互除法の場合
ここで一般の
まず
(
互いに素でない場合は
その際解が存在するためには
したがってこの問題は
解答1(中国剰余定理)
#![allow(unused_imports)]
use proconio::{input, fastout};
use std::cmp::*;
pub fn extgcd(a: i64, b: i64) -> (i64, i64, i64) {
if b > 0 {
let (d, mut y, x) = extgcd(b, a % b);
y -= (a / b) * x;
(d, x, y)
} else {
(a, 1, 0)
}
}
pub fn crt(ns: &[i64], ms: &[i64]) -> (i64, i64) {
assert_eq!(ns.len(), ms.len());
let (mut r, mut m) = (0, 1);
for i in 0..ns.len() {
let (d, p, _q) = extgcd(m, ms[i]);
match (ns[i] - r) % d {
0 => {
let t = (ns[i] - r) / d * p % (ms[i] / d);
r += m * t;
m *= ms[i] / d;
}
_ => return (0, 0),
}
}
((r % m + m) % m, m)
}
#[fastout]
fn main() {
input!(t: usize);
for _ in 0..t {
input!(n: i64, s: i64, k: i64);
match crt(&[0, n - s], &[k, n]) {
(0, 0) => println!("-1"),
(r, _) => println!("{}", r / k),
}
}
}
解答2(拡張ユークリッドの互除法)
#![allow(unused_imports, dead_code)]
use proconio::{input, fastout};
use std::cmp::*;
pub fn gcd(a: i64, b: i64) -> i64 {
match (a, b) {
(a, 0) => a,
(a, b) => gcd(b, a % b),
}
}
pub fn extgcd(a: i64, b: i64) -> (i64, i64, i64) {
if b > 0 {
let (d, mut y, x) = extgcd(b, a % b);
y -= (a / b) * x;
(d, x, y)
} else {
(a, 1, 0)
}
}
pub mod modulo {
use super::extgcd;
use std::cell::RefCell;
type Num = i64;
thread_local ! (static MOD : RefCell < Num > = RefCell :: new (0 ) );
pub fn set_mod(m: Num) {
MOD.with(|x| x.replace(m));
}
pub fn modulo() -> Num {
MOD.with(|x| *x.borrow())
}
pub fn signed_mod(a: Num) -> Num {
let m = modulo();
(a % m + m) % m
}
/// Modulo and `a` must be coprime integers.
pub fn invmod(a: Num) -> Num {
let m = modulo();
let (_d, x, _y) = extgcd(a, m);
signed_mod(x)
}
/// Modulo must be a prime number.
pub struct Comb {
n: usize,
fac: Vec<Num>,
inv: Vec<Num>,
ifac: Vec<Num>,
}
impl Comb {
pub fn new(n: usize) -> Self {
let mut fac = vec![0; n];
let mut inv = vec![0; n];
let mut ifac = vec![0; n];
fac[0] = 1;
fac[1] = 1;
ifac[0] = 1;
ifac[1] = 1;
inv[1] = 1;
let m = modulo();
for i in 2..n {
let iu = i as i64;
fac[i] = fac[i - 1] * iu % m;
inv[i] = m - inv[m as usize % i] * (m / iu) % m;
ifac[i] = ifac[i - 1] * inv[i] % m;
}
Self { n, fac, inv, ifac }
}
pub fn comb(&self, n: usize, r: usize) -> Num {
let m = modulo();
if n < r {
0
} else {
self.fac[n] * (self.ifac[r] * self.ifac[n - r] % m) % m
}
}
}
}
#[fastout]
fn main() {
use modulo::*;
input!(t: usize);
for _ in 0..t {
input!(n: i64, s: i64, k: i64);
let d = gcd(k, n);
let ans = match s % d {
0 => {
let (n, s, k) = (n / d, s / d, k / d);
set_mod(n);
(n - s) * invmod(k) % n
},
_ => -1
};
println!("{}", ans);
}
}
ABC179 D - Leaping Tak
問題
1マス目から
-
S
考察
分からなかった．愚直なDPだとTLEとなるので上手く式変形する必要があるようだ．
と変形できることから，dpの累積和をsdpとすればある区間
するとこの更新式は
となる．
解答
modintの実装はkenkooooさんの実装.(Gist)
use proconio::input;
#[allow(unused_imports)]
use std::cmp::*;
pub mod modint {
// 中略
}
fn main() {
use modint::*;
input!(n: usize, k: usize, v: [(usize, usize); k]);
set_modint(998_244_353u64);
let mut dp: Vec<ModInt> = vec![ModInt::new(0u64); n];
let mut sdp: Vec<ModInt> = vec![ModInt::new(0u64); n + 1];
dp[0] = ModInt::new(1u64);
sdp[0] = ModInt::new(1u64);
for i in 0..n {
for (l, r) in &v {
let a = { if i > *r { i - r } else { 0 } };
let b = { if i + 1 > *l { i - l + 1 } else { 0 } };
dp[i] += sdp[b] - sdp[a];
}
sdp[i+1] = sdp[i] + dp[i];
}
println!("{}", dp[n-1].value());
}
別解法
どうやら区間が一般の
-
S v x^v f
を考えると， - 2回の操作で
N - 1 f^2 x^{N-1} - 3回の操作で
N - 1 f^3 x^{N-1} - ...
となるので，これらを全て足し合わせるので -
1+f+f^2+f^3+\cdots = \frac{1}{1-f} x^{N -1}
が求めたい値となる．
求めたい場合には形式的冪級数を使用する．
往々にして形式的冪級数を全部実装するとくそ長くなる．
また，高速化ができていないので今回の場合900ms掛かっている．かなしい．
use proconio::input;
#[allow(unused_imports)]
use std::cmp::*;
type Mod = ntt::ModInt::<ntt::Mod998244353>;
fn main() {
input!(n: usize, k: usize);
let mut v = vec![Mod::new(0); n+1];
for _ in 0..k {
input!(l: usize, r: usize);
for i in l..=r { v[i] += 1; }
}
let f = fps::FPS::new(v);
let ans = (-f + Mod::new(1)).inv();
if ans.0.len() >= n {
println!("{}", ans.values()[n-1]);
} else {
println!("{}", 0);
}
}
全容はこちら
FFABC176 D - Wizard in Maze
問題
- 上下左右の隣接マスへの移動:
0 - 上記以外の近隣の
5\times 5 1
方針
01-BFSというものを知らなかった．
ここが丁寧で分かりやすかった．
ゼロコストで移動できるところを双方向キューの先頭に，コスト１で移動できるところを双方向キューの末尾に入れることで効率的に探索できる．
解答
use proconio::input;
use proconio::marker::Chars;
use std::collections::VecDeque;
fn main() {
input!(
h: i64, w: i64,
ch: usize, cw: usize,
dh: usize, dw: usize,
s: [Chars; h]
);
let mut cost = vec![vec![1u64<<60; w as usize]; h as usize];
let mut dq = VecDeque::<(i64, i64)>::new();
dq.push_front(((ch-1) as i64, (cw-1) as i64));
cost[ch-1][cw-1] = 0;
loop {
match dq.pop_front() {
Some((y, x)) => {
for j in -2..=2 {
for i in -2..=2 {
if (i, j) == (0, 0) { continue; }
if y + j < 0 || x + i < 0 { continue; }
if y + j >= h || x + i >= w { continue; }
let ny: usize = (y + j) as usize;
let nx: usize = (x + i) as usize;
if s[ny][nx] == '#' { continue; }
let c = cost[y as usize][x as usize];
let dist = j.abs() + i.abs();
match dist {
1 => {
if cost[ny][nx] > c {
cost[ny][nx] = c;
dq.push_front((ny as i64, nx as i64));
}
},
_ => {
if cost[ny][nx] > c + 1 {
cost[ny][nx] = c + 1;
dq.push_back((ny as i64, nx as i64));
}
}
}
}
}
},
None => break
}
}
let ans = cost[dh-1][dw-1];
if ans == 1u64<<60 {
println!("-1");
} else {
println!("{}", ans);
}
}
ABC 162 E - Sum of gcd of Tuples (Hard)
問題
考察
まず全探索は無理なので，組み合わせからGCDを求めるのではなくGCDが定まった時にそれを満たす数列の個数を求めるという方向に発想を転換する．
ここで例えば
これを一般化して考えるとGCDがちょうど
GCDが「
効率的に構築していくためには
計算量はfor二重で怪しく見えちゃうかもだが逆数なので
解答
#![allow(unused_imports)]
use proconio::{input, fastout};
use std::cmp::*;
#[fastout]
fn main() {
const MOD: u64 = 1_000_000_007;
input!(n: u64, k: usize);
let mut ctr = vec![0i64; k+1];
for g in (1..=k).rev() {
// GCDがgの倍数になるような個数aは
// 要素すべてがgの倍数であればよいので
// Floor(k / g) ^ N で求まる
ctr[g] = powmod((k / g) as u64, n, MOD) as i64;
// 重複しているものを除く
// GCDがgとなるものは
// aから,2*gの倍数となるもの,3*gの倍数となるもの...を引いていけばよい
// 配列を降順で求めていけば再利用できる
for i in 2.. {
if g * i > k { break; }
ctr[g] -= ctr[g*i];
ctr[g] += MOD as i64;
ctr[g] %= MOD as i64;
}
}
println!("{}", ctr.iter().enumerate().fold(0, |acc, (i, &x)| (acc + x * i as i64) % MOD as i64));
}
使用自作ライブラリ
FFABC 161 F - Division or Substraction
問題
正整数
-
N \equiv 0 (\mathrm{mod}~~K) N N / K -
N \not\equiv 0 (\mathrm{mod}~~K) N N - K
考察
-
K=2 13\rightarrow11\rightarrow9\rightarrow7\rightarrow5\rightarrow3\rightarrow1 -
K=3 13\rightarrow10\rightarrow7\rightarrow4\rightarrow1 -
K=4 13\rightarrow9\rightarrow5\rightarrow1 -
K=5 13\rightarrow8\rightarrow3 -
K=6 13\rightarrow7\rightarrow1 -
K=7 13\rightarrow6 -
K=8 13\rightarrow5 -
K=9 13\rightarrow4 -
K=10 13\rightarrow3 -
K=11 13\rightarrow2 -
K=12 13\rightarrow1 -
K=13 13\rightarrow1
まず，
次に
解答
#![allow(unused_imports)]
use proconio::{input, fastout};
use std::cmp::*;
pub fn divisor(n: u64) -> Vec<u64> {
let mut ret = Vec::new();
for i in 1.. {
if i * i > n { break }
if n % i == 0 {
ret.push(i);
if i * i != n { ret.push(n / i); }
}
}
ret.sort_unstable();
ret
}
#[fastout]
fn main() {
//! kがnの約数でない場合
//! n \equiv 1 (mod k)であればよいので
//! n-1の1以外の約数であれば題意を満たす
//!
//! kがnの約数である場合
//! nは高々10^12なので約数を全部列挙し
//! それぞれについて愚直に割っていき
//! 割り切れなくなった値n'について
//! n' % k == 1であれば結果に加える
input!(n: u64);
let div1 = divisor(n-1);
let div2 = divisor(n);
let mut ans = div1.len() - 1;
for d in div2.iter() {
if *d == 1 { continue; }
let mut x = n;
while x % d == 0 { x /= d; }
if x % d == 1 { ans += 1; }
}
println!("{}", ans);
}
ABC 153 F - Silver Fox vs Monster
問題
直線上の座標
ギンギツネちゃんはある座標
敵を全員倒す際に必要な爆弾の個数の最小値を求めよ．
考察
数直線の負の方向を「左」，正の方向を「右」と呼ぶことにする．
この手の問題ではまず，爆発を無駄にさせない方法を考察する必要がある．昇順にモンスターを退治していくとしたとき，爆風の左端ぎりぎりにモンスターを置いたほうがより右に爆風が届く．そうかんがえると
- 左端のモンスターの体力が0になるまで攻撃
- 爆風は
X_{left}+2D - 次に倒すモンスターを見つける
という操作を繰り返していけばよい．
愚直に実装した場合区間更新が
ここは遅延セグメント木やいもす法で高速化が可能．
また，右端のモンスターのインデックスを見つける方法は尺取り法でも二分探索でも間に合う．
いもす法を使う場合には，累積和テーブルを構築すると同時に処理を行っていくという方針がとれる．
解答
#![allow(unused_imports)]
use proconio::{input, fastout};
use std::cmp::*;
use lazy_segtree::*;
#[fastout]
fn main() {
input!(n: usize, d: usize, a: i64);
input!(mut enemies: [(usize, i64); n]);
enemies.sort_by_key(|e| e.0);
let x = enemies.iter().map(|e| e.0).collect::<Vec<_>>();
let mut h = enemies.iter().map(|e| e.1).collect::<Vec<_>>();
// 左端から爆破させていく
// 昇順に敵を並べ届く敵の右端のindexを尺取り法で取得
// HPを減らすには遅延セグメント木を使う
for _ in 0..10 { h.push(0); }
let mut seg = LazySegTree::new(
h.clone(),
|&a, &b| a + b,
|&a, &b| a + b,
|&a, &b| a + b,
0, 0
);
let mut ans = 0;
let mut right = 0;
for left in 0..n {
let cur = seg.query(left, left+1);
if cur <= 0 { continue; }
// 最も右の攻撃対象を求める
while right + 1 < n && x[right + 1] - x[left] <= 2 * d { right += 1; }
// 一番左の敵を倒すのに必要な攻撃回数
let need = (cur + a - 1) / a;
seg.update(left, right + 1, -need*a);
ans += need;
}
println!("{}", ans);
}
使用自作ライブラリ
FFABC 165 C - Many Requirements
問題
正整数
長さ
-
A_{b_i}-A_{a_i}=c_i d_i
とする．数列の得点の最大値を求めよ．
考察
重複組み合わせの列挙にDFSを用いる場合，新たに追加する要素は数列の最後の要素以上
解答
#![allow(unused_imports)]
use proconio::{input, fastout};
use std::cmp::*;
#[macro_export]
macro_rules! max {
($a: expr) => { $a };
($a: expr, $b: expr) => { std::cmp::max($a, $b) };
($a: expr, $($rest: expr), +) => { std::cmp::max($a, max!($($rest),+)) };
}
#[macro_export]
macro_rules! chmax {
($a: expr, $($rest: expr),+) => {{
let cmp_max = max!($($rest),+);
if $a < cmp_max { $a = cmp_max; true } else { false }
}};
}
fn dfs(n: usize, m: i64, req: &[(usize, usize, i64, i64)], mut a: &mut Vec<i64>, mut ans: &mut i64) {
if a.len() == n {
let mut p = 0;
for r in req.iter() {
if a[r.1-1] - a[r.0-1] == r.2 {
p += r.3;
}
}
chmax!(*ans, p);
}
else {
for i in a.last().copied().unwrap_or(1)..=m {
a.push(i);
dfs(n, m, req, &mut a, &mut ans);
a.pop();
}
}
}
#[fastout]
fn main() {
input!(n: usize, m: i64, q: usize, req: [(usize, usize, i64, i64); q]);
let mut a = vec![];
let mut ans = 0;
dfs(n, m, &req, &mut a, &mut ans);
println!("{}", ans);
}
追記
Pythonのitertoolsにはcombinations_with_replacement という重複組み合わせを全列挙する関数がある．Rustにも組み合わせ論的な関数がいくつかあれば嬉しいのでRustのitertoolsが使用出来ない環境下でも使用可能なiter系の関数を実装した．
-
accumulate累積した配列を作りたいとき(scan使って書いてもいいが毎回忘れるので) -
bit_brutebit全探索したいとき -
combinations組み合わせを全列挙したいとき -
combinations_with_replace重複組み合わせを全列挙したいとき
pub trait Accumulate: Iterator {
fn accumulate<T>(self, v0: T, f: fn(&T, &Self::Item) -> T) -> AccumulateItertor<Self, T>
where Self: Sized
{
AccumulateItertor { sum: v0, func: f, iter: self }
}
}
impl<I: ?Sized> Accumulate for I where I: Iterator {}
pub struct AccumulateItertor<I: Iterator, T> {
sum: T,
func: fn(&T, &I::Item) -> T,
iter: I,
}
impl<I, T> Iterator for AccumulateItertor<I, T>
where
I: Iterator,
T: Clone
{
type Item = T;
fn next(&mut self) -> Option<Self::Item> {
self.iter.next().map(|v| {
let v = (self.func)(&self.sum, &v);
self.sum = v.clone();
v
})
}
}
pub trait BitBruteForce: Iterator {
fn bit_brute(self) -> BitBruteForceIterator<Self>
where Self: Sized
{
BitBruteForceIterator { vec: self.collect(), mask: 0 }
}
}
impl<I: ?Sized> BitBruteForce for I where I: Iterator {}
pub struct BitBruteForceIterator<I: Iterator> {
vec: Vec<I::Item>,
mask: usize,
}
impl<I> Iterator for BitBruteForceIterator<I>
where
I: Iterator,
I::Item: Clone + Copy + Sized
{
type Item = Vec::<I::Item>;
fn next(&mut self) -> Option<Self::Item> {
let n = self.vec.len();
if self.mask < (1 << n) {
let bit_n = self.mask.count_ones() as usize;
let mut v = Vec::with_capacity(bit_n);
for i in 0..n {
if self.mask >> i & 1 == 1 {
v.push(self.vec[i])
}
}
self.mask += 1;
Some(v)
} else {
None
}
}
}
pub trait Combinations: Iterator {
fn combinations(self, r: usize) -> CombinationsIterator<Self> where Self: Sized {
let indices = (0..r).collect();
CombinationsIterator { vec: self.collect(), indices, r, first: true }
}
fn combinations_with_replacement(self, r: usize) -> CombinationsWithReplacementIterator<Self> where Self: Sized {
let indices = vec![0; r];
CombinationsWithReplacementIterator { vec: self.collect(), indices, r, first: true }
}
}
impl<I: ?Sized> Combinations for I where I: Iterator {}
pub struct CombinationsIterator<I: Iterator> {
vec: Vec<I::Item>,
indices: Vec<usize>,
r: usize,
first: bool
}
pub struct CombinationsWithReplacementIterator<I: Iterator> {
vec: Vec<I::Item>,
indices: Vec<usize>,
r: usize,
first: bool
}
impl<I> Iterator for CombinationsIterator<I>
where
I: Iterator,
I::Item: Sized + Copy
{
type Item = Vec<I::Item>;
fn next(&mut self) -> Option<Self::Item> {
let n = self.vec.len();
let r = self.r;
if n < r { return None }
if self.first {
self.first = false;
} else {
let mut i = r - 1;
while self.indices[i] == i + n - r {
if i > 0 { i -= 1; } else { return None }
}
self.indices[i] += 1;
for j in i+1..r {
self.indices[j] = self.indices[j - 1] + 1;
}
}
Some(self.indices.iter().map(|&i| self.vec[i]).collect())
}
}
impl<I> Iterator for CombinationsWithReplacementIterator<I>
where
I: Iterator,
I::Item: Sized + Copy
{
type Item = Vec<I::Item>;
fn next(&mut self) -> Option<Self::Item> {
let n = self.vec.len();
let r = self.r;
if self.first {
self.first = false;
} else {
let mut i = r - 1;
while self.indices[i] == n - 1 {
if i > 0 { i -= 1; } else { return None }
}
let v = self.indices[i];
for j in i..r {
self.indices[j] = v + 1;
}
}
Some(self.indices.iter().map(|&i| self.vec[i]).collect())
}
}
使い方は以下のテストコードを見ればなんとなくわかると思う(なげやり)
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn test_accumulate() {
let v = vec![1, 2, 3, 4, 5];
let c = v.iter().accumulate(0, |&a, &b| a + b).collect::<Vec<_>>();
assert_eq!(c, vec![1, 3, 6, 10, 15]);
let c = v.iter().accumulate(1, |&a, &b| a * b).collect::<Vec<_>>();
assert_eq!(c, vec![1, 2, 6, 24, 120]);
}
#[test]
fn test_bitbrute() {
let v = vec![2u32, 4, 6];
let ans: Vec<Vec<&u32>> = vec![vec![], vec![&2], vec![&4], vec![&2, &4], vec![&6], vec![&2, &6], vec![&4, &6], vec![&2, &4, &6]];
for (i, comb) in v.iter().bit_brute().enumerate() {
assert_eq!(ans[i], comb);
}
}
#[test]
fn test_bitbrute2() {
let v = vec![1u32, 40, 1099, 1034, 5];
let a = 1105;
let mut f = false;
for comb in v.iter().bit_brute() {
let sum: u32 = comb.iter().copied().sum();
if a == sum {
f = true;
assert_eq!(comb, vec![&1u32, &1099, &5]);
}
}
assert!(f);
}
#[test]
fn test_combination() {
let v = vec![1, 2, 3];
let a = vec![vec![&1, &2], vec![&1, &3], vec![&2, &3]];
for (i, comb) in v.iter().combinations(2).enumerate() {
assert_eq!(a[i], comb)
}
}
#[test]
fn test_combination_with_replace() {
let v = vec![1, 2, 3];
let a = vec![vec![&1, &1], vec![&1, &2], vec![&1, &3], vec![&2, &2], vec![&2, &3], vec![&3, &3]];
for (i, comb) in v.iter().combinations_with_replacement(2).enumerate() {
assert_eq!(a[i], comb)
}
}
}
これを使えば今回の例では以下のように書ける．使いどころ少ないけど意外と便利かも(自賛)
#![allow(unused_macros)]
use proconio::{input, fastout};
#[macro_export]
macro_rules! max {
($a: expr) => { $a };
($a: expr, $b: expr) => { std::cmp::max($a, $b) };
($a: expr, $($rest: expr), +) => { std::cmp::max($a, max!($($rest),+)) };
}
#[macro_export]
macro_rules! chmax {
($a: expr, $($rest: expr),+) => {{
let cmp_max = max!($($rest),+);
if $a < cmp_max { $a = cmp_max; true } else { false }
}};
}
#[fastout]
fn main() {
input!(n: usize, m: usize, q: usize);
input!(f: [(usize, usize, usize, usize); q]);
let mut ans = 0;
for a in (1..=m).combinations_with_replacement(n) {
let mut p = 0;
for i in 0..q {
if a[f[i].1-1] - a[f[i].0-1] == f[i].2 { p += f[i].3 }
}
chmax!(ans, p);
}
println!("{}", ans);
}