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

問題

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

解けなかったので解説を読みました。

sugarknri.hatenablog.com

考え方

余事象を考えると分かりやすいんでしょうか。

最終的に作られるピラミッドの列は、

になります。ここで は を満たすものです。この値と元の列 を比べて動かないブロックの数を数えます。

コード

import java.util.Arrays;
import java.util.Scanner;

public class Exec0077 {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int N = scan.nextInt();
        int A[] = new int[101];
        Arrays.fill(A, 0);
        // 1オリジン
        for(int i = 1; i <= N; i++) {
            A[i] = scan.nextInt();
        }

        scan.close();

        // ブロックの合計
        int sum = 0;
        for(int i = 1; i <= N; i++) {
            sum += A[i];
        }

        // ピラミッドの真ん中の値nを求める
        // ピラミッドの列数 = 2 * n - 1
        // cost: 初期値で動かないブロックの数
        int n = 1;
        int cost = 0;


        for(int i = 1; i < 1000; i++) {
            if(sum == i * i) {
                n = i;
                break;
            }else if(sum < i * i) {
                n = i - 1;
                break;
            }
        }
        //cost = sum - n * n;
        cost = 0;
        // System.out.println(n);
        int l;
        if(2 * n - 1>= N) {
            l = N;
        }else {
            l = 2 * n - 1;
        }
        for(int i = 1; i <= l; i++) {
            if(i <= n) {
                if(A[i] >= i) {
                    cost += i;
                }else {
                    cost += A[i];
                }
            }else {
                int t = 2 * n - i;
                if(A[i] >= t) {
                    cost += t;
                }else {
                    cost += A[i];
                }
            }
        }
        // 移動回数はブロックの個数 - 動かないブロックの数
        int ans = sum - cost;
        System.out.println(ans);
    }
}

感想

この発想は僕にはできないですね。