ABC414

ABC414、ミラティブプログラミングコンテストです。Mirrativといえば、ぼくが中学生の頃(なので8か9年ぐらい前？)にお世話になっていたサービスなので、まさかこんなところでまた巡り合うとは思っておらずとても驚くなどしていました。

---

それとは別でABC414は出るかどうかかなり悩みました。しばらくは海外コンテストも含めて継続して出ていたのですが、先週土曜日のCF以降あまり乗り気にならず、ABCも同様だったんですよね。精進自体はちょっとしていましたが¹。そんな感じで始まったABC414です。相変わらず録画もあります。

結果としては遅めの5完。これで青perfが出るんだぁという不思議な気持ち。

A - Streamer Takahashi

$X_i$が$L$以下かつ$Y_i$が$R$以上であることが、配信をすべて見られる条件です。そのように実装すればよいです。提出

use proconio::input;

fn main() {
    input!{
        n: usize,
        l: u64,
        r: u64,
        v: [(u64,u64); n],
    }
    let ans = v.iter()
        .filter(|&(x,y)| x <= &l && &r <= y)
        .count();
    println!("{}", ans);
}

何も考えずに適当に「包含判定をすればいいですね～」と言いながら書き始めたら条件が全然あっておらず、サンプルも通らずで困惑していました。水色コーダーさん、その問題A問題ですよ？

B - String Too Long

要約問題文ありがたいです。RLEを復元しつつ、長さが100を超えた時点で打ち切ってToo Longを出力すればよいです。同じ文字を繰り返すときはstd::iter::repeatが便利でいいですね²。

本当はfor文を使わずにきれいに書きたいところですが、合計の長さが最大で$10^{20}$と少し大きすぎるため、手続き的に書くことに。提出

use std::iter::repeat;

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

fn main() {
    input!{
        n: usize,
        c: [(char, usize); n],
    }
    let mut ans = vec![];
    let mut count = 0;
    for (v, c) in c.iter() {
        if count + *c > 100 {
            println!("Too Long");
            return;
        }
        count += *c;
        ans.push(repeat(*v).take(*c).collect::<String>());
    }
    println!("{}", ans.iter().join(""));
}

C - Palindromic in Both Bases

なんか難しかったっぽい？確かに実装方針で沼った部分もありましたが、特別難しいとは感じなかったので不思議です。

回文なので、文字列の前半が決まると後半としてあり得るものは2つに絞られます。例えば前半として123とした場合は、後半として21を付け足した12321か、321を付け足した123321の2択です。これを考えると、$N=10^{12}$の最大ケースでも前半部分としてありうるものは高々$10^6$通りですから、$N$以下で十進数表記が回文となるものを全列挙することが可能です。

値$m$に対する進数変換/回文判定はそれぞれ$O(\log m)$でできます。結局、$M$を「$N$の前半部分としてありうるものの最大値」として³、全体で$O(M \log M)$時間でこの問題を解くことができます。前述の通り$M\leq10^6$なので、十分高速です。提出

use proconio::input;

static M : usize = 1000001;
fn main() {
    input!{
        a: usize,
        n: usize,
    }

    let mut v = vec![];
    for i in 1..=n.min(M) {
        let mut k = i;

        let mut vv = vec![];
        while k > 0 {
            vv.push(k%10);
            k /= 10;
        }

        let mut k1 = i;
        for x in vv.iter() {
            k1 *= 10;
            k1 += x;
        }
        let res1 = k1.to_string();
        if k1 <= n && res1.chars().eq(res1.chars().rev()) {
            v.push(k1);
        }

        let mut k1 = i;
        for x in vv[1..].iter() {
            k1 *= 10;
            k1 += x;
        }
        let res1 = k1.to_string();
        if k1 <= n && res1.chars().eq(res1.chars().rev()) {
            v.push(k1);
        }
    }

    let ans = v.iter()
        .filter(|x| {
            let mut k = **x;
            let mut v = vec![];
            while k > 0 {
                v.push(k%a);
                k /= a;
            }
            v.iter().eq(v.iter().rev())
        })
        .sum::<usize>();
    println!("{}", ans);
}

なお、提出版では何を考えたのか$M$を$10^7$に設定しているせいで1380msもかかっています。あぶねぇ。

D - Transmission Mission

電波強度をすべて同じに設定して$M$個以下で全体を被覆するかを判定すれば良いですね～と、うきうきで二分探索を実装しますがサンプル3が合いません。あれ？おかしいな...

よく見ると誤読をしています。電波強度は別々に設定できて、その最小値なんですか。はぁ。なんですかこれは？

---

とりあえず落ち着いて考えると、ソートしてdedupした上でどの区間を取るか？という話になりそうです。すると、$\text{dp}_{i,j} :=i$番目まで見て$j$回取らない選択をしたときの和の最小値、という自明なdpが生えます...が、これは$O(NM)$です。間に合いません。

