第6回 ドワンゴからの挑戦状 予選 C - Cookie Distribution

かなり好きなタイプの問題。
C - Cookie Distribution

問題

N 人の人にクッキーを配りたい。i = 1, ..., K に対して、以下の操作を順番に行う。

  • N 人の中から a[i] 人を等確率にランダムに選び、その人たちにクッキーを 1 個ずつ渡す。

最終的に 人 i がもらったクッキーの枚数を c[i] とし、 c[1] * c[2] * ... c[N] を 嬉しさと呼ぶことにする。
嬉しさの期待値に C(N, a[1]) * ... * C(N, a[K]) を掛けたものは整数になるが、これを mod (10^9 + 7) で求めよ。

制約

  • 1 <= K <= 20
  • 1 <= N <= 1000
  • 1 <= a[i] <= N

解法

dp[i][j] := (i 回目まで処理を行った後の、c[1] * ... c[j] の期待値 (j = 0 の場合は 1)) と置く。
dp[i + 1][j] を dp[i][...] を使って表したい。ここで、c[1] * ... * c[j] を数える代わりに、人 1 から 人 j までがもらったクッキーの j 個組を数えることにする。 (両者は同じものである)
a[i + 1] 個のクッキーを配った後のこの量は、0 <= s <= j となる s ごとに以下の値を求めて合計すればわかる:

  • j 個のうち s 個はもともと配られていたもの、残りの (j - s) 個は今配られた a[i + 1] 個のうちのどれかとしたときの、j 個組の個数

j 個のうち s 個の場所の選び方が C(j, s) 通り、個数が dp[i][s] (対称性より)、a[i + 1] 個のクッキーのうち (j - s) 個が残りの場所に配られる確率は C(n - (j - s), n - a[i + 1]) / C(n, a[i + 1]) である。これらを全て掛けて dp[i][s] * C(j, s) * C(n - (j - s), n - a[i + 1]) / C(n, a[i + 1]) が求める量である。
これを全ての s について足し合わせれば良い。計算量は、DP テーブルのエントリ数が O(KN) 個、各エントリの計算に O(N) 時間かかるので、合計 O(KN^2) である。

