yukicoder No.77 レンガのピラミッド

問題

問題概要

省略

解法

奇数列のピラミッドに対して全探索を行う。i列のピラミッドを作るときに、足りないブロックの数と、余ったブロックの数それぞれの列に対してカウントする。答えは、足りないところに余りから追加するためのコストが、tarinaiで、 余りを足りないところに追加して、残った分を捨て置き場に移動するコストが、amari - tarianiである。よって答えは、tariani + amari - tarinai = amari となり、amariが答えとなる。それを奇数列のピラミッドすべてに対して行い最小値を求めればよい。

ミス

与えられた列の数より、多いピラミッドを作ることを考慮していなくて、WAを食らった。最終的に答えがamariでよかったとは。

コード

#include <iostream>
#include <queue>
#include <vector>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
#define rep(i,n) for(int i=0;i<(n);i++)
const int INF = 1e9;

int n, a[110];
int main(void){
    cin >> n;
    int sum = 0;
    rep(i, n){
        cin >> a[i];
        sum += a[i];
    }

    int ans = INF;
    for (int i = 1; i <= 200; i += 2)//何列ピラミッドにするか
    {
        int tarinai = 0, amari = 0;
        int aim = 0;
        //左側 + 真ん中
        for (int l = 0; l < i / 2 + 1; ++l)
        {
            aim++;
            if(l < n){
                if(a[l] < aim){
                    tarinai += aim - a[l];
                }else{
                    amari += a[l] - aim;
                }
            }else{
                tarinai += aim;
            }
        }

        aim = 0;
        //右側
        for (int r = i - 1; r >= i / 2 + 1; --r)
        {
            aim++;
            if(r < n){
                if(a[r] < aim){
                    tarinai += aim - a[r];
                }else{
                    amari += a[r] - aim;
                }
            }else{
                tarinai += aim;
            }
        }

        //使わない列
        for (int j = i; j < n; ++j)
        {
            amari += a[j];
        }

        if(amari >= tarinai){
            //足りないところに余りから追加するのに、足りない分だけのコスト tarinai
            //余りを足りないところに追加して、残った分を捨て置き場に移動するコスト amari - tariani
            // ans = min(ans, tarinai + amari - tarinai);
            ans = min(ans, amari);
        }
    }
    printf("%d\n", ans);
    return 0;
}