Loading...
1/20/2025
+58と激デカ勝ちです。やったね。
パット見はpythonのevalに投げることで簡単に解けそうですが、よく見ると2文字目が*
ではなくx
なので流石に無理。素直に一文字目と三文字目をスライスで取得して数値型に変換してから掛けるのが良いでしょう。提出
s = input() a = int(s[0]) b = int(s[2]) print(a*b)
であり、これはから始めて順に掛けていけば計算できます。に等しいが存在することが保証されているので、等しくなったら出力を行ってプログラムを終了すればよいです。提出
use proconio::input; fn main() { input!{ x: u64, } let mut a = 1; for i in 1.. { a *= i; if a == x { println!("{}", i); return; } } }
ABC335C - Loong Trackingが思い出されます。実際にヘビが抜けていくことをシミュレーションすると、列にいるヘビの数をとするととなり間に合いません。ここで、抜けていったヘビの長さの総和と「ヘビが一匹も抜けていないとしたときに、番目に入ってきたヘビの頭の座標」を保持しておくことで差分計算が可能になり、全体でかな?で計算が可能です。提出
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); } } }
かなり嫌な気持ちになります。なんですかこれは?
作図をすると以下のことに気づきます。x-y平面に円が存在すると考えると、中心の座標がにある正方形の個数はです。
これは、軸に乗っていない、x軸よりも下にある正方形の個数が三平方の定理を用いることで計算でき(個になる)、対称性から上下は同じ数になるので2倍し、軸に乗っている正方形1つを足すというような気持ちです。第一象限だけを求めて4倍にすることも考えましたが、どうしても軸の上にある正方形の重複を省くのが面倒になりそうだったのでこういった方針を取りました。
これで全体でとなり、十分高速です。提出
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になるのがかなり怖いなぁと思いました。緑中位だと思うんだが...
入力例1を手で試すと、初期のレートからレートの逆転は発生しない事がわかります。例えば、レート範囲2~4のコンテストにレート4の人が参加するとレートは5になりますが、以降は「最初からレート5の人」と「最初レート4で、参加によって5になった人」のRatedコンテストは全ておなじになるためです。 よって、初期のレーティングに対して、回のコンテストを終えたときのレーティングをとすると、は広義単調増加となっています(に対してこれは成り立ちます)。レーティング範囲を木上の二分探索することによって、クエリとして与えられる最大のレーティングをとするとでこの問題を解くことができます。提出
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)); } }