ワクチンデマの根拠で挙げられているファイザー公式文書を読んだ

ファイザーの公式文書でワクチンの有害性が指摘されている!」というデマツイートが流れてきたから、流石にそんなわけなくない?と思ってその公式文書として挙げられているPDFの当該箇所を読んでみたけど、英語かつ専門用語で思ったより難しかった……

https://cdn.pfizer.com/pfizercom/2020-11/C4591001_Clinical_Protocol_Nov2020.pdf

よくデマの根拠とされている部分

8.3.5. Exposure During Pregnancy or Breastfeeding, and Occupational Exposure

Exposure to the study intervention under study during pregnancy or breastfeeding and occupational exposure are reportable to Pfizer Safety within 24 hours of investigator awareness.

8.3.5.1. Exposure During Pregnancy

An EDP occurs if:

  • A female participant is found to be pregnant while receiving or after discontinuing study intervention.

  • A male participant who is receiving or has discontinued study intervention exposes a female partner prior to or around the time of conception.

  • A female is found to be pregnant while being exposed or having been exposed to study intervention due to environmental exposure. Below are examples of environmental exposure during pregnancy:

    • A female family member or healthcare provider reports that she is pregnant after having been exposed to the study intervention by inhalation or skin contact.
    • A male family member or healthcare provider who has been exposed to the study intervention by inhalation or skin contact then exposes his female partner prior to or around the time of conception.

The investigator must report EDP to Pfizer Safety within 24 hours of the investigator's awareness, irrespective of whether an SAE has occurred. The initial information submitted should include the anticipated date of delivery (see below for information related to termination of pregnancy).

(まず前提として、この文書は治験のやり方を書いたもので、何かの結果を報告するものではないはずです)

たしかにこの辺りをDeepLとかに入れると「妊娠中の曝露は、以下のような場合に発生します: 女性参加者が、試験介入を受けている間、または試験介入を中止した後に妊娠していることが判明した場合...」と仰々しい感じになります。反ワクチン派の知人が「曝露が〜」という話をしていたのも多分これが根拠になっていたんですね。

Exposure=曝露は普段の生活ではあまり馴染みがありませんが、曝露試験のことで、ワクチンの接種をした後にウイルスに曝し、ワクチンの安全性や有効性を評価する試験のことです。

上記の部分は「妊婦に曝露試験をしてしまったことが判明した場合、重篤な有害事象 (SAE) が発生していなかったとしても24時間以内に Pfizer Safety に連絡しなさい」という治験のルールを説明したものですね。

Codeforces Round #773 (Div. 1) C. Anonymity Is Important

問題

https://codeforces.com/contest/1641/problem/C

N要素の配列とQ個のクエリが来る。配列の各要素は0か1だが分からない。クエリは以下の3種類。

  • L番目からR番目が全て0である。
  • L番目からR番目のどれか1つ以上が1である。
  • j番目の数が1ならYES、0ならNO、その時点では確定していなければN/Aを出力。

解法

予め全て読み込んでおく。これらを3回全部見る。

クエリ再生1周目

クエリのうち、まずは「L番目からR番目が全て0である」というクエリだけ処理することにする。次の2種類の操作がサポートされた遅延セグメントツリーを用意する。

  • L番目からR番目までをX以上ならXに書き換える。
  • L番目からR番目までのうち最大値を取り出す。

このセグメントツリーとクエリを使って、配列内の0の各要素について、その値が0と確定した時刻を記録することができる。

クエリ再生2周目

もう一度クエリを最初から全て見る。今度は「L番目からR番目のどれか1つ以上が1である」というクエリだけ処理することにする。L番目からR番目の中の0の要素数が最後までR-L個に満たなければ、このクエリによって1の要素は確定しないのでスルーして良い。L番目からR番目の要素に1の要素が1つだけあり、それがj番目と確定した場合、それ以外の0の要素が確定した時刻の最大値が分かる。その時刻かこのクエリ自体の時刻の大きいほうが、j番目が1と確定した時刻と言える。

クエリ再生3周目

今度は出力するクエリだけ処理することにする。クエリを2周したことで、各要素について、「0だと確定した時刻」「1だと確定した時刻」「何も確定していない」のいずれかが分かっている。指定された要素について、クエリ以前に確定していればYES/NOを、クエリの時点で確定していなければN/Aを出力する。

コード

use std::collections::BTreeSet;

use lazy_segment_tree::LazySegmentTree;

const INF: i64 = 1 << 60;
fn main() {
    let (r, w) = (std::io::stdin(), std::io::stdout());
    let mut sc = IO::new(r.lock(), w.lock());

    let n: usize = sc.read();
    let q: usize = sc.read();
    let mut seg = LazySegmentTree::new(
        n,
        || -INF,
        |&left: &i64, &right: &i64| left.max(right),
        |&f: &Option<i64>, &x: &i64| {
            if let Some(f) = f {
                f.min(x)
            } else {
                x
            }
        },
        |&f: &Option<i64>, &g: &Option<i64>| match (f, g) {
            (Some(x), Some(y)) => Some(x.min(y)),
            _ => f.or(g),
        },
        || None,
    );
    for i in 0..n {
        seg.set(i, INF);
    }

    let mut non_zero = (0..n).collect::<BTreeSet<_>>();
    let mut queries = vec![];
    for i in 0..q {
        let t: usize = sc.read();
        if t == 0 {
            let l = sc.usize0();
            let r: usize = sc.read();
            let x: usize = sc.read();
            queries.push((t, l, r, x));
            if x == 0 {
                seg.apply_range(l..r, Some(i as i64));
                while let Some(&x) = non_zero.range(l..r).next() {
                    assert!(non_zero.remove(&x));
                }
            }
        } else {
            let j = sc.usize0();
            queries.push((t, j, 0, 0));
        }
    }

    let mut ans_one = vec![false; n];
    let mut time = vec![INF; n];
    for i in 0..q {
        let (t, l, r, x) = queries[i];
        if t == 0 && x == 1 {
            let min = *non_zero.range(l..).next().unwrap();
            let max = *non_zero.range(..r).next_back().unwrap();
            if min == max {
                let pos = min;
                let mut max = i as i64;
                if l < pos {
                    max = max.max(seg.prod(l..pos));
                }
                if (pos + 1) < r {
                    max = max.max(seg.prod((pos + 1)..r));
                }

                ans_one[pos] = true;
                time[pos] = time[pos].min(max);
            }
        }
    }

    for i in 0..n {
        let zero_time = seg.prod(i..(i + 1));
        if zero_time != INF {
            time[i] = zero_time;
            assert!(!ans_one[i]);
        }
    }

    for i in 0..q {
        let (t, j, _, _) = queries[i];
        if t == 1 {
            if time[j] <= i as i64 {
                if ans_one[j] {
                    sc.write("YES\n");
                } else {
                    sc.write("NO\n");
                }
            } else {
                sc.write("N/A\n");
            }
        }
    }
}
pub mod lazy_segment_tree {
    type Range = std::ops::Range<usize>;

