子どものじゃんけん。

上の子は下の子と揉めたときに「じゃんけんで決めよう」と言う。下の子はずっとグーかずっとチョキを出し続けるので、最初にグーであいこなら次がパーで必勝なのを上の子は把握している。

上の子はなぜか「おおさかじゃんけん」という負けたもの勝ちのじゃんけんをする。下の子も負けたときに負けてないおおさかじゃんけんと言い張るようになった。

PAST #3 第三回 アルゴリズム実技検定 過去問

• M - 行商計画問題 https://atcoder.jp/contests/past202005-open/tasks/past202005_m
  • 提出: https://atcoder.jp/contests/past202005-open/submissions/49653213
  • 巡回セールスマン問題
  • 事前に N 個の街と道のグラフを、出発する街と K 個の街の K+1 個の街と街と街を結ぶ (距離をコストとする) グラフに変換しておく
  • K <= 16 なので後は巡回セールスマン問題の要領で bitDP をする

use std::vec;

use proconio::{input, marker::Usize1};

macro_rules! chmin {
    ($min_v: expr, $v: expr) => {
        if $v < $min_v {
            $min_v = $v;
            true
        } else {
            false
        }
    };
}

fn dijkstra(n: usize, inf: usize, e: &[Vec<usize>], s: usize) -> Vec<usize> {
    use std::{cmp::Reverse, collections::BinaryHeap};
    let mut d = vec![inf; n];
    let mut pq = BinaryHeap::new();
    d[s] = 0;
    pq.push(Reverse((0, s)));
    while let Some(Reverse((w_u, u))) = pq.pop() {
        if w_u > d[u] {
            continue;
        }
        for v in e[u].iter().copied() {
            let w = w_u + 1;
            if w < d[v] {
                d[v] = w;
                pq.push(Reverse((w, v)));
            }
        }
    }
    d
}

fn main() {
    input! {
        n: usize,
        m: usize,
        uv: [(Usize1, Usize1); m],
        s: Usize1,
        k: usize,
        t: [Usize1; k],
    };

    let inf = 1 << 60;
    let dist = {
        let mut edges = vec![vec![]; n];
        for (u, v) in uv {
            edges[u].push(v);
            edges[v].push(u);
        }
        let mut dist = vec![vec![0_usize; k + 1]; k + 1];
        for i in 0..=k {
            let d = dijkstra(n, inf, &edges, if i == k { s } else { t[i] });
            for j in 0..k {
                dist[i][j] = d[t[j]];
                dist[j][i] = d[t[j]];
            }
        }
        dist
    };

    let mut dp = vec![vec![inf; k + 1]; 1 << (k + 1)];
    dp[0][k] = 0;
    for i in 0..=k {
        chmin!(dp[1 << i][i], dist[k][i]);
    }
    for bits in 1..1 << (k + 1) {
        for i in 0..=k {
            if (bits & (1 << i)) != 0 {
                for j in 0..=k {
                    chmin!(dp[bits][j], dp[bits ^ (1 << i)][i] + dist[i][j]);
                }
            }
        }
    }
    let ans = dp[(1 << (k + 1)) - 1].iter().copied().min().unwrap();
    println!("{}", ans);
}

今日のコミット。

• rust-atcoder 1 commit
  • past202005-open m