PAST本1冊分（B5 x 3cm）くらいを送れる。
送料が200円ととにかく安い。
オンラインで手続きできる。
- CSVをアップロードして20人分を一括で登録できる。
送り状PDFがダウンロードできるので、自前で印刷して貼る必要がある。
- のりで1枚ずつ貼るのは想像以上にキツい。コンビニではシール用紙印刷ができないので厳しい。

宅急便（ヤマト運輸）

好きなサイズの荷物を送れる。
ヤマト運輸のサービスはオンラインで手続きをしておくと、コンビニでバーコードを見せるだけで送れる。
- ただし手続きサイトはスマホ専用（UAを偽装すればPCでもいけるが、その場合UXは最悪）
60サイズ（PAST本4冊分くらい）で1000円程度なので、1ヶ所に送る場合でもクリックポストで別個に送った方が安いまである。
さすがに10冊くらい送るなら宅急便のほうが安い。

宅急便コンパクト（ヤマト運輸）

PAST本1冊分（B5 x 3cm）くらいを送れる。
送料は500円くらいと安くはない。
さらに70円くらいの専用の箱を別途買う必要がある。これはコンビニで買える。
- 自分で梱包を用意するのはダルいので、1冊だけ送るときなどは気にならない。

まとめ

とにかくクリックポストが安い。1-4冊ずつを別々の場所に送る場合は、別途梱包などを用意する必要があるが、思考停止でクリックポストで良さそう。のりで送り状を貼りまくる作業は覚悟を決めてやるしかない。戦いの中で成長しろ。数冊だけ送る場合は梱包を用意するコストが大きくなるので、梱包ごと買える宅急便コンパクトの方がラク。

2021-04-30

2021/04/29

$O(N \times 3^N)$ なのだが定数倍に死ぬほど厳しいので、前計算できる部分を $O(N^2 \times 2^N)$ で計算しておく。
atcoder.jp

全く歯が立たなかった。正六角形ならば勝てることに気付いて渦巻き状に構築しようとしたがハズレ方針だったっぽい。
atcoder.jp

N番目を取得できるsetとしてFenwick treeを使うこともBSTを使うこともできるが、手元にTreapがあったので貼ることにしたところ、今まで顕在化しなかったバグがあり大爆死した。insert/eraseで実装していたが、merge/splitで全部書き直した。
atcoder.jp

Baby-step Giant-step のアルゴリズムと言うらしい。アイディア的には平方分割。どうしても通らないケースが3つあったが、そういったケースはどうせ1だろうということで、TLEしそうになったら1を出力する邪悪解法で通した。
D - あまり

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 x: u64 = sc.read();
    let p: u64 = sc.read();
    let a: u64 = sc.read();
    let b: u64 = sc.read();

    let start = Instant::now();
    for i in 0.. {
        if let Some(x) = baby_step_giant_step(x, i, p) {
            let d = b - a;
            let x = x % p;
            let a = a % p;
            let b = a + d;
            if a <= x && x <= b {
                println!("{}", i);
                return;
            }
        }
        if start.elapsed().as_millis() > 1500 {
            break;
        }
    }
    let mut xa = mod_pow(x, a, p);
    let mut ans = xa;
    for _ in (a + 1)..=b {
        xa = (xa * x) % p;
        ans = ans.min(xa);

        if start.elapsed().as_millis() > 4900 {
            println!("1");
            return;
        }
    }

    println!("{}", ans);
}

fn mod_pow(x: u64, mut e: u64, m: u64) -> u64 {
    let mut result = 1;
    let mut cur = x;
    while e > 0 {
        if e & 1 == 1 {
            result = (result * cur) % m;
        }
        e >>= 1;
        cur = (cur * cur) % m;
    }
    result
}

fn baby_step_giant_step(x: u64, y: u64, m: u64) -> Option<u64> {
    let h = (m as f64).sqrt() as u64 + 1;

    let mut xby = y;
    let mut baby = vec![(0, 0); h as usize];
    for b in 0..h {
        baby[b as usize] = (xby, b);
        xby = (xby * x) % m;
    }
    baby.sort();

    let xh = mod_pow(x, h, m);
    let mut xah = xh;
    for a in 1..=h {
        match baby.binary_search(&(xah + 1, 0)) {
            Ok(i) => {
                if i > 0 && baby[i - 1].0 == xah {
                    return Some(a * h - baby[i - 1].1);
                }
            }
            Err(i) => {
                if i > 0 && baby[i - 1].0 == xah {
                    return Some(a * h - baby[i - 1].1);
                }
            }
        }
        xah = (xah * xh) % m;
    }
    None
}

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-04-30

2021/04/28

どう見ても $O(N \times 3^N)$ と思って実装したが、どうしても TLE してしまう。よく考えると $3^15 \sim 1.4 \times 10^7$ なので定数倍に死ぬほど厳しくなるが、想定解らしい。まじか…

atcoder.jp