    pub struct LazySegmentTree<S, Op, E, F, Mapping, Composition, Id> {
        n: usize,
        size: usize,
        log: usize,
        data: Vec<S>,
        lazy: Vec<F>,
        op: Op,
        e: E,
        mapping: Mapping,
        composition: Composition,
        id: Id,
    }

    impl<S, Op, E, F, Mapping, Composition, Id> LazySegmentTree<S, Op, E, F, Mapping, Composition, Id>
    where
        S: Clone,
        E: Fn() -> S,
        F: Clone,
        Op: Fn(&S, &S) -> S,
        Mapping: Fn(&F, &S) -> S,
        Composition: Fn(&F, &F) -> F,
        Id: Fn() -> F,
    {
        pub fn new(
            n: usize,
            e: E,
            op: Op,
            mapping: Mapping,
            composition: Composition,
            id: Id,
        ) -> Self {
            let size = n.next_power_of_two() as usize;
            LazySegmentTree {
                n,
                size,
                log: size.trailing_zeros() as usize,
                data: vec![e(); 2 * size],
                lazy: vec![id(); size],
                e,
                op,
                mapping,
                composition,
                id,
            }
        }
        pub fn set(&mut self, mut index: usize, value: S) {
            assert!(index < self.n);
            index += self.size;
            for i in (1..=self.log).rev() {
                self.push(index >> i);
            }
            self.data[index] = value;
            for i in 1..=self.log {
                self.update(index >> i);
            }
        }

        pub fn get(&mut self, mut index: usize) -> S {
            assert!(index < self.n);
            index += self.size;
            for i in (1..=self.log).rev() {
                self.push(index >> i);
            }
            self.data[index].clone()
        }

        pub fn prod(&mut self, range: Range) -> S {
            let mut l = range.start;
            let mut r = range.end;
            assert!(l < r && r <= self.n);

            l += self.size;
            r += self.size;

            for i in (1..=self.log).rev() {
                if ((l >> i) << i) != l {
                    self.push(l >> i);
                }
                if ((r >> i) << i) != r {
                    self.push(r >> i);
                }
            }

            let mut sum_l = (self.e)();
            let mut sum_r = (self.e)();
            while l < r {
                if l & 1 != 0 {
                    sum_l = (self.op)(&sum_l, &self.data[l]);
                    l += 1;
                }
                if r & 1 != 0 {
                    r -= 1;
                    sum_r = (self.op)(&self.data[r], &sum_r);
                }
                l >>= 1;
                r >>= 1;
            }

            (self.op)(&sum_l, &sum_r)
        }

        pub fn all_prod(&self) -> S {
            self.data[1].clone()
        }

        pub fn apply(&mut self, mut index: usize, f: F) {
            assert!(index < self.n);
            index += self.size;
            for i in (1..=self.log).rev() {
                self.push(index >> i);
            }
            self.data[index] = (self.mapping)(&f, &self.data[index]);
            for i in 1..=self.log {
                self.update(index >> i);
            }
        }
        pub fn apply_range(&mut self, range: Range, f: F) {
            let mut l = range.start;
            let mut r = range.end;
            assert!(l <= r && r <= self.n);
            if l == r {
                return;
            }

            l += self.size;
            r += self.size;

            for i in (1..=self.log).rev() {
                if ((l >> i) << i) != l {
                    self.push(l >> i);
                }
                if ((r >> i) << i) != r {
                    self.push((r - 1) >> i);
                }
            }

            {
                let mut l = l;
                let mut r = r;
                while l < r {
                    if l & 1 != 0 {
                        self.all_apply(l, f.clone());
                        l += 1;
                    }
                    if r & 1 != 0 {
                        r -= 1;
                        self.all_apply(r, f.clone());
                    }
                    l >>= 1;
                    r >>= 1;
                }
            }

            for i in 1..=self.log {
                if ((l >> i) << i) != l {
                    self.update(l >> i);
                }
                if ((r >> i) << i) != r {
                    self.update((r - 1) >> i);
                }
            }
        }

        fn update(&mut self, k: usize) {
            self.data[k] = (self.op)(&self.data[2 * k], &self.data[2 * k + 1]);
        }
        fn all_apply(&mut self, k: usize, f: F) {
            self.data[k] = (self.mapping)(&f, &self.data[k]);
            if k < self.size {
                self.lazy[k] = (self.composition)(&f, &self.lazy[k]);
            }
        }
        fn push(&mut self, k: usize) {
            self.all_apply(2 * k, self.lazy[k].clone());
            self.all_apply(2 * k + 1, self.lazy[k].clone());
            self.lazy[k] = (self.id)();
        }
    }
}

