Pongeponge

Codingame『Highest truncated pyramid』

(トミショウ) 富商 パワーストン 水晶 クリスタル ピラミッド 神秘 ピラミット 天然石 開運 風水 CK20
 よくあるCの練習問題っぽいけど、台形になったとたんにややこしくなった感!


問題

 N個のレンガ(*)を全部使ってピラミッドを作る。
例えばN = 1なら、こう。

N=6ならこう。

**
***
N=7の場合なら、
***
****
こんな感じ、と。


どうしようか

 一発で解決する方法を思いつかなかったので、高さから攻める事にした。
台形の上底をa、高さをh、与えられるブロック数をNとする。
等差数列の和の公式を使うと、こう。
{ N = \frac{h(2a+h-1)}{2} }
高さhから上底aを求めたいのでわちゃわちゃと変形するとこうなる。
{a = \frac{2N-h^{2} +h}{2h}}
hの値を変えて突っ込むとaの値が求まるので、最も大きいhの値を調べればいい。
ただし、aは自然数の範囲。


ちょっと面白い部分

 これ、出力を見てみるとh=2の時のNが全部素数になってる。



コード
using System;
using System.Linq;
using System.IO;
using System.Text;
using System.Collections;
using System.Collections.Generic;

/**
 * Auto-generated code below aims at helping you parse
 * the standard input according to the problem statement.
 **/
class Solution
{
    static void Main(string[] args)
    {
        int total = int.Parse(Console.ReadLine());
        Console.Error.WriteLine(total);

        TP2 pyramid = new TP2(total);

        Console.WriteLine(pyramid.Draw());
    }


    //クラス内クラス
    public class TP2
    {
        private int total;
        private int width;
        private int height;

        //コンストラクタ
        public TP2(int N)
        {
            total = N;
            height = 1;
            width = N;

            ps();
        }

        //台形の上底と高さを調べる
        private void ps()
        {
            int bt = total * 2;
            int ht = (total + 1) / 2;

            for (int h = 2; h <= ht; h++)
            {
                //高さhから上底aを計算する
                int a = (bt - h * h + h) / (2 * h);
                //上底aと高さhからサイズsを求める
                int s = (h * (2 * a + h - 1)) / 2;

                if (a > 0 & s == total)
                {
                    width = a;
                    height = h;
                }
            }
        }

        //台形を描画した文字列を返す
        public string Draw()
        {
            string str = "";

            for (int h = 0; h < height; h++)
            {
                string tmp = "";

                for (int w = 0; w < width + h; w++)
                {
                    tmp += "*";
                }

                str += tmp;

                if (h < height - 1) str += System.Environment.NewLine;
            }

            return str;
        }
    }

}
追記

 もしかしたら、こうしたらより早くなるのかもしれない。

        private void ps()
        {
            int bt = total * 2;
            int ht = (total+1) / 2; 

            for(int h = IntRootOf2N(); h >= 2; h--)
            {
                int a = (bt - h * h + h) / (2 * h);
                int s = (h * (2 * a + h - 1)) / 2;

                if (s == total)
                {
                    width = a;
                    height = h;
                    break;
                }
            }
        }

        private int IntRootOf2N()
        {
            return (int)(Math.Sqrt(2 * total));
        }