Codeforces Round #786 (Div. 3) - zeronosu77108’s blog

Codeforces Round #786 (Div. 3) 。苦手の詰め合わせ。

6ペナ4完。

A. Number Transformation

$x,y$ が与えられるので、$y = x \times b ^ a$ な形にできるかという問題。最初素因数分解して良い感じにゴニョゴニョしよ～って思ってたんだけど、なんかめっちゃペナった。何がダメかと考えていたんだけど、 $y$ が小さいので雑に全探索するようにした。

制約が小さい時は愚直にやりましょう…

というかよく考えたら、 $x$ で割り切れたら、 $(y/x) ^ 1$ で良いじゃん。

fn solve() {
    let (mut x,mut y) : (usize, usize) = input_t();
    if y % x != 0 { println!("0 0"); return; }
    y /= x;

    if y == 1 { println!("1 1"); return; }

    for i in 2..=y {
        let mut t = y;
        let mut cnt = 0;
        while t % i == 0 { cnt+=1; t/=i; }
        if t == 1 { println!("{} {}", cnt, i); return; }
    }

    println!("0 0");
}

提出

B. Dictionary

問題文

癒やし枠。同じアルファベットは使わず2文字の単語を順番良く生成しておいて、それが何番目か出力したら良い。

fn main() {
    let mut mp = BTreeMap::new();
    let mut cnt = 1;
    f(&mut vec![], &mut mp, &mut cnt);

    let t : usize = input();
    for _ in 0..t {
        let s  = input::<String>();
        println!("{}", mp[&s]);
    }
}

fn f(c:&mut Vec<char>, mp:&mut BTreeMap<String, usize>, cnt:&mut usize) {
    if c.len() == 2 {
        mp.insert(c.iter().collect::<String>(), *cnt);
        *cnt += 1;
        return;
    }

    for i in 0..26 {
        let ch = (b'a' + i) as char;
        if c.len() == 1 && c[0] == ch { continue }
        c.push(ch);
        f(c, mp, cnt);
        c.pop();
    }
}

提出

C. Infinite Replacement

問題文

これも癒やし枠。 $S$ の中にある 'a' を $T$ に置き換える操作を何回かできる。その操作をして得られる文字列の種類数を求める問題。

$T$ が1文字で、それが 'a' であるなら、どんなに置き換えても結果は変わらないので、 $1$種類。$T$ の中に 'a' が含まれていて、長さが $1$ より大きいなら無限種類作れるので -1。後は、 $S$ の中の 'a' を置き換える/置き換えないの2種類が 'a' の個数分選択できるので、$S$ に含まれる 'a' の個数を $x$ とすると 2^x が答え。

fn solve() {
    let s : Vec<_> = input::<String>().chars().collect();
    let t : Vec<_> = input::<String>().chars().collect();
 
    if t.len() == 1 && t[0] == 'a' { println!("1"); return; }
    if t.contains(&'a') && t.len()>1 { println!("-1"); return; }
 
    let cnt = s.iter().filter(|&&c| c == 'a').count() as u32;
    println!("{}", 2usize.pow(cnt));
}

提出

D. A-B-C Sort

問題文

苦手。$N$ が偶数のとき、$A_0$ と $A_1$ の好きな方を $C_0$ にして、残った方を $C_1$ にすることができる。その後ろも同様に $2$ 個ずつ考えると良い。$N$ が奇数のとき、 $A_0$ は必ず $C_0$ に行く。その後は、偶数のときと同じように2個ずつ好きに swap して配置できる。後は、良い感じに配置して非減少な列にできるか判定したら良い（もうちょっと良い感じに処理まとめても良かったかも）。

fn solve() {
    let n : usize = input();
    let a : Vec<usize> = input_vec();
 
    let mut min = 0;
    if n % 2 == 0 {
        for i in (0..n).step_by(2) {
            let x = a[i].min(a[i+1]);
            let y = a[i].max(a[i+1]);
 
            if x < min { println!("NO"); return; }
            min = min.max(y);
        }
    }
 
    if n % 2 == 1 {
        min = a[0];
        for i in (1..n).step_by(2) {
            let x = a[i].min(a[i+1]);
            let y = a[i].max(a[i+1]);
            if x < min { println!("NO"); return; }
            min = min.max(y);
        }
    }
 
    println!("YES");
}

提出

修正するとこんな感じ？

E. Breaking the Wall

問題文

嫌い嫌い嫌い！算数をさせるな！！！本番中解けなかった…

2箇所遠く離れた場合は、それぞれ $2$ で割って切り上げしたやつの最小を足したとき。後は、連続する $3$ 箇所と、連続する $2$ 箇所で良い感じにやる方法を考えると良い。

連続する $3$ 箇所は、$3$ 箇所であることを使いたいのでとりあえず真ん中を連打して、両サイドの小さいをなくす。後は、真ん中か余ってる方を消せば良いので小さい方をまた切り上げで出す。

連続する $2$ 箇所。これが爆発してた。連続する箇所の値を $x, y$ とすると $\max(\lceil x/2 \rceil, \lceil y/2 \rceil, \lceil (x + y) / 3 \rceil)$ が最小手数。

fn main() {
    let n : usize = input();
    let a : Vec<usize> = input_vec();

    let mut ans = std::usize::MAX;
    for i in 0..n {
        let mut v = vec![];
        if i>0 { v.push(a[i-1]); }
        if i+1<n { v.push(a[i+1]); }

        v.sort();
        let c = v[0];
        let x = a[i].saturating_sub(2*c);
        let y = if v.len()>1 { v[1] - c } else {std::usize::MAX};

        ans = ans.min(c + (x.min(y)+1)/2);
    }

    let mut v = a.iter().map(|&i| (i+1)/2).collect::<Vec<_>>();
    v.sort();
    ans = ans.min(v[0] + v[1]);

    for a in a.windows(2) {
        let x = (a[0] + 1) / 2;
        let y = (a[1] + 1) / 2;
        let z = (a[0] + a[1] + 2) / 3;
        ans = ans.min(x.max(y).max(z));
    }
    println!("{}", ans);
}