AtCoder Beginner Contest 258 - zeronosu77108’s blog

A - When?

60 を超えたら 1時間足されて、 60 を引いた余りが分に足されるので、時間の方に $K$ を 60 で割って切り捨てた物、分の方に $K$ を 60 で割った余りを足してあげると良いです。後は、2桁 0 埋めして良い感じに出力。

fn main() {
    input! {
        k : usize
    }

    println!("{:02}:{:02}", 21 + k/60, k % 60);
}

提出

B - Number Box

問題文

B にしては難しくないですか？始点を決めて、8方向どっちに進む続けるか決めて $N-1$ 回進んでみると良いです。適当に剰余するといいんですが Rust だと負になったりするとめんどくさいので自分でリセット書きました。

fn main() {
    input! {
        n : usize,
        a : [Bytes; n]
    }

    let a = a.into_iter().map(|a| a.iter().map(|&a| (a - b'0') as usize).collect_vec()).collect_vec();

    let mut ans = 0;
    for i in 0..n { for j in 0..n {
        for (dx, dy) in vec![(!0, !0), (1, !0), (!0, 1), (1, 1), (0, !0), (!0, 0), (1, 0), (0, 1)] {
            let mut y = i;
            let mut x = j;
            let mut now = a[y][x];
            for _ in 0..n-1 {
                x = x.wrapping_add(dx);
                y = y.wrapping_add(dy);

                if n == x { x = 0; }
                if n == y { y = 0; }
                if n <= x { x = n-1; }
                if n <= y { y = n-1; }
                now = now*10 + a[y][x];
            }
            ans = ans.max(now);
        }
    }}

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

提出

C - Rotation

問題文

末尾の文字を 1文字削除、先頭に追加を繰り返すと1回につき先頭の index が -1 される感じになります。例えば、 abc に 2回操作すると bca になりますね。これは先頭の index が $0$ → $-1 (n-1)$ → $-2(n-2)$ という感じに遷移していると考えられます。そこから $X$ 文字は良い感じに足して剰余取ってあげると分かります。

fn main() {
    input! {
        n : usize,
        q : usize,
        s : Chars,
        queries : [(u8, Usize1); q]
    }

    let mut now = 0;
    let mut ans = vec![];
    for (t, x) in queries {
        match t {
            1 => { now += n - x - 1; now %= n; }
            2 => { ans.push(s[(now + x) % n]); }
            _ => unreachable!()
        }
    }

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

提出

D - Trophy

問題文

1番から順番にしかプレイできないので、まぁ順番にクリアしていくことを考えます。 $i$ 番目のステージをクリアしたときに残りの $X - i$ 回をどうするか考えるんですが、 $i$ より前のステージを繰り返しクリアするのはその前の段階でやる方が最適なので考える必要がありません。よって、 $i$ 番目までクリアしたときは $i$ 番目を残りの $X - i$ 回クリアしたときの時間を求めてその最小値を求めたら良いです。

fn main() {
    input! {
        n : usize,
        mut x : usize,
        ab : [(usize, usize); n]
    }
 
    let mut ans = std::usize::MAX;
    let mut sum = 0;
    for (a, b) in ab {
        sum += a + b;
        x -= 1;
 
        ans = ans.min(sum + x * b);
    }
 
    println!("{}", ans);
}

提出

提出した瞬間に $x < n$ の場合にバグりそう～って思ったんですが、何故か AC しました。よく考えたら $x$ を usize で受け取っていたのでめちゃくちゃでかい値になってどうにかなりました（？）本来ならこう書くべきでした提出。

E - Packing Potatoes

問題文

見てすぐここスタートにしたらどこまで行くかダブリングするか～って思いました。$\sum W_i$ よりも $X$ が大きい場合に注意して実装すると良いです…。この問題はもっと早く解けたなぁという感じ。

fn main() {
    input! {
        n : usize,
        q : usize,
        x : usize,
        w : [usize; n],
        k : [usize; q]
    }
 
 
    const LOG : usize = 40;
    let mut tab = vec![vec![0; n]; LOG+1];
 
    let w = w.into_iter().cycle().take(2*n).collect_vec();
 
    let mut csum = vec![0; w.len()+1];
    for i in 0..w.len() { csum[i+1] = csum[i] + w[i]; }
 
    let c = (x-1) / csum[n];
    let x = x % csum[n];
    for i in 0..n { tab[0][i] = csum.lower_bound(&(csum[i] + x)) % n; }
    for i in 0..LOG { for j in 0..n { tab[i+1][j] = tab[i][tab[i][j]]; }}
 
    let mut ans = Vec::with_capacity(n);
    for k in k {
        let mut pref = 0;
        for i in 0..LOG {
            if (k-1) >> i & 1 == 1 {
                pref = tab[i][pref];
            }
        }
 
        let now = tab[0][pref];
 
        let c = if now <= pref { n - pref + now } else { now - pref } + c * n;
        ans.push(c);
    }
 
    println!("{}", ans.iter().join("\n"));
}

提出

F - Main Street

問題文

見た感じ苦手問題なので飛ばしました。

G - Triangle

問題文

コンテスト中に解けず…。

$ \mathcal {O} ( N ^ 3 ) $ 通りそうだなぁと思って出してみたんですが、 Rust では通らず…。 C++ なら通ったっぽい。 C++ で書けば良かった～～～。 $i, j \ (i < j)$ を決め打って考えたときに、 $i, j$ よりも頂点番号が大きい奴で両方に繋がっている奴を見つけたら良いです。愚直にやると $ \mathcal {O} ( N ^ 3 ) $ になるんですが、 bitset で管理すると64倍高速化できます。

うーん…。最近 bitset 使ってなかったから全然思い浮かばなかったなぁ。 $i, j$ を小さい順に考えると、良い感じに $k$ を求められないかとは考えていたんだけど、残念。

こういう問題、出しても良いけど問題としては面白くないなぁ……。

fn main() {
    input! {
        n : usize,
        a : [Bytes; n]
    }
 
    let mut g = vec![bitset_fixed::BitSet::new(n); n];
    for i in 0..n {
        g[i] = bitset_fixed::BitSet::new(n);
        for j in i+1..n {
            if a[i][j] == b'0' { continue }
            g[i].set(j, true);
        }
    }
 
    let mut ans : usize = 0;
    for i in 0..n { for j in i+1..n {
        if a[i][j] == b'0' { continue }
        ans += (&g[i] & &g[j]).count_ones() as usize;
    }}
 
    println!("{}", ans);
}