AtCoder Beginner Contest 330 (AからFまで) 確認

Rustで競プロするのに慣れたりライブラリを整備したりするのも兼ねて、ABC330を解きます。
今回は用事でコンテストには出ていません。どうせネタバレを喰らわずにバチャはできないので、直後に問題を見ています。

自作ライブラリを使用し、ローカルで事前に展開する形で提出しています。展開前のコードを記述します。
AtCoderで使えるクレートに含まれない関数などを使っている可能性があること、破壊的変更をこの記事の投稿後にしている可能性があることにご注意ください。
github.com

A問題

atcoder.jp
そろそろRustの型に慣れてきたので、foldやfilterなどに慣れたいですね。練習です。
実行時間が0msになってびっくりしました。
atcoder.jp

#[allow(unused_attributes)] #[macro_use] #[allow(unused_imports)] use not_leonian_ac_lib::*;

fn main() {
    /// 標準入力のマクロ（インタラクティブ問題ならば中のマクロを変更）
    macro_rules! input {
        ($($tt:tt)*) => {
            proconio::input!($($tt)*);
            // proconio::input_interactive!($($tt)*);
        };
    }

    input!(n:usize,l:usize,a:[usize;n]);
    outputln!(a.iter().filter(|&&a| a>=l).count());
}

B問題

問題文の理解に2分くらいかかりました。
本番だとどうだろう。もっと早くサンプル見て理解してたかな。
しかもサンプルが性格悪すぎる。
それはそれとして、Rustにもclamp関数があるんですね。次いつ使うんだってくらい競プロで使うところは想像できませんが。
atcoder.jp

#[allow(unused_attributes)] #[macro_use] #[allow(unused_imports)] use not_leonian_ac_lib::*;
use num_traits::clamp;

fn main() {
    /// 標準入力のマクロ（インタラクティブ問題ならば中のマクロを変更）
    macro_rules! input {
        ($($tt:tt)*) => {
            proconio::input!($($tt)*);
            // proconio::input_interactive!($($tt)*);
        };
    }

    input!(n:usize,l:usize,r:usize,a:[usize;n]);
    vec_range(0, n, |i| clamp(a[i], l, r)).outputln();
}

C問題

atcoder.jp
C++から競プロ始めたので、こういう問題には潜在的な恐怖感があります。
Rustだと整数についてのsqrt関数の返り値が整数型なのでだいぶ楽ですね。
その代わり、切り上げを考慮する必要がありますね。とりあえず+1しておけば何とかなりはします。
後、前回あたりにabs_diff関数をライブラリに入れたのですが、まったく同名の関数がプリミティブにありました。
ライブラリからは消しておきます。破壊的変更…
atcoder.jp

#[allow(unused_attributes)] #[macro_use] #[allow(unused_imports)] use not_leonian_ac_lib::*;
use num_integer::Roots;

fn main() {
    /// 標準入力のマクロ（インタラクティブ問題ならば中のマクロを変更）
    macro_rules! input {
        ($($tt:tt)*) => {
            proconio::input!($($tt)*);
            // proconio::input_interactive!($($tt)*);
        };
    }

    input!(d:usize);
    let mut ans=E[13];
    for x in 0..=d.sqrt()+1 {
        if x*x>=d {
            ans.chmin(x*x-d);
        } else {
            let y=(d-x*x).sqrt();
            ans.chmin(d.abs_diff(x*x+y*y));
            let y=(d-x*x).sqrt()+1;
            ans.chmin(d.abs_diff(x*x+y*y));
        }
    }
    outputln!(ans);
}

フェルマーの二平方和定理を利用した別解でも解いてみました。
素数砂漠ならぬ二平方和砂漠のオーダーは研究途上のようで、論文を調べた限り下界はともかく上界はほとんど出てきませんでした。
ですが、制約の範囲だと砂漠は大きくないようで通ります。
Rustで実質無限ループのfor文って書けるんですね…
atcoder.jp

#[allow(unused_attributes)] #[macro_use] #[allow(unused_imports)] use not_leonian_ac_lib::*;

