AtCoder Beginner Contest 264 - zeronosu77108’s blog

5完 120:12 （6ペナ + 30:00 ) 506位でした。 F 問題沼ったのがかなり悔しいです。これ初手提出の時点で解けているべき感じの問題だった…。

A - "atcoder".substr()

Rust で非常にめんどくさい問題…。頑張って実装します。

fn main() {
    input! {
        l : Usize1,
        r : usize
    }

    let atcoder = "atcoder".chars().collect_vec();
    println!("{}", atcoder[l..r].iter().join(""));
}

提出

B - Nice Grid

問題文

一瞬、黒か白かの2次元配列を書きそうになったんですが、よく考えると一番近い壁までの距離の偶奇で白か黒か決まります。後は良い感じに。

fn main() {
    input! {
        r : Usize1,
        c : Usize1
    }

    let f = r.min(14 - r).min( c.min(14 - c) );
    println!("{}", if f % 2 == 0 {"black"} else {"white"});
}

提出

C - Matrix Reducing

問題文

$H, W$ が小さいので、 $A$ のどの行・列を採用するか全探索します。本当は、探索範囲を絞った方が良いと思うんだけど、めんどくさいので本当に全探索。まぁ絞った方が良かったね（779ms）

itertools の combinations とか使って探索範囲をまともにしたら 19ms になった。

fn main() {
    input! {
        h1 : usize,
        w1 : usize,
        a : [[usize; w1]; h1],
        h2 : usize,
        w2 : usize,
        b : [[usize; w2]; h2]
    }
 
    let mut ok = false;
    'e:for s1 in 1..(1<<h1) {
        for s2 in 1..(1<<w1) {
            let mut a2 = vec![];
            for i in 0..h1 {
                if (s1 >> i) & 1 == 0 { continue }
                let mut t = vec![];
                for j in 0..w1 {
                    if (s2 >> j) & 1 == 0 { continue }
                    t.push(a[i][j]);
                }
                a2.push(t);
            }
            if a2 == b { ok = true; break 'e;}
        }
    }
 
    println!("{}", if ok {"Yes"} else {"No"});
}

提出
 修正版

D - "redocta".swap(i,i+1)

問題文

"atcoder" の並び変えた文字列しか与えられないので、すごく雑なことをしても大体間に合います。転倒数とか考えたんですが、ライブラリとか無いので愚直に swap かけていきます。とりあえず 'a' を先頭に持ってくる、 't' を 2桁目に持ってくるという感じにします。

fn main() {
    input! {
        mut s : Chars
    }
 
    let atcoder = "atcoder".chars().collect_vec();
    let n = atcoder.len();
    let mut ans = 0;
    for i in 0..n {
        let mut index = s.iter().position(|&c| c == atcoder[i]).unwrap();
        while index > i {
            s.swap(index - 1, index);
            ans += 1;
            index -= 1;
        }
    }
 
    println!("{}", ans);
}

提出

E - Blackout 2

問題文

連結成分の管理なので Union-Find を使いたくなります。切るという操作はめんどくさいので、クエリを逆向きにして繋ぐという操作をやっていきます。後は、発電所に繋がっているかどうかを考えれば良いんですが、適当に新しい頂点を作ってそこに全部発電所を繋いでおけば良いです（発電所の番号は隣り合っているので超頂点じゃなくても良かったです）。後はその頂点の連結成分 - (m + 1) をしたら発電所と繋がっている都市の数が分かります。

fn main() {
    input! {
        n : usize,
        m : usize,
        e : usize,
        edges : [(Usize1, Usize1); e],
        queries : [Usize1]
    }

    let mut cut = vec![false; e];
    for q in queries.iter() { cut[*q] = true; }

    let mut uni = UnionFind::new(n + m + 1);
    let r = n + m;

    for i in n..n+m { uni.merge(r, i); }

    for (i, &(u, v)) in edges.iter().enumerate() {
        if cut[i] { continue }
        uni.merge(u, v);
    }

    let mut ans = Vec::with_capacity(queries.len());
    for &x in queries.iter().rev() {
        ans.push(uni.size(r) - m - 1);
        uni.merge(edges[x].0, edges[x].1);
    }

    println!("{}", ans.iter().rev().join("\n"));
}

提出

F - Monochromatic Path

問題文

沼った。DP っぽいものは書いてたんだけど、なぜかダイクストラみたいにやっていたし、超絶雑な場合分けで実装ゴリゴリになってた…。うーむ…。

結局優先度付キューを普通のキューにして通したけど、まぁループでも書けるね。これはもっと早く解けるべきですね。↓ のコードは修正版。

fn main() {
    input! {
        h : usize,
        w : usize,
        r : [usize; h],
        c : [usize; w],
        a : [Chars; h]
    }

    const MAX : usize = std::usize::MAX / 10;
    // const MAX : usize = 100;
    let mut dist = vec![vec![vec![vec![MAX; w]; h]; 2]; 2];
    dist[0][0][0][0] = 0;
    dist[1][0][0][0] = r[0];
    dist[0][1][0][0] = c[0];
    dist[1][1][0][0] = r[0] + c[0];
    let mut pq = VecDeque::new();

    pq.push_back((Reverse(0), 0, 0, 0, 0));
    pq.push_back((Reverse(r[0]), 1, 0, 0, 0));
    pq.push_back((Reverse(c[0]), 0, 1, 0, 0));
    pq.push_back((Reverse(r[0] + c[0]), 1, 1, 0, 0));

    for y in 0..h { for x in 0..w { for f1 in 0..2 { for f2 in 0..2 {

        // → に移動
        if x+1 < w {
            let ny = y;
            let nx = x + 1;

            if (f2 == 1 && a[y][x] != a[ny][nx]) || (f2 == 0 && a[y][x] == a[ny][nx]) {
                if dist[f1][0][ny][nx] > dist[f1][f2][y][x] {
                    dist[f1][0][ny][nx] = dist[f1][f2][y][x];
                }
            } else {
                if dist[f1][1][ny][nx] > dist[f1][f2][y][x] + c[x + 1] {
                    dist[f1][1][ny][nx] = dist[f1][f2][y][x] + c[x + 1];
                }
            }
        }


        // ↓ に移動
        if y+1 < h {
            let ny = y + 1;
            let nx = x;

            if (f1 == 1 && a[y][x] != a[ny][nx]) || (f1 == 0 && a[y][x] == a[ny][nx]) {
                if dist[0][f2][ny][nx] > dist[f1][f2][y][x] {
                    dist[0][f2][ny][nx] = dist[f1][f2][y][x];
                }
            } else {
                if dist[1][f2][ny][nx] > dist[f1][f2][y][x] + r[y + 1] {
                    dist[1][f2][ny][nx] = dist[f1][f2][y][x] + r[y + 1];
                }
            }
        }
    }}}}


    let mut ans = std::usize::MAX;
    ans = ans.min(dist[0][0][h-1][w-1]);
    ans = ans.min(dist[0][1][h-1][w-1]);
    ans = ans.min(dist[1][0][h-1][w-1]);
    ans = ans.min(dist[1][1][h-1][w-1]);

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