2023年買ったデバイス
YAMAHA GAME STREAMING AUDIO MEXER ZG01
スプラにハマっていたので、通話しながら遅延無しでスプラの音を聞くために購入 jp.yamaha.com
UGREEN HDMI 切り替え器
スプラとPCの切り替え用
Anker Eufy (ユーフィ) Smart Scale P2 Pro
痩せようと思って…
Keychron K8 Pro QMK/VIA ワイヤレス・メカニカルキーボード(US配列)
お仕事で持ち歩く用のキーボードが欲しかった
Apple Watch Ultra
スマートウォッチの調子が悪かったのと、 iPhone を使うようになっていたので持って見ようかなと思って買ってみた
Belkin 3 in 1 MagSafe充電器
iPhone と Apple Watch, AirPods 同時に充電したかった。
Belkin 2-in-1 Apple Watch + iPhone 急速充電 モバイルバッテリー
Apple Watch を充電出来るモバブ
Belkin MagSafe対応 ワイヤレス モバイルバッテリー
MagSafe で iPhone にくっつくタイプ。便利。
Stream Deck 512GB
Slay the Spire をベッドの上でやりたかったので
AirPods Pro
交代で使うため、2台目
Mac mini
Apple TV
Mac mini が直接は3台目でしか繋げなかったので。
Elgato エルガト Game Capture HD60 X
HD60? を使っていたけど、 M1系の Mac と互換性がないらしく、新しく購入
iPhone 15 Pro Max 512GB
前使っていた iPhone 11 Pro Max?を引っ張り出して使っていたので、出た瞬間に購入
Insta360 Flow
iPhone の性能上がったから、フル活用してみたいなと思って動画・写真に使ってみようと思って購入
ブラウン シリーズ9 PRO+ 9555cc シェーバー本体 5 in 1
ひげそり
iPad Pro 12.9 inch
弟が僕が使っている iPad Pro を欲しがったので(なんか前僕が「買おうかな~」と言っていたでお下がりが貰えると思っていたらしい)。 大学生にもなるしお古で良いなら僕も買い換えて、iPad あげるか~と購入
AtCoder 言語アップデート クレート個人的感想
2023-08-06 の 新ジャッジテストコンテスト -Algorithm- 以降から AtCoder で使える Rust のバージョンが 1.70.0 になり、以下のクレートが使えるようになりました。 それらを主観で使えそうとか雑にコメントしていく記事です。
ac-library-rs = "0.1.1" once_cell = "1.18.0" static_assertions = "1.1.0" varisat = "0.2.2" memoise = "0.3.2" argio = "0.2.0" bitvec = "1.0.1" counter = "0.5.7" hashbag = "0.1.11" pathfinding = "4.3.0" recur-fn = "2.2.0" indexing = "0.4.1" amplify = "3.14.2" amplify_derive = "2.11.3" amplify_num = "0.4.1" easy-ext = "1.0.1" multimap = "0.9.0" btreemultimap = "0.1.1" bstr = "1.6.0" az = "1.2.1" glidesort = "0.1.2" tap = "1.0.1" omniswap = "0.1.0" multiversion = "0.7.2" num = "0.4.1" num-bigint = "0.4.3" num-complex = "0.4.3" num-integer = "0.1.45" num-iter = "0.1.43" num-rational = "0.4.1" num-traits = "0.2.15" num-derive = "0.4.0" ndarray = "0.15.6" nalgebra = "0.32.3" alga = "0.9.3" libm = "0.2.7" rand = "0.8.5" getrandom = "0.2.10" rand_chacha = "0.3.1" rand_core = "0.6.4" rand_hc = "0.3.2" rand_pcg = "0.3.1" rand_distr = "0.4.3" petgraph = "0.6.3" indexmap = "2.0.0" regex = "1.9.1" lazy_static = "1.4.0" ordered-float = "3.7.0" ascii = "1.1.0" permutohedron = "0.2.4" superslice = "1.0.0" itertools = "0.11.0" itertools-num = "0.1.3" maplit = "1.0.2" either = "1.8.1" im-rc = "15.1.0" fixedbitset = "0.4.2" bitset-fixed = "0.1.0" proconio = "0.4.5" text_io = "0.1.12" rustc-hash = "1.1.0" smallvec = "1.11.0"
ac-library-rs
ACL の Rust版ですね。大体 これ のドキュメントを読めば分かるはず
use ac_library::Dsu; fn main() { Dsu::new(10); }
とかやれば使える
once_cell
1度しか初期化できない型を提供している。
static_assertions
定数や型に関するアサーションを提供している。コンパイル時にチェックされるらしい。
varisat
SAT ソルバー。なんで入ってるんだろう…?(2-SAT とか書くの楽なのかな?)。
この辺 読めば使えそう
use varisat::{ExtendFormula, Lit, Solver, CnfFormula}; fn main() { let mut formula = CnfFormula::new(); let (a, b, c) = (Lit::from_dimacs(1), Lit::from_dimacs(2), Lit::from_dimacs(3)); formula.add_clause(&[a, b, c]); formula.add_clause(&[!a, !b]); formula.add_clause(&[!b, !c]); formula.add_clause(&[!a, !c]); let mut solver = Solver::new(); solver.add_formula(&formula); let result = solver.solve(); assert_eq!(result.unwrap(), true); let model = solver.model().unwrap(); eprintln!("{:?}", model); // [-1, 2, -3] }
もしかしたら文字列で渡すほうが用意しやすいかも?
let dimacs_cnf = b"1 2 3 0\n-1 -2 0\n-2 -3 0\n"; solver.add_dimacs_cnf(&dimacs_cnf[..]).expect("parse error");
memoise
関数をメモ化してくれる
use memoise::memoise; # #[memoise(n <= 100)] fn fib(n: i64) -> i64 { if n == 0 || n == 1 { return n; } fib(n - 1) + fib(n - 2) }
memoise
と書いたら Vec
、 memoise_map
と書いたら BtreeMap
でメモ化してくれるみたい。
ABC314 E をこれで解いてみた(ソースコード)。使い勝手良さそう。
argio
関数の入出力を stdio に変換するマクロらしい。内側では proconio
を使っているから proconio
と同じ感じで書けるらしい。たまに嬉しそう?
#[argio] fn main(n: i32) -> i32 { n * 2 }
bitvec
C++ にもある bitset
みたいに使えるやつっぽい。(これ系いつも使い方わかりません)。
こんな感じで使えるっぽい?
fn main() { let mut bits = bitvec![usize, Msb0; 0; 20]; bits.set(0, true); for c in [1 , 6, 7, 10] { let mut shift = bits.clone(); shift.shift_right(c); bits |= shift; } println!("{:?}", bits); assert_eq!(bits[13], true); }
counter
Python の counter を参考にしているらしい。 most_common とかがあるのは便利かも?
use counter::Counter; fn main() { let v = vec![1, 4, 2, 4, 3, 4, 4]; let counts = v.iter().collect::<Counter<_>>(); eprintln!("{:?}", counts); assert_eq!(counts[&1], 1); }
hashbag
unordered_multiset。contains で数がとれるらしい。
pathfinding
グラフアルゴリズムが入っているらしい。
- A*
- BFS
- Brent
- DFS
- Dijkstra
- Edmonds Karp
- Floyd
- Fringe
- IDA*
- IDDFS
- strongly connected components
- topological sorting
- Yen
- connected components
- Kruskal
- Kuhn-Munkres
recur-fn
ラムダ再帰ができるようになるやっぽい
use recur_fn::{recur_fn, RecurFn}; fn main() { let fib = recur_fn(|fib, n: i32| { if n <= 1 { n } else { fib(n - 1) + fib(n - 2) } }); println!("{}", fib.call(10)); }
indexing
unchecked な indexing ができるらしい。ライブラリ作りには嬉しそう
amplify
マクロとか追加するやつ。
こういうことができるらしい。(BtreeMap の宣言)
#[macro_use] extern crate amplify; let map = bmap! { s!("key") => 5, s!("other_key") => 10 };
easy_ext
extension-trait-conventions をもっと簡単に記述するためのマクロ
multimap
HashMap を使った multimap
btreemultimap
BtreeMap を使った multimap
bstr
バイト文字列のライブラリ。
az
型キャストした時にチェックしてくれたりする。(-1).wrapping_as::<u32>()
とかすると 1u32.wrapping_neg()
が得られる。
glidesort
安定ソート。早いらしい。
tap
tap
とか pipe
とかを間に挟み込める。tap
はデバッグとかに使えて、 pipe
は変換とか挟み込める。
消し忘れそう…。
use tap::Tap; fn main() { let n = 13; let odd_sum = (0..n).filter(|&x| x % 2 == 1) .tap(|x| println!("odd: {:?}", x)) .sum::<usize>(); println!("{}", odd_sum); }
omniswap
参照が重複して std::mem::swap
できないやつも swap できるようにするマクロ。
fn main() { let mut a = vec![vec![1, 2, 3], vec![4, 5, 6]]; // std::mem::swap(&mut a[0][1], &mut a[1][3]); // これはダメ omniswap::swap!(&mut a[0][1], &mut a[1][3]); }
multiversion
CPUによって関数の実装を変えたりできるやつ。
num
整数色々。num-bigint
、 num-complex
、num-integer
とか色々ある。
整数範囲の sqrt
とか便利。
ndarray
行列ライブラリ
nalgebra
行列ライブラリ
alga
代数系トレイト。Monoid とか入ってる
libm
libm の Rust 実装。 f32, f64 の便利関数が色々
rand
乱数関連の色々
getrandom
OS の乱数生成器のインターフェース
petgraph
グラフライブラリ。前のバージョンでも入っていた。
indexmap
なんか色々機能のある HashMap と HashSet
regex
正規表現。前のバージョンでも入っていた。
lazy_static
遅延評価のマクロ。前のバージョンでも入っていた。
ordered-float
Float のラッパー。前のバージョンから入っていたらしい。Float をソートするときに楽できる。
let mut v = [OrderedFloat(NAN), OrderedFloat(2.0), OrderedFloat(1.0)]; v.sort(); assert_eq!(v, [OrderedFloat(1.0), OrderedFloat(2.0), OrderedFloat(NAN)]);
ascii
ASCII文字列・文字を扱うやつ。前のバージョンでも入っていた。
permutohedron
next_permutation
とかを提供している。前のバージョンでも入っていた。
superslice
超便利なやつ。 lower_bound
とかを提供している。前のバージョンでも入っていた。
use superslice::*; let b = [1, 3]; assert_eq!(b.lower_bound(&1), 0); assert_eq!(b.upper_bound(&1), 1); assert_eq!(b.equal_range(&3), 1..2);
itertools
これも超便利。 iter に対して色々できる。前のバージョンでも入っていた。
maplit
HashMap とかがマクロで定義できるやつ。amplify と近いかも
im-rc
永続データ構造が使える。色々なデータ構造が入ってる。
fixedbitset
bitset
bitset-fixed
bitset
proconio
競プロの IO を楽にするやつ。
rustc-hash
高速で非暗号なハッシュ
smallvec
smallvec
AtCoder Beginner Contest 305
AtCoder Beginner Contest 305 です。
A - Water Station
5で割った切り上げ・切り捨てを計算して、5をかけると前後の補給所の場所が分かるので、それのうち近い方を出力する。
fn main() { input! { n: usize, } let a1 = (n + 4) / 5 * 5; let a2 = n / 5 * 5; let f = |a:usize,b:usize| { a.max(b) - a.min(b) }; if f(a1, n) < f(a2, n) { println!("{}", a1); } else { println!("{}", a2); } }
B - ABCDEFG
A,B,C,D,E,F,G の間の距離が分かっているので、与えられている2つのアルファベットの距離を求める問題。 適当にそれぞれの位置を入れておいて引けば良い。
fn main() { input! { p : char, q : char, } let d = vec![0, 3, 4, 8, 9, 14, 23]; let i = (p as u8 - b'A') as usize; let j = (q as u8 - b'A') as usize; println!("{}", d[i.max(j)] - d[i.min(j)]); }
C - Snuke the Cookie Picker
長方形になるようにクッキーが置かれていて、1個なくなっているクッキーの場所を求める問題。$2 \times 2$ 以上なので、最小・最大の座標を求めておけば長方形の4つ端が分かるので、その間でクッキーが置かれていないところが答え。
fn main() { input! { h : usize, w : usize, s : [Chars; h] } let mut minx = 1000; let mut miny = 1000; let mut maxx = 0; let mut maxy = 0; for i in 0..h { for j in 0..w { if s[i][j] == '#' { minx = minx.min(i); miny = miny.min(j); maxx = maxx.max(i); maxy = maxy.max(j); } }} let mut ans = (0,0); for i in minx..=maxx { for j in miny..=maxy { if s[i][j] == '.' { ans = (i,j); } }} println!("{} {}", ans.0+1, ans.1+1) }
提出
D - Sleep Log
累積和で大まかに求めておく。累積和で求められなかったはみ出ている分を後出て足してあげる。
fn main() { input! { n : usize, a : [usize; n], q : usize, queries : [(usize, usize); q] } let mut b = vec![0; n - 1]; for i in 0..n-1 { if i % 2 == 1 { b[i] = a[i+1] - a[i]; } } let mut csum = vec![0; n]; for i in 0..n-1 { csum[i+1] = csum[i] + b[i]; } for (l, r) in queries { let lindex = a.lower_bound(&l); let rindex = a.upper_bound(&r); let mut ans = csum[rindex - 1] - csum[lindex]; if lindex % 2 == 0 { ans += a[lindex] - l; } if rindex % 2 == 0 { ans += r - a[rindex - 1]; } println!("{}", ans); } }
E - Art Gallery on Graph
なんか沼った。最初の提出に$=$ が 抜けているだけだった。
グラフ上に警備員がいて、それぞれ体力が決まっていて、体力分離れたところまで警備できる。 警備されている頂点を昇順に出力して下さいという問題。
スタート地点をいくつか持って、最大値から更新していくダイクストラをすると良い。
fn main() { input! { n : usize, m : usize, k : usize, edges : [(Usize1, Usize1); m], ph : [(Usize1, usize); k] } let mut g = vec![vec![]; n]; for (a, b) in edges { g[a].push(b); g[b].push(a); } let mut que = BinaryHeap::new(); let mut dist = vec![None; n]; for (p, h) in ph { que.push((h, p)); dist[p] = Some(h); } while let Some((h, p)) = que.pop() { if dist[p].unwrap() != h { continue; } if h == 0 { continue; } for &q in &g[p] { if dist[q].is_none() || dist[q].unwrap_or(0) < h - 1 { dist[q] = Some(h - 1); que.push((h - 1, q)); } } } let ans = (0..n).filter(|&i| dist[i].is_some()).collect_vec(); println!("{}\n{}", ans.len(), ans.iter().map(|a| a + 1).join(" ")); }
F - Dungeon Explore
入力がめんどくさいインタラクティブ。 Rust のインタラクティブが下手くそ過ぎて TLE めっちゃ出しちゃった。 最初から自作の適宜入力取るやつで書いておけば良かった。
移動回数 $ 2 \times N $ 以下で頂点$1$ から頂点$N$ に移動してくださいという問題。 連結かつ単純なので、DFSみたいに探索していったら $2 \times N$ 回以内に $N$ まで移動できる。
fn main() { let (n, m) : (usize, usize) = input_t(); let mut g = vec![vec![]; n]; let mut used = vec![false; n]; let mut stack= vec![]; let mut pref = vec![0; n]; let e = input_vec::<usize>().into_iter().skip(1).map(|x| x - 1).collect_vec(); g[0] = e; for &u in &g[0] { stack.push((false, u)); stack.push((true, u)); pref[u] = 0; } while let Some((f, v)) = stack.pop() { if f { if used[v] { continue; } used[v] = true; println!("{} ", v + 1); if v + 1 == n { break; } stdout().flush().unwrap(); let e = input_vec::<usize>().into_iter().skip(1).map(|x| x - 1).collect_vec(); g[v] = e; for &u in &g[v] { if used[u] { continue; } stack.push((false, u)); stack.push((true, u)); pref[u] = v; } } else { println!("{} ", pref[v] + 1); stdout().flush().unwrap(); let _ = input_vec::<usize>().into_iter().skip(1).map(|x| x - 1).collect_vec(); } } }
G - Banned Substrings
圧倒的に時間が足りなかった。
$N$ がある程度小さい場合は、末尾6桁を持って DP したら答えを求めることができる。しかし、大きいので DP 遷移を 行列にして行列累乗をしたら良い。 6桁未満は愚直に求めると楽かも。
うーん…解きたかった。
fn main() { input! { n : usize, m : usize, s : [String; m] } let mut dp = FxHashMap::default(); dp.insert("".to_owned(), Mint::new(1)); for _ in 0..n.min(6) { let mut next = FxHashMap::default(); for (k, &v) in dp.iter() { for i in 0..2 { let k = k.chars().rev().take(5).collect::<String>(); let k = k.chars().rev().collect::<String>(); let ns = k + if i==0 { "a" } else { "b" }; if s.iter().any(|s| { let ns = ns.chars().rev().take(s.len()).collect::<String>(); let ns = ns.chars().rev().collect::<String>(); &ns == s }) { continue; } *next.entry(ns).or_insert(Mint::new(0)) += v; } } dp = next; } if n <= 6 { println!("{}", dp.iter().fold(Mint::new(0), |acc, (_, x)| acc + x)); return; } let mut v = vec![Mint::new(0); 1<<6]; let mut mat = matrix::Matrix::new(1<<6, 1<<6, Mint::new(0)); for (k, &val) in dp.iter() { let k = k.chars().fold(0, |acc, c| acc * 2 + if c=='a' { 0 } else { 1 }); v[k] += val; for i in 0..2 { let l = (k * 2 + i) & 0b111111; mat[k][l] += 1; } } let t = mat.pow(n - 6, Mint::new(1)); let ans = t * &v; println!("{}", ans.iter().sum::<Mint>()); }
Ex - Shojin
見てない
まとめ
途中の問題で沼り過ぎて、勝負のGにあんまり時間かけられなかった…。 競プロやらなさすぎて、鈍ってるなぁと思った。
パフォーマンス 1469。レート 1702 → 1680
Codeforces Round 867 (Div. 3)
Codeforces Round 867 (Div. 3) バーチャル参加したのでまとめ。 A, B, C, D, E 5完。 F は実装下手くそで時間内に解けなかった。 ChatGPT に課金したので、問題文貼り付けて「要約して下さい」って言い続けたけた。よく考えたら翻訳では…?まぁ日本語でまとめてくれたから何でもいいや。
A. TubeTube Feed
$A_i \leq t$ で $B_i$ が最大となるような $i$ を選ぶ。
fn solve(sc:&mut Scanner) { let n = sc.usize(); let t = sc.usize(); let a = sc.vec::<usize>(n); let b = sc.vec::<usize>(n); let mut ans = None; let mut max = 0; for i in 0..n { if a[i] + i <= t && chmax(&mut max, b[i]) { ans = Some(i); } } if let Some(ans) = ans { println!("{}", ans + 1); } else { println!("-1"); } }
B. Karina and Array
数列の要素を好きに削除して良いので、隣り合う値の積の最大値を最大化して下さいという問題。 正の絶対値が大きいやつ2つか、負の絶対値が大きい奴2つをかけるのが良いのソートして雑にやる。 要らないとは思ったけど $0$ が含まれていたら $0$ とも MAX を取っておいた。
fn solve(sc:&mut Scanner) { let n = sc.usize(); let mut a = sc.vec::<i64>(n); a.sort(); let mut ans = a[0] * a[1]; ans = ans.max(a[n-1] * a[n-2]); if a.iter().any(|&a| a == 0) { ans = ans.max(0); } println!("{}", ans); }
C. Bun Lover
うずまきパンのチョコレート部分の長さを求める問題。難しい
3箇所囲まれている場所が必ず4箇所あって、他は2箇所囲まれている。後は、共有部分を引けば良いがわからない。サンプルから $10, 17, 26$ になるので、OIESに投げてみると $ n ^ 2 + 1$ と言われるので、言われるがままに引く。
fn solve(sc:&mut Scanner) { let n = sc.usize(); let mut ans = 0; ans += 3 * 4; ans += 2 * (n * n - 4); ans -= (n-1) * (n-1) + 1; println!("{}", ans); }
D. Super-Permutation
よくわからないけど、$1$ 以外の奇数はダメそう。 偶数の場合、$0, 2, 4, \cdots$ と $\cdots, 5, 3, 1$ を交互に混ぜれば良さそう(サンプル)。
fn solve(sc:&mut Scanner) { let n = sc.usize(); if n == 1 { println!("1"); return; } if n % 2 == 1 { println!("-1"); return; } let mut ans = vec![0; n]; let f = |x:usize| { if x == 0 {n} else {x}}; for i in (0..n).step_by(2) { ans[i] = f(i); } for i in (0..n).rev().step_by(2) { ans[i] = f(n - i); } println!("{}", ans.iter().map(|&a| a.to_string()).collect::<Vec<_>>().join(" ") ) }
E. Making Anti-Palindromes
文字列を折りたたんだとき(?)に同じじゃないようにしたくて、できる操作はスワップ。操作回数の最小値は?という問題。めんどくさい。
$ s _ i $ と $ s _ {n - i - 1}$ が一致しているときの、文字種を適当に求めて他の文字種と打ち消し合っていけばスワップ回数が減らせる。残った奴はもう適当にスワップするしかないので全部足す。
fn solve(sc:&mut Scanner) { let n = sc.usize(); let mut t = sc.chars(); if n % 2 == 1 { println!("-1"); return; } let mut cnt = vec![0; 26]; for &c in t.iter() { cnt[(c as u8 - 'a' as u8) as usize] += 1; } let max = cnt.iter().max().cloned().unwrap(); if max > n / 2 { println!("-1"); return; } let mut pair = vec![0; 26]; for i in 0..n/2 { if t[i] == t[n-i-1] { pair[(t[i] as u8 - 'a' as u8) as usize] += 1; } } let mut pq : BinaryHeap<_> = pair.iter().filter(|&&x| x > 0).cloned().collect(); let mut ans = 0; while pq.len() > 2 { let a = pq.pop().unwrap(); let b = pq.pop().unwrap(); if a > 1 { pq.push(a - 1); } if b > 1 { pq.push(b - 1); } ans += 1; } if !pq.is_empty() { ans += pq.pop().unwrap(); } println!("{}", ans); }
F. Gardening Friends
全方位木DPが下手くそで時間内に実装できなかった。
fn solve(sc:&mut Scanner) { let n = sc.usize(); let k = sc.usize(); let c = sc.usize(); let edges = sc.edges(n-1); let mut g = vec![vec![]; n]; for (a, b) in edges { g[a].push(b); g[b].push(a); } let dist = bfs(0, n, &g); let mut dp1 = vec![0; n]; let mut visited = vec![false; n]; dfs1(0, &g, &mut dp1, &mut visited); let mut dp2 = vec![0; n]; let mut visited = vec![false; n]; dfs2(0, None, &g, &dp1, &mut dp2, &mut visited); // eprintln!("{:?}", dp1); // eprintln!("{:?}", dp2); // eprintln!("{:?}", dist); let mut ans = 0; for i in 0..n { ans = ans.max( (dp1[i].max(dp2[i]) * k).saturating_sub(dist[i] * c) ); } println!("{}", ans); } fn dfs1(v: usize, g: &Vec<Vec<usize>>, dp: &mut Vec<usize>, visited: &mut Vec<bool>) { visited[v] = true; for &next in &g[v] { if visited[next] { continue; } dfs1(next, g, dp, visited); dp[v] = dp[v].max(dp[next] + 1); } } fn dfs2(v: usize, p: Option<usize>, g: &Vec<Vec<usize>>, dp1:&Vec<usize>, dp2: &mut Vec<usize>, visited: &mut Vec<bool>) { visited[v] = true; let mut left = vec![0]; for &u in g[v].iter().filter(|&&u| Some(u) != p) { left.push(left.last().cloned().unwrap().max(dp1[u] + 1)); } let mut right = vec![0]; for &u in g[v].iter().rev().filter(|&&u| Some(u) != p) { right.push(right.last().cloned().unwrap().max(dp1[u] + 1)); } right.reverse(); for (i, &u) in g[v].iter().filter(|&&u| Some(u) != p).enumerate() { let d = left[i].max(right[i+1]) + 1; dp2[u] = d.max(dp2[v] + 1); dfs2(u, Some(v), g, dp1, dp2, visited); } } fn bfs(start: usize, n: usize, g: &Vec<Vec<usize>>) -> Vec<usize> { let mut dist = vec![std::usize::MAX; n]; let mut q = std::collections::VecDeque::new(); q.push_back((start, 0)); while let Some((v, d)) = q.pop_front() { if dist[v] <= d { continue; } dist[v] = d; for &next in &g[v] { q.push_back((next, d+1)); } } dist }
G1. Magic Triples (Easy Version)
見てない
G2. Magic Triples (Hard Version)
見てない
まとめ
全方位木DP、ライブラリ化するか定期的に書いてすぐ実装できるようにしようね!
AtCoder Beginner Contest 294
AtCoder Beginner Contest 294 です。
A,B,C,D,E,F,G のノーペナ 59:54 7 完 でした。 2回目のカンスト。初めてのカンストは嘘通してたので、今回はまともに解いて初カンスト? (そうなら嬉しい) 実は 21:00 まで寝落ちしていて、寝起き過ぎて出るか迷っていたんだけど出て良かった。
A - Filter
数列が与えられるので、偶数だけ抜き出して出力する。
fn main() { input! { n : usize, a : [usize; n] } println!("{}", a.iter().filter(|&x| x%2 == 0).join(" ")); }
B - ASCII Art
$ 1 $ 以上ならその値に合わせて 'A'
とかに変換する。
fn main() { input! { h : usize, w : usize, a : [[u8; w]; h] } let mut b = vec![vec!['.'; w]; h]; for i in 0..h { for j in 0..w { if a[i][j] == 0 { continue } b[i][j] = (b'A' + a[i][j] - 1) as char; }} println!("{}", b.iter().map(|b| b.iter().join("")).join("\n"));;;;;;; }
提出
C - Merge Sequences
マージの過程を良い感じにする感じ。$A$ を見ているインデックスと $B$ を見ているインデックスを作って、小さい方からインデックスを進めていくと良い。終端の処理がめんどくさいので雑に書く。
fn main() { input! { n : usize, m : usize, a : [usize; n], b : [usize; m] } let mut ans1 = vec![0; n]; let mut ans2 = vec![0; m]; let mut i = 0; let mut j = 0; let mut now = 1; while i < n && j < m { if a[i] < b[j] { ans1[i] = now; i += 1; } else if a[i] > b[j] { ans2[j] = now; j += 1; } now += 1; } while i < n { ans1[i] = now; i += 1; now += 1; } while j < m { ans2[j] = now; j += 1; now += 1; } println!("{}\n{}", ans1.iter().join(" "), ans2.iter().join(" ")); }
D - Bank
呼ばれたとか、受付に行くとかちょっとだけ読みにくい…。まだ呼ばれていない人を BtreeSet とかで管理して小さい順に取り出す(これは Deque とかで良かったかも)。既に呼ばれたが受付に行っていない人も BtreeSet で管理して良い感じに出力する。
fn main() { input! { n : usize, q : usize } let mut no : BTreeSet<_> = (1..=n).collect(); let mut que = BTreeSet::new(); let mut ans = Vec::with_capacity(q); for _ in 0..q { input! { t : u8 } match t { 1 => { let min = no.iter().next().cloned().unwrap(); no.remove(&min); que.insert(min); } 2 => { input! { x : usize } que.remove(&x); } 3 => { let min = que.iter().next().cloned().unwrap(); ans.push(min); } _ => unreachable!() } } println!("{}", ans.iter().join(" ")); }
E - 2xN Grid
ランレングス圧縮されたものが渡されるので、元の数列で $A_i = B_i$ となるような $i$ の個数を求める。
C問題 と同じ感じで、それぞれインデックスを持って短い方を進めつつ同じ奴があったらその長さを計算していくと良い。
fn main() { input! { l : usize, n1 : usize, n2 : usize, vl1 : [(usize, usize); n1], vl2 : [(usize, usize); n2] } let mut nowi = 0; let mut leni = 0; let mut nowj = 0; let mut lenj = 0; let mut ans : usize = 0; loop { let (v1, len1) = vl1[nowi]; let (v2, len2) = vl2[nowj]; if leni + len1 >= lenj + len2 { if v1 == v2 { ans += (leni + len1).min(lenj + len2) - leni.max(lenj); } lenj += len2; nowj += 1; } else { if v1 == v2 { ans += (leni + len1).min(lenj + len2) - lenj.max(leni); } leni += len1; nowi += 1; } if nowi >= n1 || nowj >= n2 { break } } println!("{}", ans); }
F - Sugar Water 2
二分探索したら良さそうですね~、どうやったら判定できるんですか? 食塩水 ありがとう…をしていた。
$ x \% $ にするときに、何g 足りない(余っている)か計算しておいてソートしておけば、$ x \% $ の砂糖水を作る事ができる組合せが何個あるか適当に計算できる。
$A, B$ の分も計算してソートしてたけど、別にそんなことしなくて良かったな。
fn main() { input! { n : usize, mm : usize, k : usize, ab : [(f64, f64); n], cd : [(f64, f64); mm] } let mut l = 0.0; let mut r = 100.0; for _ in 0..100 { let m = (l + r) / 2.0; let mut aa = Vec::with_capacity(n); for &(a, b) in ab.iter() { let p = a / (a + b) * 100.; aa.push((a + b) * (p - m)); } aa.sort_by(|a, b| a.partial_cmp(b).unwrap()); let mut cc = Vec::new(); for &(c, d) in cd.iter() { let p = c / (c + d) * 100.; cc.push((c + d) * (p - m)); } cc.sort_by(|a, b| a.partial_cmp(b).unwrap()); let mut cnt = 0; for &a in aa.iter() { let index = cc.lower_bound_by(|&c| c.partial_cmp(&(-a)).unwrap()); cnt += mm - index; } if cnt >= k { l = m; } else { r = m; } } println!("{}", l); }
G - Distance Queries on a Tree
HLD してセグ木で和を求めると良い。遥か昔に作ったライブラリで使い方覚えていなかったが、名前と引数の雰囲気で実装できた。
fn main() { input! { n : usize, edges : [(Usize1, Usize1, usize); n-1], q : usize, } let mut hld = HeavyLightDecomposition::new(n); for &(u,v, w) in edges.iter() { hld.add_edge(u, v); } hld.build(0); def_monoid!(M, usize, 0, |x, y| x + y); let mut seg = SegmentTree::<M>::new(n); for &(u, v, w) in edges.iter() { hld.for_each_edge(u, v, |l, r| { seg.set(l.min(r), w); }); } let mut ans = Vec::with_capacity(q); for _ in 0..q { input! { t : u8 } match t { 1 => { input! { i:Usize1, w:usize } hld.for_each_edge(edges[i].0, edges[i].1, |l, r| { seg.set(l.max(r), w); }); } 2 => { input! { u:Usize1, v:Usize1 } let mut t = 0; hld.for_each_edge(u, v, |l, r| { t += seg.fold(l..=r); }); ans.push(t); } _ => unreachable!(), } } println!("{}", ans.iter().join("\n")); }
Ex - K-Coloring
見たけど分からず。
まとめ
なんか得意回でした!普段だったら F が解けなくて切れてたと思うけど、食塩水 を覚えていたので助かった。 水に落ちていたので青にジャンプして戻れて嬉し~
2400パフォ 1586 → 1698 ( +112)
AtCoder Beginner Contest 284
AtCoder Beginner Contest 284 です。
1ペナ 5完。 ペナ込み 25:14(+5:00)。 5完まではぼちぼち早かったけど、全人類 F 通してて悲しい気持ちになった。 Rolling Hash っぽいものをゴニョニョ書いてたけど、バグらせて終了。というか条件をちゃんと分離できてなかった…。
A - Sequence of Strings
逆順に出力する。
fn main() { input! { s : [String] } println!("{}", s.iter().rev().join("\n")); }
B - Multi Test Cases
奇数を数える。マルチテストケース。
fn main() { input! { t : usize } let mut ans = Vec::with_capacity(t); for _ in 0..t { input! { a : [usize] } ans.push(a.iter().filter(|&a| a % 2 == 1).count()); } println!("{}", ans.iter().join("\n")); }
C - Count Connected Components
シンプルに連結成分を数える問題。
Union-Find で適当にマージして、 i == root(i)
となるやつを数えると連結成分が分かる。
fn main() { input! { n : usize, m : usize, edges : [(Usize1, Usize1); m] } let mut uni = UnionFind::new(n); for (a ,b) in edges { uni.merge(a, b); } let ans = (0..n).filter(|&i| i == uni.root(i)).count(); println!("{}", ans); }
D - Happy New Year 2023
よく分からないので、ポラード・ロー法とか使ってる早いライブラリを Library Checker から盗んでくる…(Factorize)。
よく考えると、 $ \sqrt [ 3 ] { N } $ くらいまで探索したら良いので、そんな感じで書いても良かったかも。
fn main() { input! { t : usize } let mut ans = vec![]; for _ in 0..t { input! { n : i64 } let f = pollard_rho::factorize(n); let mut p = 0; let mut q = 0; for (k, v) in f { if v == 1 { q = k; } else { p = k; } } ans.push(format!("{} {}", p, q)); } println!("{}", ans.iter().join("\n")); }
E - Count Simple Paths
答えが $ \min ( K , 10 ^ 6) $ なので、超えたら全ての探索を打ち切ったら間に合う。 適当に DFS とかを書く。 インクリメントする場所の関係で出力が $ 10 ^ 6 $ より大きくなることがあって 1WA。
fn main() { input! { n : usize, m : usize, edges : [(Usize1, Usize1); m] } let mut ans = 0; let mut g = vec![vec![]; n]; for (a, b) in edges { g[a].push(b); g[b].push(a); } let mut path = FxHashSet::default(); dfs(0, &g, &mut path, &mut ans); println!("{}", 1_000_000.min(ans)); } fn dfs(v:usize, g:&Vec<Vec<usize>>, path:&mut FxHashSet<usize>, ans:&mut usize) { *ans += 1; path.insert(v); if *ans >= 1_000_000 { return; } for &u in g[v].iter() { if path.contains(&u) { continue } dfs(u, g, path, ans); } path.remove(&v); }
F - ABCBAC
バグらせ太郎。 Z algorithm とかでうまくできそうだな~と思いながら、良い方法が思い浮かばなかったので Rolling Hash もどきで力業実装しようとするも、うまくできず…。
結局後から AC。もうちょっと落ち着いて考えれば解けたなぁという感想。 Rolling Hash 、 LeetCode の Weekly Contest で Rolling Hash もどきを書いて通したことがあるくらいでその方針に走ったのが良くないかもなぁ…。 Z algorithm とか Suffix Array とかなんとなくは知ってるんだけど意味が分からなくなりがちなので結局通せないがち何だよなぁ…。その辺の問題たくさん解くか~。
Rolling Hash もバグらせないようにライブラリ化したんだけど、逆を勝手に持っておくようにしたんだけどよく考えたら、 $B ^ {-i}$ みたいなので逆を計算した方が良くないか? まぁ、また今度で…。
G - Only Once
見てない
Ex - Count Unlabeled Graphs
見てない。
まとめ
文字列苦手過ぎる…。
AtCoder Beginner Contest 265
AtCoder Beginner Contest 265 です。
初めてカンストパフォ出しました。嬉し~
A - Apple
3個$Y$円で買った方が安い場合、7個中、3個セット1つ・バラ4個とかを買う意味がないので、全部バラで買うか、3個で買えるだけ買って余りをバラで買うかのどちらかをやれば良いです。
fn main() { input! { x : usize, y : usize, n : usize } println!("{}", (n * x).min(n/3*y + n%3*x)); }
B - Explore
なんか問題文めんどくさい。次の部屋に移動するのに $A_i$ かかって持ち時間 $T$ で最後の部屋にたどり着けますか?という問題。たまにボーナスがある。 $N \leq 10 ^ 5$ なので $i$ 番目の部屋に到達すると $X_i$ 時間増えますみたいなのを全部配列に入れておく。 ボーナスがなければ $0$ にしておけば良い。
$0$ 以下か未満かを雑に読んでて 1 ペナ。
fn main() { input! { n : usize, m : usize, t : usize, a : [usize; n - 1], xy : [(Usize1, usize); m] } let mut xv = vec![0; n]; for (x, y) in xy { xv[x] = y; } let mut now = t; for (i, &a) in a.iter().enumerate() { now += xv[i]; if now <= a { println!("No"); return; } now -= a; } println!("Yes"); }
C - Belt Conveyor
愚直にシミュレーションする。はみ出たり、既に訪れている所に来たら終わる。
fn main() { input! { h : usize, w : usize, g : [Chars; h] } let mut now = (0, 0); let mut visited = vec![vec![false; w]; h]; loop { if visited[now.0][now.1] { println!("-1"); return; } visited[now.0][now.1] = true; match g[now.0][now.1] { 'R' => { if now.1 + 1 >= w { break } now.1 += 1; } 'L' => { if now.1 == 0 { break } now.1 -= 1; } 'U' => { if now.0 == 0 { break } now.0 -= 1; } 'D' => { if now.0 + 1 >= h { break } now.0 += 1; } _ => unreachable!() } } println!("{} {}", now.0 + 1, now.1 + 1); }
D - Iroha and Haiku (New ABC Edition)
最初全部 $P$ になるやつだと思って、適当に紙に書いたらサンプル全然合わなくて「???」ってなってた。 累積和を取っておいて、その地点から +P, +P+Q, +P+Q+R を二分探索すると良い。
ok 関数のダメ判定を index > n
で書いてたんだけど提出直前に index >= n
にして 1 WA。 累積和なので index > n
で良かった…。
fn main() { input! { n : usize, p : usize, q : usize, r : usize, a : [usize; n] } let mut csum = vec![0; n + 1]; for i in 0..n { csum[i + 1] = csum[i] + a[i]; } let ok = |x:usize, k:usize, a:&Vec<usize>| { let index = a.lower_bound(&(x + k)); if index > n { (false, 0) } else { (a[index] == x + k, index) } }; for i in 0..n { let (f1, index1) = ok(csum[i], p, &csum); if !f1 { continue } let (f2, index2) = ok(csum[index1], q, &csum); if !f2 { continue } let (f3, index3) = ok(csum[index2], r, &csum); if !f3 { continue } println!("Yes"); return; } println!("No"); }
E - Warp
$A,B,C,D,E,F$ が固定なので、そんなに状態が多く無さそうなので、再帰で書いて後から適当にメモ化した。
fn main() { input! { n : usize, m : usize, a : i64, b : i64, c : i64, d : i64, e : i64, f : i64, xy : [(i64, i64); m] } let xy : FxHashSet<_> = xy.into_iter().collect(); let mut memo = FxHashMap::default(); let ans : Mint = dp(0, n,0i64, 0i64, a,b,c,d,e,f,&xy, &mut memo); println!("{}", ans); } fn dp(i:usize, n:usize, x: i64, y: i64, a: i64, b: i64, c: i64, d: i64, e: i64, f: i64, xy: &FxHashSet<(i64, i64)>, memo:&mut FxHashMap<(usize,i64,i64), Mint>) -> Mint { if xy.contains(&(x, y)) { return Mint::new(0); } if i == n { return Mint::new(1); } if let Some(res) = memo.get(&(i, x, y)) { return *res; } let mut res = Mint::new(0); res += dp(i+1, n,x + a, y + b, a, b, c, d, e, f, xy, memo); res += dp(i+1, n,x + c, y + d, a, b, c, d, e, f, xy, memo); res += dp(i+1, n,x + e, y + f, a, b, c, d, e, f, xy, memo); memo.insert((i, x, y), res); res }
F - Manhattan Cafe
これ成分ごとに $ \ [ \max(p_i, q_i) - D, \min(p_i, q_i) + D ] $ くらいの範囲で、$p$ に関する差の絶対値の和と $q$ に関する差の絶対値の和を持って適当にやれば良さそう。 E と同じく再帰で適当に書いて後でメモ化した。
後で解説を読んでみたんだけど、何を言っているか分からない。困った
fn main() { input! { n : usize, d : i64, p : [i64; n], q : [i64; n] } let mut memo = FxHashMap::default(); let ans = f(0, n, 0, 0, d, &p, &q, &mut memo); println!("{}", ans); } fn f(i: usize, n: usize, pd:i64, qd:i64, d: i64, p: &Vec<i64>, q: &Vec<i64>, memo:&mut FxHashMap<(usize, i64, i64), Mint>) -> Mint { if i == n { return if pd <= d && qd <= d { Mint::new(1) } else { Mint::new(0) }; } if let Some(res) = memo.get(&(i, pd, qd)) { return *res; } let mut res = Mint::new(0); let min = p[i].min(q[i]); let max = p[i].max(q[i]); for r in max-d ..= min+d { let pd = pd + (p[i] - r).abs(); let qd = qd + (q[i] - r).abs(); if pd > d || qd > d { continue } res += f(i+1, n, pd, qd, d, p, q, memo); } memo.insert((i, pd, qd), res); res }
G - 012 Inversion
遅延セグ木で 0の数、1の数、2の数とかを持って天才遷移かけば通りそうだったけど、書けなかった。
Ex - No-capture Lance Game
読んだけど全く方法が思いつかず…
まとめ
なんか参加する前は失敗する気がしてたんですが、最終的には大成功でした。
初めてのカンストパフォ! 2400パフォ 1626 → 1731(+105)。うれし~