pub struct IO<R, W: std::io::Write>(R, std::io::BufWriter<W>);

impl<R: std::io::Read, W: std::io::Write> IO<R, W> {
    pub fn new(r: R, w: W) -> Self {
        Self(r, std::io::BufWriter::new(w))
    }
    pub fn write<S: ToString>(&mut self, s: S) {
        use std::io::Write;
        self.1.write_all(s.to_string().as_bytes()).unwrap();
    }
    pub fn read<T: std::str::FromStr>(&mut self) -> T {
        use std::io::Read;
        let buf = self
            .0
            .by_ref()
            .bytes()
            .map(|b| b.unwrap())
            .skip_while(|&b| b == b' ' || b == b'\n' || b == b'\r' || b == b'\t')
            .take_while(|&b| b != b' ' && b != b'\n' && b != b'\r' && b != b'\t')
            .collect::<Vec<_>>();
        unsafe { std::str::from_utf8_unchecked(&buf) }
            .parse()
            .ok()
            .expect("Parse error.")
    }
    pub fn usize0(&mut self) -> usize {
        self.read::<usize>() - 1
    }
    pub fn vec<T: std::str::FromStr>(&mut self, n: usize) -> Vec<T> {
        (0..n).map(|_| self.read()).collect()
    }
    pub fn chars(&mut self) -> Vec<char> {
        self.read::<String>().chars().collect()
    }
}

Educational Codeforces Round 121 (Rated for Div. 2) E. Black and White Tree

問題

https://codeforces.com/contest/1626/problem/E

木があります。いくつかの頂点が黒く塗られています。黒い頂点は必ず2つ以上あります。ある頂点に駒があるとき、黒い頂点を1つ選択することで、駒を選択した頂点の方向に1回動かすことができます。2回連続で同じ頂点を選択することができない時、頂点iに置かれた駒を適切に黒い頂点を選択することでいずれかの黒い頂点まで移動させることができるか求めてください。

解法

駒が置かれた頂点から見て同じ方向に2つ黒い頂点があるとき、これらを交互に選択することでその方向に連続で移動することができる。このことから、黒い頂点に移動できない頂点たちは、黒い頂点に囲まれた領域にあり、かつ、その領域の外に黒い頂点はない。

f:id:kenkoooo:20220121023933p:plain

コード

use std::collections::{BTreeSet, VecDeque};
use std::time::Instant;

fn main() {
    let (r, w) = (std::io::stdin(), std::io::stdout());
    let mut sc = IO::new(r.lock(), w.lock());

    let n: usize = sc.read();
    let color: Vec<i64> = sc.vec(n);
    let mut graph = vec![vec![]; n];
    for _ in 1..n {
        let u = sc.usize0();
        let v = sc.usize0();
        graph[u].push(v);
        graph[v].push(u);
    }

    let a = (0..n).find(|&i| color[i] == 1).unwrap();
    let dist_a = bfs(&graph, a);
    let b = (0..n)
        .filter(|&i| i != a && color[i] == 1)
        .min_by_key(|&i| dist_a[i])
        .unwrap();
    let dist_b = bfs(&graph, b);
    let ab = dist_b[a];

    let ans = if let Some(x) = (0..n).find(|&i| dist_b[i] + dist_a[i] == ab && color[i] == 0) {
        let mut q = VecDeque::new();
        q.push_back(x);
        let n = graph.len();
        let mut dist = vec![n; n];
        dist[x] = 0;
        while let Some(v) = q.pop_front() {
            if color[v] == 1 {
                continue;
            }
            for &next in graph[v].iter() {
                if dist[next] > dist[v] + 1 {
                    dist[next] = dist[v] + 1;
                    q.push_back(next);
                }
            }
        }

        let reached = (0..n).filter(|&i| color[i] == 1 && dist[i] < n).count();
        let total = (0..n).filter(|&i| color[i] == 1).count();
        if reached != total {
            vec![1; n]
        } else {
            let mut ans = vec![1; n];
            for i in 0..n {
                if dist[i] < n {
                    ans[i] = 0;
                }
            }

            for i in 0..n {
                if graph[i].iter().any(|&i| color[i] == 1) {
                    ans[i] = 1;
                }
                if color[i] == 1 {
                    ans[i] = 1;
                }
            }

            let mut s = vec![BTreeSet::new(); n];
            for i in 0..n {
                for &j in graph[i].iter() {
                    if dist[i] < n && dist[j] < n {
                        s[i].insert(j);
                    }
                }
            }

            let mut q = VecDeque::new();
            for i in 0..n {
                if s[i].len() == 1 && color[i] == 0 {
                    q.push_back(i);
                }
            }
            while let Some(i) = q.pop_front() {
                let next = s[i].clone();
                for next in next {
                    assert!(s[next].remove(&i));
                    if s[next].len() == 1 && color[next] == 0 {
                        q.push_back(next);
                    }
                }
                s[i].clear();
            }

            for v in 0..n {
                if graph[v].iter().all(|&i| color[i] == 0) {
                    continue;
                }

                for &next in graph[v].iter() {
                    if s[next].is_empty() {
                        dfs(next, v, &graph, &mut ans);
                    }
                }
            }

            if (0..n)
                .filter(|&i| s[i].len() >= 3)
                .any(|v| graph[v].iter().any(|&next| color[next] == 1))
            {
                vec![1; n]
            } else {
                ans
            }
        }
    } else {
        assert_eq!(ab, 1);
        vec![1; n]
    };

    for (i, ans) in ans.into_iter().enumerate() {
        if i > 0 {
            sc.write(' ');
        }
        sc.write(ans);
    }
    sc.write('\n');
}
fn dfs(v: usize, p: usize, graph: &Vec<Vec<usize>>, ans: &mut Vec<i64>) {
    ans[v] = 1;
    for &next in graph[v].iter() {
        if p == next {
            continue;
        }
        dfs(next, v, graph, ans);
    }
}