fn main() {
    /// 標準入力のマクロ（インタラクティブ問題ならば中のマクロを変更）
    macro_rules! input {
        ($($tt:tt)*) => {
            proconio::input!($($tt)*);
            // proconio::input_interactive!($($tt)*);
        };
    }

    input!(d:usize);
    for i in 0.. {
        for n in [d+i, d-i] {
            let pe=n.prime_factorize();
            let mut ok=true;
            for (p,e) in pe {
                if p%4==3 && e%2==1 {
                    ok=false;
                }
            }
            if ok {
                outputln!(i);
                return;
            }
        }
    }
}

フェルマーの二平方和定理、ミラー・ラビン素数判定法、ポラード・ロー法、const fnによる線形篩で1ms(Fastest)になりました。
想定解での最速が2msなので絶対想定解の小手先の高速化でいけたって…
ついでにミラー・ラビン素数判定法とポラード・ロー法はライブラリに追加しました。
atcoder.jp

use std::sync::Mutex;

use num_integer::gcd;
use once_cell::sync::Lazy;

fn main() {
    macro_rules! input {
        ($($tt:tt)*) => {
            proconio::input!($($tt)*);
        };
    }

    input!(d:usize);
    let lsb=d&(usize::MAX-d+1);
    let m=d/lsb;
    if m%4==1 {
        if is_sum_of_two_squares(m) {
            println!("0");
            return;
        }
    }
    for i in 1.. {
        for n in [d+i, d-i] {
            let lsb=n&(usize::MAX-n+1);
            let m=n/lsb;
            if m%4==1 {
                if is_sum_of_two_squares(m) {
                    println!("{i}");
                    return;
                }
            }
        }
    }
}

fn is_prime(n: usize) -> bool {
    if n<NMAX {
        return IS_PRIME[n];
    }
    if n==2 {
        return true;
    }
    if n==1 || n%2==0 {
        return false;
    }
    ModInt::set_mod(n);
    let m=n-1;
    let lsb=m&(usize::MAX-m+1);
    let s=lsb.ilog2();
    let d=m/lsb;
    let tests=[2, 325, 9375, 28178, 450775, 9780504, 1795265022];
    for a in tests {
        if a%n==0 {
            continue;
        }
        let mut x=num::pow(ModInt::new(a),d);
        let mut r=0;
        if x.v==1 {
            continue;
        }
        while x.v!=m {
            x=num::pow(x,2);
            r+=1;
            if x.v==1 || r==s {
                return false;
            }
        }
    }
    true
}

fn find_prime_factor(n: usize) -> usize {
    if n%2==0 {
        return 2;
    }
    ModInt::set_mod(n);
    let m=(n as f64).powf(0.125) as usize+1;
    for c in 1..n {
        let f=|x:usize| ((ModInt::new(x)*ModInt::new(x)).v+c)%n;
        let mut y=0;
        let (mut g,mut q,mut r)=(1,1,1);
        let mut k=0;
        let mut x=y;
        let mut ys=y;
        while g==1 {
            x=y;
            while k<3*r/4 {
                y=f(y);
                k+=1;
            }
            while k<r && g==1 {
                ys=y;
                for _ in 0..std::cmp::min(m,r-k) {
                    y=f(y);
                    q=(ModInt::new(q)*ModInt::new(x.abs_diff(y))).v;
                }
                g=gcd(q, n);
                k+=m;
            }
            k=r;
            r*=2;
        }
        if g==n {
            g=1;
            y=ys;
            while g==1 {
                y=f(y);
                g=gcd(x.abs_diff(y), n);
            }
        }
        if g==n {
            continue;
        }
        if is_prime(g) {
            return g;
        } else if is_prime(n/g) {
            return n/g;
        } else {
            return find_prime_factor(g);
        }
    }
    panic!("{n}");
}

fn is_sum_of_two_squares(mut n: usize) -> bool {
    while n>=NMAX && !is_prime(n) {
        let p=find_prime_factor(n);
        if p%4==3 {
            let mut s=0;
            while n%p==0 {
                n/=p;
                s+=1;
            }
            if s%2==1 {
                return false;
            }
        } else {
            while n%p==0 {
                n/=p;
            }
        }
    }
    if n>=NMAX {
        return n%4!=3;
    }
    IS_SUM_OF_TWO_SQUARES[n]
}

static MOD:Lazy<Mutex<usize>>=Lazy::new(|| Mutex::new(2));

#[derive(Clone)]
struct ModInt {
    v: usize
}

