Zenn
Open15

競技プログラミング精進記録

Rust
#
競技プログラミング
FFFF

ABC 126 A - Changing a Character

https://atcoder.jp/contests/abc126/tasks/abc126_a

問題

N文字の大文字からなる文字列SのK番目の文字を小文字にしたものを出力せよ

考察

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>()
     );
 }
FFFF

ABC 143 E - Travel by Car

https://atcoder.jp/contests/abc143/tasks/abc143_e

問題

N頂点M辺の無向グラフがあり，各辺はa_i,b_i間を結びコストはc_iである．このグラフ上で容量Lのタンクを用い て移動する．コストcの辺を移動するとその分燃料が減り辺の途中で0となるような移動はできない．また，各頂点上で燃料を満タンにすることができる．

Q個のクエリが与えられる．それぞれのクエリでは二頂点s,tが与えられる．そのそれぞれに対して最小の燃料補給回数を答えよ．

考察

まずは全点対間での最短経路をワーシャルフロイド法で構築する．
その後，全ての点のペアのうち経路がL以下であるペアにコスト1の辺を貼ったグラフを用意する．
そのグラフに対してもう一度ワーシャルフロイド法を使えば始点終点間での燃料補給回数が各クエリO(1)で求められる．

解答

 #![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 });
     }
 }

使用自作ライブラリ

FFFF

ABC 164 E - Two Currencies

https://atcoder.jp/contests/abc164/tasks/abc164_e

問題

N個の町がありM個の道がありそれぞれの町を結んでいる．i番目の道は町u_i, v_i間を結び，通行にはa_i個の銀貨を消費し，b_iだけの時間を消費する．

通行のための銀貨は金貨と交換することで発行できる．それぞれの町ごとに為替が決まっておりi番目の町では金貨1枚をc_i枚 の銀貨にd_iだけ時間をかけて交換できる．

金貨が尽きることはないとし，はじめに銀貨をS枚持って町1にいるとするとき，町$ 1$から町2,町3,...町Nに至るまでに掛かる最短時間をそれぞれ求めよ．

考察

制約を見ると町の数と通行に必要な銀貨がそれぞれ50が最大である．
すなわち，銀貨は高々2500枚持っておけば全ての町まで到達できる．

銀貨の制約がなければ通常のダイクストラなどの方法で最短経路が分かるが今回の場合は通行に必要な銀貨を予め通行前に持っておく必要がある．
そこで，ダイクストラ法では頂点(v)を状態として探索していたがこの問題の場合は頂点と現在持っている銀貨(v, silver)を状態としてダイクストラ法を行ってみる．最短時間を格納する配列は，頂点と持っている銀貨の2次元で用意しておき，頂点遷移の際に「 銀貨の発行」と「辺の移動(通貨が足りているときのみ)」を行う．

このような，頂点遷移の際に状態として「現在の頂点」以外を考慮して行うダイクストラ法は「拡張ダイクストラ法」などと呼ばれる．(ダイクストラ法自体が拡張されているわけではない)

解答

 #![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 }
     }};
 }
FFFF

ABC 164 D - Multiple of 2019

https://atcoder.jp/contests/abc164/tasks/abc164_d

問題

1から9までの数字からなる文字列の連続する部分文字列のうち2019の倍数であるものが何個あるかを求めよ

考察

右側から累積和をとる．すると区間[i, j]の値はS_j - S_iを10^i分の1した値となる．したがってある区間が2019の倍数であるならばそれを10^i倍した値も2019の倍数である(※10,2019が互いに素であるため成立する)．

よって，S_iとS_jの2019で割った剰余が等しいものを2つ選択する操作を0-2018で行えばよい．実装の際は剰余ごとにカウンターを持っておくなどする．

解答

 #![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);
 }
FFFF

ABC 187 D - Choose Me

https://atcoder.jp/contests/abc187/tasks/abc187_d

問題

ある町iでは青木派がA_i人，高橋派がB_i人いる．
高橋氏がある町で演説を行うと青木派，高橋派の両方が高橋派に投票するが，演説をしなかった町では青木派は青木氏に投票し，高橋派は誰にも投票を行わない．
高橋派の得票数が青木派を上回るには最小でいくつの町で演説を行えばよいか．

考察

