ABC418

A~Eまでの5完でした。とはいっても、ゲキヤバセット過ぎてびっくりするなどしていました。 Bで4ペナする水コーダー、水色剥奪かも。

A - I'm a teapot

末尾における判定は大体の言語でメソッド/関数が用意されているのでそれを使えばよいです。Rustならends_withが使えます。提出

use library::utils::input::Input;

fn solve(ip: &mut Input) {
    let n = ip.next::<usize>();
    let s = ip.next::<String>();
    println!("{}", if s.ends_with("tea") { "Yes" } else { "No" });
}

B - You're a teapot

難しすぎてびっくりしてしまいました。制約が$|S|\leq100$と小さいので、すべての条件を満たす部分文字列に対して愚直に充填率を判定すれば良いです。提出

s = input()

ans = 0.0
for i in range(len(s)):
    for j in range(i+3, len(s)+1):
        if s[i] == 't' and s[j-1] == 't':
            count = s[i:j].count('t')
            val = (count-2) / (len(s[i:j]) - 2)
            if ans < val:
                ans = val
                
print(ans)

何でハマっていたかと言うと、$[l, r)$の組を全探索していたのですが、$r=|S|$が入っていないせいで、例えば"ttt"といった入力に対して0を返していたのが原因でした。うーん。

C - Flush

ある$x$でゲームに勝利する事ができるならば$x+1$でも勝利できますし、反対にある$x$で勝利できないならば$x-1$では勝利できません。つまり、$x$には線形性があるので、二分探索によって条件を満たす$x$の最小値を求めることができそうです。

ここで、$x$が与えられたときに、勝利できるか否かを判定することを考えます。ディーラーは$\min (b-1, A_i)$個のティーバッグを渡していくのが良くて、その和が$x$以上となるならばディーラーの勝利です。この和は、$A$を事前にソートしておき、累積和を持っておくことによってもとまります。より詳細には、$A_i \geq B$を満たす最小の$i$を見つけることで、$\sum_{j=1}^i A_j + (N-i) (B-1)$で計算できます。

よって、クエリあたり$O(\log \sum A)$で答えを求められるので、全体で$O(Q \log \sum A)$時間でこの問題が解けました。 提出

use library::utils::input::Input;

fn solve(ip: &mut Input) {
    let n = ip.next::<usize>();
    let q = ip.next::<usize>();
    let mut a = ip.vector::<u64>(n);
    a.sort();

    let csum = CumulativeSum::new(&a);
    
    for _ in 0..q {
        let bi = ip.next::<u64>();

        let i = a.lower_bound(bi);
        let score = csum.get(..i) + (bi - 1) * (n - i) as u64;
        
        //dbg!(i, score);

        let mut ng = bi - 1;
        let mut ok = csum.get(..);
        while ok - ng > 1 {
            let mid = (ok + ng) / 2;
            
            if score < mid {
                ok = mid;
            } else {
                ng = mid;
            }
        }

        println!("{}", if score < ok { ok.to_string() } else { "-1".to_string() });
    }

}

D - XNOR Operation

$S$の各文字の間にはXNOR演算子が入っていると考えると、以下のように考えられます。

$S[l, r]$を、好きな順序で計算したときの結果が$1$となるような$l, r$の組は何通りか？

これは、XNOR演算子に良い性質が無いとかなり厳しそうです。というのも、 好きな順序でevalすることができるので、愚直に$l, r$の組を全探索するしかなさそうだからです。ということで良い性質を見つけたいですが、まぁ一番有り得そうなのはXNORが結合律を満たす、つまり「好きな順序でevalできる」といいながら実際にはどの順でevalしても最終的な結果は同じである、という所でしょう。

もしXNOR演算子が結合律を満たすのであれば、$\text{dp}_{i, j} := i$番目までevalした結果が$j$であるようなものの個数、とする動的計画法によってこの問題が解けます。実際解けました。これで証明とさせていただきましょう。

...だめですよね。はい。XNORはNOT XORと同じですから、以下を示せばよいです。

$$\lnot (\lnot (A \veebar B ) \veebar C) = \lnot (A \veebar \lnot (B \veebar C))$$

で、これはWolframAplhaに投げてみると、両辺ともに$A \veebar B \veebar C$になるらしいです。よって両辺が等しいことが示せたので、XNOR演算子は結合律を満たします。

以上から、この問題が解けました。提出

use library::utils::input::Input;

fn solve(ip: &mut Input) {
    let n = ip.next::<usize>();
    let s = ip.next::<String>().chars().collect::<Vec<_>>();
    
    let mut ans = 0u64;
    let mut dp = vec![0; 2];
    
    for i in 0..n {
        let mut ndp = vec![0; 2];
        
        if s[i] == '0' {
            ndp[1] += dp[0];
            ndp[0] += dp[1];
        } else {
            ndp[1] += dp[1];
            ndp[0] += dp[0];
        }
        
        ndp[if s[i] == '0' { 0 } else { 1 }] += 1;
        dp = ndp;
        ans += dp[1];
    }

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

オーバーフローで1ペナ。もったいない。

E - Trapezium

ある四角形が台形となるためには、対辺が平行である必要があります。逆に、対辺が平行な2つの線分を選べば台形が構築できますから、2点の選び方を全探索して、辺の傾きごとに数えれば$O(N^2)$でできます。

ただし、このままでは平行四辺形を2度数えてしまいます。なので平行四辺形の数も調べればよいです。第計は満たさず平行四辺形が満たす性質で、扱いやすいのがなにかな～と思いながら調べると、対角線が中点で交わるというめちゃくちゃいい性質があるじゃないですか！これも2点の選び方を全探索して、中点の座標を持って数えておけば計算できます。

これらの差を取ってあげれば重複が省かれ、答えが得られます。定数倍が厳しくて1ペナ。平衡二分木の定数倍が重いとはいえ、流石にこの手の問題の$O(N^2 \log N)$は許してほしいなぁの気持ち。提出

use std::collections::BTreeMap;

use library::utils::input::Input;
use num_rational::Ratio;

fn solve(ip: &mut Input) {
    let n = ip.next::<usize>();
    let p = (0..n).map(|_| ip.pair::<i64, i64>()).collect::<Vec<_>>();

    let a = |x: (i64,i64), y: (i64,i64)| -> Option<Ratio<i64>> {
        let (x1, y1) = x;
        let (x2, y2) = y;
        if x2 == x1 {
            return None;
        } else {
            return Some(Ratio::new(y2-y1, x2-x1));
        }
    };
    
    let mid_p = |x: (i64,i64), y: (i64,i64)| -> (i64, i64) {
        (x.0 + y.0, x.1 + y.1)
    };
    
    let mut map = BTreeMap::new();
    let mut map2 = BTreeMap::new();
    let mut zero = 0u64;
    
    
    for i in 0..n {
        for j in i+1..n {
            if let Some(d) = a(p[i], p[j]) {
                *map.entry(d).or_insert(0) += 1u64;
            } else {
                zero += 1;
            }
            
            let p = mid_p(p[i], p[j]);
            *map2.entry(p).or_insert(0) += 1u64;
        }
    }
    
    let mut ans = map.iter().map(|(_, &v)| v * (v - 1) / 2).sum::<u64>();
    
    if zero >= 2 {
        ans += zero * (zero - 1) / 2;
    }
    let sub = map2.iter().map(|(_, &v)| v * (v - 1) / 2).sum::<u64>();
    println!("{}", ans - sub);
}