AtCoder Beginner Contest 443

Denso Create Programming Contest 2026（AtCoder Beginner Contest 443）

A Append s

输入一个字符串，在该字符串后追加一个字母 \(s\)，并输出。

string s;
cin>>s;
cout<<s<<'s'<<endl; 

B Setsubun

依次累加年份，直到总数 \(\geq K\)，输出当前年份 \(-n\) 即可。

for(int i=n;;i++)
{
    sum+=i;
    if(sum>=k)
    {
        printf("%d\n",i-n);
        return 0;
    }
}

C Chokutter Addiction

直观想法：暴力枚举每一天，如果 chokutter 处于打开状态 且 当前时间 Aoki-kun 经过，未来 \(100\) 个时间都关闭。统计 chokutter 能开多久。

注意数据范围，\(1\leq T\leq 10^9\)，枚举时间一定会 \(\text{TLE}\)。

换种思路，枚举 Aoki-kun 经过的时间。

可以用 \(cnt\) 表示 \(cnt\) 及之前的 \(100s\) 内 chokutter 处于关闭状态。

每次 Aoki-kun 经过，若当前时间 \(<=cnt\)，chokutter 处于关闭状态，可以无视。

否则，将 chokutter 关闭 \(100s\)，cnt+=100。

同时，用 \(sum\) 记录 chokutter 一共开启了多长时间。

\(sum\) 初值为 \(T\)，每次 \(cnt+100\)，\(sum\) 就 \(-100\)。

sum=t;
for(int i=1;i<=n;i++)
    if(cnt<a[i]) sum-=100,cnt=a[i]+100;
if(cnt>t) sum+=cnt-t;
printf("%d\n",sum);

D Pawn Line

解法1：只能拿部分分

二维动态规划

题单：第7单元 动态规划 - 2 \(T\to Z\)

状态：\(f[i][j]\) 表示 如果第 \(j\) 行第 \(i\) 列放置了棋子，最少需要操作的次数

状态转移：考虑到相邻两列棋子的行数差的绝对值 \(\leq 1\)，

\(f[i][j]\) 仅与 \(f[i-1][j-1]\)、\(f[i-1][j]\) 和 \(f[i-1][j+1]\) 有关

\[f[i][j] = \min\{ f[i-1][j-1],f[i-1][j],f[i-1][j+1] \}+r[i]-j \]

由于题目数据范围 \(2\leq N\leq 3\times 10^5\)，这样写既会 \(\text{TLE}\) 也会 \(\text{MLE}\)，不过还是能有不少分数。

scanf("%d",&t);
while(t--)
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%d",&r[i]);

    for(int i=1;i<=n;i++)
        for(int j=1;j<=n+1;j++)
            f[i][j]=INF;

    for(int i=1;i<=n;i++)
    {
        f[i][1]=min(f[i-1][1],f[i-1][2])+r[i]-1;
        for(int j=2;j<=r[i];j++)
            f[i][j]=min(f[i-1][j],min(f[i-1][j-1],f[i-1][j+1]))+r[i]-j;
    }
    ans=INF;
    for(int i=1;i<=r[n];i++)
        ans=min(ans,f[n][i]);
    printf("%d\n",ans);
}

解法2：

类似于 差分约束

可以参考 官方题解 的证明过程

正反方向依次进行一遍约束条件：

从左到右：\(r[i]=\min\{r[i-1]+1,r[i]\}\)

从右到左：\(r[i]=\min\{r[i+1]+1,r[i]\}\)

对于相邻两列 \(x\)，\(x+1\)，从左到右可以表示 右边高于左边，从右到左可以表示 左边高于右边

因为只能向上移动，不能比原本的位置低，所以要取 \(\min\)

这样进行之后，得到的 \(r[i]\) 就是最优情况下的坐标，进而得到答案

scanf("%d",&t);
while(t--)
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%d",&r[i]),a[i]=r[i];

    for(int i=2;i<=n;i++)
        r[i]=min(r[i-1]+1,r[i]);
    for(int i=n-1;i>=1;i--)
        r[i]=min(r[i+1]+1,r[i]);

    ans=0;
    for(int i=1;i<=n;i++)
        ans+=(LL)a[i]-r[i];
    printf("%lld\n",ans);
} 

E Climbing Silver

动态规划

题单：

第7单元 动态规划 - 1

第7单元 动态规划 - 2

一个性质：

如果某列最下方的墙可以被摧毁（可以移动到该位置），那么这一列 最下方墙上面的格子 都能移动到

反之，如果某列最下方的墙不能被摧毁（无法移动到该位置），那么这一列所有墙都无法被摧毁

状态：\(f[i][j]\) 表示第 \(i\) 行第 \(j\) 列的格子能否到达

状态转移：

用 \(vis[i][j]\) 表示 \((i,j)\) 是否为第 \(j\) 列最下方的墙。

for(int j=1;j<=n;j++)
{
    for(int i=n;i>=1;i--)
    {
        if(a[i][j]) 
        {
            vis[i][j]=true;
            break;
        }
    }
}

根据题意，\((i,j)\) 只能从 \((i+1,j), (i+1,j-1), (i+1,j+1)\) 这三个位置到达

定义 \(flag=f[i+1][j]||f[i+1][j-1]||f[i+1][j+1]\)

如果 \(flag\) 为假，\((i,j)\) 一定不能到达，\(f[i][j]\) 标记为假，否则可能可以到达

对于位置 \((i,j)\)：

• 如果 \(flag\) 为真，而且 \((i,j)\) 为空格，该位置可以到达，\(f[i][j]=true\)

• 如果 \(flag\) 为真，但 \((i,j)\) 为墙：

  • 如果 \((i,j)\) 是第 \(j\) 列最下方的墙，就标记第 \(j\) 列前 \(i\) 行的位置都能到达
  • 反之，该位置不能到达

for(int i=n-1;i>=1;i--)
{
    for(int j=1;j<=n;j++)
    {
        if(f[i][j]) continue;
        bool flag=false;
        if(f[i+1][j]||f[i+1][j-1]||f[i+1][j+1]) flag=true;
        if(flag)
        {
            if(!a[i][j]) f[i][j]=true;
            if(vis[i][j]) 
                for(int k=1;k<=i;k++)
                    f[k][j]=true;
        }
    }
}

注意 \(f[i][j]\) 的初值，从 \((N,C)\) 出发，第 \(C\) 列的所有格子均可到达。

for(int i=1;i<=n;i++)
    f[i][c]=1;

最后输出第 \(1\) 行格子是否可以到达，能到达为 \(1\)，不能到达为 \(0\)。

for(int i=1;i<=n;i++)
    printf("%d",f[1][i]);
puts("");