はじめに

AtCoder Beginner Contest 393のA-FをRustで解いてみました。

もう1ヶ月半くらい前のコンテストになってしまいましたがこの回に参加できていなかったことを思い出したため解きました。

問題は各見出しのリンクからご覧ください。

私達ハウインターナショナルでは、社名をもじってハウッカソンという名のイベントを毎月最終金曜日に実施しています。

ハウッカソンのテーマに競技プログラミングを選ぶメンバーもいます。

A問題

青木くんと高橋くんに毒味をさせてあたりの牡蠣を探します。match式で書きました。

use proconio::*;

fn main() {
    input! {
        s1: String,
        s2: String
    }
    let s1 = s1 == "sick";
    let s2 = s2 == "sick";
    let ans = match (s1, s2) {
        (true, true) => 1,
        (true, false) => 2,
        (false, true) => 3,
        (false, false) => 4,
    };
    println!("{}", ans);
}

B問題

A, B, C が等間隔で並んでいる場所の数えあげ問題です。

s <= 100と小さいので3重ループが通るので何も考えずに実装したものが通りました。

use proconio::{marker::Chars, *};

fn main() {
   input! {
       s: Chars
   }
   let mut ans = 0;
   for i in 0..s.len() {
       for j in i + 1..s.len() {
           for k in j + 1..s.len() {
               if s[i] != 'A' || s[j] != 'B' || s[k] != 'C' {
                   continue;
               }
               if j - i != k - j {
                   continue;
               }
               ans += 1;
           }
       }
   }
   println!("{}", ans);
}

C問題

単純グラフを実際にu, vから作ってみます。
まずは自己ループがあるときはu == vなのでその時はフィルタします。
あとは、同じ頂点同士を結ぶ辺が複数あれば重複を除去したいです。
グラフは無向グラフなので(a, b)でも(b, a)でも関係ないので適当に(min, max)で順番を揃えておいて重複を除去することで無向グラフの完成です。

あとはこのように作られたグラフの要素数が元のグラフよりどれだけ小さくなっているかを出力すればそれが答えになります。

n頂点という情報を全く使わずにこの問題が解けてしまいましたね。

use std::cmp::{max, min};

use itertools::Itertools;
use proconio::*;

fn main() {
   input! {
       _n: usize,
       m: usize,
       uv: [(usize, usize); m]
   }
   let mut g = uv
       .iter()
       .filter(|&&e| e.0 != e.1)
       .map(|&e| (min(e.0, e.1), max(e.0, e.1)))
       .collect_vec();
   g.sort();
   g.dedup();
   println!("{}", m - g.len());
}

D問題

i個目の1のところに残りのすべての1を寄せることを考えます。
まずはとりあえず、中心の1より左にあるiはすべて(i - 1)に、右にあるiはすべて(i + 1)に寄せてしまいましょう。

すると、これにかかるコストは中心の1より左側にある1の座標をlnとして右側にある1の座標をrnとすると

左側： (i - l1) + (i - l2) + (i - l3) + ...
右側： (r1 - i) + (r2 - i) + ...

とすることができます。

制約が大きいのでこれを都度都度計算していては間に合いませんが、
上の式を変換すると

左側：i * (左側にある個数) - (左側にある1のiの合計)
右側：(右側にある1のiの合計) - i * (右側にある個数)

とできるので、Sを左から順番に舐めていって、1が来た時の個数とその座標を足しこむ計算をすればこの処理は定数時間で計算可能になります。

よって、左にあるiはすべて(i - 1)に、右にあるiはすべて(i + 1)に寄せてしまうことはできました。

あとは、今左にあるものはすべて(i - 1)に、右にあるものはすべて(i + 1)に寄ってもらっているので、これをもとに戻ってもらえばよいです。

どのくらい余計に移動してもらっているかを考えます。

左側の例で行くと、左側の個数が1個であればその1は(i - 1)に来てもらう必要があるので余計な移動は発生していません。