fn bfs(graph: &Vec<Vec<usize>>, from: usize) -> Vec<usize> {
    let mut q = VecDeque::new();
    q.push_back(from);
    let n = graph.len();
    let mut dist = vec![n; n];
    dist[from] = 0;
    while let Some(v) = q.pop_front() {
        for &next in graph[v].iter() {
            if dist[next] > dist[v] + 1 {
                dist[next] = dist[v] + 1;
                q.push_back(next);
            }
        }
    }
    dist
}

pub struct ReRooting<T, Identity, Merge, AddRoot> {
    dp: Vec<Vec<T>>,
    ans: Vec<T>,
    graph: Vec<Vec<usize>>,
    identity: Identity,
    merge: Merge,
    add_root: AddRoot,
}

impl<T, Identity, Merge, AddRoot> ReRooting<T, Identity, Merge, AddRoot>
where
    T: Clone,
    Identity: Fn() -> T,
    Merge: Fn(T, T) -> T,
    AddRoot: Fn(T) -> T,
{
    pub fn new(n: usize, identity: Identity, merge: Merge, add_root: AddRoot) -> Self {
        Self {
            dp: vec![vec![]; n],
            ans: vec![identity(); n],
            graph: vec![vec![]; n],
            identity,
            merge,
            add_root,
        }
    }
    pub fn add_edge(&mut self, a: usize, b: usize) {
        self.graph[a].push(b);
    }
    pub fn build(&mut self) {
        self.dfs(0, 0);
        self.dfs2(0, 0, (self.identity)());
    }

    fn dfs(&mut self, v: usize, p: usize) -> T {
        let mut sum = (self.identity)();
        let deg = self.graph[v].len();
        self.dp[v] = vec![(self.identity)(); deg];
        let next = self.graph[v].clone();
        for (i, next) in next.into_iter().enumerate() {
            if next == p {
                continue;
            }
            let t = self.dfs(next, v);
            self.dp[v][i] = t.clone();
            sum = (self.merge)(sum, t);
        }
        (self.add_root)(sum)
    }
    fn dfs2(&mut self, v: usize, p: usize, dp_p: T) {
        for (i, &next) in self.graph[v].iter().enumerate() {
            if next == p {
                self.dp[v][i] = dp_p.clone();
            }
        }

        let deg = self.graph[v].len();
        let mut dp_l = vec![(self.identity)(); deg + 1];
        let mut dp_r = vec![(self.identity)(); deg + 1];
        for i in 0..deg {
            dp_l[i + 1] = (self.merge)(dp_l[i].clone(), self.dp[v][i].clone());
        }
        for i in (0..deg).rev() {
            dp_r[i] = (self.merge)(dp_r[i + 1].clone(), self.dp[v][i].clone());
        }

        self.ans[v] = (self.add_root)(dp_l[deg].clone());

        let next = self.graph[v].clone();
        for (i, next) in next.into_iter().enumerate() {
            if next == p {
                continue;
            }
            self.dfs2(
                next,
                v,
                (self.add_root)((self.merge)(dp_l[i].clone(), dp_r[i + 1].clone())),
            );
        }
    }
}
pub struct IO<R, W: std::io::Write>(R, std::io::BufWriter<W>);

impl<R: std::io::Read, W: std::io::Write> IO<R, W> {
    pub fn new(r: R, w: W) -> IO<R, W> {
        IO(r, std::io::BufWriter::new(w))
    }
    pub fn write<S: ToString>(&mut self, s: S) {
        use std::io::Write;
        self.1.write_all(s.to_string().as_bytes()).unwrap();
    }
    pub fn read<T: std::str::FromStr>(&mut self) -> T {
        use std::io::Read;
        let buf = self
            .0
            .by_ref()
            .bytes()
            .map(|b| b.unwrap())
            .skip_while(|&b| b == b' ' || b == b'\n' || b == b'\r' || b == b'\t')
            .take_while(|&b| b != b' ' && b != b'\n' && b != b'\r' && b != b'\t')
            .collect::<Vec<_>>();
        unsafe { std::str::from_utf8_unchecked(&buf) }
            .parse()
            .ok()
            .expect("Parse error.")
    }
    pub fn usize0(&mut self) -> usize {
        self.read::<usize>() - 1
    }
    pub fn vec<T: std::str::FromStr>(&mut self, n: usize) -> Vec<T> {
        (0..n).map(|_| self.read()).collect()
    }
    pub fn chars(&mut self) -> Vec<char> {
        self.read::<String>().chars().collect()
    }
}

ABC233 G - Strongest Takahashi

atcoder.jp

空行はスキップして良いという発想も大事だが、そもそも全ての長方形領域を列挙した O(N4) もそこまで大きくないというのに気付かなかった。

|rust| const INF: i64 = 1 << 60; fn main() { let (r, w) = (std::io::stdin(), std::io::stdout()); let mut sc = IO::new(r.lock(), w.lock());

let n: usize = sc.read();
let map: Vec<Vec<char>> = (0..n).map(|_| sc.chars()).collect();

let mut dp = vec![vec![vec![vec![INF; n + 1]; n]; n + 1]; n];

let ans = calc(&map, 0, n, 0, n, &mut dp);
println!("{}", ans);

}