impl ModInt {
    fn set_mod(m: usize) {
        *MOD.lock().unwrap()=m;
    }
    fn new(val: usize) -> Self {
        ModInt { v: val%*MOD.lock().unwrap() }
    }
}

impl num::One for ModInt {
    fn one() -> Self {
        ModInt { v: 1 }
    }
}

impl std::ops::Mul for ModInt {
    type Output = ModInt;
    fn mul(self, rhs: Self) -> Self::Output {
        let m=*MOD.lock().unwrap();
        if m>=1<<32 {
            ModInt { v: ((self.v%m) as u128*(rhs.v%m) as u128%m as u128) as usize }
        } else {
            ModInt { v: (self.v%m)*(rhs.v%m)%m }
        }
    }
}

const NMAX:usize=500_000;

const RET:([bool; NMAX], [bool; NMAX])=linear_sieve();

const IS_PRIME:[bool; NMAX]=RET.0;
const IS_SUM_OF_TWO_SQUARES:[bool; NMAX]=RET.1;

const fn linear_sieve() -> ([bool; NMAX], [bool; NMAX]) {
    let mut lpf=[0;NMAX];
    let mut is_prime=[false;NMAX];
    let mut is_sum=[false;NMAX];
    let mut primes=[0;NMAX];
    let mut cur=0;
    is_sum[0]=true;
    is_sum[1]=true;
    let mut i=2;
    while i<NMAX {
        if lpf[i]==0 {
            lpf[i]=i;
            is_prime[i]=true;
            primes[cur]=i;
            cur+=1;
            if i%4!=3 {
                is_sum[i]=true;
            }
        }
        let mut j=0;
        while j<cur {
            let p=primes[j];
            if p*i>=NMAX || p>lpf[i] {
                break;
            }
            lpf[p*i]=p;
            if p%4==3 {
                if i%p==0 && is_sum[i/p] {
                    is_sum[p*i]=true;
                }
            } else {
                if is_sum[i] {
                    is_sum[p*i]=true;
                }
            }
            j+=1;
        }
        i+=1;
    }
    (is_prime,is_sum)
}

D問題

atcoder.jp
考察すると、答えは全ての'o'についての、同じ行にある自分以外の'o'の個数と同じ列にある自分以外の'o'個数の積の総和であることがわかります。（Lの真ん中に注目する形）
すると、同じ組を重複して数えることもありません。
実装について、iproduct!マクロを使うと2重ループを1重ループのように書けることに気付きました。（もちろん、全ての添字に対して同じ処理をするだけの場合にしか使えませんが）
あと、こういう場合にlet mut ans=0usize;のように明示的に型を指定する癖もつけておくべきかもしれません。（1敗）
atcoder.jp

use itertools::iproduct;
#[allow(unused_attributes)] #[macro_use] #[allow(unused_imports)] use not_leonian_ac_lib::*;
use proconio::marker::Chars;

fn main() {
    /// 標準入力のマクロ（インタラクティブ問題ならば中のマクロを変更）
    macro_rules! input {
        ($($tt:tt)*) => {
            proconio::input!($($tt)*);
            // proconio::input_interactive!($($tt)*);
        };
    }

    input!(n:usize,s:[Chars;n]);
    let mut ohcnt=vec![0;n];
    let mut owcnt=vec![0;n];
    for (i,j) in iproduct!(0..n, 0..n) {
        if s[i][j]=='o' {
            ohcnt[i]+=1;
            owcnt[j]+=1;
        }
    }
    let mut ans=0usize;
    for (i,j) in iproduct!(0..n, 0..n) {
        if s[i][j]=='o' {
            ans+=(ohcnt[i]-1)*(owcnt[j]-1);
        }
    }
    outputln!(ans);
}

E問題

atcoder.jp
正直コンテスト出てたらこれの実装で手間取ってそうだったので延命しました。
下の記事を参考にしつつ、前にも必要だと思ったBTreeMapによる個数を管理する多重集合をライブラリ化しました。
これでmex関連はだいぶ楽になったと思います。
rsk0315.hatenablog.com
atcoder.jp

use std::collections::BTreeSet;

#[allow(unused_attributes)] #[macro_use] #[allow(unused_imports)] use not_leonian_ac_lib::*;
use proconio::marker::Usize1;

