ABC393

頭が回っておらず誤読などもありで、ABCDFの遅めの5完に終わりました。苦しい。

A - Poisonous Oyster

面倒くさいですが愚直に4通り場合分けします。bit演算をすると場合分けが減って微妙に楽だったかも。 提出

void solve() {
    string s, t; cin >> s >> t;
    string sick = "sick";
    string fine = "fine";
    if (s == sick && t == sick) cout << "1\n";
    else if (s == sick && t == fine) cout << "2\n";
    else if (s == fine && t == sick) cout << "3\n";
    else cout << "4\n";

}

B - A..B..C

\(i\) と \(j\) を決めれば \(k\) の位置が決まるので、その3要素が条件を満たすかどうかを判定すればよいです。 提出

#define rep(i,n) for (ll i=0;i<n;++i)
#define rep2(i,a,n) for (ll i=a;i<n;++i)
void solve() {
    string s; cin >> s;
    int n = s.size();
    int ans = 0;
    rep(i, n) {
        rep2(j, i+1, n) {
            int d = j - i;
            int k = j + d;
            if(k >= n) continue;
            if (s[i] == 'A' && s[j] == 'B' && s[k] == 'C') {
                ans++;
            }
        }
    }
    cout << ans << '\n';
}

実は \(S\) の長さはたかだか100なので、愚直に3重ループを書いても良かったのですがこれが一番初めに思いついたのでそのまま実装しました。
\(S_i\) , \(S_j\) , \(S_k\) が全て同じ、と誤読しており、AのAC後6分とかなりの時間を使いました。もったいない...

C - Make it Simple

これは(グラフの知っている必要がありますが)言われた通りのことをどう実現しますか？という問題です。
自己ループは、 \(u_i=v_i\) であるようなものを数えればよいので簡単です。問題は多重辺ですが、ある頂点から伸びている辺の集合を保持しておけば良く、Rustであれば BTreeSet (あるいは HashSet )で持っておけば十分高速に数えることができます。 提出

use std::collections::BTreeSet;
use proconio::{input, marker::Usize1};

