Rustコトハジメ

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

LeetCode Weekly Contest 153 反省会

初LeetCode。3完。まぁ、Cまで解き切ったことは評価出来る。

LeetCodeの形式はめんどくさい。あとRustの場合、整数値が全部i32で渡されるから、usizeに変換しないといけなかったり、相当うざい。変なimportが残ってると、コンパイルエラーになったりもする。うざい。この方式でジャッジすることって何かメリットあるのか。

B

アルゴリズム要素なし。Pythonでやった。

C

https://leetcode.com/contest/weekly-contest-153/problems/maximum-subarray-sum-with-one-deletion/

方針としては、どこかを消すと仮定して、その左右から最大をとってくるというマージソートみたいな考え方。こういうタイプの考え方は多い。

  • 削除しない場合もある
  • 空配列はだめ

というコーナーケースをうまくくぐり抜ける必要がある。

まず、累積和を作ってから、それを最小値SEG、最大値SEGで管理する。こうすると、例えば左側であれば、左の範囲で最小値をとって、累積和から引くことによって削除位置から左方向で最大の和をO(logN)で計算することが出来る。

ただ大変なだけの問題だった。

    pub fn maximum_sum(arr: Vec<i32>) -> i32 {
        let n=arr.len();

        let mut maxv=std::i32::MIN;
        // 単の時(負もある)
        for i in 0..n {
            maxv=max(maxv,arr[i]);
        }
        // dbg!(maxv);

        let cumsum1 = cumsum1(&arr);
        let mut min_seg: SEG<MIN> = SEG::new(n);
        for i in 0..n {
            min_seg.update(i, cumsum1[i+1]);
        }

        let mut max_seg: SEG<MAX> = SEG::new(n);
        for i in 0..n {
            max_seg.update(i, cumsum1[i+1]);
        }

        // delを消した時の左右を調べる
        for del in 0..n {
            // dbg!(del);
            let left = if del==0 { 0 } else {
                let left_min = min_seg.query(0, del);
                // dbg!(left_min);
                max(cumsum1[del],max(cumsum1[del]-left_min,0))
            };
            // dbg!(left);
            let right = if del==n-1 { 0 } else {
                let right_max = max_seg.query(del+1, n);
                // dbg!(right_max);
                max(right_max-cumsum1[del+1],0)
            };
            // dbg!(right);
            let mid = max(arr[del],0);
            let best = left+right+mid;
            // dbg!(best);
            if best>0 {
                maxv=max(maxv,best);
            }
        }
        maxv
    }

D

なんとなく、前から網羅的にdp[i][j](i番目がarr2[j]の場合)みたいな感じで更新していくのかなと思ったが、トータルでオーダがO(N3)になるような気がして震えた。