ある町で演説をすると，高橋派はA_i+B_i票を得て，青木派はA_i票失う．なので愚直に(A_i + B_i, A_i)で降順ソートすれば良さそうに見える．
だが，(A_i, B_i) = [(0, 10), (7, 2), (4, 5)]を考えてみる．
(A_i + B_i, A_i)で降順ソートするとi=0,1,2の順で演説を行って行けばよくそれぞれの演説後の得票数は(A, T) = (11, 10), (4, 19), (0, 28)となり2つの町で演説を行う必要がある．
しかし，実は最初に2番目の町で演説を行えば(A, T)=(4, 9)となり，1つの町の演説で済む．

このような二属性を上手く扱う方法としては，差を考察すると良い．
青木派と高橋派の得票数の差はある町で演説を行えば2A_i+B_iだけ減る．
よってこの差が大きい順に演説を行い，差が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
         }
     }
 }
FFFF

ABC 189 C - Mandarin Orange

https://atcoder.jp/contests/abc189/tasks/abc189_c

問題

ヒストグラム中の最大矩形の面積を求めよ．

考察1

二乗解法でも間に合うけど色々考察できそう．蟻本にも全く同じのあった．

左端lを固定し，右端rを[l, N]の範囲で増やしていく．

解法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

ある区間[l, r]からできる矩形の面積は(r-l+1)\min_{i\in[l, r]}A_iである．
その区間の最小値を取る指数j=\arg{\min_{i\in[l,r]}} A_iの前後で分割しそれぞれの区間に対して再帰的に矩形の面積を取って いくことでも解くことができる．

再帰が深くなりそうで怖いがN=10^6の自作データでもエラーを起こすことなく60msで実行できた．

区間の最小値の取得はセグメント木でもSparse TableでもいいがO(1)で区間最小を取れるSparse Tableのほうがはやい．(といってもテーブルの構築がボトルネックで結局O(N\log N)なのでまあ好きな方を使えばいいと思うけど)

解答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

蟻本に載っている解法．

https://rustforbeginners.hatenablog.com/entry/largest-rectangle-dpl-3-c
を参照するとわかりやすいかも．
(自分ではあまり理解できてない)

FFFF

ABC 146 E - Rem of Sum is Num ⭐

https://atcoder.jp/contests/abc146/tasks/abc146_e

むずい......

問題

正の整数Kと長さNの整数列A_iが与えられる．
長さNの整数列A_iの空でない連続する部分列のうち，要素の和をKで割った余りが要素の数と等しくなるような部分列の数 を求めよ．

考察

部分列の個数と聞かれたら取り敢えず累積和を取ってみる．S_iをA_iの累積和とし，Sの先頭に0を挿入する．
すると(S_j - S_i) \% K = j - iとなるような組(i,j)~(i<j)の数を求める問題に等しくなる．
(S_j - S_i) \% K = j - iを変形するとS_j - j \equiv S_i - i~~(\mathrm{mod}~K)となる．

Kの剰余は高々K-1なので

  • (S_i-i)\%Kの値が同じ組(i, j)のうち
  • 部分列の長さ(j-i+1)がK-1以下の
    部分列の個数を求めればよい

二乗の解法では間に合わないので(i,j)の範囲内での度数を連想配列などで保持しておき，右端を走査的に探索していく．

解答

 #![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);
 }
FFFF

ABC170 E - Smart Infants ⭐

https://atcoder.jp/contests/abc170/tasks/abc170_e

問題

AtCoderに参戦している幼児がN人おり，1\sim Nの番号が付いている．また，幼稚園は1\sim 2\times10^5校あり，幼稚園児iのレートはA_iでありはじめ，幼稚園B_iに属している．
幼稚園児は転園をQ回繰り返す．j回目の転園ではC_jからD_jの幼稚園に転園する．
それぞれの転園の後の，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));
     }
 }
FFFF

ABC186 E - Throne

https://atcoder.jp/contests/abc186/tasks/abc186_e

あまり，あまり慣れてない．

問題

N個の円上に並べられた椅子があり，うち一つは玉座である．
はじめ，玉座から時計回りにS個隣の椅子に座っている．そこから時計回りにK個先の椅子に座ることを繰り返す．始めて玉座に座ることができるのは何回移動した後になるか．もし永遠に玉座に移動できない場合には-1を出力せよ．

方針

