【AtCoder Regular Contest 100】Solution / Editorial / 题解

【AtCoder Regular Contest 100】Solution / Editorial / 题解

比赛地址

先纪念一下ARC第100场!
Tasks
– Linear Approximation
– Equal Cut
– Or Plus Max
– Colorful Sequences (too hard to deal with it)

C – Linear Approximation

Statement

Snuke has an integer sequence $A$ of length $N$.
He will freely choose an integer $b$.
Here, he will get sad if $A_i$ and $b+i$ are far from each other.
More specifically, the sadness** of Snuke is calculated as follows:
$$abs(A_1 – (b+1)) + abs(A_2 – (b+2)) + … + abs(A_N – (b+N))$$
Here, $abs(x)$ is a function that returns the absolute value of $x$.
Find the minimum possible sadness of Snuke.

Idea

输入的时候先把$A_i$减去$i$,然后对新的数组排序,显然满足条件的$b$就是新数组的中位数。

Code

很短很好写,没有特判。

    for(int i=1; i<=n; i++)
        cin>>a[i], a[i]-=i;
    sort(a+1,a+n+1);
    long long t=a[(n+1)>>1];
    for(int i=1; i<=n; i++)
        ans+=abs(a[i]-t)
    cout<<ans<<endl;

D – Equal Cut

Statement

Snuke has an integer sequence $A$ of length $N$.
He will make three cuts in $A$ and divide it into four (non-empty) contiguous subsequences $B, C, D$ and $E$.
The positions of the cuts can be freely chosen.
Let $P,Q,R,S$ be the sums of the elements in $B,C,D,E$, respectively.
Snuke is happier when the absolute difference of the maximum and the minimum among $P,Q,R,S$ is smaller.
Find the minimum possible absolute difference of the maximum and the minimum among $P,Q,R,S$.

Idea

将数组分成连续的四段,即决定三个分割点,使每一段数字之和尽可能地接近。
$O(n)$枚举第二个分割点,对于每一个不同的位置,都有唯一确定的,分割它左边和右边部分的方案,使得结果对于这个位置最优。发现在第二个点向右移动的时候,第一个和第三个分割点也在不断向右移动。用两个指针处理即可。

Code

// Equal Cut.cpp: 定义控制台应用程序的入口点。
// XG_Zepto, 7/3/2018. All rights reserved.

#include "stdafx.h"
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#define maxn 200101
using namespace std;
long long n,a[maxn],s[maxn],ans=0x7777777777777777;
long long gt(int l,int r){
    return s[r]-s[l];
}
int l,r,m;
bool movl(){
    if (l+1==m) return 0;
    long long t1=abs(gt(0,l)-gt(l,m));
    long long t2=abs(gt(0,l+1)-gt(l+1,m));
    return t2<=t1;
}
bool movr(){
    if (r+1==n) return 0;
    long long t1=abs(gt(m,r)-gt(r,n));
    long long t2=abs(gt(m,r+1)-gt(r+1,n));
    return t2<=t1;
}
void update(){
    long long t1=min(gt(0,l),min(gt(l,m),min(gt(m,r),gt(r,n))));
    long long t2=max(gt(0,l),max(gt(l,m),max(gt(m,r),gt(r,n))));
    ans=min(ans,t2-t1);
}
int main(){
    ios::sync_with_stdio(false);
    cin>>n;
    for (int i=1;i<=n;i++)
        cin>>a[i];
    for (int i=1;i<=n;i++)
        s[i]=s[i-1]+a[i];
    l=1,r=3,m=2;update();
    for (m=2;m<=n-2;m++){
        while(movl()) l++;
        while(movr()) r++;
        update();
    }
    cout<<ans<<endl;
    system("PAUSE");
    return 0;
}

E – Or Plus Max

Statement

There is an integer sequence of length $2^N$: $A_0, A_1, …, A_{2^N-1}$. (Note that the sequence is $0$-indexed.)
For every integer $K$ satisfying $1 \leq K \leq 2^N-1$, solve the following problem:

Let $i$ and $j$ be integers. Find the maximum value of $A_i + A_j$ where $0 \leq i < j \leq 2^N-1$ and $(i$ $or$ $j) \leq K$.
Here, $or$ denotes the bitwise OR.

Idea

以下是官方题解:

中文:找到满足条件的前二大的$A_i$和$A_j$,使得$i \ or \ j ⊆ x$。必要条件是$x ⊆ i$和$x ⊆ j$。令$f_x$为满足条件的$i$和$j$,我们只要从小到大枚举$x$,对于每一个x的非零位j,我们可以用$f_x$的值去更新$f_{x|(1<<j)}$。同时维护$f_{x_0}$和$f_{x_1}$(前二大),最后$O(2^N)$更新答案。
时间复杂度$O(N 2^N)$。

Code

// Or Plus Max.cpp: 定义控制台应用程序的入口点。
// XG_Zepto, 7/4/2018. All rights reserved.

#include "stdafx.h"
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#define maxn 2000100
using namespace std;
int n,a[maxn],f[maxn][2],ans[maxn];
void work(int x,int y){
    if (f[x][0]==y||f[x][1]==y) return;
    if (a[f[x][1]]<a[y]){
        f[x][1]=y;
        if (a[f[x][0]]<a[f[x][1]]) swap(f[x][0],f[x][1]);
    }
}
int main(){
    ios::sync_with_stdio(false);
    cin>>n;
    for (int i=0;i<(1<<n);i++){
        cin>>a[i];f[i][0]=i;
    }
    for (int x=0;x<(1<<n);x++)
        for (int j=0;j<n;j++){
            if ((x>>j)&1) continue;
            work(x|(1<<j),f[x][0]);
            work(x|(1<<j),f[x][1]);
        }
    for (int i=1;i<(1<<n);i++){
        ans[i]=max(ans[i-1],a[f[i][0]]+a[f[i][1]]);
        cout<<ans[i]<<endl;
    }
    system("PAUSE");
    return 0;
}

Summary

这场比赛没有打完就被电话拖住了。。。
幸好当时没有交题不然又是一题选手(

Show Comments