fn main() {
    input!{
        n: usize,
        m: usize,
        e: [(Usize1, Usize1); m],        
    }
    let mut ans = 0;

    let mut g = vec![BTreeSet::new(); n];
    for &(u, v) in e.iter() {
        if u == v || g[u].contains(&v) {
            ans += 1;
        }
        g[u].insert(v);
        g[v].insert(u);
    }

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

これも誤読をしていて、「木を構築する」だと思ってぜんぜん違う問題を解いていました。あの？

D - Swap to Gather

差分計算を頑張るやつです。
ある \(S_i(1\leq i \leq |S|, S_i=1)\) を中心に集めることを考えると、それより左側にある 1 に対する操作回数と、右にある操作回数を \(O(|S|)\) で求めることができます。具体的には、以下の擬似コードのように求めることができます 。

j <- i
zero_count <- 0
operate_count <- 0
while j < |S|:
  if s[j] == 0:
    zero_count <- zero_count + 1
  else:
    operate_count <- operate_count + 1

ここで、 \(i\) に1加算したときの(つまり i <- i+1 で更新したときの)操作回数は、更新後の \(S_i\) が0であれば左側にある1の個数だけ増えて右側にある1の個数だけ減ります。更新後の \(S_i\) が1で合った場合には操作回数は変化しません。
これらを用いて \(i=1\) から始めて差分計算をしていくことで、初期値が \(O(|S|)\) 、差分計算を \(O(1)\) でできるため、この問題が十分高速に解けます。 提出

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

fn main() {
    input!{
        n: usize,
        s: Chars,
    }
    let mut l = 0u64;
    let mut r = 0;
    let mut cur = 0;
    {
        let mut z_cnt = 0;
        for i in 0..n {
            if s[i] == '0' {
                z_cnt += 1;
            } else {
                cur += z_cnt;
                r += 1;
            }
        }
    }

    let mut ans = INF;
    for i in 0..n {
        if s[i] == '0' {
            cur += l;
            cur -= r;
        } else if s[i] == '1' {
            r -= 1;
            ans.chmin(cur);
            l += 1;
        }
    }
    println!("{}", ans);
}

F - Prefix LIS Query

そもそもLIS(最小増加部分列)をどうやって求めたかということを思い出すと、これは dp[i] := 長さiの最長増加部分であって、i番目の値としてあり得る最小値 とする動的計画法で、数列の長さ \(N\) に対して \(O(N\log N)\) 時間で求められるのでした。この動的計画法の配列は必ず狭義単調増加になります。
ここで問題をよく見ると、i番目のクエリは「 \(R_i\) 番目の更新を行った後のdp配列のうち、 \(k \leq X_i\) を満たす最大の \(k\) のインデックスを求めよ」というように言い換えることができます。よって、クエリ先読み+二分探索によって、この問題が \(O(N\log N)\) 時間で解くことができます。 提出
実装ではそこまで頭が回っていないので「長さ \(i\) の最長増加部分列のうち \(i\) 番目の値としてあり得る最小値」を配列で持っていますが、これは不要です。

use itertools::Itertools;
use proconio::{input, marker::Usize1};

fn main() {
    input!{
        n: usize,
        q: usize,
        a: [u64; n],
        queries: [(Usize1, u64); q],
    }

    let mut ans = vec![0; q];
    let mut qi = 0;
    let indicates = (0..q).sorted_unstable_by_key(|i| queries[*i].0).collect_vec();

    let mut dp = vec![INF; n];
    let mut mv = vec![INF; n];

    for i in 0..n {
        let idx = dp.lower_bound(a[i]);
        dp[idx] = a[i];
        mv[idx] = mv[idx].min(a[i]);

        while qi < q && queries[indicates[qi]].0 == i {
            let j = mv.lower_bound(queries[indicates[qi]].1);
            ans[indicates[qi]] = if j < n && mv[j] == queries[indicates[qi]].1 { j + 1 } else { j };
            qi += 1;
        }
    }
    println!("{}", ans.iter().join("\n"));
}

E - GCD of Subset(Upsolve)

難しすぎ！
条件を満たす \(A_i\) の約数の個数としてあり得る最大値は240個 ですから、これが全列挙できれば最大ケースでも \(10^6 \times 240(\simeq 2\times10^8)\) 回程度の計算で最大公約数を求めることができます。よって、 \(A\) に含まれる約数を高速に列挙することができればこの問題が解けそうです。

本番中はそれぞれに対して約数列挙を行う \(O(N^{\frac{3}{2}})\) 方針を考えていましたが、これでは最悪ケースで間に合いません。
ここで、数列に含まれる数の約数を直接求めるのではなく、一気に列挙する方法を考えます。これは「ある値 \(x\) に対して、(条件の範囲内で) \(x\) を約数に持つもの」を列挙する、という方針です。この方針で \(M=\max(A)\) までのものを列挙することを考えましょう。
\(x=1\) のとき、1を約数に持つものは \(1, 2, \cdots, M\) の \(M\) 個です。次に、 \(x=2\) のときは、 \(2, 4, \cdots, M\) の約 \(\frac{M}{2}\) 個です。
この調子で列挙していくと、計算回数は \(\sum_{i=1}^{M} \frac{M}{i}\) となり、これは調和級数の和なので \(O(M\log M)\) と高速に列挙することが可能です。
よって、元の問題が解けました。ただし、本当に全部の値を保持すると空間が足りなくなる可能性があるので、 \(A\) に含まれる値だけを持っておくとよいでしょう。 提出

use itertools::Itertools;
use proconio::input;

static M: usize = 1e6 as usize + 2;

fn mp(has: &[bool]) -> Vec<Vec<usize>> {
    let mut res = vec![vec![]; M];
    let mut i = 2;
    while i < M {
        let mut j = i;
        while j < M {
            if has[j] {
                res[j].push(i);
            }
            j += i;
        }
        i += 1;
    }
    res
}

fn main() {
    input! {
        n: usize,
        k: usize,
        a: [usize; n],
    }
    let has = a.iter().fold(vec![false; M], |mut v, &ai| { v[ai] = true; v} );
    let v = mp(&has);

    let mut cnt = vec![0; M];
    for &ai in a.iter() {
        for &vi in v[ai].iter() {
            cnt[vi] += 1;
        }
    }

    let mut ans = vec![1; n];
    'i: for (i, &ai) in a.iter().enumerate() {
        for &vi in v[ai].iter().rev() {
            if cnt[vi] >= k {
                ans[i] = vi;
                continue 'i;
            }
        }
    }
    println!("{}", ans.iter().join("\n"));
}