AtCoder Beginner Contest 247 - zeronosu77108’s blog

A - Move Right

二進法表記されたやつを右シフトしてください。みたいな問題。受け取るのがめんどくさいので Vec<char> みたいなもので受け取って rotate_right して先頭を '0' にしたら OK。

fn main() {
    input! {
        mut s : Chars
    }
 
    s.rotate_right(1);
    s[0] = '0';
    println!("{}", s.iter().join(""));
}

提出

B - Unique Nicknames

問題文

なんですか？この問題。姓か名のどちらかが他の人の姓・名と被っていなければ OK。フラグ持ってやれば良い。

fn main() {
    input! {
        n : usize,
        st : [(String, String); n]
    }
 
    let mut used = vec![vec![false; 2]; n];
    for (i, (s,t)) in st.iter().enumerate() {
        let mut sf = true;
        let mut tf = true;
        for (j, (sj, tj)) in st.iter().enumerate() {
            if i == j { continue }
            sf &= !(s==sj || s==tj);
            tf &= !(t==sj || t==tj);
        }
 
        if !sf && !tf { println!("No"); return; }
    }
 
    println!("Yes");
}

提出

C - 1 2 1 3 1 2 1

問題文

定義が再帰的になっている。$N \leq 16$ なので雑に f(n-1) + n.to_storing() + f(n-1) みたいなことをしたら良いです。

fn main() {
    input! {
        n : usize,
    }
 
    println!("{}", f(n));
}
 
fn f(n:usize) -> String {
    if n == 1 { return "1".to_string() }
    let mut res = "".to_string();
    let s1 = f(n-1);
    res.push_str(&s1);
    res.push(' ');
    res.push_str(&n.to_string());
    res.push(' ' );
    res.push_str(&s1);
    res
}

提出

D - Cylinder

問題文

最初 $c$ 回 deque に push しようと思ったけど $c \leq 10⁹$ なのでランレングス圧縮したような状態でもって、取り出したときに調整します。余ったら push_front して戻しておきます。

fn main() {
    input! { q : usize }
 
    let mut a = VecDeque::new();
    let mut ans = vec![];
    for _ in 0..q {
        input! { t : u8 }
        match t {
            1 => {
                input! { (x, c) : (usize, usize) }
                a.push_back((x, c));
            }
            2 => {
                let mut sum = 0;
                input! { mut c : usize }
                while c > 0 {
                    let (x, mut d) = a.pop_front().unwrap();
                    let b = c.min(d);
                    sum += x * b;
                    c -= b; d -= b;
                    if d != 0 { a.push_front((x, d)); }
                }
                ans.push(sum);
            }
            _ => unreachable!()
        }
    }
 
    println!("{}", ans.iter().join("\n"));
}

提出

E - Max Min

問題文

なんか最初に良い方針が思いつかなくて焦っちゃったかも。めちゃくちゃ迷走した。途中で左端を固定して二分探索っていうまともそうな方針をたてたんだけど、バグらせて無事死亡。

結局、$Y \leq A_i \leq X$ となる範囲を切り出して、そこでしゃくとり法をするようにした。最終的には楽そうな実装にできたけど、うーん……。良くなかった。

fn main() {
    input! {
        n : usize,
        x : usize,
        y : usize,
        a : [usize; n]
    }
 
    let mut v = split(y, x, a);
 
    let mut ans = 0;
    let mut cnt = BtreeMultiSet::new();
 
    for v in v {
        let mut j = 0;
        let mut yf = false;
        let mut xf = false;
 
        for i in 0..v.len() {
            if j < i { j = i; yf=false; xf=false; }
            while (!yf || !xf) && j<v.len() {
                if v[j] == y && !cnt.contains(&y) { yf = true; }
                if v[j] == x && !cnt.contains(&x) { xf = true; }
                cnt.add(v[j]);
                j += 1;
            }
 
            if yf && xf { ans += v.len() + 1 - j; }
            cnt.remove(v[i]);
            yf &= cnt.contains(&y);
            xf &= cnt.contains(&x);
        }
    }
 
    println!("{}", ans);
}
 
 
fn split(min:usize, max:usize, a:Vec<usize>) -> Vec<Vec<usize>>{
    let mut res = vec![];
    let mut tmp = vec![];
    for &a in a.iter() {
        if !(min..=max).contains(&a) {
            if tmp.is_empty() { continue }
            res.push(tmp.clone());
            tmp.clear();
        } else { tmp.push(a); }
    }
    if !tmp.is_empty() { res.push(tmp.clone()); }
    res
}