x回の行動後に玉座に座れるならば，S+Kx\equiv 0(\textrm{mod.} N)が成立する．
このようなxを求める方法として

  • 拡張ユークリッドの互除法を使う方法

  • 中国剰余定理を使う方法
    がある．

  • 中国剰余定理の場合

y=Kxとするとy\equiv 0 (\textrm{mod.} K)とy\equiv -S(\textrm{mod.} N)を満たすようなyを求めればxが求まる．

座れない場合，中国剰余定理の実装上で(0, 0)を返すようにすれば中国剰余定理に座れるかどうかの判定を任せることができる．

  • 拡張ユークリッドの互除法の場合

Kx\equiv -S(\textrm{mod.}N)の合同式を解くことができればよい．
ここで一般のax\equiv b(\textrm{mod.}M)の一時合同方程式の解を考える．

まずaとMが互いに素のときはaの逆元を求めるだけで良い．
(x\equiv a^{-1}b(\textrm{mod.}M))

互いに素でない場合はd:= \textrm{gcd}(a, M), a'=a/d, M'=M/dとすれば上記の互いに素の問題に帰着できる．
その際解が存在するためにはbがdの倍数である必要がある．
したがってこの問題はd=\textrm{gcd}(K, N)とおき，Sがdで割り切れない場合には玉座に座ることができず，割り切れる場合にはN, S, Kをdで割り，Kの逆元を求めればよいということになる．

解答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);
     }
 }
FFFF

ABC179 D - Leaping Tak

https://atcoder.jp/contests/abc179/tasks/abc179_d

問題

Nマスからなるマス目と，K個の互いに素集合な区間[l_i, r_i]が与えられる．その区間に属する整数からなる集合をSとする．
1マス目からNマス目まで以下の操作を繰り返し到達できるような操作列の個数を998244353で割った余りを求めよ．

  • Sに含まれる整数から1つ選び，その数分だけマスを進める

考察

分からなかった．愚直なDPだとTLEとなるので上手く式変形する必要があるようだ．
dp[i]をマスiに到達できる操作列の個数とすると，

\displaystyle dp[i] = \sum_{v\in S}dp[i - v]であるが，
\displaystyle dp[i] =\sum_{k=1}^{K}\sum_{j=l_k}^{r_k} dp[i - j]

と変形できることから，dpの累積和をsdpとすればある区間[l,r)の総和はsdp[r] - sdp[l]と表せる．

するとこの更新式は
\displaystyle dp[i] = \sum_{k=1}^{K} \left(sdp[i - l_k + 1] - sdp[i - r]\right)
となる．

解答

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());
 }

別解法

https://drken1215.hatenablog.com/entry/2020/09/20/081800
どうやら区間が一般のSであってもO(N\log N)で解けるようだ

  • Sの元vに対してx^vの係数が1であるような多項式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);
     }
 }

全容はこちら

https://atcoder.jp/contests/abc179/submissions/19386496

FFFF

ABC176 D - Wizard in Maze

https://atcoder.jp/contests/abc176/tasks/abc176_d

問題

H\times Wマスの迷路で，あるマスからとあるマスまで移動するのにかかるコストの最小値を求めよ．ただしコストは以下の要領で計算される

  • 上下左右の隣接マスへの移動: 0
  • 上記以外の近隣の5\times 5マスへの移動: 1

方針

01-BFSというものを知らなかった．
https://betrue12.hateblo.jp/entry/2018/12/08/000020

ここが丁寧で分かりやすかった．

ゼロコストで移動できるところを双方向キューの先頭に，コスト１で移動できるところを双方向キューの末尾に入れることで効率的に探索できる．

解答

 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);
     }
 }
FFFF

ABC 162 E - Sum of gcd of Tuples (Hard)

https://atcoder.jp/contests/abc162/tasks/abc162_e

問題

1以上K以下の整数で構成されるN個の数列A_iは，全体でK^N個あるがそれらすべてに対しての\mathrm{gcd}(A_i)の和を10^9+7で割った余りを求めよ．

考察

まず全探索は無理なので，組み合わせからGCDを求めるのではなくGCDが定まった時にそれを満たす数列の個数を求めるという方向に発想を転換する．

ここで例えばN=2,K=4としたとき，GCDが2となるのは(2, 2), (2, 4), (4, 2)である．GCDが丁度2でないといけないため，(4, 4)は含まれていないことに注意する．