fn main() {
    /// 標準入力のマクロ（インタラクティブ問題ならば中のマクロを変更）
    macro_rules! input {
        ($($tt:tt)*) => {
            proconio::input!($($tt)*);
            // proconio::input_interactive!($($tt)*);
        };
    }

    input!(n:usize,q:usize,mut a:[usize;n],ix:[(Usize1,usize);q]);
    let mut mset=MultiSet::<usize>::new();
    let mut comp=BTreeSet::<usize>::from_iter(0..=n);
    for &a in &a {
        if a<=n {
            mset.insert_one(a);
            comp.remove(&a);
        }
    }
    for (i,x) in ix {
        if a[i]<=n {
            if mset.remove_one(a[i]).unwrap()==0 {
                comp.insert(a[i]);
            }
        }
        a[i]=x;
        if x<=n {
            mset.insert_one(x);
            comp.remove(&x);
        }
        outputln!(comp.first().unwrap());
    }
}

他の方はそもそもmexを高速に返せる多重集合のデータ構造をライブラリに追加していたので自分もそうしました。
抜かりなくいきましょう。
atcoder.jp

#[allow(unused_attributes)] #[macro_use] #[allow(unused_imports)] use not_leonian_ac_lib::*;
use proconio::marker::Usize1;

fn main() {
    /// 標準入力のマクロ（インタラクティブ問題ならば中のマクロを変更）
    macro_rules! input {
        ($($tt:tt)*) => {
            proconio::input!($($tt)*);
            // proconio::input_interactive!($($tt)*);
        };
    }

    input!(n:usize,q:usize,mut a:[usize;n],ix:[(Usize1,usize);q]);
    let mut ms=MexMultiSet::new(n);
    for &a in &a {
        ms.insert_one(a);
    }
    for (i,x) in ix {
        ms.remove_one(a[i]);
        a[i]=x;
        ms.insert_one(a[i]);
        outputln!(ms.mex());
    }
}

F問題

atcoder.jp
想定解の実装重いですね…
今回出てたら（slope trickに気付かない限り）Fが解けずにEを遅解きしてめちゃくちゃ冷えてた気がします…助かった
swap、VecDeque、クロージャ、自作ライブラリのget_from_last関数やget_mut_from_last関数を目一杯使って100行超えてしまったので、コンテスト中書けた気がしませんね…
atcoder.jp

use std::{mem::swap, collections::VecDeque};

#[allow(unused_attributes)] #[macro_use] #[allow(unused_imports)] use not_leonian_ac_lib::*;

