2週間ぶりに勝てました。いい感じ～

A - ?UPC

今日のWriterはKUPC作問陣の人たちだな～と思いながらコードを書くとサンプルが合いません(え？) よく問題を読み直すと、与えられるのは一文字ではなく複数文字で、その先頭を取るらしいです。軽く書き直して提出すればOK。提出

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

fn main() {
    input!{
        c: Chars
    }
    println!("{}UPC" , c[0]);
}

B - Heavy Snake

シンプルにちょっと大変な全探索ですが、Rustのmapやmaxなどを駆使して書きます。提出

use proconio::input;

fn main() {
    input!{
        n: usize,
        d: u64,
        v: [(u64, u64); n],
    }

    for i in 1..=d {
        println!("{}", v.iter().map(|&(t, d)| t*(d+i)).max().unwrap());
    }
}

C - Various Kagamimochi

上に乗せる餅が決まれば、下に置くことが可能な餅の最小値が定まります。ということで、二分探索でそのような餅のインデックスを求めれば後はn-(求めたindex)で下に置きうる餅の個数が分かります。提出

use proconio::input;

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

    let mut ans = 0;
    for i in 0..n {
        let k = a[i]*2;
        let idx = a.lower_bound(k);
        ans += n-idx;
    }
    println!("{}", ans);
}

pub trait VecLibs<T: std::cmp::Ord> {
    fn lower_bound(&self, elm: T) -> usize;
    fn upper_bound(&self, elm: T) -> usize;
}

