Rustコトハジメ

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

ABC137 反省会

AtCoder Beginner Contest 137 - AtCoder

今回も3完しか出来なかったが、今回のDはわかっちゃいなかったため、気分的な落ち込みはない。まだDを確実に解けるというレベルには達していないんだと思う。また一週間トレーニングします。

C

「32ビットで収まらないことがある」で一度ハマった。アルゴリズムと本質的に無関係なハメで、かなり不愉快。

型推論の悪いところで、おれはてっきりusizeで計算してると思っていたのだが、実はi32で計算していたらしい。最後の入力だけ落ちた。

実装

Rustで書くと大変だるい。

fn solve() {
    input! {
        N: usize,
        S: [chars; N],
    }
 
    let mut ss = vec![];
    for s in S {
        let mut s = s;
        s.sort();
        let mut st = String::new();
        for c in s {
            st.push(c);
        }
        ss.push(st);
    }
    let mut m = HashMap::new();
    for s in ss {
        if !m.contains_key(&s) {
            m.insert(s.clone(), 0 as usize);
        }
        *m.get_mut(&s).unwrap() += 1 as usize;
    }
    let mut res = 0;
    for v in m.values() {
        let cnt = v * (v-1) / 2;
        res += cnt;
    }
    println!("{}", res);
}

D

まず最初にやったのが、(お金, 日数)の逆順でソートして先頭から貪欲にとっていくという謎回答だが、2回提出してWA。これは明らかに間違っていて、最適解にたどり着けない。

それから、お金が高くて日数が高いやつを優先的に、ぎりぎりのラインの日を探して予約していくという方針にしたが、探すところがどうしてもリニアサーチにしかならず、結局TLE。

解説を見ると、M日目から逆に見ていって、その都度そこでやれる最強のバイトをするという方針で解けることがわかり、もやもやが晴れた。

逆から見ていく系はよくみるが、ふとジョブスケジューリングで逆から見ていくという風に言い換えると、全く同じ問題を見たことがあるような気がしてきた。(どの問題だったかは忘れてた。モロにジョブスケジューリングみたいな名前だった気がするが)

これかも。D - Megalomania

実装

実装演習として、コンテスト後に解いた。コンテストでRustを使うのは慣れてないため、結構時間がかかった。

ポイントは、RustのBinaryHeapはmax-heapであるため、min-heapとして扱うには値を逆転させる必要があること。これはダイクストラ法とかでも結構ハマる。うざすぎるので使い勝手の良いものを自分で実装した方がいいかも。

処理速度だけど、おれのコードが36msで、C++での最速が17ms。C++でも結構60msとか行ってるものもあるので、Rustはやっぱり速いと思う。今回総合一位の人がなんとPythonで解いてて、Dは397msかかってる。実装が少し非効率ならたちまちTLEしそうな際どいラインな気がする。Pythonで攻めてるのは非効率なコードを書かない自信があるからだろうから、すごい。

fn solve() {
    input! {
        N: usize, M: i32,
        AB: [(i32, i32); N]
    }

    let mut que0 = BinaryHeap::new();
    for (a,b) in AB {
        que0.push((-a,b)); // min-heap by a, max-heap by b
    }
    // dbg!(&que0);

    let mut res = 0;
    let mut que1 = BinaryHeap::new();
    for i in (0..M).rev() {
        let t = M-i;
        loop {
            if que0.is_empty() {
                break;
            }

            let x = que0.pop().unwrap();
            let (a,b) = (-x.0,x.1);
            if a <= t {
                que1.push(b); // max-heap by b
            } else {
                que0.push((-a,b)); // push back
                break;
            }
        }
        // dbg!(&que1);
        if let Some(x) = que1.pop() {
            // dbg!(x);
            res += x;
        }
    }
    println!("{}", res);
}