Arc135 partial solution

Competition address

https://atcoder.jp/contests/arc135/tasks.

A - Floor, Ceil - Decomposition

https://atcoder.jp/contests/arc135/tasks/arc135_a.

Answer key

mathematical problem .
Give a positive integer $X$,$f(x)$ Is the maximum product after one pass operation .
hypothesis $X_{-}=\lfloor \frac{x}{2}\rfloor ,X_{+}=\lceil \frac{x}{2}\rceil$. We can write
$$\begin{gathered} f(1)=1 \\ f(X)=max(X,f(X_{-})\times f(X_{+}))\forall x\ge 2 \end{gathered}$$.
Now let's deduce the mathematical formula
$f(X_{-})\times f(X_{+})\ge X_{-}\times X_{+}\ge \frac{X-1}{2}\times \frac{X}{2}\ge \frac{X-1}{4}\times X$.
such , We know when $X\ge 4$ When ,$\frac{X-1}{4}\times X\ge X$.
therefore ：
$$\begin{gathered} f(X)=X\forall X\le 4 \\ f(X)=f(X_{-})\times f(X_{+})\forall X\ge 5 \end{gathered}$$.
such , We can use DFS To achieve .
Let's take a look at the data range ,$1\le X\le 10^{18}$, The data is very big , Need to use memory search to optimize .

AC Code

#include<bits/stdc++.h>
using namespace std;
using LL=long long;
using PLL=pair<LL,LL>;

const LL MO=998244353;

unordered_map<LL, LL> M;

LL dfs(LL x) {
    
    if (M.count(x)) {
    
        return M[x];
    }
    M[x]=x;
    if (x<=4) {
    
        return M[x];
    }
    return M[x]=(dfs(x/2)*dfs((x+1)/2))%MO;
}
int main(){
    
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    LL x;
    cin>>x;

    cout<<dfs(x)<<"\n";

    return 0;
}

B - Sum of Three Terms

https://atcoder.jp/contests/arc135/tasks/arc135_b.

Answer key

It's math again .
Hypothetical sequence $A$ For the sequence that satisfies the condition , such
$S_i=A_i+A_{i+1}+A_{i+2}\Rightarrow A_{i+2}=S_i-A_i-A_{i+1}$.
When $i=1$ When ,$A_3=S_1-A_1-A_2$, This equation has $3$ An unknown number , So we assume that $A_1=a,A_2=b$, We can deduce the following
$$\{\begin{array}{l}{A}_1=a\\ A_2=b\\ A_3=S_1-A_1-A_2=S_1-a-b\\ A_4=S_2-A_2-A_3=S_2-S_1+a\\ A_5=S_3-A_3-A_4=S_3-S_2+b\\ A_6=S_4-A_4-A_5=S_4-S_3-a-b\\ A_7=S_5-A_4-A_6=S_5-S_4+a\\ A_8=S_6-A_6-A_7=S_6-S5+b\\ ...\end{array}$$
such , We know the law . Next we need to know when there is a solution .
The existence of solutions , We can use the simplest sequence $S_1,S_2,S_3$ Is there a pair $(a,b)$ Satisfy , This will get .

$$\{\begin{array}{l}{S}_1\le a\\ S_2\le b\\ a+b\le S_3\end{array}$$
therefore ,
When $S_1+S_2>S_3$ When , There is no solution to the problem .
When $S_1+S_2\le S_3,(a,b)=(S_1,S_2)$, Existence solution .
such , This problem becomes a simulation problem .

AC Code

#include<bits/stdc++.h>
using namespace std;
using LL=long long;
using PLL=pair<LL,LL>;

const int N=3e5+10;
LL s[N];
LL a[N];

int main(){
    
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    LL n;
    cin>>n;
    for (LL i=1; i<=n; i++) {
    
        cin>>s[i];
    }

    LL sum=0;
    LL c1=0;
    for (LL i=1; i<n; i+=3) {
    
        sum+=s[i]-s[i+1];
        c1=max(c1, sum);
    }
    sum=0;
    LL c2=0;
    for (LL i=2; i<n; i+=3) {
    
        sum+=s[i]-s[i+1];
        c2=max(c2, sum);
    }
    sum=0;
    LL c3=0;
    for (LL i=3; i<n; i+=3) {
    
        sum+=s[i]-s[i+1];
        c3=max(c3, sum);
    }

    if (c1+c2+c3>s[1]) {
    
        cout<<"No\n";
        return 0;
    }
    a[1]=c1;a[2]=c2;a[3]=s[1]-c1-c2;
    for (LL i=2; i<=n; i++) {
    
        a[i+2]=s[i]-a[i]-a[i+1];
    }
    cout<<"Yes\n";
    for (LL i=1; i<=n+2; i++) {
    
        cout<<a[i]<<" ";
    }
    cout<<"\n";

    return 0;
}