【AtCoder】ABC 418 振り返り

AtCoder Beginner Contest 418 に参加しました。その振り返りです。
結果としては、A~E の 5 完でした。

黄色パフォーマンスがひさびさにとれてよかったです。全体的に得意な問題が多かったことと、青 perf の問題がなかったことで早解きが活きたことが勝因だと思います。

A. I'm a teapot

$S$ の終わり 3 文字が tea と一致するかどうかを判定する問題です。
本番は、一文字ずつ比較しました。便利な String の関数があるはずとは思いましたが、覚えていませんでした。end_with の使い方を覚えておきたいと思います。

println!(
    "{}",
    if s.len() >= 3 && s[s.len() - 3] == 't' && s[s.len() - 2] == 'e' && s[s.len() - 1] == 'a' {
        "Yes"
    } else {
        "No"
    }
);

これをより簡単に書くと、s.end_with("tea") となります。

B. You're a teapot

$O(|S|^3)$ が計算可能なので、部分文字列の始点と終点を全探索できます。f64 を使用することになるのですが、今回は誤差が影響しません。

let mut ans = 0.0;
for i in 0..s.len() - 1 {
    for j in i + 1..=s.len() {
        if j - i >= 3 && s[i] == 't' && s[j - 1] == 't' {
            let cnt = s[i..j].iter().filter(|c| **c == 't').count();
            let x = (cnt - 2) as f64 / (j - i - 2) as f64;
            if ans < x {
                ans = x;
            }
        }
    }
}
println!("{}", ans);

C. Flush

問題文が難読です。
ディーラーがどのような行動をとるかを考えてみます。
難易度を $b$ とします。同じティーバッグを $b$ 個渡すとよくないですが、なるべくたくさんのティーバッグを渡したいです。そこで、すべてのティーバッグを $b - 1$ 個ずつ渡すことが最適だとわかります。 $b - 1$ 個に満たないティーバッグはすべて渡して問題ありません。そこからさらに一つ渡すと、勝利ができます。
逆にこれ以上、渡すことはできません。この状況からどれか一つでも渡してしまうとあるティーバッグは $b$ 個揃ってしまいます。

よって、求める問題は、

$$
\sum_{i = 0}^{N - 1} \min(A_i, b - 1)
$$

を計算する問題となります。
これは、 $A$ を昇順にソートしておき、初めて $b - 1 \le A_x$ となるような $x$ に対して

$$
\sum_{i = 0}^{N - 1} \min(A_i, b - 1) = \sum_{i = 0}^{x - 1} A_i + \sum_{i = x}^{N - 1} (b - 1) = \sum_{i = 0}^{x - 1} A_i + (b - 1)(N - x)
$$

となります。第一項は、 $A$ の累積和をとっておくことで $O(1)$ でもとめることが可能です。 $x$ は二分探索で $O(\log N)$ 求めることが可能です。

以上より、この問題を $O(Q \log N)$ で解くことができました。

a.sort();
let mut s = vec![0];
for &a in &a {
    s.push(s.last().unwrap() + a);
}
let mx = *a.iter().max().unwrap();
for &b in &b {
    if b > mx {
        println!("-1");
    } else {
        let i = a.lower_bound(&(b - 1));
        println!("{}", s[i] + (b - 1) * (n - i) + 1);
    }
}

上のように、そもそも全部使っても勝つことができない場合もあります。場合分けをして判定する必要があります。この問題、思ったよりも難しかったです。茶 perf であることに驚いています。

D. XNOR Operation

条件を満たす部分文字列の個数を数える問題です。
文字列を XNOR で短くしていきますが、この際に演算を行う順序によって結果が変わってしまうと大変そうだなと感じました。そこで、XNOR を $\oplus$ として、

$$
\forall x, y, z \in \lbrace 0, 1 \rbrace, (x \oplus y) \oplus z = x \oplus (y \oplus z)
$$

