AtCoder Beginner Contest 237 - zeronosu77108’s blog

久しぶりに Rated 参加しました。ちょっと悲しい気持ちになっています。 5完 57:41（4ペナ）でした。

A - Not Overflow

Rust で良い感じに $2^{31}$ を計算する方法が思いつかなかったので、愚直に求めました。よく考えたら 2i64.pow(31) したら良かったです。

fn main() {
    input! {
        n : i64
    }

    let mut p = 1;
    for _ in 0..31 { p *= 2; }

    println!("{}", if (-p..p).contains(&n) {"Yes"} else {"No"});
}

提出
 powを使ったやつ

B - Matrix Transposition

問題文

最初 D 問題が表示されていて、「Bにしては難しくない？」って思いながら解いて出したら全部 RE になってめちゃくちゃ焦りました。

Rust で，行と列を転置するを思いだしたんですが、出力するだけなら自分で書いた方が早いかな～と雑に書きました。↓→ みたいな順で出力されるようにしたら良いです。

fn main() {
    input! {
        h : usize,
        w : usize,
        a : [[usize; w]; h]
    }

    for i in 0..w { for j in 0..h {
        print!("{}{}", a[j][i], if j+1==h {"\n"} else {" "});
    }}
}

提出

C - kasaka

問題文

雑なことをしたら、コーナーケースでかなり死にました。

基本的には、後ろ側にある 'a' を削除して回文なら OK です。ただし、前側にある 'a' か、後ろ側にある 'a' の数の小さい方だけ後ろに残します。そのときに回文であればOK（なんかもう少し筋の良い書き方ありそう）

fn main() {
    input! {
        mut s : Chars
    }
 
    if s == s.iter().rev().cloned().collect_vec() {
        println!("Yes");
        return;
    }
 
    let mut cnt1 = s.iter().rev().take_while(|&&c| c=='a').count();
    let mut s = s.into_iter().rev().skip_while(|&c| c=='a').collect_vec();
    s.reverse();
 
    let cnt = s.iter().take_while(|&&c| c=='a').count();
    for _ in 0..cnt.min(cnt1) { s.push('a'); }
 
    println!("{}",
             if s == s.iter().rev().cloned().collect_vec() {"Yes"}
             else {"No"}
    )
}

提出

D - LR insertion

問題文

難しいです！

挿入される位置が、バラバラなので Vec などでやると大変なことになりそうです。昇順に処理をすると間に挿入する事になるのですが、降順に処理すると $S_i$ が 'R' なら列の最初に $i-1$ を追加、 'L' なら列の最後に追加するだけで良くなります。

後は、 Deque などを使えば実装できます（Vecを2つ持つでもOK）

fn main() {
    input! {
        n : usize,
        mut s : Chars
    }

    let mut ans : VecDeque<_> = vec![n].into_iter().collect();
    for i in (0..n).rev() {
        match s[i] {
            'L' => ans.push_back(i),
            'R' => ans.push_front(i),
            _ => unreachable!()
        }
    }

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

提出

E - Skiing

問題文

負辺があるので普通のダイクストラではダメです。

一度登って、降りることを考えたときに何度も登り降りして楽しさが増加することはないので、 BFS みたいなことをしながら楽しさに更新があったらそこから再更新をしていけば良いです（落とすようなケース作れるのかな？）。コンテスト中には知らなかったんですが、これ SPFA って呼ばれるアルゴリズムの劣化版みたいな感じになってそうですね？

2秒で「ダイクストラではダメだな～」って思ったのに、ダイクストラで通ったみたいです。これはお気持ちなんですが、解説に以下のように書いてあるのでただのダイクストラで通らないことを確認してくれ！と思いました。

この問題に直接ダイクストラ法を用いることはできません。

fn main() {
    input! {
        n : usize,
        m : usize,
        h : [i64; n],
        edges : [(Usize1, Usize1); m]
    }

    let mut g = vec![vec![]; n];
    for (a,b) in edges { g[a].push(b); g[b].push(a); }

    let mut q = VecDeque::new(); q.push_back((0,0));

    let mut ans = vec![std::i64::MIN/10; n]; ans[0] = 0;
    while let Some((v, c)) = q.pop_front() {
        if ans[v] < c { continue }
        for &u in g[v].iter() {
            let p = ans[v] + if h[v]<h[u] {2*(h[v]-h[u])} else {h[v]-h[u]};
            if ans[u] >= p { continue }
            ans[u] = p;
            q.push_back((u, p));
        }
    }

    println!("{}", ans.iter().max().unwrap())
}

提出

F - |LIS| = 3

問題文

最初、最長増加部分列の長さが $i$ で最長増加部分列の最後が $j$ みたいなものを考えていたんですが、情報が足りないな～と思って、最長増加部分列の長さが $i$ で最長増加部分列の最後の1つ手前が $j$ で、最長増加部分列の最後が $k$ を書いていました。しかし通らず…

3つが確定なので LIS で使う配列を lower_bound で更新していくように、 DP の添字に LIS 配列を持って後で集計したら良かったです。これは解けたなぁって感じです…

use proconio::input;

fn main() {
    input! {
        n : usize,
        m : usize
    }
    const MOD : usize = 998244353;

    let mut dp = vec![vec![vec![0; m+2]; m+2]; m+2];
    dp[m+1][m+1][m+1] = 1;

    for _ in 0..n {
        let mut next = vec![vec![vec![0; m+2]; m+2]; m+2];
        for i in 1..=m+1 { for j in 1..=m+1 { for k in 1..=m+1 {
            for m in 1..=m {
                if m<=i {
                    next[m][j][k] += dp[i][j][k];
                    next[m][j][k] %= MOD;
                }
                else if m<=j {
                    next[i][m][k] += dp[i][j][k];
                    next[i][m][k] %= MOD;
                }
                else if m<=k {
                    next[i][j][m] += dp[i][j][k];
                    next[i][j][m] %= MOD;
                }
            }
        }}}
        dp = next;
    }

    let mut ans = 0;
    for i in 1..=m { for j in i+1..=m { for k in j+1..=m {
        ans += dp[i][j][k];
        ans %= MOD;
    }}}

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

}