なお、dp[i][s] -> dp[i + 1][j] の遷移に登場する変数が s, j - s の形でしか登場しないので、任意 mod の畳み込みを用いることで O(KN log N) にすることもできる。(参考: AtCoder AGC #005 : F - Many Easy Problems - kmjp's blog)

登場する典型

  • 積の期待値を求めたい場合に、組合せ論的に扱いやすいものに置き換えて考える
  • 積の期待値 = 期待値の積 ではないので注意
    • 今回の場合、c[i] 同士は全然独立ではないので、この式は成り立たない

実装上の注意点

とくになし

提出: #9422487 (Rust)

fn solve() {
    let out = std::io::stdout();
    let mut out = BufWriter::new(out.lock());
    macro_rules! puts {
        ($($format:tt)*) => (write!(out,$($format)*).unwrap());
    }
    input! {
        n: usize, k: usize,
        a: [usize; k],
    }
    let (fac, invfac) = fact_init(n + 1);
    let comb = |x, y| {
        if x < y {
            ModInt::new(0)
        } else {
            fac[x] * invfac[y] * invfac[x - y]
        }
    };
    let mut dp = vec![vec![ModInt::new(0); n + 1]; k + 1];
    dp[0][0] += 1;
    for i in 0..k {
        for j in 0..n + 1 {
            let val = dp[i][j];
            dp[i + 1][j] += val;
            for l in 0..j {
                if a[i] + l >= j {
                    let val = dp[i][l] * comb(j, l) * comb(n + l - j, a[i] + l - j);
                    dp[i + 1][j] += val * invfac[n] * fac[a[i]] * fac[n - a[i]];
                }
            }
        }
    }
    let mut ans = dp[k][n];
    for i in 0..k {
        ans *= comb(n, a[i]);
    }
    puts!("{}\n", ans);
}

まとめ

個人的には D が比較的難しかった (solved 数を見る限り C > D だったらしいが)。おかげで E にあまり時間が掛けられなかった。ゆるせね〜 (責任転嫁)

yukicoder No.963 門松列列(2)

最近流行りの例のアレ。
No.963 門松列列(2) - yukicoder

問題

長さ N の交代順列の個数を、mod 1012924417 (= 483 * 2^21 + 1) で割ったあまりを求めよ。
交代順列: 1 から N の並び替えであって、任意の i (2 <= i <= N - 1) に対して a[i - 1] < a[i] と a[i] > a[i + 1] が同値であるもの。

  • 2 <= N <= 202020

解法

N=i のときの問題の答えを dp[i] と置き、そのうち左端で a[1] < a[2] が成り立っているものだけの個数を dp2[i] と置く。n >= 2 のとき dp2[n] = dp[n] / 2 であり、0 <= n <= 1 のときは dp2[n] = dp[n] = 1 とする。
そうすると、挿入 DP の考え方で、n >= 2 のとき dp[n] = \sum_{j = 0}^{n - 1} dp2[j] * dp2[n - 1 - j] * C(n - 1, j) が言える。(n を j 番目に入れるとき、n の左側に置く数の選び方は C(n - 1, j) 通り、n の左右の並べ方はそれぞれ dp2[j], dp2[n - 1 - j] 通り。)
ep[i] := dp2[i] / i! と置くことにすると、n >= 2 のとき ep[n] = \sum_{j = 0}^{n - 1} ep[j] * ep[n - 1 - j] / n が言える。これは、左側からだんだん値が決まっていく畳み込みなので、分割統治しながら FFT をしていけば解ける。(O(N log^2 N) 時間)
さらに考察を進めることもできる。E := \sum_{n = 0}^{\infty} ep[i] x^i と置く。このとき、漸化式を E の式で表しなおすと、E = 1 + x/2 + \int_0^x E(t)^2/2 dt となる。両辺を微分すると  E' = (1 + E^2) / 2 となり、これを初期条件 E(0) = 1 の下で解くと E(x) = tan(x/2 + pi/4) = (1 + sin x) / cos x となる。sin, cos のテイラー展開は簡単にわかり、形式的冪級数の商は O(N log N) 程度で計算する方法があるので、全体で O(N log N) 時間で解ける。

登場する典型

実装上の注意点

  • FFT で元にする範囲、計算した結果を書き込む範囲に気をつける。今回の場合は以下の2つ:
    • [0, x) * [0, x) を [x, 2x) に書き込む
    • 2x <= lo のときに [0, 2x) * [lo, lo + x) の2倍を [lo + x, lo + 2x) に書き込む。2倍するのは [0, 2x) 側が左右両方に現れうるためで、2x まで見ないといけないのは lo -> lo + 2x - 1 みたいな遷移があり得るため。なお、FFT の幅は 2x でよい。長さ 2x のところで1周するが、1周した後の値は x 番目の左側にしか来ないため。
  • 初期値に気をつける
    • 今回は ep[0] = ep[1] = 1

提出: #414769 (Rust)
(動的 FFT)

fn rec(lo: usize, hi: usize, dp: &mut [ModInt], ep: &mut [ModInt],
       fac: &[ModInt], invfac: &[ModInt]) {
    let n = hi - lo;
    debug_assert!(n.is_power_of_two());
    if (lo, hi) == (0, 2) {
        dp[0] += 1;
        dp[1] += 1;
        ep[0] += 1;
        ep[1] += 1;
        return;
    }
    if n == 1 {
        return;
    }
    let mid = (lo + hi) / 2;
    rec(lo, mid, dp, ep, fac, invfac);
    // FFT
    let zeta = ModInt::new(5).pow((MOD - 1) / n as i64);
    let mut tmp = vec![ModInt::new(0); n];
    let mut tmp2 = vec![ModInt::new(0); n];
    for i in lo..mid {
        tmp[i - lo] = ep[i];
    }
    // Difference can be anything in [1, n - 1].
    for i in 0..n {
        tmp2[i] = ep[i];
    }
    fft::transform(&mut tmp, zeta, 1.into());
    fft::transform(&mut tmp2, zeta, 1.into());
    let mut invn = ModInt::new(n as i64).inv();
    // If not overlapping, multiply by two.
    if lo != 0 {
        invn *= 2;
    }
    for i in 0..n {
        tmp[i] = tmp[i] * tmp2[i] * invn;
    }
    fft::transform(&mut tmp, zeta.inv(), 1.into());
    for i in mid..hi {
        dp[i] += tmp[i - lo - 1] * fac[i - 1];
        ep[i] += tmp[i - lo - 1] * fac[i - 1] * invfac[i] * invfac[2];
    }
    rec(mid, hi, dp, ep, fac, invfac);
}

fn solve() {
    let out = std::io::stdout();
    let mut out = BufWriter::new(out.lock());
    macro_rules! puts {
        ($($format:tt)*) => (write!(out,$($format)*).unwrap());
    }
    input!(n: usize);
    const W: usize = 1 << 18;
    let (fac, invfac) = fact_init(W);
    let mut dp = vec![ModInt::new(0); W];
    let mut ep = vec![ModInt::new(0); W];
    rec(0, W, &mut dp, &mut ep, &fac, &invfac);
    //debugln!("{:?}", dp);
    //debugln!("{:?}", ep);
    puts!("{}\n", dp[n]);
}

まとめ

solved 数少なすぎ && そろそろ形式的冪級数ライブラリを整備しなければ…。

yukicoder No.951 【本日限定】1枚頼むともう1枚無料!

典型のはずなのにかなりハマった。
No.951 【本日限定】1枚頼むともう1枚無料! - yukicoder

問題

N 種類のピザがあり、i 番目のピザのコストは P[i] 円、美味しさは D[i] である。各ピザはちょうど1枚だけ売られている。以下の行動を好きな回数繰り返すことができる。

  • ピザを買う。そのピザの値段を P[i] 円としたとき、P[i] 円以下の残っているピザを一つ選び、0 円で買うことができる。

買ったピザの美味しさの和を最大にしたい。支払いを K 円以内にするとき、実現できる美味しさの和の最大値を求めよ。

解法

最適戦略としてどのようなものがありえるかを考察する。買ったピザの値段を高い順に並べたものを X_0, X_1, ..., X_{a - 1} とすると、この中で 0 円にすべきなのは X_1, X_3, ... である。値段の低い順番に見た時、以下のようなルールでピザを選んでいくのと同値である。

  • 「正規の金額でピザを買う」「0 円でピザを買う」「ピザを無視する」の3種類の行動を取ることができる。「0 円でピザを買う」は「0 円にできる権利」を使わないと選べない。最初「0 円にできる権利」を 1 回使うことができる。「0 円にできる権利」を使うと 1 個減り、正規の金額でピザを買うと「0 円にできる権利」は 1 回使える状態に戻る。最終的に「0 円にできる権利」は 1 回使える状態になっていないといけない。(最後の購入は正規の金額でなければならない)

0 円にできる権利はどの地点でも最大 1 回しか残っていない。よって、状態は [現在位置][使った金額][権利の残り回数] の O(NK) 状態である。

登場する典型

  • 最適戦略の形を考える
  • ナップサック DP などの、更新の方向が決まっている DP について、次元を一つ落とす
    • 遷移が DP[i][j] -> DP[i + 1][k] (常に j < k) の形をしている場合、逆からループすることで1次元で済ませることができる。
    • 今回の場合は、(使った金額, 権利の残り回数) の辞書順で考えるとよい

実装上の注意点

  • (P[i], D[i]) のソートを忘れない

提出:
#413247 (Rust, 高速化前)
#413250 (Rust, 高速化後)

(高速化後)

fn solve() {
    let out = std::io::stdout();
    let mut out = BufWriter::new(out.lock());
    macro_rules! puts {
        ($($format:tt)*) => (write!(out,$($format)*).unwrap());
    }
    input! {
        n: usize, k: usize,
        pd: [(usize, i64); n],
    }
    let mut pd = pd;
    pd.sort();
    const INF: i64 = 1 << 50;
    let mut dp = vec![[-INF; 2]; k + 1];
    dp[0] = [0, 0];
    // (j, 0) -> (j, 1), (j, 1) -> (j + p, 0) の遷移を一挙にやりたい。
    // (j, l) が大きくなる方向にしか遷移しないため、
    // (j, l) の辞書順の逆に遷移させればよい.
    for i in 0..n {
        let (p, d) = pd[i];
        for j in (0..k + 1).rev() {
            if j + p <= k {
                dp[j + p][0] = max(dp[j + p][0], dp[j][1] + d);
            }
            dp[j][1] = max(dp[j][1], dp[j][0] + d);
        }
    }
    let mut ma = 0;
    for i in 0..k + 1 {
        ma = max(ma, dp[i][0]);
    }
    puts!("{}\n", ma);
}

まとめ

こういう DP 配列を潰す系の高速化は、常識な気もする一方でどこにも書かれていない気がする。誰かまとめてほしい

PAKEN Programming Camp 2019 Day 1 - Speedrun O: りんごだいぼうけん

関係ないところを高速化しようとしてハマった。
りんごだいぼうけん

問題

H * W のグリッド上にリンゴが M 個、スタートとゴールがそれぞれ 1 個、壁が何個かある。リンゴを K 個以上回収してスタートからゴールまで最短距離で行け。

解法

M 個のリンゴ間、およびスタートからリンゴ、リンゴからゴールまでの距離を計算し、bitDP を行う。
距離の計算は、単純にダイクストラ法を使うと計算量が O(HWM log (HW)) ~= 4 * 10^8 になり落ちてしまうので、01BFS で線形 (O(HWM) ~= 2 * 10^7) にする。
bitDP は O(2^M M^2) ~= 4 * 10^8 かかるが、これでも通る。(おそらくキャッシュに乗りやすいため)

登場する典型

  • 01BFS
    • O(HWM log(HW)) だと落ちてしまうので
  • bitDP
    • 3s あれば N <= 20 くらいでも O(2^N N^2) で ok

実装上の注意点

頻繁に動く添字はなるべく多次元配列の最後の添字にするなどして、キャッシュに乗りやすいように書く

提出: https://onlinejudge.u-aizu.ac.jp/beta/review.html#PakenCamp19Day1/4077654 (Rust)

/*
 * Dijkstra's algorithm.
 * Verified by: AtCoder ABC035 (http://abc035.contest.atcoder.jp/submissions/676539)
 */

struct Dijkstra {
    edges: Vec<Vec<(usize, i64)>>, // adjacent list representation
}

/*
 * Code from https://doc.rust-lang.org/std/collections/binary_heap/
 */
#[derive(Copy, Clone, Eq, PartialEq)]
struct State {
    cost: i64,
    position: usize,
}

// The priority queue depends on `Ord`.
// Explicitly implement the trait so the queue becomes a min-heap
// instead of a max-heap.
impl Ord for State {
    fn cmp(&self, other: &State) -> Ordering {
        // Notice that the we flip the ordering here
        match other.cost.cmp(&self.cost) {
            std::cmp::Ordering::Equal => other.position.cmp(&self.position),
            x => x,
        }
    }
}

// `PartialOrd` needs to be implemented as well.
impl PartialOrd for State {
    fn partial_cmp(&self, other: &State) -> Option<Ordering> {
        Some(self.cmp(other))
    }
}


impl Dijkstra {
    fn new(n: usize) -> Self {
        Dijkstra { edges: vec![Vec::new(); n] }
    }
    fn add_edge(&mut self, from: usize, to: usize, cost: i64) {
        self.edges[from].push((to, cost));
    }
    /*
     * This function returns a Vec consisting of the distances from vertex source.
     */
    fn solve(&self, source: usize, inf: i64) -> Vec<i64> {
        let n = self.edges.len();
        let mut d = vec![inf; n];
        let mut que = std::collections::VecDeque::new();
        que.push_back(State {cost: 0, position: source});
        while let Some(State {cost, position: pos}) = que.pop_front() {
            if d[pos] <= cost {
                continue;
            }
            d[pos] = cost;
            for adj in &self.edges[pos] {
                if adj.1 == 0 {
                    que.push_front(State {cost: cost + adj.1, position: adj.0});
                } else {
                    que.push_back(State {cost: cost + adj.1, position: adj.0});
                }
            }
        }
        return d;
    }
}

fn main() {
    let out = std::io::stdout();
    let mut out = BufWriter::new(out.lock());
    macro_rules! puts {
        ($($format:tt)*) => (write!(out,$($format)*).unwrap());
    }
    input! {
        h: usize, w: usize, k: usize,
        a: [chars; h],
    }
    let mut dijk = Dijkstra::new(h * w);
    let dxy = [(1, 0), (0, 1), (-1, 0), (0, -1)];
    let mut st = 0;
    let mut en = 0;
    let mut apples = vec![];
    for i in 0..h {
        for j in 0..w {
            let v = i * w + j;
            match a[i][j] {
                'a' => apples.push(v),
                's' => st = v,
                'e' => en = v,
                _ => (),
            };
            if a[i][j] == '#' { continue; }
            for d in 0..4 {
                let (dx, dy) = dxy[d];
                let nx = i as i32 + dx;
                let ny = j as i32 + dy;
                if nx < 0 || nx >= h as i32 || ny < 0 || ny >= w as i32 {
                    continue;
                }
                let nx = nx as usize;
                let ny = ny as usize;
                if a[nx][ny] == '#' { continue; }
                dijk.add_edge(v, nx * w + ny, 1);
            }
        }
    }
    let m = apples.len();
    const INF: i64 = 1 << 20;
    let mut sdist = vec![0; m];
    {
        let tmp = dijk.solve(st, INF);
        for i in 0..m {
            sdist[i] = tmp[apples[i]];
        }
    }
    let mut tdist = vec![0; m];
    {
        let tmp = dijk.solve(en, INF);
        for i in 0..m {
            tdist[i] = tmp[apples[i]];
        }
    }
    let mut mat = [[0; 20]; 20];
    for i in 0..m {
        let tmp = dijk.solve(apples[i], INF);
        for j in 0..m {
            mat[i][j] = tmp[apples[j]] as i32;
        }
    }
    let mut dp = vec![[INF as i32; 20]; 1 << m];
    for i in 0..m {
        dp[1 << i][i] = sdist[i] as i32;
    }
    for bits in 0usize..1 << m {
        for j in 0..m {
            if (bits & 1 << j) == 0 { continue; }
            for i in 0..m {
                if (bits & 1 << i) != 0 { continue; }
                let to = bits ^ 1 << i;
                dp[to][i] = min(dp[to][i], dp[bits][j] + mat[j][i]);
            }
        }
    }
    let mut mi = INF as i32;
    for bits in 0usize..1 << m {
        if bits.count_ones() < k as u32 { continue; }
        for i in 0..m {
            if (bits & 1 << i) == 0 { continue; }
            mi = min(mi, dp[bits][i] + tdist[i] as i32);
        }
    }
    puts!("{}\n", if mi >= INF as i32 { -1 } else { mi });
}

まとめ

これでダイクストラではなく bitDP を高速化しようとずっと頑張っていたのは、勘が鈍っているとしか。

PAKEN Programming Camp 2019 Day 1 - Speedrun M: カードはおやつに入りますか?(Are Cards Snacks?)

ちょっとハマったのでメモ。
カードはおやつに入りますか?(Are Cards Snacks?)

問題

N 枚のカードがあり、i 枚目には整数 A[i] が書かれている。square1001 君はカードのうち何枚かを選んで合計 K にしたいので、最小の枚数のカードを除去して邪魔せよ。

解法

愚直にやったら (自分が残すカードの集合, square1001 君がとるカードの集合) の全探索で O(3^N) になる。これでは無理なので高速化を行う。
ある集合 S に対して、「S の部分集合であって、和をとると K になるものの個数」が高速に求めたい気分になるので、dp[S] = (S の和が K なら 1, そうでなければ 0) とした配列 dp に対して高速ゼータ変換を行えばよい。

登場する典型

高速ゼータ変換

実装上の注意点

なし

提出:
https://onlinejudge.u-aizu.ac.jp/beta/review.html#PakenCamp19Day1/4077478
(Rust)

fn solve() {
    let out = std::io::stdout();
    let mut out = BufWriter::new(out.lock());
    macro_rules! puts {
        ($($format:tt)*) => (write!(out,$($format)*).unwrap());
    }
    input! {
        n: usize, k: i64,
        a: [i64; n],
    }
    let mut dp = vec![0; 1 << n];
    for bits in 0..1 << n {
        let mut sum = 0;
        for i in 0..n {
            if (bits & 1 << i) != 0 {
                sum += a[i];
            }
        }
        dp[bits] = if sum == k { 1 } else { 0 };
    }
    for i in 0..n {
        for bits in 0..1 << n {
            if (bits & 1 << i) != 0 {
                continue;
            }
            dp[bits | 1 << i] += dp[bits];
        }
    }
    let mut mi = n;
    for bits in 0usize..1 << n {
        let bc = n - bits.count_ones() as usize;
        if dp[bits] == 0 {
            mi = min(mi, bc);
        }
    }
    puts!("{}\n", mi);
}

まとめ

O(3^N) で解きたくなったら高速ゼータ変換を疑うのが良いかもとは思った。(過適合か…?)

第一回日本最強プログラマー学生選手権-予選- E - Card Collector

いい加減マトロイドの基本をスラスラと思い出せるようにならないと非常にまずいと感じた。
E - Card Collector

問題

H 行 W 列のマス目の上に N 枚のカードが置かれている。i番目のカードは R[i] 行 C[i] 列に置かれており、整数 A[i] が書かれている。(同じマス目に2枚以上のカードが置かれる可能性もある。)
以下のようにカードを取るとき、取ったカードに書かれている整数の合計値としてありうるものの最大値を求めよ。

  • 各行から最大1枚取る。
  • その後、各列から最大1枚取る。その際、直前のステップで取ったカードは取れない。

解法

「マトロイドの上の貪欲法」の一言で片付けられるが、片付けずマトロイドについての定理をこの問題での場合に特殊化して記述する。

M をカード全体の集合とする。カードの集合 A に含まれるカードを全部取れるとき、集合 A を独立集合と呼ぶことにし、集合族 F を F := {A \subseteq M | 集合 A は独立集合} で定める。
以下の補題を示す。

(補題: 増加公理) 独立集合 A, B に対して、|A| > |B| が成り立つ場合、ある x \in A \setminus B が存在して  B \cup \{x\} は独立集合。

(証明)*1
 A = A0 \coprod A1, B = B0 \coprod B1 とし、A0, B0 は行ごとに最大1個、A1, B1 は列ごとに最大1個のカードが含まれるような集合とする。 |A| > |B| であるため、|A0| > |B0| か |A1| > |B1| のどちらかは成立する。一般性を失わず、|A0| > |B0| として良い。
A0 でカバーされていて B0 でカバーされていない行が存在するので、ある x \in A0 \setminus B0 が存在して、 B0 \cup \{x\} は行ごとに最大1個のカードしか含まない。

  1. そのような x であって、B1 に含まれないものが存在する場合
    x は B に含まれず  (B0 \cup \{x\}) \coprod B1 は独立集合である。
  2. そのような x がすべて B1 に含まれる場合
    そのような要素を B1 側から B0 側に持ってくることで、 B = A0 \coprod (B1 \setminus (A0 \setminus B0)) とできる。 C := B1 \setminus (A0 \setminus B0) と置くと |A1| > |C| であるため、列に対して同じ議論を行うことで、ある y \in A1 \setminus C が存在して  B \cup \{y\} は独立集合であることがわかる。(終)

増加公理を利用して、以下の貪欲を行う。

  1. 集合 S を  S := \emptyset で初期化する。
  2. 重み A[c] の大きい順にカードを取ることを試みる。カード c を取ろうとする時、 S \cup \{c\} が独立集合であれば、S に c を追加する。そうでなければ何もしない。
  3. 全てのカードをチェックした後の S が最適解である。

これが最適解を与えることの証明を与える。
(証明)*2
仮に S と異なる集合 T が最適解であったとする。両方とも極大なので、増加公理から |S| = |T| である。S の要素を A の値が大きい順に s_0, ..., s_{k - 1}, T の要素を A の値が大きい順に t_0, ..., t_{k - 1} とする。
初めて A[s_i] < A[t_i] が成り立つ i を j とする。C := {t_0, ..., t_j}, D := {s_0, ..., s_{j - 1}} と置くと、増加公理から C のある元 t_u があって  D \cup \{t_u\} は独立。
ここで、A[t_u] >= A[t_j] > A[s_j] であるため、貪欲で s_j が選ばれたという事実と矛盾する。(終)

最後に、ある集合 S が独立集合であるかどうかの判定を行うアルゴリズムを考える。*3 左側 H 頂点、右側 W 頂点の二部グラフを考え、カード i を、左側の R[i] と右側の C[i] を結ぶ重み付きの辺とする。取ったカードたちによる部分グラフを考えた時、各連結成分に対して (辺の本数) <= (頂点の個数) であることが、独立であることと同値なので、各連結成分に対して辺の本数と頂点の個数を管理すればよい。これは UnionFind などを用いてできる。

登場する典型

実装上の注意点

とくになし。

提出: #7329715 (Rust)

fn solve() {
    let out = std::io::stdout();
    let mut out = BufWriter::new(out.lock());
    macro_rules! puts {
        ($($format:tt)*) => (write!(out,$($format)*).unwrap());
    }
    input! {
        n: usize, h: usize, w: usize,
        rca: [(usize1, usize1, i64); n],
    }
    let mut ans = vec![];
    for (r, c, a) in rca {
        ans.push((a, r, c));
    }
    ans.sort();
    ans.reverse();
    let mut uf = UnionFind::new(h + w);
    let mut tol = vec![1; h + w];
    let mut tot = 0;
    for &(val, r, c) in &ans {
        let v = c + h;
        if !uf.is_same_set(r, v) {
            let a = uf.root(r);
            let b = uf.root(v);
            let sum = tol[a] + tol[b];
            if sum >= 1 {
                uf.unite(a, b);
                tot += val;
                let root = uf.root(a);
                tol[root] = sum - 1;
            }
        } else {
            let a = uf.root(r);
            if tol[a] >= 1 {
                tot += val;
                tol[a] -= 1;
            }
        }
    }
    puts!("{}\n", tot);
}

まとめ

各行最大1個、各列最大1個のマトロイドは、交差が二部マッチングからなる独立性システムになるという事実がよく知られているが、それが交差ではなく合併になっても効率的に解けるという点で面白かった。

*1:行ごと最大1個、列ごと最大1個が明らかにマトロイドであり、(M, F) はこれらの合併なのでマトロイドである、という証明をインライン展開した。

*2:この証明は任意のマトロイドに適用できる。

*3:独立性オラクルとしてこのような単純なアルゴリズムが使えるのはおそらくこの問題特有で、一般にはマトロイドの合併の独立性オラクルの実装は難しい気がする。識者のツッコミ待ちです

AtCoderで赤になるまでにやったこと

AtCoderで赤タッチしたのももう1.5年も前ですが書きます。覚えていないこと・抜け・漏れなどのオンパレードですがご容赦ください。

お前は誰

kobae964 - AtCoderです。2017年11月に初めてAtCoderでredになりました。


なんで今更これ書いたの

当時は面倒だったので書きませんでした。その後人々が変色時に記事を書いていくようになり、見かけた記事は大体全部読んでいました。
微笑ましいと思ったもののAtCoderの赤でそれをやった人を見たことがなかったので、せっかくなので書こうと思いました。すでに誰か書いていたらごめんなさい。

注意事項

筆者はAGCよりもARCの方が得意なため、AGCでの立ち回りは強い人に聞いてください。

赤になるまでにやったこと

問題を解いた

2000問くらい解きました。


使った知識・メタ典型

赤タッチするなら 蟻本 + 赤の人ならほとんどが知っている知識の半分 くらいが必要になると思います。
以下では蟻本上級編以上のレベルの内容を列挙していきます。列挙の漏れは100%確実にあります。

使えた知識 (これが問われたら30分以内にわかる)
知っていたが使いこなせなかった知識 (これが問われたら1時間以上かかる)
  • 包除原理 (2^n系包除, 約数系包除, Zeta/Hadamard変換全般, ポリアの数え上げ定理)
  • 行列累乗 (遷移を行列にエンコードするのが苦手だった)
  • スライド最小値
  • 区間スケジューリング
  • Convex Hull Trick
  • 分割統治
  • 複雑なDP
    • 実家DP (配列をセグメント木で管理して、一点更新/区間和などに高速に対応する)
    • 累積和を取りながらDP (今のAtCoderでは結構見る)
    • 挿入DP
    • 桁DP
    • K種類の物を順番に埋めていく時にindexが最後に埋めた物以外の(K-1)個できるやつ (問題例)
    • …列挙していったらキリがないなこれ
  • 最大長方形 (stackを使うやつ)
  • マンハッタン距離は回す (問題例)
  • 小さい場合に手許でbrute forceして分析
  • Prim法 (は?)
  • 誤読して時間を溶かさない
  • 変な方針を思いついた場合に、変であることに素早く気付く
    • 変な貪欲に突っ走らない
知らなかったけど後で必要になった知識
  • 集合をクラスタに分けるO(3^n)系DP (O(3^n)時間、O(2^n)空間で、dp[S] <- dp[T] * sub[S - T]みたいにするやつ)
  • 構築の手筋
    • 2ベキ
    • 必要条件を列挙して可能性を絞るテクニック
  • 必要条件を集めたらいつのまにか十分条件になってました系の考察
  • 計算量周りのテクニック
  • 木についてのテク (重心分解, HL分解)
  • MSTについての性質(マトロイド性、貪欲が効くことなど、問題例)
  • MSTのアルゴリズム (Boruvka法、Voronoi図を作る方法)
使わなかった知識
  • 枝刈り全探索
  • 幾何
  • 難しいデータ構造 (AtCoder以外では使った)
    • 遅延セグメント木
    • Sparse table
    • 平衡二分木
    • 平方分割

まとめ

赤を目指すには

  • 知識を増やす (汎用性の高い方法で覚えておくとよい)
  • なんとなくの考察 (第一感) の正確性を上げる (一発で正しい答えにたどり着ける確率を上げる)
  • 嘘解法についての嗅覚を鋭くする
  • 式変形を高速に、正確に行う
  • 知らないことでも実験して考える

とかが必要になる気がします。*1 いずれまた赤から落ちると思うのでそうなったらこれの通りにまた頑張ります。

ここまで読んでくださりありがとうございました。

赤になって得られたもの (追記 2019/7/1)

強い人と知り合いになれる確率がグッと高まる

赤になることに限定せず、強くなることによるメリットとして、いわゆる「いつもの勢」と呼ばれる、国内オンサイトコンテスト常連の人たちについての話をしない訳にはいかないでしょう。
赤になった年の翌年、入社した会社で強い人と知り合い、それがきっかけとなりいつもの勢の人々と知り合いになりました。いつもの勢の輪に入れているとは思いませんが、少なくとも観測できるようにはなったと言っていいです。彼らの競プロに対する考え方は、非常に参考になります。ストイックに精進したい人にはいい環境だと思います。

OpenCupに出場できる確率が高まる

これもコネが増えたことによる帰結です。
OpenCupについて、chokudaiさんなどが言及しているのをたまに目にする人がいるかもしれません。OpenCupというのは、ある期間日曜午後に (不定期に) 行われる、5時間チーム戦内輪コンテストです。*2 これも社にいた強い人に教えてもらい、幸運にも組んでいただける人を見つけることができました。精進したい人にはオススメです。

ARCがunratedになる

ARCみたいな面白いコンテストにunratedで出て新戦法を試すことができるのはメリットだと思います。多分tourist出しの練習をした人絶対いると思いますよ

Q. ユーザによっては一度に限り変更できる場合があるようですが、なぜ私は出来ないのでしょうか?

先日ユーザ名を一度だけ変更できる機能が実装されましたが、最大レートが2800以上のユーザはユーザ名の変更ができません。草

f:id:koba-e964:20190701021801p:plain
max rating >= 2800になると現れる文言

モチベーション維持の方法 (追記 2019/7/1)

ブランク期間の長さにペナルティをつける

自分の心の中のレート := 本来のレート - 100 / 1ヶ月 * ブランク期間 くらいにすると、ratedを避けるモチベがなくなっていいっすよ
これはAtCoder固有の事情ですが、ある程度の参加回数になると1回の大失敗で下げられるレートの上限が121 (= -800 * log_2(0.9)) になります。つまり36日ratedに出ないともう何やっても悪くなりません。無敵だな!

ポエム (ここから下は読む必要なし) (追記 2019/7/1)

私は高校時代、数学オリンピックに出ていましたが、ろくに何も精進しなくて本戦 (予選の次にある2番目のやつ) 止まりで、春合宿出場者やIMO出場者に対して羨望に近い憧れを抱いていました。そんな私が、高校時代から知ってはいたものの手を出せずにいた競技プログラミングに手を出したのが大学1年の時です。当時はTopCoder *3 がまだ盛んで、参加して緑落ちしては嘆き、黄色に昇格しては狂喜乱舞し、というのをやっていました。おそらく当時はUnionFindやbitDPすらまともに書けなかったと思います。レッドコーダーたちについては、尊敬の念をもって見ており、自分がなれるとは夢にも思っていませんでした。
転機と呼べるものがいつあったか、正確には思い出せませんが、大学3年くらいの時だと思います。演習で競プロみたいな内容のものがあり、競プロの面白さに目覚めました。そのときはyukicoderあたりを埋めまくって典型を覚えていったと思います。
本格的に取り組み始めたのは院生になってからだと思います。研究そっちのけで (は?) 競プロに打ち込み、M1の11月にオレンジになりました。そこからはより一層のめり込み、友達との食事の時間も考察に明け暮れる始末で (は?)、ratedのたびに2800以上のパフォーマンスを取っては赤パフォだと喜び、2400以下のパフォーマンスを取っては落ち込み、という繰り返しをしました。
途中からARCでパフォーマンス3200を取れるようになってきたので、このまま続けていればいずれは赤になれる、と徐々に確信できるようになりました。が、実際になれたときの喜びはひとしおでした。高校時代憧れの的でしかなかった国際科学オリンピック出場者に一歩だけ近づけたのだという思いが湧きました。

この先 (追記 2019/7/1)

誰か強くなる方法を教えてください m(_ _)m

*1:誰も「赤になる方法」みたいな記事を書きたがらないように見えるのは、こういう情報量ゼロの内容しかないからでは、と思っています。

*2:内輪なので参加するのはちょっと面倒です

*3:今は表記がTopcoderになっていますが、2012年頃はTopCoderだったと思います