が成り立つかどうかを確認しようと思いました。
Wikipedia (https://ja.wikipedia.org/wiki/XNOR%E3%82%B2%E3%83%BC%E3%83%88) によると成り立つようです。

そこで、演算は左から行なっていけばよいことがわかります。つまり、

$$
\bigoplus_{i = l}^{r} A_i = \Big( \bigoplus_{i = l}^{r - 1} A_i \Big) \oplus A_r
$$

が成り立ちます。よって、部分問題から更新することができるので DP ができそうです。（EDPC をやったおかげで、DP っぽいなみたいな勘どころが良くなった気がしています。言語化はできていません。）

演算を行なった結果が $0, 1$ のどちらかさえもてば、次の計算ができます。よって演算結果が $0, 1$ のどちらかを耳にもって、DP をしていくことを考えることができます。途中から始まる分も、その都度そこが始まりになる分を加算しておくことで数え上げることが可能です。以下のようなコードになります。

let mut ans = 0;
let mut dp = [0usize, 0usize];
dp[(t[0] - b'0') as usize] += 1;
for t in &t[1..] {
    ans += dp[1];
    let ndp = if *t == b'0' {
        [dp[1] + 1, dp[0]]
    } else {
        [dp[0], dp[1] + 1]
    };
    dp = ndp;
}
println!("{}", ans + dp[1]);

$O(N)$ で計算することができました。

E. Trapezium

台形の数え上げです。制約を見ると、 $O(N^4)$ が通らないのでうまく高速化しなければなりません。 $O(N^2)$ くらいであることが予想できます。

$a, b, c, d$ の $4$ 点が台形になる条件を考えます。中学生の頃の気持ちになると、台形の条件として $O(N^2)$ で計算できるものは $ab \parallel cd$ です。異なる $3$ 点が同一直線上にないという条件で、$ab, cd$ がこの条件を満たすときに一直線上にあることはありません。つまり、台形であることと同値になります。

よって、傾きごとに何個ずつあるかをカウントしていけばよいです。傾きですが、かならず有理数になります。よって、誤差がなく比較できます。

これで提出すると、サンプルが合いません。サンプル 1 をよくみると、平行四辺形がダブルカウントされていることに気づくことができます。

よって、残る問題は、平行四辺形の数え上げになりました。もう一度、中学生の頃の気持ちになると $ab \parallel cd, ab = cd$ と同値であることがわかります。よって、傾きごとにカウントする際に長さも記録し、長さが同じ組み合わせが何通りあるかを別で求めればよいです。

let mut map = HashMap::new();
for i in 0..n - 1 {
    for j in i + 1..n {
        let a = xy[i];
        let b = xy[j];
        let mut x = a.0 - b.0;
        let mut y = a.1 - b.1;
        let d2 = x * x + y * y;
        let g = gcd(x.abs() as u64, y.abs() as u64) as i64;
        x /= g;
        y /= g;
        if x < 0 {
            x *= -1;
            y *= -1;
        }
        if x == 0 {
            y = 1;
        }
        if y == 0 {
            x = 1;
        }
        map.entry((x, y)).or_insert(vec![]).push(d2);
    }
}
let mut ans = 0usize;
let mut mul = 0usize;
for (k, v) in map.iter() {
    ans += v.len() * (v.len() - 1) / 2;
    let mut w = HashMap::new();
    for d2 in v.iter() {
        *w.entry(*d2).or_insert(0) += 1;
    }
    for (k, v) in w.iter() {
        mul += v * (v - 1) / 2;
    }
}
println!("{}", ans - mul / 2);

さて、傾きですが、 $+ \infty, 0$ のときを注意しなければなりません。 $(0, 1), (1, 0)$ とあらわすことにし、それ以外は最大公約数で割ってあげるとよいです。
$O(N^2)$ で計算することができました。 HashMap なので少し遅いですが、Rust のおかげで通ります。

F. We're teapots

解けていません。クエリを整理していくと「 $[l, r)$ にちょうど $x$ 個のコーヒーがある」という条件になります。このとき、すべての条件で $[l, r)$ は非交和になります。
さらに、コーヒーがそれぞれで隣り合わないという条件に対応するため、左端と右端がそれぞれなにかを耳に持たなければなりません。

区間をセットで管理して、うまく部分更新したいなと言う気持ちになっていたら終わりました。

オレンジperf なので、復習もとりあえずはしなくてよいかなって感じです。

総括

一週間の精進の結果が現れたと感じました。EDPC を全て解いたことで D に気づくことができました。典型90 のおかげで E の幾何問題に対してもちゃんと考察できました。
このまま、黄色になりたいな。