2個の時は1個は(i - 1)に来る必要がありますが、2個目は(i - 2)に来ていればOKなので1だけ余分な移動が発生しています。

3個の時は1, 2個目は上と同様で、3個目は(i - 3)に来ていればOKなので2だけ余分な移動が発生して、2個目と合わせて1 + 2 = 3の余分な移動が発生しています。

したがって、余分な移動は 1 + 2 + 3 + .... + (左側にある個数 - 1)個ということがわかります。

(左側にある個数 - 1) = kとするとこれは k * (k + 1) / 2で求められます(定数時間で求められます。)

右側にも同じことができるので、i個目の1のところに残りのすべての1を寄せたときのコストを定数時間で求めることができました。

よって全体でO(|S|)でこの問題が解けました。

普段勘で解いてるのでこういう風に言語化すると結構難しいですね。
言語化する癖をつけていきたいです。

use std::cmp::min;

use proconio::{marker::Chars, *};

fn main() {
  input! {
      n: usize,
      s: Chars
  }
  let mut rt = 0;
  let mut lt = 0;
  let mut lc = 0usize;
  let mut rc = 0usize;
  for i in 0..s.len() {
      if s[i] == '1' {
          rt += i;
          rc += 1usize;
      }
  }
  let f = |n: usize| {
      n * (n + 1) / 2
  };
  let mut ans = usize::MAX;
  for i in 0..s.len() {
      if s[i] != '1' {
          continue;
      }
      rc -= 1;
      rt -= i;
      let lb = if i == 0 {0} else {(i - 1) * lc} - lt;
      let kb = if lc == 0 {0} else {f(lc - 1)};
      let left = lb - kb;
      let rb = rt - (i + 1) * rc;
      let kb = if rc == 0 {0} else {f(rc - 1)};
      let right = rb - kb;
      ans = min(ans, left + right);
      lc += 1usize;
      lt += i;
  }

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

E問題

制約からO(n√n)かかる約数全列挙を封じたい思いがひしひしと伝わりました。

まず、xをgcdとして正解の候補にできるか？ということを考えた時に、これの条件は
aの中にxを約数にもつ数がk個以上あるということになります。

このようにして取り出した正解の候補の中のその数が持つ最大値を答えてあげればよいということがわかります。

それをそのまま実装したのが以下になります。

use std::cmp::max;

use proconio::*;

fn main() {
    input! {
        n: usize,
        k: usize,
        a: [usize; n]
    }
    let &m = a.iter().max().unwrap();
    let mut count = vec![0; m + 1];
    let mut numc = vec![0; m + 1];
    for &num in a.iter() {
        numc[num] += 1usize;
    }

    for i in 1..=m {
        let mut now = i;
        let mut cc = 0;
        loop {
            let co = numc[now];
            cc += co;
            now += i;
            if now > m {
                break;
            }
        }
        count[i] = cc;
    }
    let mut v = vec![];
    for i in 1..=m {
        if count[i] >= k {
            v.push(i);
        }
    }
    let mut ans = vec![1; m + 1];
    for &num in v.iter() {
        let mut now = num;
        loop {
            ans[now] = max(ans[now], num);
            now += num;
            if now > m {
                break;
            }
        }
    }

    for &num in a.iter() {
        println!("{}", ans[num]);
    }
}

さて、上記実装の下記の部分ですが、mをaの中に含まれている数の最大値としたときに、
now += iする内部のループが1..=mの外部のループの中で回っています。

for i in 1..=m {
        let mut now = i;
        let mut cc = 0;
        loop {
            let co = numc[now];
            cc += co;
            now += i;
            if now > m {
                break;
            }
        }
        count[i] = cc;
    }

一見すると、これO(m^2)かかりそうだと思いますが、実はこの計算量はO(mlogm)で抑えられます。調和級数というやつです。

詳細だったり厳密な理解は調べていただければと思いますが、以下に自分が理解している直感的なイメージを説明しておきます。

中のループのループ回数は
i = 1のとき m / 1 回
i = 2のとき m / 2 回
i = 3のとき m / 3 回

回ると思います。

よって、全体でループする回数は

m / 1 + m / 2 + m / 3 + .... + m / m回になります。

これをiを使って書くと

m * \sum_{i=1}^{m} \frac{1}{i}

となります。

そして、ここからがかなり大雑把ですがこれを離散でなく連続だとするとインテグラルで書けるので、

m * \int \frac{1}{i} di

となります。この積分はlogmで抑えられますね。(数Ⅱか数Ⅲのはなしです)

よって、連続で考えた時に m logmで抑えられるということは

m * \sum_{i=1}^{m} \frac{1}{i}

も当然mlog(m)で抑えられます。という理解です。

完全に嘘理解だと思いますがこの理解がズレていたとして困ることもなさそうなのでこれからもこの理解のまま進むのだろうと思います。

よって、この問題もO(mlog(m))で解けました。

F問題

r <= 2 * 10 ^ 5なので、すべてのrを固定して考えられます。
なので、r を末尾として考えることも可能になるわけです。
空配列にaiを挿入していきながらクエリを先読みしてその時のrのクエリに回答していきましょう。

さて、aiを末尾に挿入したときにどのようなことをしたいかを考えます。

今回は狭義単調増加の配列の最大値を求めたいので、aiをつなげてできる配列の最大値は、
それまで出てきたaiより小さい配列でできる最大の配列長 + 1になります。

そして、求めたい値は全ての要素が Xi以下のものですが、これは狭義単調増加から、一番最後の値が小さければよいですね。

よって、やりたいことをまとめると

末尾の値がaiよりも小さい配列でできる配列の最大長の区間取得, aiの1点更新
末尾の値がx以下の配列の最大長の区間取得

ができればよいので、これはsegment treeで実現できますね。

ただ、x <= 10 ^ 9で大きいので座標圧縮してあげる必要があります。

use std::{cmp::max, collections::HashMap};

use ac_library::{Monoid, Segtree};
use itertools::Itertools;
use proconio::{marker::Usize1, *};

#[derive(Clone, Copy)]
struct M;

impl Monoid for M {
    type S = usize;
    fn identity() -> Self::S {
        0
    }
    fn binary_operation(a: &Self::S, b: &Self::S) -> Self::S {
        max(*a, *b)
    }
}

fn main() {
    input! {
        n: usize,
        q: usize,
        a: [usize; n],
        mut rx: [(Usize1, usize); q]
    }
    let mut v = rx.iter().map(|&e| e.1).collect_vec();
    v.extend(a.to_owned());
    v.sort();
    v.dedup();
    let mut ids = HashMap::new();
    let mut id = 0;
    for &num in v.iter() {
        ids.insert(num, id);
        id += 1usize;
    }
    let mut map = HashMap::new();
    for (idx, &(r, x)) in rx.iter().enumerate() {
        let x = ids.get(&x).unwrap();
        map.entry(r).or_insert(Vec::new()).push((x, idx));
    }
    let def = vec![];
    let mut seg: Segtree<M> = Segtree::new(id);
    let mut ans = vec![usize::MAX; q];
    for (idx ,&num) in a.iter().enumerate() {
        let &id = ids.get(&num).unwrap();
        let pre = seg.prod(..id);
        let now = seg.prod(id..=id);
        seg.set(id, max(now, pre + 1));
        let qs = map.get(&idx).unwrap_or(&def);
        for &(x, qi) in qs.iter() {
            let aa = seg.prod(..=x);
            ans[qi] = aa;
        }
    }
    for &num in ans.iter() {
        println!("{}", num);
    }
}

終わりに

考えていることを言語化って練習しないとできないなあと改めて実感しました！