fn main() {
    /// 標準入力のマクロ（インタラクティブ問題ならば中のマクロを変更）
    macro_rules! input {
        ($($tt:tt)*) => {
            proconio::input!($($tt)*);
            // proconio::input_interactive!($($tt)*);
        };
    }

    input!(n:usize,mut k:usize,xy:[(usize,usize);n]);
    let mut x=vec_range(0, n, |i| xy[i].0);
    let mut y=vec_range(0, n, |i| xy[i].1);
    x.sort();
    y.sort();
    let mut xs=VecDeque::from(x.rle());
    let mut ys=VecDeque::from(y.rle());
    let moving=|s: &mut VecDeque<(usize,usize)>, is_front: bool, dist: usize, cnt:usize| {
        if is_front {
            if dist==s[1].0-s[0].0 {
                s.pop_front();
                s[0].1+=cnt;
            } else {
                s[0].0+=dist;
            }
        } else {
            if dist==s.get_from_last(1).0-s.get_from_last(2).0 {
                s.pop_back();
                s.get_mut_from_last(1).1+=cnt;
            } else {
                s.get_mut_from_last(1).0-=dist;
            }
        }
    };
    loop {
        let xdist=xs.get_from_last(1).0-xs[0].0;
        let ydist=ys.get_from_last(1).0-ys[0].0;
        if xdist<ydist {
            swap(&mut xs, &mut ys);
        }
        let xdist=xs.get_from_last(1).0-xs[0].0;
        let ydist=ys.get_from_last(1).0-ys[0].0;
        if xs.len()==1 {
            break;
        }
        if xdist>ydist {
            if xs[0].1<xs.get_from_last(1).1 {
                let cnt=xs[0].1;
                let dist=min(min(xs[1].0-xs[0].0, xdist-ydist), k/cnt);
                if dist>0 {
                    moving(&mut xs, true, dist, cnt);
                    k-=dist*cnt;
                } else {
                    break;
                }
            } else {
                let cnt=xs.get_from_last(1).1;
                let dist=min(min(xs.get_from_last(1).0-xs.get_from_last(2).0, xdist-ydist), k/cnt);
                if dist>0 {
                    moving(&mut xs, false, dist, cnt);
                    k-=dist*cnt;
                } else {
                    break;
                }
            }
        } else {
            if xs[0].1<xs.get_from_last(1).1 {
                if ys[0].1<ys.get_from_last(1).1 {
                    let xcnt=xs[0].1;
                    let ycnt=ys[0].1;
                    let dist=min(min(xs[1].0-xs[0].0, ys[1].0-ys[0].0), k/(xcnt+ycnt));
                    if dist>0 {
                        moving(&mut xs, true, dist, xcnt);
                        moving(&mut ys, true, dist, ycnt);
                        k-=dist*(xcnt+ycnt);
                    } else {
                        break;
                    }
                } else {
                    let xcnt=xs[0].1;
                    let ycnt=ys.get_from_last(1).1;
                    let dist=min(min(xs[1].0-xs[0].0, ys.get_from_last(1).0-ys.get_from_last(2).0), k/(xcnt+ycnt));
                    if dist>0 {
                        moving(&mut xs, true, dist, xcnt);
                        moving(&mut ys, false, dist, ycnt);
                        k-=dist*(xcnt+ycnt);
                    } else {
                        break;
                    }
                }
            } else {
                if ys[0].1<ys.get_from_last(1).1 {
                    let xcnt=xs.get_from_last(1).1;
                    let ycnt=ys[0].1;
                    let dist=min(min(xs.get_from_last(1).0-xs.get_from_last(2).0, ys[1].0-ys[0].0), k/(xcnt+ycnt));
                    if dist>0 {
                        moving(&mut xs, false, dist, xcnt);
                        moving(&mut ys, true, dist, ycnt);
                        k-=dist*(xcnt+ycnt);
                    } else {
                        break;
                    }
                } else {
                    let xcnt=xs.get_from_last(1).1;
                    let ycnt=ys.get_from_last(1).1;
                    let dist=min(min(xs.get_from_last(1).0-xs.get_from_last(2).0, ys.get_from_last(1).0-ys.get_from_last(2).0), k/(xcnt+ycnt));
                    if dist>0 {
                        moving(&mut xs, false, dist, xcnt);
                        moving(&mut ys, false, dist, ycnt);
                        k-=dist*(xcnt+ycnt);
                    } else {
                        break;
                    }
                }
            }
        }
    }
    let xdist=xs.get_from_last(1).0-xs[0].0;
    let ydist=ys.get_from_last(1).0-ys[0].0;
    if xdist<ydist {
        swap(&mut xs, &mut ys);
    }
    outputln!(xdist);
}

evimaさんによる別解。
正方形の長さで二分探索します。以降、長さをとします。
x軸について注目します。正方形の右端をとしたとき、各点が正方形の内部にたどり着くまでの移動回数のグラフは＼＿／の形になります。
そして、点の座標をとすると、傾きはとで変わります。そして、この関数は絶対値関数を使って表せ、となります。
つまり、個の絶対値関数の和の最小化に問題を落とし込めるため、以下の定理を用いることができます。
manabitimes.jp
あとはx軸とy軸の両方について最小値を求めて、その和が以内であるかを二分探索の判定条件とすればよいです。
itertools::Itertools::merge関数を、わかりやすい関数にしておきmerge_vecs関数としてライブラリに追加しました。
atcoder.jp

#[allow(unused_attributes)] #[macro_use] #[allow(unused_imports)] use not_leonian_ac_lib::*;