fn calc( map: &Vec<Vec>, r_from: usize, r_to: usize, c_from: usize, c_to: usize, memo: &mut Vec<Vec<Vec<Vec>>>, ) -> i64 { let dr = r_to - r_from; let dc = c_to - c_from; if dr.min(dc) == 0 { return 0; } if memo[r_from][r_to][c_from][c_to] < INF { return memo[r_from][r_to][c_from][c_to]; }

let mut min_cost = dr.max(dc) as i64;
for i in r_from..r_to {
    if (c_from..c_to).all(|j| map[i][j] == '.') {
        let head = calc(map, r_from, i, c_from, c_to, memo);
        let tail = calc(map, i + 1, r_to, c_from, c_to, memo);
        min_cost = min_cost.min(head + tail);
    }
}

for j in c_from..c_to {
    if (r_from..r_to).all(|i| map[i][j] == '.') {
        let left = calc(map, r_from, r_to, c_from, j, memo);
        let right = calc(map, r_from, r_to, j + 1, c_to, memo);
        min_cost = min_cost.min(left + right);
    }
}

memo[r_from][r_to][c_from][c_to] = min_cost;
min_cost

}

pub struct IO<R, W: std::io::Write>(R, std::io::BufWriter);

impl<R: std::io::Read, W: std::io::Write> IO<R, W> { pub fn new(r: R, w: W) -> IO<R, W> { IO(r, std::io::BufWriter::new(w)) } pub fn write<S: ToString>(&mut self, s: S) { use std::io::Write; self.1.write_all(s.to_string().as_bytes()).unwrap(); } pub fn read<T: std::str::FromStr>(&mut self) -> T { use std::io::Read; let buf = self .0 .by_ref() .bytes() .map(|b| b.unwrap()) .skip_while(|&b| b == b' ' || b == b'\n' || b == b'\r' || b == b'\t') .take_while(|&b| b != b' ' && b != b'\n' && b != b'\r' && b != b'\t') .collect::<Vec<>>(); unsafe { std::str::from_utf8_unchecked(&buf) } .parse() .ok() .expect("Parse error.") } pub fn usize0(&mut self) -> usize { self.read::() - 1 } pub fn vec<T: std::str::FromStr>(&mut self, n: usize) -> Vec { (0..n).map(|| self.read()).collect() } pub fn chars(&mut self) -> Vec { self.read::().chars().collect() } }

||<

Put "open" to your class and its method when you get a NullPointerException by mocking your class by Mockito.

Problem

When you have MyClass and try to write a test by mocking MyClass as the following, you will get an NPE:

MyClass:

open class MyClass {
    fun createList(string: String): List<String> {
        return listOf("A", "B", "C", string)
    }
}

Mocking MyClass by Mockito:

import org.junit.jupiter.api.Test
import org.mockito.kotlin.any
import org.mockito.kotlin.mock
import org.mockito.kotlin.whenever

class TestMyClass {
    @Test
    fun testMyClass() {
        val mock = mock<MyClass>()
        whenever(mock.createList(any())).thenReturn(emptyList())
    }
}

Exception you will get:

java.lang.NullPointerException: Parameter specified as non-null is null: method MyClass.createList, parameter string

Solution: Put "open" not only to your class but also to the method