ところで、これは区間を取るための条件が存在しないため、大きい方から貪欲に選べば最適になります⁴。未証明ですが、ACをすれば証明なので気にしないことにします。とにかく問題が解けました。実装が微妙に合いません。気合で合わせます。提出

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

fn main() {
    input!{
        n: usize,
        m: usize,
        mut a: [u64;n]
    }

    let v = a.iter()
        .sorted()
        .dedup()
        .tuple_windows()
        .map(|(ai,aj)| {
            aj-ai
        })
        .sorted()
        .collect_vec();
    if v.len() < m { 
        println!("0");
    } else {
        println!("{}", v[..=v.len()-m].iter().sum::<u64>());    
    };
}

E - Count A%B=C

う～～～ん、見た目のなんですかこれは？感がすごいです。取り敢えず考察をすると、$B$を固定してしまえば$A$に対する$C$が一意に定まるので、$B$を固定することを考えます。

固定された$B$に対して$A$が取りうる値の個数は、$x \in \lbrack B, N\rbrack$なる$x$であって、$x$を$B$で割ったあまりが0ではないものの個数です。逆に、そのような$x$であって$B$で割ったあまりが0になるものの個数は$\lfloor\frac{N}{x}\rfloor$ですから、求めたい値の個数は$N-B+1-\lfloor\frac{N}{x}\rfloor$個とわかります。しかし、このままでは$O(N)$かかってしまうので高速化する必要があります。

ここで、求めたい値の個数の式を眺めると、$\lfloor\frac{N}{x}\rfloor$の値が同じであればまとめて計算できそうな気がします。$\lfloor\frac{N}{x}\rfloor$自体は($x$を変数としてみると)広義単調減少な関数なので、二分探索を用いることで$\lfloor\frac{N}{x}\rfloor$がおなじになるような$x$の最大値は簡単に見つかります⁵。

最小値を$l$,最大値を$r$とすると、数えたい組み合わせは$\sum_{i=l}^r N-i+1-\lfloor\frac{N}{x}\rfloor$と計算できます。適当に式変形を行うと、$(r-l+1)(N+1-\lfloor\frac{N}{x}\rfloor) - \sum_{i=l}^r i$で、これは$O(1)$で計算することができます。全体では、$\lfloor\frac{N}{x}\rfloor$として取りうる値の個数だけこの計算を行う必要があります。

---

以下は聞きかじりなので「こいつは聞いたことをあたかも自分が考えたかのように言ってるな～」と思いながら読んでほしいです。

関数$f(x)=\lfloor\frac{N}{x}\rfloor$とする。

1. $f(x)\geq\sqrt N$のとき、以下から$f(x)$の取りうる値は高々$\sqrt N$個

$$\begin{align} f(x) &= \lfloor\frac{N}{x}\rfloor \geq \sqrt N\\ &\Rightarrow x \leq \frac{N}{\sqrt N} = \sqrt N \end{align}$$

2. $f(x) < \sqrt N$のとき、$f(x)$の取りうる値は高々$\sqrt N$個

よって、全体として$f(x)$が取りうる値の個数は$2\sqrt N$個以下となる。

---

以上から、全体で$O(\sqrt N \log N)$時間でこの問題を解くことができました。二分探索分の$\log N$は落とせるらしいですが、まあRustは高速な言語なので良いでしょう。提出

use ac_library::ModInt998244353 as Mint;
use proconio::input;

fn sum(n: Mint) -> Mint {
    n * (n+1) / 2
}

fn main() {
    input!{
        n: u64,
    }
    let mut ans = Mint::new(0);
    let mut b = 2;

    while b <= n {
        let zc = n/b;

        let mut ok = b;
        let mut ng = n+1;
        while ok.abs_diff(ng) > 1 {
            let mid = (ok+ng)/2;
            if n/mid == zc {
                ok = mid;
            } else {
                ng = mid;
            }
        }

        // [b, ok] までの個数を数え上げ
        ans += Mint::new(ok-b+1) * (n + 1 - zc);
        ans -= sum(Mint::new(ok)) - sum(Mint::new(b-1));
        b = ok+1;
    }
    println!("{}", ans);
}

Footnotes

1. ゼータ変換・メビウス変換を履修していました。色んな人に協力してもらって感謝の気持でいっぱいです。 ↩

2. Rustではstd::io::repeatも存在していて、間違えてioの方をuseしていたせいで「あれ、こういう書きかたできなかったっけ...？」で時間を食いました ↩

3. これは$\sqrt N$といっていいような気がしますが、なんか変なコーナーが有ると嫌なのでこういう表記をしておきます ↩

4. 例えば「区間を選択した直後の区間は取れない」といった条件が存在すると貪欲は嘘です。 ↩

5. 最小値は「前回の最大値+1」としてわかっているものと仮定しています ↩