提出

F - Cards

問題文

本番中にあんまり読めなかった……。焦って読んだからかあんまり問題の意味を理解してなかったし、本番中に解けなかった。

いくつかのカードを選んで、$1$ ～ $N$ 全ての数があるようにしたい。$P$ と $Q$ は順列なので、カードに書かれている数を繋ぐといくつかのサイクルに分かれる。それのなんかの値のかけ算になる。頂点が1つだと $1$、 2だと $3$（どちらか片方+両方）、みたいに計算して OEIS に投げるとリュカ数というそれっぽいやつが出てくる。なんか良い感じに計算したら良い。

fn main() {
    input! {
        n : usize,
        p : [Usize1; n],
        q : [Usize1; n]
    }
 
    let mut uni = UnionFind::new(n);
    for (p, q) in p.into_iter().zip(q) { uni.merge(p, q); }
 
    let mut memo = FxHashMap::default();
    let roots = (0..n).filter(|i| *i == uni.root(*i)).collect_vec();
    let ans = roots.iter().map(|&i| f(uni.size(i), &mut memo)).fold(1, |acc,v| (acc * v) % MOD);
    println!("{}", ans);
}
 
fn f(n:usize, memo:&mut FxHashMap<usize,usize>) -> usize {
    if n==0 { return 2 }
    if n==1 { return 1 }
    if let Some(res) = memo.get(&n) { return *res }
 
    let res = (f(n-1, memo) + f(n-2, memo)) % MOD;
    memo.insert(n, res);
    res
}

提出

G - Dream Team

問題文

本番中にチラッと読んだんだけど、なんとなーく最小費用流みを感じて「使ったこと無いし…」って諦めちゃった。500点取ってもあんまり順位上がらないので、こちらを頑張った方が良かったかもしれない。

所属大学と得意分野のマッチングで、人が辺だと考えると重み付き二部マッチングになる。MinCostFlow に min_cost_slope というのが合って、流量とコストの関係を折れ線グラフで返してくれる関数があるので、それを使う。が、なぜかグラフの形を間違えてバグらせる。折れ線グラフで間がないので復元（？）をして出力すると良い（僕は Rust版ACL をお借りした）。

fn main() {
    input! {
        n : usize,
        edges : [(Usize1, Usize1, i64); n]
    }
 
    let mut g = MinCostFlowGraph::new(450);
    const S : usize = 400;
    const T : usize = 401;
    const B : usize = 150;
    const BASE : i64 = 1_000_000_000_000_000;
 
    for i in 0..B {
        g.add_edge(S, i, 1, 0);
        g.add_edge(i + B, T, 1, 0);
    }
    for (a, b, c) in edges { g.add_edge(a, b + B, 1, BASE - c); }
 
    let slope = g.slope(S, T, 500);
    let slope = slope.into_iter().map(|(flow, cost)| (flow, flow * BASE - cost)).collect_vec();
  
    let mut ans = slope.windows(2).map(|s|{
        let base = s[0].1;
        let a = (s[1].1 - s[0].1) / (s[1].0 - s[0].0);
        (0..(s[1].0 - s[0].0)).map(|i| base + i * a).collect_vec()
    }).flatten().collect_vec();
 
    ans.push(slope.last().unwrap().1);
 
    println!("{}\n{}", ans.len() - 1, ans.iter().skip(1).join("\n"));
}