山傘のプログラミング勉強日記

プログラミングに関する日記とどうでもよい雑記からなるブログです。

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

問題

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

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

sugarknri.hatenablog.com

考え方

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

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

 2 * n - 1

になります。ここで n n ^2 \leq ブロックの個数 \lt (n + 1)^2を満たすものです。この値と元の列 N を比べて動かないブロックの数を数えます。

コード

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);
    }
}

感想

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