Zenn
🏇

ABC202 write up

2021/05/31に公開
AtCoder
tech

abc202にバーチャル参加しました．
ABCの3完で終了後Dを解説ACしたので書きます．

A - Three Dice

3つのサイコロの目が与えられて，その目の反対の面の目の合計を出力する．
サイコロはある面とその反対の面の目を足し合わせると7になるので，7から出た目を引いてそれを足し合わせればOK．

a.rs
#![allow(unused_imports)]
#![allow(non_snake_case)]
use proconio::{fastout, input, marker::*};

fn main() {
    input! {
        mut a:usize,
        mut b:usize,
        mut c:usize
     }
    a = 7 - a;
    b = 7 - b;
    c = 7 - c;
    println!("{}", a + b + c);
}

B - 180°

0,1,6,8,9からなる文字列Sが与えられるので，Sを反転させて，
0 => 0
1 => 1
6 => 9
8 => 8
9 => 6
となるように変換する問題． 問題文に指示されたように文字列を弄る

b.rs
#![allow(unused_imports)]
#![allow(non_snake_case)]
use proconio::{fastout, input, marker::*};

fn main() {
    input! {
        s:Chars
    }
    for i in s.into_iter().rev() {
        let a = match i {
            '0' => '0',
            '1' => '1',
            '6' => '9',
            '8' => '8',
            '9' => '6',
            _ => '_',
        };
        print!("{}", a);
    }
    println!("");
}

C - Made Up

1 \leq i,j \leq NかつA_i = B_{C_j}であるような整数の組(i,j)の数を答える問題．
愚直にAとBを探索するとO(N^2)となってTLEするので，予めHashMapなどを使って数列B_{C_j}に出現する数字の種類と回数を記録して，Aに出現する数字がB_{C_j}に何回出てきたかを合計する事でO(N)でA_i = B_{C_j}の整数の組を数えられる．

c.rs
#![allow(unused_imports)]
#![allow(non_snake_case)]
use cmp::{max, min, Reverse};
use proconio::{fastout, input, marker::*};
use std::collections::*;
use std::*;

fn main() {
    input! {
        n:usize,
        a:[i64;n],
        b:[i64;n],
        c:[usize;n]
    }
    let mut h = HashMap::new();
    for i in c {
        *h.entry(b[i - 1]).or_insert(0) += 1;
    }
    dbg!(&h);
    let mut ans:i64 = 0;
    for i in a {
        ans += h.get(&i).unwrap_or(&0);
    }
    println!("{}", ans);
}

D - aab aba baa

むずかしかった...解説ACしました
A個のaとB個のbを並べた文字列を辞書順に並べた時，K番目の文字列を出力する問題．
辞書順配列は先頭の文字から考えると良いらしい．なので答えになる文字列をS_{ans}とする時，S_{ans}の先頭はaであるのかbであるのかを考える．
もし，S_{ans}の先頭がaの時，その後に続く文字列としてあり得る組み合わせの数は(A-1)+Bのどこにbを入れ込むかと考えれば{}_{(A-1)+B}C_{B}となる．(勿論{}_{(A-1)+B}C_{A}でも良い)
なのでKが{}_{(A-1)+B}C_{B}よりも小さければ必ずS_{ans}の先頭はaであり，そうでなければbであると確定できる．その後の文字もaを選択したならAから1引き，bを選択したならBから1引いて文字列を確定させていく．
イメージ的に2分探索みたいだな〜と思って書いてました．違うけど

d.rs
#![allow(unused_imports)]
#![allow(non_snake_case)]
use std::cmp::{max, min, Reverse};
use std::collections::*;
use proconio::{fastout, input, marker::*};
use num::integer::binomial;

fn main() {
    input! {
        mut a:i64,
        mut b:i64,
        mut k:i64
    }k -= 1;
    let n = a+b;
    let mut ans = String::new();
    for i in 0..n {
        if a > 0 {
            let aCb = binomial(a+b-1,b);
            if k < aCb {
                ans.push('a');
                a -= 1;
            }else{
                ans.push('b');
                b -= 1;
                k -= aCb;
            }
        }else{
            ans.push('b');
            b -= 1;
        }
    }
    println!("{}",ans);
}

もしかしたら別解？

試してないのでWAるかもしれませんが，Kを階乗進で表して求めるという方法もできる？のかなーなんて思っていました．いつかやりたい．

Discussion