open class MyClass {
+   open fun createList(string: String): List<String> {
-   fun createList(string: String): List<String> {
        return listOf("A", "B", "C", string)
    }
}

2021/11/21

ARC129A - Smaller XOR

atcoder.jp

頑張って桁DPをやっていて、解説を読んで崩れ落ちた…

fn main() {
    let (r, w) = (std::io::stdin(), std::io::stdout());
    let mut sc = IO::new(r.lock(), w.lock());

    let n: i64 = sc.read();
    let l: i64 = sc.read();
    let r: i64 = sc.read();
    let ans = solve(n, r) - solve(n, l - 1);
    println!("{}", ans);
}

fn solve(n: i64, max: i64) -> i64 {
    let mut dp = vec![vec![vec![0; 2]; 2]; 2];
    dp[0][0][0] = 1;
    for pos in (0..63).rev() {
        let max_d = (max >> pos) & 1;
        let n_d = (n >> pos) & 1;

        let mut next = vec![vec![vec![0; 2]; 2]; 2];
        for started in 0..2 {
            let is_started = started == 1;
            for lower in 0..2 {
                let is_lower = lower == 1;

                for xor_lower in 0..2 {
                    for next_digit in 0..2 {
                        let next_started = if is_started || next_digit == 1 { 1 } else { 0 };
                        let next_lower = if is_lower || max_d > next_digit { 1 } else { 0 };
                        let next_n_lower = if xor_lower == 1 || (next_digit == 1 && n_d == 1) {
                            1
                        } else {
                            0
                        };

                        if next_lower != 1 && max_d < next_digit {
                            continue;
                        }
                        if next_n_lower != 1 && next_digit == 1 {
                            continue;
                        }

                        next[next_started][next_lower][next_n_lower] +=
                            dp[started][lower][xor_lower];
                    }
                }
            }
        }

        dp = next;
        // eprintln!("{:?}", dp);
    }

    let ans = dp[1][0][1] + dp[1][1][1];
    ans
}

pub struct IO<R, W: std::io::Write>(R, std::io::BufWriter<W>);

impl<R: std::io::Read, W: std::io::Write> IO<R, W> {
    pub fn new(r: R, w: W) -> IO<R, W> {
        IO(r, std::io::BufWriter::new(w))
    }
    pub fn write<S: ToString>(&mut self, s: S) {
        use std::io::Write;
        self.1.write_all(s.to_string().as_bytes()).unwrap();
    }
    pub fn read<T: std::str::FromStr>(&mut self) -> T {
        use std::io::Read;
        let buf = self
            .0
            .by_ref()
            .bytes()
            .map(|b| b.unwrap())
            .skip_while(|&b| b == b' ' || b == b'\n' || b == b'\r' || b == b'\t')
            .take_while(|&b| b != b' ' && b != b'\n' && b != b'\r' && b != b'\t')
            .collect::<Vec<_>>();
        unsafe { std::str::from_utf8_unchecked(&buf) }
            .parse()
            .ok()
            .expect("Parse error.")
    }
    pub fn usize0(&mut self) -> usize {
        self.read::<usize>() - 1
    }
    pub fn vec<T: std::str::FromStr>(&mut self, n: usize) -> Vec<T> {
        (0..n).map(|_| self.read()).collect()
    }
    pub fn chars(&mut self) -> Vec<char> {
        self.read::<String>().chars().collect()
    }
}

ARC129D - -1+2-1

atcoder.jp

面白かった。数列に対する操作を行う時、数列そのものの変化よりも、その数列の階差数列の変化を観察した方が分かりやすくなることがある。この問題はその逆バージョンで、与えられた数列が階差数列だとして、元の数列に対する変化がどのようなものか考えることで解ける。

fn main() {
    let (r, w) = (std::io::stdin(), std::io::stdout());
    let mut sc = IO::new(r.lock(), w.lock());

    let n: usize = sc.read();
    let a: Vec<i64> = sc.vec(n);

    if a.iter().sum::<i64>() != 0 {
        println!("-1");
        return;
    }

    let mut b = vec![0; n];
    for i in 1..n {
        b[i] = b[i - 1] + a[i - 1];
    }
    assert_eq!(b[0], 0);
    assert_eq!(b[n - 1] + a[n - 1], 0);

    let b_sum = b.iter().sum::<i64>();
    if b_sum % (n as i64) != 0 {
        println!("-1");
        return;
    }

    let one = b_sum / (n as i64);
    for b in b.iter_mut() {
        *b -= one;
    }

    let mut ans = 0;
    let mut carry = 0;
    for i in 0..(3 * n) {
        if b[i % n] > 0 {
            carry += b[i % n];
            b[i % n] = 0;
        } else {
            let t = carry.min(-b[i % n]);
            carry -= t;
            b[i % n] += t;
        }
        ans += carry;
    }
    println!("{}", ans);
}

pub struct IO<R, W: std::io::Write>(R, std::io::BufWriter<W>);

impl<R: std::io::Read, W: std::io::Write> IO<R, W> {
    pub fn new(r: R, w: W) -> IO<R, W> {
        IO(r, std::io::BufWriter::new(w))
    }
    pub fn write<S: ToString>(&mut self, s: S) {
        use std::io::Write;
        self.1.write_all(s.to_string().as_bytes()).unwrap();
    }
    pub fn read<T: std::str::FromStr>(&mut self) -> T {
        use std::io::Read;
        let buf = self
            .0
            .by_ref()
            .bytes()
            .map(|b| b.unwrap())
            .skip_while(|&b| b == b' ' || b == b'\n' || b == b'\r' || b == b'\t')
            .take_while(|&b| b != b' ' && b != b'\n' && b != b'\r' && b != b'\t')
            .collect::<Vec<_>>();
        unsafe { std::str::from_utf8_unchecked(&buf) }
            .parse()
            .ok()
            .expect("Parse error.")
    }
    pub fn usize0(&mut self) -> usize {
        self.read::<usize>() - 1
    }
    pub fn vec<T: std::str::FromStr>(&mut self, n: usize) -> Vec<T> {
        (0..n).map(|_| self.read()).collect()
    }
    pub fn chars(&mut self) -> Vec<char> {
        self.read::<String>().chars().collect()
    }
}

ARC129C - Multiple of 7

atcoder.jp

「文字列の[l..r]を切り出して数としてみた時、これがxの倍数となっている」というのは [0..l]00000... と [0..r]000... を割ったあまりが等しいことを意味する。例えば1234567789の77の部分が7の倍数であるのは、1234560000と1234567700のあまりが等しいことと同値。これを見つけられずに謎の解法で殴り倒してしまった。

fn main() {
    let (r, w) = (std::io::stdin(), std::io::stdout());
    let mut sc = IO::new(r.lock(), w.lock());

    let n: i64 = sc.read();
    let ans = solve(n);
    for ans in ans {
        sc.write(ans);
    }
    sc.write('\n');
}

fn solve(n: i64) -> Vec<i64> {
    let mut c = vec![];
    let mut z = n;
    while z > 0 {
        let x = (z as f64 + 100.0).sqrt() as i64 * 2;
        for k in (1..=x).rev() {
            if k * (k - 1) / 2 <= z {
                c.push(k);
                z -= k * (k - 1) / 2;
                break;
            }
        }
    }
    assert!(c.len() <= 7, "n={} c={:?}", n, c);

    let mut b = vec![];
    for (target, count) in c.into_iter().enumerate() {
        let target = target as i64;
        let count = if target == 0 { count - 1 } else { count };
        for _ in 0..count {
            b.push(target);
        }
    }
    b.push(0);
    b.reverse();

    let n = b.len();
    let mut ans = vec![];
    let mut pow10 = 1;
    for i in (1..n).rev() {
        let prev = b[i - 1];
        let next = b[i];

        for x in 1.. {
            assert!(x < 10);
            if (prev + x * pow10) % 7 == next {
                ans.push(x);
                break;
            }
        }

        pow10 = (pow10 * 10) % 7;
    }

    ans.reverse();
    ans
}

pub struct IO<R, W: std::io::Write>(R, std::io::BufWriter<W>);

impl<R: std::io::Read, W: std::io::Write> IO<R, W> {
    pub fn new(r: R, w: W) -> IO<R, W> {
        IO(r, std::io::BufWriter::new(w))
    }
    pub fn write<S: ToString>(&mut self, s: S) {
        use std::io::Write;
        self.1.write_all(s.to_string().as_bytes()).unwrap();
    }
    pub fn read<T: std::str::FromStr>(&mut self) -> T {
        use std::io::Read;
        let buf = self
            .0
            .by_ref()
            .bytes()
            .map(|b| b.unwrap())
            .skip_while(|&b| b == b' ' || b == b'\n' || b == b'\r' || b == b'\t')
            .take_while(|&b| b != b' ' && b != b'\n' && b != b'\r' && b != b'\t')
            .collect::<Vec<_>>();
        unsafe { std::str::from_utf8_unchecked(&buf) }
            .parse()
            .ok()
            .expect("Parse error.")
    }
    pub fn usize0(&mut self) -> usize {
        self.read::<usize>() - 1
    }
    pub fn vec<T: std::str::FromStr>(&mut self, n: usize) -> Vec<T> {
        (0..n).map(|_| self.read()).collect()
    }
    pub fn chars(&mut self) -> Vec<char> {
        self.read::<String>().chars().collect()
    }
}

2021/11/17

Codeforces Round #751 (Div. 1) C. Optimal Insertion

codeforces.com

とりあえずbはソートしても良いことが分かって、aに挿入された後のb全体で見てもソートされていることが分かる。すると、bを小さい順にaに挿入していくと、既に挿入されたbの値と後から挿入されるbの値はお互いに影響しないことが分かる。よって、各biの挿入は独立に考えてよく、biは挿入した際に増える反点数が最小であるような位置に挿入すれば良い。複数ある場合は一番前にすると無難。

use crate::fenwick_tree::FenwickTree;
use crate::lazy_segment_tree::LazySegmentTree;

fn main() {
    let (r, w) = (std::io::stdin(), std::io::stdout());
    let mut sc = IO::new(r.lock(), w.lock());

    let t: usize = sc.read();
    for _ in 0..t {
        let n: usize = sc.read();
        let m: usize = sc.read();

        let mut a = Vec::with_capacity(n);
        for i in 0..n {
            let x: i64 = sc.read();
            a.push((x, i));
        }

        let mut b: Vec<i64> = sc.vec(m);
        a.sort();
        b.sort();
        let ans = solve(a, b);
        sc.write(ans);
        sc.write('\n');
    }
}
const INF: i64 = 1 << 60;

fn solve(a: Vec<(i64, usize)>, b: Vec<i64>) -> i64 {
    let n = a.len() + 1;
    let mut min_seg = LazySegmentTree::new(
        n,
        || (INF, n),
        |&s: &(i64, usize), &t: &(i64, usize)| s.min(t),
        |&f, &(x, i)| (f + x, i),
        |&f, &g| f + g,
        || 0,
    );

    for i in 0..n {
        min_seg.set(i, (0, i));
    }

    for i in 0..(n - 1) {
        min_seg.apply_range((i + 1)..n, 1);
    }

    let mut cost = 0;
    let mut a_cur = 0;
    let mut b_cur = 0;
    while a_cur < a.len() {
        let mut tt = 0;
        while b_cur < b.len() && b[b_cur] < a[a_cur].0 {
            b_cur += 1;
            tt += 1;
        }
        if tt > 0 {
            let (x, _) = min_seg.prod(0..n);
            cost += tt * x;
        }

        let mut next = a_cur;
        while next < a.len() && a[a_cur].0 == a[next].0 {
            next += 1;
        }

        for i in a_cur..next {
            let (_, i) = a[i];
            min_seg.apply_range((i + 1)..n, -1);
        }

        if b_cur < b.len() && b[b_cur] == a[a_cur].0 {
            let mut b_next = b_cur;
            while b_next < b.len() && b[b_cur] == b[b_next] {
                b_next += 1;
            }

            let count = b_next - b_cur;
            let (x, _) = min_seg.prod(0..n);
            cost += x * count as i64;
            b_cur = b_next;
        }

        for i in a_cur..next {
            let (_, i) = a[i];
            min_seg.apply_range(0..i, 1);
        }

        a_cur = next;
    }

    let mut tt = b.len() - b_cur;
    if tt > 0 {
        let (x, _) = min_seg.prod(0..n);
        cost += tt as i64 * x;
    }

    let mut bit = FenwickTree::new(n, || 0);
    let mut s = 0;

    for (_, i) in a {
        s += bit.sum(i, n);
        bit.add(i, 1);
    }
    cost + s
}
pub mod fenwick_tree {
    /// `FenwickTree` is a data structure that can efficiently update elements
    /// and calculate prefix sums in a table of numbers.
    /// [https://en.wikipedia.org/wiki/Fenwick_tree](https://en.wikipedia.org/wiki/Fenwick_tree)
    pub struct FenwickTree<T, F> {
        n: usize,
        data: Vec<T>,
        initialize: F,
    }

