練習メモ3-2

ARC 070
C: 二分探索
D: 二分探索したけどWAがとれないし部分点取る気もないしで、ダメ。
最近なんでWAが出るのか全くわからんみたいのが多いしデバッグ能力が死んでいる。

CF　405

Bはまあいつもどおり連結成分ごとに辺の数かぞえればいい。
Cが解けないのは病気。
Dはまあmod kでDPだよねとは思ったんだけどややこしくなって詰められなかった。
解説に実装楽な方法が書いてあったのでそれで解いたが、部分木の長さの合計にこれだけ足すとKで割れますよ〜というのを求めるらしい。

fn exec() {
    let mut sc = Scanner::new();
    let (n, k): (usize, usize) = (sc.ne(), sc.ne());
    let mut adj = vec![Vec::new(); n];
    for _ in 0..n - 1 {
        let u: usize = sc.ne::<usize>() - 1;
        let v: usize = sc.ne::<usize>() - 1;
        adj[u].push(v);
        adj[v].push(u);
    }
    fn subtract(a: usize, b: usize, k: usize) -> usize {
        let a = a as i32;
        let b = b as i32;
        let k = k as i32;
        (((a - b) % k + k) % k) as usize
    }

    fn dfs(adj: &Vec<Vec<usize>>,
           cur: usize,
           par: usize,
           depth: usize,
           k: usize)
           -> (i64, Vec<i64>, i64) {
        let mut ans = 0;
        let mut tsize = 1;
        let mut res = vec![0; k];
        res[depth % k] = 1;
        for &nxt in &adj[cur] {
            if nxt == par {
                continue;
            }
            let (child_size, ret, cans) = dfs(&adj, nxt, cur, depth + 1, k);
            ans += cans;
            tsize += child_size;
            for i in 0..k {
                for j in 0..k {
                    let dist = subtract(i + j, 2 * depth, k);
                    let need = subtract(k, dist, k) as i64;
                    ans += need * res[i] * ret[j];
                }
            }
            for i in 0..k {
                res[i] += ret[i];
            }
        }
        let n = adj.len() as i64;
        ans += tsize * (n - tsize);
        (tsize, res, ans)
    }
    let (_, _, ans) = dfs(&adj, 0, 0, 0, k);
    println!("{}", ans / (k as i64));
}

depthを持たせると手動でずらさなくてもいいっていうのは頭いいなと思った。

それにしても、ここ二週間マラソンマッチとPCゲームしかしていなかったのでかなり鈍っている。

Russian Code Cup 2017 Warm up
参加者少なかった。問題はわりと実装よりだったので特にメモとかはいいかな。

JOI春合宿　オープンコンテスト
一応問題は全部読んだけど、難しすぎる。
一日目
部分点すら解けない。
二日目
普通に解けない。
三日目
Long Mansionの部分点はセグ木で取れそうだったか、微妙にバグって終了した。
Long Distance Coachは面白そうだったけど結局解いてない。
四日目
誘拐2の部分点は自明なメモ化再帰で取れた。
Cityは素数をかけ算すればいいかなと思ったけど64bitすら超えそうなので無理だった。8点は取れたけど。