これを一般化して考えるとGCDがちょうどgになるような個数というのはGCDがgの倍数になるものから，「2gの倍数になるもの」,「3gの倍数になるもの」...を引いていけばよいことになる．

GCDが「gの倍数になるもの」の個数はK以下のgの倍数から各要素の数字を選んでいけばよいため\lfloor K/g\rfloor^N個存在する．

効率的に構築していくためにはKから降順で「GCDがgになるもの」のテーブルを構築していけばよく，そうすることで倍数を除 く際に求めた値を再利用することができる．

計算量はfor二重で怪しく見えちゃうかもだが逆数なのでO(K\log K)で済む．

解答

 #![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));
 }

使用自作ライブラリ

FFFF

ABC 161 F - Division or Substraction

https://atcoder.jp/contests/abc161/tasks/abc161_f

問題

正整数Nに対して以下の操作をN>0である間，繰り返した際に最終的にN=1となるようなKの選び方は何通りあるか．

  • N \equiv 0 (\mathrm{mod}~~K)ならばNをN / Kに置換する
  • N \not\equiv 0 (\mathrm{mod}~~K)ならばNをN - Kに置換する

考察

N=13を考える．

  • 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

K=2,3,4,6,12,13が満たすことが分かる．

まず，KがNの約数でないようなとき(つまり引く操作だけ行うような場合)では最終的に1となる数というのはN \equiv 1 (\mathrm{mod}~~K)であるような数，すなわちN-1 \equiv 0 (\mathrm{mod}~~K)であるのでN-1の1以外の約数が題意を満たすこと が分かる

次にKがNの約数であるときはNの1以外の約数全てに対して愚直にシミュレーションを行えばよい．

N-1とNは互いに素なので2つの条件が被ることはないことに注意する．

解答

 #![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);
 }
FFFF

ABC 153 F - Silver Fox vs Monster

https://atcoder.jp/contests/abc153/tasks/abc153_f

問題

直線上の座標X_iに体力がH_iのモンスターがN体いる．
ギンギツネちゃんはある座標xを指定し，[x-D,x+D ]の範囲の敵にAダメージ与えられる爆弾を使うことができる．
敵を全員倒す際に必要な爆弾の個数の最小値を求めよ．

考察

数直線の負の方向を「左」，正の方向を「右」と呼ぶことにする．

この手の問題ではまず，爆発を無駄にさせない方法を考察する必要がある．昇順にモンスターを退治していくとしたとき，爆風の左端ぎりぎりにモンスターを置いたほうがより右に爆風が届く．そうかんがえると

  • 左端のモンスターの体力が0になるまで攻撃
  • 爆風はX_{left}+2Dまで届くためその範囲の敵の体力を減らす
  • 次に倒すモンスターを見つける

という操作を繰り返していけばよい．
愚直に実装した場合区間更新がO(N)の計算量になるため，上手く減らす．
ここは遅延セグメント木やいもす法で高速化が可能．

また，右端のモンスターのインデックスを見つける方法は尺取り法でも二分探索でも間に合う．

いもす法を使う場合には，累積和テーブルを構築すると同時に処理を行っていくという方針がとれる．

https://drken1215.hatenablog.com/entry/2020/01/26/234000

解答

 #![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);
 }

使用自作ライブラリ

FFFF

ABC 165 C - Many Requirements

https://atcoder.jp/contests/abc165/tasks/abc165_c

問題

正整数N,M,Qとクエリa_i, b_i, c_i, d_iがQ個与えられる．

長さNかつ1\leq A_1\leq A_2...\leq A_N\leq Mを満たす数列Aに対して得点を

  • A_{b_i}-A_{a_i}=c_iを満たすd_iの総和

とする．数列の得点の最大値を求めよ．

考察

N,Mの制約が小さいので全部列挙する．数列を列挙するためには重複組み合わせ{}_{M}\mathrm{H}_{N}を全て列挙すればいいの で列挙する関数がかければあとは得点を合計するだけである．

重複組み合わせの列挙にDFSを用いる場合，新たに追加する要素は数列の最後の要素以上M以下のであるので数列の要素がNにな るまで再帰的に呼び出し，要素数がNになれば評価を行う，というように書けば展望が見やすい．

解答

 #![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_brute bit全探索したいとき
  • 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);
 }