    impl<T, F> FenwickTree<T, F>
    where
        T: Copy + std::ops::AddAssign + std::ops::Sub<Output = T>,
        F: Fn() -> T,
    {
        /// Constructs a new `FenwickTree`. The size of `FenwickTree` should be specified by `size`.
        pub fn new(size: usize, initialize: F) -> FenwickTree<T, F> {
            FenwickTree {
                n: size + 1,
                data: vec![initialize(); size + 1],
                initialize,
            }
        }

        pub fn add(&mut self, k: usize, value: T) {
            let mut x = k;
            while x < self.n {
                self.data[x] += value;
                x |= x + 1;
            }
        }

        /// Returns a sum of range `[l, r)`
        pub fn sum(&self, l: usize, r: usize) -> T {
            self.sum_one(r) - self.sum_one(l)
        }

        /// Returns a sum of range `[0, k)`
        pub fn sum_one(&self, k: usize) -> T {
            assert!(k < self.n, "Cannot calculate for range [{}, {})", k, self.n);
            let mut result = (self.initialize)();
            let mut x = k as i32 - 1;
            while x >= 0 {
                result += self.data[x as usize];
                x = (x & (x + 1)) - 1;
            }

            result
        }
    }
}

pub mod lazy_segment_tree {
    type Range = std::ops::Range<usize>;

    pub struct LazySegmentTree<S, Op, E, F, Mapping, Composition, Id> {
        n: usize,
        size: usize,
        log: usize,
        data: Vec<S>,
        lazy: Vec<F>,
        op: Op,
        e: E,
        mapping: Mapping,
        composition: Composition,
        id: Id,
    }

