bouzuya.hatenablog.com

ぼうずやのにっき

bouzuya/firestore-path 0.8.0 / ABC218 C

bouzuya/firestore-path 0.8.0 をつくった。

Rust で Firestore の path の操作を助ける crate 。

0.8.0 では効率性より利便性を重視して .clone() の呼び出しが少なくなるようにメソッド名を変更した。 .parent() などを呼び出すたびに .clone().parent() としていたのが不要になった。 .parent() のほか .root_document_name() も同様に。

以前のような self を取るメソッドは .into_* の形に変更した。

おまけで .parent_document_name() を追加した。 document_name.parent().parent() としていたのを document_name.parent_document_name() とできる。短くなっていないけど意味を読み取りやすいはず。

ABC218 : AtCoder Beginner Contest 218

  • C - Shapes https://atcoder.jp/contests/abc218/tasks/abc218_c
    • 提出: https://atcoder.jp/contests/abc218/submissions/49793082
    • 計算量の下げ方が思いつかなかったので O(N^4) 解法で解いた
    • 最初に # の個数の一致を確認しておく
    • これで S の # の位置だけ確認すれば T の # が多くて不一致になる状況を避けられる
    • 回転・平行移動の組み合わせで O(N^2) さらに一致の確認で O(N^4) になる
    • ただ実際には # のマスが範囲外にあることや不一致であることがわかった時点で抜けるようにしておく
    • 最悪ケースで TLE になりそうだけどパスした
use proconio::{input, marker::Chars};

fn rotate(s: &[Vec<char>]) -> Vec<Vec<char>> {
    let n = s.len();
    let mut t = vec![vec![' '; n]; n];
    for i in 0..n {
        for j in 0..n {
            t[j][n - 1 - i] = s[i][j];
        }
    }
    t
}

fn main() {
    input! {
        n: usize,
        mut s: [Chars; n],
        t: [Chars; n],
    };

    if s.iter()
        .map(|s_i| s_i.iter().filter(|&&c| c == '#').count())
        .sum::<usize>()
        != t.iter()
            .map(|t_i| t_i.iter().filter(|&&c| c == '#').count())
            .sum::<usize>()
    {
        println!("No");
        return;
    }

    for _ in 0..4 {
        let n2 = n as i64;
        for oi in -n2..=n2 {
            for oj in -n2..=n2 {
                let mut ok = true;
                'outer: for i in 0..n {
                    for j in 0..n {
                        if s[i][j] == '#'
                            && (!(0..n2).contains(&(i as i64 + oi))
                                || !(0..n2).contains(&(j as i64 + oj))
                                || t[(i as i64 + oi) as usize][(j as i64 + oj) as usize] != '#')
                        {
                            ok = false;
                            break 'outer;
                        }
                    }
                }
                if ok {
                    println!("Yes");
                    return;
                }
            }
        }
        s = rotate(&s);
    }
    println!("No");
}

今日のコミット。