impl<T: std::cmp::Ord> VecLibs<T> for Vec<T> {
    fn lower_bound(&self, elm: T) -> usize {
        let mut left = 0;
        let mut right = self.len();
        while left < right {
            let mid = (left + right) / 2;
            if self[mid] < elm {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        left
    }

    fn upper_bound(&self, elm: T) -> usize {
        let mut left = 0;
        let mut right = self.len();
        while left < right {
            let mid = (left + right) / 2;
            if self[mid] <= elm {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        left
    }
}

ここまで6分。ペース的には悪くないですが、早解き回を感じて少し焦ります¹。

D - Coming of Age Celebration

宇宙人は左から順番に成人していくこと、$i$番目に成人する人が配る石の個数は$N-i$個であることを考えると、その宇宙人が成人した時点で「最終的に持っている石の数」が先読みして計算できそうです。 よって、成人したときにもらえる石の個数を高速に求めることを考えれば良さそうです。区間加算なので遅延セグ木が頭をよぎります。うーん、定数倍が重いといってもRustなので通りそうな気がします。[[ABC387]]でC問題を桁DPを渋って失敗した反省があるので遅延セグ木に行くべきなような気がします。でもMonoidを書いたりするのはちょっと面倒くさいです。 10秒ぐらい葛藤していましたが単一取得なのでimos法で良いと気づきました。実装が微妙に炎上し、嫌な顔をしながら書くとサンプルが通ったので提出。そのままACです。提出

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

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

    let mut imos = vec![0; n];
    let mut current = 0;
    for i in 0..n {
        current += imos[i];
        a[i] += current;

        let left = n - i - 1;
        let give = if a[i] > left as i64 { left as i64 } else { a[i] };
        if give != left as i64{
            imos[i+a[i] as usize+1] -= 1;
        }
        a[i] -= give;
        current += 1;
    }
    println!("{}", a.iter().join(" "));
}

E - Simultaneous Kagamimochi

うーん、わかりません。貪欲では落ちそうですがそれ以外思いつきません。 いくつかのケースを試すと、前から鏡餅を作れるなら作る貪欲では落ちるケースを思いつきました。じゃあ後ろからなら？前から落ちるなら落ちそうですが、hackケースが見つかりません。直感は貪欲は落ちると言っていますが、他の方針は思いつきません。堂々巡りです。 貪欲の実装の軽さ+WAの1ペナと思考ロックによる時間の浪費+直感が間違っている可能性を比較すると、1ペナもらったほうがギリギリ重症ぐらいで済みそうな気がします²。ということで提出。ちゃんとWA、想定内です。

ということで、違う方針を考えます。少し考え直すと、自明に答えの下界が$0$, 上界は$\frac{N}{2}$で、どう見ても単調性があるので答えの二分探索が見えてきますが、判定関数を正しく書けば二分探索分の$\log$を落とすことができそうです。 上界が$\frac{N}{2}$ということはそれ以前のものは上に、以降のものは下に配置すると決め打っても良さそうです。上下を分ければ、あとは作れるなら作る貪欲でよいです。提出

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

fn main() {
    input!{
        n: usize,
        a: [u64; n],
    }
    let v = a[0..n/2].iter().copied().collect_vec();
    let w = a[n/2..].iter().copied().collect_vec();
    let mut vi = 0;
    let mut wi = 0;

    let mut ans = 0;
    while vi < v.len() && wi < w.len() {
        if v[vi]*2 <= w[wi] {
            ans += 1u64;
            vi += 1;
            wi += 1;
        } else {
            wi += 1;
        }
    }
    println!("{}", ans);
}

G - Simultaneous Kagamimochi 2(Upsolve)

餅$i$を上に配置するときに、下に配置しうる最小のindexを持って何かをすることを考えましたが、そこから分からず。

解法としては、indexそのものを持つのではなく、「何個進んだところの餅からは配置可能であるか」を持ちます³(これを$C$と書きます)。ここで、(各クエリに対して)$k$個配置可能であるか？という問題[^problem]を考えると、

を満たす最大の$K$が答えとなります。これは、$L$から始めて前半の$k$項は上段に配置(これが$L+k-1$に対応)し、その各餅について「餅$i$を上段に置いたときの下段に起きうる一番手前の餅とペアを作って、それ以降の餅は全てペアを作れると仮定したとき($\text{max}(C_i, k)$に対応)の右端が$R$に収まるか」を判定しています。判定は左辺を最も大きくする$i$についてのみ調べれば良いことを念頭に式をよく見ると、$\max_{L\leq i < L+k} C_i$が高速に求まれば解の二分探索が可能であるので、$C$をセグ木に乗せればよいです。

よって、この問題が解けました。木上の二分探索をすれば$\log$が一つ落ちるみたいですが、C++やRustであればそこまで気にしなくてもよいでしょう。提出

use ac_library::{Max, Segtree};
use proconio::{input, marker::Usize1};

fn main() {
    input!{
        n: usize,
        mut a: [u64; n],
        q: usize,
    }
    a.push(INF);
    let mut seg :Segtree<Max<usize>> = Segtree::new(n);
    for (i, ai) in a[0..n].iter().enumerate() {
        seg.set(i, a.lower_bound(*ai * 2) - i);
    }

    let check = |l: usize, r: usize, k: usize| -> bool {
        let val = seg.prod(l..l+k);
        l+k-1+val.max(k)<=r
    };

    for _ in 0..q {
        input! {
            l: Usize1,
            r: Usize1
        }

        let mut ok = 0;
        let mut ng = n-l;

        while ng-ok>1 {
            let mid = (ok+ng)/2;
            if check(l, r, mid) {
                ok = mid;
            } else {
                ng = mid;
            }
        }
        println!("{}", ok);
    }
}

pub static INF: u64 = 1e18 as u64;

pub trait VecLibs<T: std::cmp::Ord> {
    fn lower_bound(&self, elm: T) -> usize;
    fn upper_bound(&self, elm: T) -> usize;
}

impl<T: std::cmp::Ord> VecLibs<T> for Vec<T> {
    fn lower_bound(&self, elm: T) -> usize {
        let mut left = 0;
        let mut right = self.len();
        while left < right {
            let mid = (left + right) / 2;
            if self[mid] < elm {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        left
    }

    fn upper_bound(&self, elm: T) -> usize {
        let mut left = 0;
        let mut right = self.len();
        while left < right {
            let mid = (left + right) / 2;
            if self[mid] <= elm {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        left
    }
}

$R-L=1$のときに二分探索のwhileが最初からfalseになる場合があり、ちょっと手間取りました。