    impl<S, Op, E, F, Mapping, Composition, Id> LazySegmentTree<S, Op, E, F, Mapping, Composition, Id>
    where
        S: Clone,
        E: Fn() -> S,
        F: Clone,
        Op: Fn(&S, &S) -> S,
        Mapping: Fn(&F, &S) -> S,
        Composition: Fn(&F, &F) -> F,
        Id: Fn() -> F,
    {
        pub fn new(
            n: usize,
            e: E,
            op: Op,
            mapping: Mapping,
            composition: Composition,
            id: Id,
        ) -> Self {
            let size = n.next_power_of_two() as usize;
            LazySegmentTree {
                n,
                size,
                log: size.trailing_zeros() as usize,
                data: vec![e(); 2 * size],
                lazy: vec![id(); size],
                e,
                op,
                mapping,
                composition,
                id,
            }
        }
        pub fn set(&mut self, mut index: usize, value: S) {
            assert!(index < self.n);
            index += self.size;
            for i in (1..=self.log).rev() {
                self.push(index >> i);
            }
            self.data[index] = value;
            for i in 1..=self.log {
                self.update(index >> i);
            }
        }

        pub fn get(&mut self, mut index: usize) -> S {
            assert!(index < self.n);
            index += self.size;
            for i in (1..=self.log).rev() {
                self.push(index >> i);
            }
            self.data[index].clone()
        }

        pub fn prod(&mut self, range: Range) -> S {
            let mut l = range.start;
            let mut r = range.end;
            assert!(l < r && r <= self.n);

            l += self.size;
            r += self.size;

            for i in (1..=self.log).rev() {
                if ((l >> i) << i) != l {
                    self.push(l >> i);
                }
                if ((r >> i) << i) != r {
                    self.push(r >> i);
                }
            }

            let mut sum_l = (self.e)();
            let mut sum_r = (self.e)();
            while l < r {
                if l & 1 != 0 {
                    sum_l = (self.op)(&sum_l, &self.data[l]);
                    l += 1;
                }
                if r & 1 != 0 {
                    r -= 1;
                    sum_r = (self.op)(&self.data[r], &sum_r);
                }
                l >>= 1;
                r >>= 1;
            }

            (self.op)(&sum_l, &sum_r)
        }

        pub fn all_prod(&self) -> S {
            self.data[1].clone()
        }

        pub fn apply(&mut self, mut index: usize, f: F) {
            assert!(index < self.n);
            index += self.size;
            for i in (1..=self.log).rev() {
                self.push(index >> i);
            }
            self.data[index] = (self.mapping)(&f, &self.data[index]);
            for i in 1..=self.log {
                self.update(index >> i);
            }
        }
        pub fn apply_range(&mut self, range: Range, f: F) {
            let mut l = range.start;
            let mut r = range.end;
            assert!(l <= r && r <= self.n);
            if l == r {
                return;
            }

            l += self.size;
            r += self.size;

            for i in (1..=self.log).rev() {
                if ((l >> i) << i) != l {
                    self.push(l >> i);
                }
                if ((r >> i) << i) != r {
                    self.push((r - 1) >> i);
                }
            }

            {
                let mut l = l;
                let mut r = r;
                while l < r {
                    if l & 1 != 0 {
                        self.all_apply(l, f.clone());
                        l += 1;
                    }
                    if r & 1 != 0 {
                        r -= 1;
                        self.all_apply(r, f.clone());
                    }
                    l >>= 1;
                    r >>= 1;
                }
            }

            for i in 1..=self.log {
                if ((l >> i) << i) != l {
                    self.update(l >> i);
                }
                if ((r >> i) << i) != r {
                    self.update((r - 1) >> i);
                }
            }
        }

        fn update(&mut self, k: usize) {
            self.data[k] = (self.op)(&self.data[2 * k], &self.data[2 * k + 1]);
        }
        fn all_apply(&mut self, k: usize, f: F) {
            self.data[k] = (self.mapping)(&f, &self.data[k]);
            if k < self.size {
                self.lazy[k] = (self.composition)(&f, &self.lazy[k]);
            }
        }
        fn push(&mut self, k: usize) {
            self.all_apply(2 * k, self.lazy[k].clone());
            self.all_apply(2 * k + 1, self.lazy[k].clone());
            self.lazy[k] = (self.id)();
        }
    }
}
pub struct IO<R, W: std::io::Write>(R, std::io::BufWriter<W>);

impl<R: std::io::Read, W: std::io::Write> IO<R, W> {
    pub fn new(r: R, w: W) -> IO<R, W> {
        IO(r, std::io::BufWriter::new(w))
    }
    pub fn write<S: ToString>(&mut self, s: S) {
        use std::io::Write;
        self.1.write_all(s.to_string().as_bytes()).unwrap();
    }
    pub fn read<T: std::str::FromStr>(&mut self) -> T {
        use std::io::Read;
        let buf = self
            .0
            .by_ref()
            .bytes()
            .map(|b| b.unwrap())
            .skip_while(|&b| b == b' ' || b == b'\n' || b == b'\r' || b == b'\t')
            .take_while(|&b| b != b' ' && b != b'\n' && b != b'\r' && b != b'\t')
            .collect::<Vec<_>>();
        unsafe { std::str::from_utf8_unchecked(&buf) }
            .parse()
            .ok()
            .expect("Parse error.")
    }
    pub fn usize0(&mut self) -> usize {
        self.read::<usize>() - 1
    }
    pub fn vec<T: std::str::FromStr>(&mut self, n: usize) -> Vec<T> {
        (0..n).map(|_| self.read()).collect()
    }
    pub fn chars(&mut self) -> Vec<char> {
        self.read::<String>().chars().collect()
    }
}