ABC389

+58と激デカ勝ちです。やったね。

A - 9x9

パット見はpythonのevalに投げることで簡単に解けそうですが、よく見ると2文字目が * ではなく x なので流石に無理。素直に一文字目と三文字目をスライスで取得して数値型に変換してから掛けるのが良いでしょう。 提出

s = input()
a = int(s[0])
b = int(s[2])
print(a*b)

B - tcaF

\(N! = 1 \times 2 \times \cdots \times N\) であり、これは \(i=1\) から始めて順に掛けていけば計算できます。 \(X\) に等しい \(N\) が存在することが保証されているので、等しくなったら出力を行ってプログラムを終了すればよいです。 提出

use proconio::input;

fn main() {
    input!{
        x: u64,
    }
    let mut a = 1;
    for i in 1.. {
        a *= i;
        if a == x {
            println!("{}", i);
            return;
        }
    } 
}

C - Snake Queue

ABC335C - Loong Tracking が思い出されます。実際にヘビが抜けていくことをシミュレーションすると、列にいるヘビの数を \(N\) とすると \(O(NQ)\) となり間に合いません。ここで、抜けていったヘビの長さの総和と「ヘビが一匹も抜けていないとしたときに、 \(i\) 番目に入ってきたヘビの頭の座標 \(A_i\) 」を保持しておくことで差分計算が可能になり、全体で \(O(Q)\) かな？で計算が可能です。 提出

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

fn main() {
    input!{
        q: usize,
    }

    let mut mergin = 0;
    let mut v = vec![];
    let mut len = vec![];
    let mut sum = 0;
    let mut i = 0;
    for _ in 0..q {
        input! {
            t: u8
        }
        if t == 1 {
            input! {
                l: u64,
            }
            v.push(sum);
            len.push(l);
            sum += l;
        } else if t == 2 {
            mergin += len[i];
            i += 1;
        } else {
            input! {
                k: Usize1,
            }
            println!("{}", v[i+k]-mergin);
        }
    }
}

D - Squares in Circle

かなり嫌な気持ちになります。なんですかこれは？
作図をすると以下のことに気づきます。x-y平面に円が存在すると考えると、中心の \(x\) 座標が \(i\) にある正方形の個数は \(\lfloor\sqrt{r^2-(i+0.5)^2}-0.5\rfloor \times 2 + 1\) です。

これは、 \(x\) 軸に乗っていない、x軸よりも下にある正方形の個数が三平方の定理を用いることで計算でき( \(\lfloor\sqrt{r^2-(i+0.5)^2}-0.5\rfloor\) 個になる)、対称性から上下は同じ数になるので2倍し、 \(x\) 軸に乗っている正方形1つを足すというような気持ちです。第一象限だけを求めて4倍にすることも考えましたが、どうしても軸の上にある正方形の重複を省くのが面倒になりそうだったのでこういった方針を取りました。
これで全体で \(O(r)\) となり、十分高速です。 提出

r = int(input())
r2 = r**2
ans = 0

import math
for i in range(1, r):
    p = math.floor(math.sqrt(r2 - pow(i+0.5, 2)) - 0.5)
    val = p * 2 + 1
    ans += val 

ans *= 2
ans += math.floor(math.sqrt(r2 - (0.5**2)) - 0.5)*2 + 1

print(ans)

これは賢いと思う。誤差が怖いなぁとは思っておりお祈りしていましたが、この問題のもとでは気にする必要はないようです。浮動小数点数わからない。
あと、この問題が茶diffになるのがかなり怖いなぁと思いました。緑中位だと思うんだが...

F - Rated Range

入力例1を手で試すと、初期のレートからレートの逆転は発生しない事がわかります。例えば、レート範囲2~4のコンテストにレート4の人が参加するとレートは5になりますが、以降は「最初からレート5の人」と「最初レート4で、参加によって5になった人」のRatedコンテストは全ておなじになるためです。
よって、初期のレーティング \(i\) に対して、 \(x\) 回のコンテストを終えたときのレーティングを \(A_i\) とすると、 \(A\) は広義単調増加となっています( \(x=1, 2, \cdots, Q\) に対してこれは成り立ちます)。レーティング範囲を木上の二分探索することによって、クエリとして与えられる最大のレーティングを \(X\) とすると \(O((N+Q)\log X)\) でこの問題を解くことができます。 提出

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

struct Mn;
impl MapMonoid for Mn {
    type M = Max<usize>;
    type F = usize;
    
    fn identity_map() -> Self::F {
        0
    }
    
    fn mapping(f: &Self::F, x: &<Self::M as ac_library::Monoid>::S) -> <Self::M as ac_library::Monoid>::S {
        *f+x
    }
    
    fn composition(f: &Self::F, g: &Self::F) -> Self::F {
        *f+g
    } 
}

fn main() {
    input!{
        n: usize,
        r: [(usize, usize); n],
        q: usize,
        qv: [usize; q],
    }

    static N :usize = 5e5 as usize + 5;
    let mut seg :LazySegtree<Mn> = LazySegtree::new(N);
    for i in 0..N {
        seg.set(i, i);
    }

    for (l, r) in r {
        let li = seg.max_right(0, |x| x < l);
        let ri = seg.max_right(0, |x| x < r+1);
        if li < N && ri < N {
            seg.apply_range(li..ri, 1);
        }
    }
    for q in qv {
        println!("{}", seg.get(q));
    }
}