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充電器

iPhoneApple 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

ac-library-rs

ACL の Rust版ですね。大体 これ のドキュメントを読めば分かるはず

use ac_library::Dsu;

fn main() {
    Dsu::new(10);
}

とかやれば使える

once_cell

once_cell

1度しか初期化できない型を提供している。

static_assertions

static_assertions

定数や型に関するアサーションを提供している。コンパイル時にチェックされるらしい。

varisat

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

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 と書いたら Vecmemoise_map と書いたら BtreeMap でメモ化してくれるみたい。

ABC314 E をこれで解いてみた(ソースコード)。使い勝手良さそう。

argio

argio

関数の入出力を stdio に変換するマクロらしい。内側では proconio を使っているから proconioと同じ感じで書けるらしい。たまに嬉しそう?

#[argio]
fn main(n: i32) -> i32 {
    n * 2
}

bitvec

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

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

hashbag

unordered_multiset。contains で数がとれるらしい。

pathfinding

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

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

indexing

unchecked な indexing ができるらしい。ライブラリ作りには嬉しそう

amplify

amplify

マクロとか追加するやつ。

こういうことができるらしい。(BtreeMap の宣言)

#[macro_use]
extern crate amplify;

let map = bmap! {
    s!("key") => 5,
    s!("other_key") => 10
};

easy_ext

easy_ext

extension-trait-conventions をもっと簡単に記述するためのマクロ

multimap

multimap

HashMap を使った multimap

btreemultimap

btreemultimap

BtreeMap を使った multimap

bstr

bstr

バイト文字列のライブラリ。

az

az

型キャストした時にチェックしてくれたりする。(-1).wrapping_as::<u32>() とかすると 1u32.wrapping_neg() が得られる。

glidesort

glidesort

安定ソート。早いらしい。

tap

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

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

multiversion

CPUによって関数の実装を変えたりできるやつ。

num

num

整数色々。num-bigintnum-complexnum-integer とか色々ある。 整数範囲の sqrt とか便利。

ndarray

ndarray

行列ライブラリ

nalgebra

nalgebra

行列ライブラリ

alga

alga

代数系トレイト。Monoid とか入ってる

libm

libm

libm の Rust 実装。 f32, f64 の便利関数が色々

rand

rand

乱数関連の色々

getrandom

getrandom

OS の乱数生成器のインターフェース

petgraph

petgraph

グラフライブラリ。前のバージョンでも入っていた。

indexmap

indexmap

なんか色々機能のある HashMap と HashSet

regex

regex

正規表現。前のバージョンでも入っていた。

lazy_static

lazy_static

遅延評価のマクロ。前のバージョンでも入っていた。

ordered-float

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

ASCII文字列・文字を扱うやつ。前のバージョンでも入っていた。

permutohedron

permutohedron

next_permutation とかを提供している。前のバージョンでも入っていた。

superslice

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

itertools

これも超便利。 iter に対して色々できる。前のバージョンでも入っていた。

maplit

maplit

HashMap とかがマクロで定義できるやつ。amplify と近いかも

im-rc

im-rc

永続データ構造が使える。色々なデータ構造が入ってる。

fixedbitset

fixedbitset

bitset

bitset-fixed

bitset-fixed

bitset

proconio

proconio

競プロの IO を楽にするやつ。

rustc-hash

rustc-hash

高速で非暗号なハッシュ

smallvec

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

提出



問題文

長方形になるようにクッキーが置かれていて、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);
    }
}

提出



問題文

なんか沼った。最初の提出に$=$ が 抜けているだけだった。

グラフ上に警備員がいて、それぞれ体力が決まっていて、体力分離れたところまで警備できる。 警備されている頂点を昇順に出力して下さいという問題。

スタート地点をいくつか持って、最大値から更新していくダイクストラをすると良い。

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 に課金したので、問題文貼り付けて「要約して下さい」って言い続けたけた。よく考えたら翻訳では…?まぁ日本語でまとめてくれたから何でもいいや。

image.png (3.5 kB)

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 とかなんとなくは知ってるんだけど意味が分からなくなりがちなので結局通せないがち何だよなぁ…。その辺の問題たくさん解くか~。

後から通したACコード

Rolling Hash もバグらせないようにライブラリ化したんだけど、逆を勝手に持っておくようにしたんだけどよく考えたら、 $B ^ {-i}$ みたいなので逆を計算した方が良くないか? まぁ、また今度で…。

ライブラリ化したやつ
Z algorithm版



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)。うれし~