fn main() {
    /// 標準入力のマクロ（インタラクティブ問題ならば中のマクロを変更）
    macro_rules! input {
        ($($tt:tt)*) => {
            proconio::input!($($tt)*);
            // proconio::input_interactive!($($tt)*);
        };
    }

    input!(n:usize,k:usize,xy:[(usize,usize);n]);
    let mut x=vec_range(0, n, |i| xy[i].0);
    let mut y=vec_range(0, n, |i| xy[i].1);
    x.sort();
    y.sort();
    outputln!(binary_search(max(x.get_from_last(1)-x[0], y.get_from_last(1)-y[0]).isize(), -1, |l| {
        let l=l.usize();
        let xl=vec_range(0, n, |i| x[i]+l);
        let yl=vec_range(0, n, |i| y[i]+l);
        let xpos=merge_vecs(&x, &xl)[n-1];
        let ypos=merge_vecs(&y, &yl)[n-1];
        let dist=|p:usize, pos:usize| if p+l<pos { pos-p-l } else if p>pos { p-pos } else { 0 };
        let xsum=x.iter().fold(0, |s, &x| s+dist(x, xpos));
        let ysum=y.iter().fold(0, |s, &y| s+dist(y, ypos));
        xsum+ysum<=k
    }));
}

元々select_nth_unstable関数で実装するつもりだったので、速度の実験も兼ねてこちらも書いてみました。
こちらのほうが速かったです。sort関数でもやってみましたが論外でした。
atcoder.jp

#[allow(unused_attributes)] #[macro_use] #[allow(unused_imports)] use not_leonian_ac_lib::*;

fn main() {
    /// 標準入力のマクロ（インタラクティブ問題ならば中のマクロを変更）
    macro_rules! input {
        ($($tt:tt)*) => {
            proconio::input!($($tt)*);
            // proconio::input_interactive!($($tt)*);
        };
    }

    input!(n:usize,k:usize,xy:[(usize,usize);n]);
    let x=vec_range(0, n, |i| xy[i].0);
    let y=vec_range(0, n, |i| xy[i].1);
    let &xmax=x.iter().max().unwrap();
    let &xmin=x.iter().min().unwrap();
    let &ymax=y.iter().max().unwrap();
    let &ymin=y.iter().min().unwrap();
    outputln!(binary_search(max(xmax-xmin, ymax-ymin).isize(), -1, |l| {
        let l=l.usize();
        let mut xs=vec_range(0, 2*n, |i| if i<n { x[i] } else { x[i-n]+l });
        let mut ys=vec_range(0, 2*n, |i| if i<n { y[i] } else { y[i-n]+l });
        xs.select_nth_unstable(n-1);
        ys.select_nth_unstable(n-1);
        let xpos=xs[n-1];
        let ypos=ys[n-1];
        let dist=|p:usize, pos:usize| if p+l<pos { pos-p-l } else if p>pos { p-pos } else { 0 };
        let xsum=x.iter().fold(0, |s, &x| s+dist(x, xpos));
        let ysum=y.iter().fold(0, |s, &y| s+dist(y, ypos));
        xsum+ysum<=k
    }));
}

slope trickによる別解。
slope trickをライブラリに追加しました。本当にライブラリで殴るだけで解けてしまいますね。
オーダーにlogが追加でつくため速くはありませんが、上の別解をsort関数でやるよりは速かったです。
atcoder.jp

#[allow(unused_attributes)] #[macro_use] #[allow(unused_imports)] use not_leonian_ac_lib::*;

fn main() {
    /// 標準入力のマクロ（インタラクティブ問題ならば中のマクロを変更）
    macro_rules! input {
        ($($tt:tt)*) => {
            proconio::input!($($tt)*);
            // proconio::input_interactive!($($tt)*);
        };
    }

    input!(n:usize,k:usize,xy:[(usize,usize);n]);
    let x=vec_range(0, n, |i| xy[i].0);
    let y=vec_range(0, n, |i| xy[i].1);
    let &xmax=x.iter().max().unwrap();
    let &xmin=x.iter().min().unwrap();
    let &ymax=y.iter().max().unwrap();
    let &ymin=y.iter().min().unwrap();
    outputln!(binary_search(max(xmax-xmin, ymax-ymin).isize(), -1, |l| {
        let mut x_st=SlopeTrick::<usize>::new();
        for &x in &x {
            x_st.add_left_slope(x);
            x_st.add_right_slope(x+l.usize());
        }
        let mut y_st=SlopeTrick::<usize>::new();
        for &y in &y {
            y_st.add_left_slope(y);
            y_st.add_right_slope(y+l.usize());
        }
        x_st.min()+y_st.min()<=k
    }));
}

G問題もやってもよかったのですが、他のやりたい予定が意外に多いのと、積の和典型が得意ではないのと、今週風邪を引いてしまったのでなしにします。
場合分けの問題は一生コンテスト中に解ける気がしませんね…