ABC165 解説 - Motsu_xe 競プロのhogeやfuga

初手Eが簡単すぎてそんな訳ねーだろって疑ってたけど結局あっててグダったり、Cで制約全く見てなくて全然ダメだったの除けば、まあサクサク解けたんじゃないかな(2問グダってる時点でサクサクではないかも)。結果は49:06 18位。1ページ目に収まっていい感じですね。

コンテストページ

A - We Love Golf

思考

何も考えずに全探索すれば余裕で間に合います。

実装例

#include<bits/stdc++.h>
using namespace std;

int main(){
    int a,b,k;
    cin>>k>>a>>b;
    for(;a<=b;++a) if(a%k==0) return puts("OK"),0;
    puts("NG");
}

コンテスト中のACコード

B - 1%

思考

複利って知ってますか？指数関数的に借金が増えていってやばいことで有名です。まあ今回は預金なんですが、額面が指数的に変化するので、目標金額に対してかかる日数は対数オーダーです。ご丁寧に最大ケースが置いてあるので、愚直で間に合うことがわかります。不動小数点数でも誤差は大丈夫ですが、~~まあ*101/100の方が安全ですね~~これだとWAだわやっベー、オーバーフローします。いや本番中は気づいてたんだけど、うん。

実装例

#include<bits/stdc++.h>
using namespace std;
using ll=long long;

int main(){
    ll x,t{100},ans{};
    cin>>x;
    while(t<x){
        ++ans;
        t=t*1.01;
    }
    cout<<ans<<endl;
}

コンテスト中のACコード

C - management

思考

制約をよく見てなくてクソむずい感じがして辛かったです。 $A_1=1$ としてよい*1ので、全探索しても高々 $M^{N-1}\leq 10^9$ 通りしかなくて、実際には単調増加だけ調べればいいので、これより遥かに少ないです*2。全探索は再帰で前から決めていけばいいです。簡単のために地域を $0\leq A_i\lt M$ としています。

実装例

#include<bits/stdc++.h>
using namespace std;
void chmax(int&x,int y);

int n,m,q,a,b,c,d,ans{},A[10]={};
struct t{
    int a,b,c,d;
};
vector<t> e;

void f(){
    int tmp{};
    for(auto&[aa,bb,cc,dd]:e){
        if(A[bb]-A[aa]==cc) tmp+=dd;
    }
    chmax(ans,tmp);
}

void rec(int i=1){
    if(i==n){
        f();
        return;
    }
    for(int j=A[i-1];j<m;++j){
        A[i]=j;
        rec(i+1);
    }
}

int main(){
    cin>>n>>m>>q;
    for(int i{}i<q;++i){
        cin>>a>>b>>c>>d;
        --a,--b;
        e.push_back(t{a,b,c,d});
    }
    rec();
    cout<<ans<<endl;
}

コンテスト中のACコード

D - Floor Function

思考

$x=pB+q(0\leq q \lt B)$ とおくと、
$\begin{align*} \left\lfloor\frac{Ax}B\right\rfloor-A\left\lfloor\frac xB\right\rfloor &=\left\lfloor\frac{A(pB+q)}B\right\rfloor-A\left\lfloor\frac {pB+q}B\right\rfloor\\ &=Ap+\left\lfloor\frac{Aq}B\right\rfloor-Ap\\ &=\left\lfloor\frac{Aq}B\right\rfloor \end{align*}$
となる。 $q$ のとり取りうる範囲を考えると、 $0\leq q\leq \min(N,B-1)$ であり、 $q$ が最大のとき $\left\lfloor\frac{Aq}B\right\rfloor$ が最大となるため、 $\left\lfloor\frac{A\min(N,B-1)}B\right\rfloor$ が答えとなる。

実装例

#include<bits/stdc++.h>
using namespace std;
using ll=long long;

int main(){
    ll a,b,n;
    cin>>a>>b>>n;
    cout<<(a*min(b-1,n))/b<<endl;
}

コンテスト中のACコード

E - Rotation Matching

思考

$M=\left\lfloor\frac{N-1}2\right\rfloor$ のときだけ考えればよい。 $N$ 回やるので、第1ラウンドの対戦者の数字の差だけで戦う組が全て定まる。ここでの数字の差というのは、N人を円環上に並べたときの、2者の近い方の距離である。もし差が同じものがあればアウトで、全部違うならOKである。これは簡単に構成できる(図を書くのはめんどいので実装を見てください)。

実装例

#include<bits/stdc++.h>
using namespace std;

int main(){
    int n,m;
    cin>>n>>m;
    bool f{true};
    if(n&1){
        int l=1,r=n;
        for(int i{};i<m;++i){
            cout<<l<<" "<<r<<'\n';
            ++l,--r;
        }
    }
    else{
        int l=1,r=n;
        for(int i{};i<m;++i){
            cout<<l<<" "<<r<<'\n';
            ++l,--r;
            if(f&&4*l>n) ++l,f=false;
        }
    }
}

コンテスト中のACコード

F - LIS on Tree

思考

この問題めっちゃ好きです。
まず一般の配列上でのLISを知っていますか？知っていてください、既知とします。ブラックボックス化すると、長さ $N$ の配列の $1,..,i$ 番目までのLISの長さを順に1つあたり $O(logN)$ 、合計 $O(NlogN)$ で求められます。このとき利用するのは、ある配列Lに対して、配列の要素の変更1要素あたり高々1回、配列上のlower_boundの計算2回のみで達成されます。
木上を頂点1を根としてDFSしながら、頂点に入る時にLを更新し、頂点から出る時にLを元に戻すことで、常に頂点1からある頂点へのパス上の $A_i$ についてのLISが解ける状況になります。
あとはどうやって頂点から出る時にLを元に戻すかですが、変更する際に、変更したindexと変更前の $A_i$ をstackに突っ込んでおくことで達成できます。全体で $O(NlogN)$ で解くことができました。

実装例

#include<bits/stdc++.h>
using namespace std;

struct q{
    int idx,b;
};
 
struct tree{
    size_t n,r,md;
    vector<vector<int>> e;
    vector<int> l,A,ans;
    stack<q> Q;
    explicit tree(int n):n(n),e(n),l(n+1,INT_MAX),A(n),ans(n),Q(){}
    void built(){
        static int a,b;
        for(auto&i:A) cin>>i;
        for(int i{};i<n-1;++i){
            cin>>a>>b;
            --a,--b;
            add(a,b);
        }
    }
    void add(int a,int b){
        e[a].emplace_back(b);
        e[b].emplace_back(a);
    }
    void r_dfs(int i=0,int p=-1){
        int idx=lower_bound(l.begin(),l.end(),A[i])-l.begin();
        Q.push(q{idx,l[idx]});
        l[idx]=A[i];
        ans[i]=lower_bound(l.begin(),l.end(),INT_MAX)-l.begin();
        for(auto j:e[i]) if(j!=p) r_dfs(j,i);
        auto [id,b]=Q.top();Q.pop();
        l[id]=b;
    }
};

int main(){
    int n;
    cin>>n;
    tree t(n);
    t.built();
    t.r_dfs();
    for(auto&i:t.ans) cout<<i<<'\n';
}