Rustコトハジメ

プログラミング言語Rustと競プロに関する情報をお届けします。

AGC037 反省会

AtCoder Grand Contest 037 - AtCoder

Aだけはとった。が、300点というだけあって簡単だったと思う。しかし、以前のおれならうっかり落としていたかも知れないから、ちゃんと取り切るようになった点は成長を感じる。

あと、Bに取り組んでサンプルは通せてるし、コンテスト中にあったscrambleというテストセットは半分くらい通していた。以前なら800点には一切歯が立たずに即投了だったと思うので、これは成長を感じる。

どうせAとれば上出来なんだろと思って、最初にBとCを眺めて考えて時間ロスしたため、標準的な15分くらいでACすることが出来なかった。次にAGCに参加する時はこの戦略はやめようと思う。

A

日本語的に、問題の意味がわからなかった。

満たすものが存在する

だったら、一箇所でも満たしていればいいのか?と思ってサンプルを見ると全箇所満たしているので、単に「満たす」で良いのではないか。

前方向から貪欲にやってみるでなんとなく良さそう(長くしていく意味がなさそうなので)という感じがするので、そういう方針で実装を始めるが、前の列と今の列が等しいことをマップを使って差分検出していく系か?と勘違いし、さらに時間をロスした。

B

全くわからないので、サンプルの答えから計算方法を逆算することにした。素因数分解してみると、それぞれの素数の個数がわかって、それを無理やりひねり出すアルゴリズムを考えた。一個の色については誰に配るかでN!あるというのは自明なので、その上で差分を考えるというのが課題。

実装したアルゴリズムは、RGBが揃うまでたどっていって、例えば

RRGBとかになった時には、最初のRと後ろのBはさっさと精算した方が良いし、Gはこの1つを使うに決まってる。この2つのRはどちらを使っても良い。なぜならば、仮に後ろを使って今稼いだとしても後で1つ損して帳消しになるから。

RRGGBなども同じで、この場合はGGもどちらを使ってもいい。なぜならば、RとGを一つ消費すると、次にBを見つけるまでたどっていき、結局残ったRGを消費するから。この時、Gの位置は結果には影響しない。

という感じでもっともらしく考えることが出来たし、サンプルも通るコードを書けたので、勝ったかと思ったが、何か間違っていたのか、WAとなった。こんな感じのものを書いた。

fn solve() {
    input! {
        N: usize,
        S: chars,
    }
    let p = 998244353;
    let mut ans = factorial(N, p);
    let mut pows = vec![0; N+1];
    let mut filled = vec![false; 3];
    let mut cur = vec![];
    for i in 0..S.len() {
        let c = S[i];
        // dbg!(c);
        cur.push(c);
        let n = if c == 'R' {
            0
        } else if c == 'G' {
            1
        } else if c == 'B' {
            2
        } else { 10000 };
        filled[n] = true;
        let mut ready = true;
        for &b in &filled {
            if !b {
                ready = false;
                break;
            }
        }
        if !ready {
            continue;
        }
        // dbg!("ready");
        // dbg!(&cur);
        let first_c = cur[0];
        let mut first_cnt = 0;
        let mut i = 0;
        while cur[i] == first_c {
            first_cnt += 1;
            i += 1;
        }
        let second_c_first = i;
        let second_c = cur[second_c_first];
        let mut second_cnt = 0;
        while cur[i] == second_c {
            second_cnt += 1;
            i += 1;
        }

        // dbg!(first_cnt, second_cnt);

        pows[first_cnt] += 1;
        pows[min(first_cnt, second_cnt)] += 1;
        
        let k = cur.len() - 1;
        cur.remove(k);
        cur.remove(second_c_first);
        cur.remove(0);

        filled = vec![false; 3];
        for &c in &cur {
            let n = if c == 'R' {
                0
            } else if c == 'G' {
                1
            } else if c == 'B' {
                2
            } else { 10000 };
            filled[n] = true;
        }
    }

    for i in 2..pows.len() {
        let pow = pows[i];
        if pow == 0 {
            continue;
        }
        ans *= modpow(i, pow, p);
        ans %= p;
    }
    println!("{}", ans);
}

C

よくわからなかった。なんとなく感覚としては、

  1. もしかしてグラフか?(ルールをエッジにしてグラフに置き換えるとか)
  2. 答えの配列から逆に辿っていく?

くらいかと思ったが、方針が思いつかなかった。わりと典型臭がするので復習はやる。