paizaで杏ちゃんにサンタコスさせてみた

そろそろクリスマスですね！

彼女の杏ちゃんにもサンタクロースの恰好を要求してもいいんじゃないですかね？！

水着、メガネを杏ちゃんにご着用頂いていましたが今回はサンタコスに挑戦してもらいます。

水着回の記事

takachan.hatenablog.com

めがね回の記事
takachan.hatenablog.com

海辺で金髪の杏ちゃんにサンタコス、、、きっと似合うと思います。。うえっへっへ。

このヘッポコSEの実力見せてやるぜ！

・・・

・・・・・・

・・・・・・・・・

やりました！

今回は何故か5分でできました。拍子抜けです。

今回も、特に策を弄さず事に当たったため実行速度は0.3～0.5秒でした。

解き方

前回、前々回と同様に、しょっぱなからネタバレをすると面白くないので

• 仕様の確認
• 考え方
• コーディング

を、それぞれ考えていきたいと思います。

仕様の確認

まずは仕様の確認を仕様と思います。

どれどれ・・・・

SEはこれくらい分りやすい仕様書書いてほしいですね！！

おおよそ、面積の比較みたいですね。

入力は小さい値から順番に入力されるのではなくバラバラにされるようです。

今回は、指定される変数値が多いので仕様をよく読んで理解したほうがよさそうです。
また、最大値が各変数値0 ～ 100までなので力技で全てを巡回して計算する対応で対応可能と思われます。

考え方

この問題よく見ると、(最後に考慮する必要はありますが)Z方向の高さは毎回計算する必要ありません。

全ての要素が90度で考えられる立方体の問題なので、

「立方体の面積」ではなく、「長方形の面積」で計算して最後に選択されている面にZをかかければつじつまが合いそうです。

単純化して、平面で扱うため、各入力データの読み込みが終わった時に、論理的に以下のようなグリッド上の格子模様をイメージして扱いたいので、X方向とY方向で別々の配列に記録して昇順にソートします。

その後左上から右下に順に面積を計算し、一番小さい値を記録していきます。

ここで各グリッドの面積の求め方ですが、動的に計算を行わないとプログラム上で処理できないため、

x方向の開始地点を「x_start」、終了地点を「x_end」
y方向は「y_start」、「y_end」とした場合

area = (x_end - x_start) * (y_end - y_start)

で求められます。

実際はxとyの各値は配列に入れる予定なので

x方向のグリッドの各分割を記録した配列を「in_x」
y方向のグリッドの各分割を記録した配列を「in_y」として、2重のfor文i, jでループを回した場合

area = (in_x[i + 1] - in_x[i]) * (in_y[j + 1] - in_y[j])

もしくは

area = (in_x[1] - in_x[i - 1]) * (in_y[j] - in_y[j - 1])

となります。カレントポジションから前を参照するか、後を参照するかで添え字への加算および減算の扱いは違います。
そして、最後に回答を表示するときに area * Z とすれば、一番小さい容積が求まります。

コーディング

解説は上記考え方とコメントの通りです。
ネタバレなんで自分でコード書きたい人はご注意を・・・

using System;
using System.Collections.Generic;

namespace ConsoleApplication1
{
    internal class Program
    {
        public static void Main(string[] args)
        {

            string[] ss = Console.ReadLine().Split(' ');

            // 他の値は必要になるまで数値に変換しない
            int n = int.Parse(ss[3]);

            var in_x = new List<int>();
            var in_y = new List<int>();

            for (int i = 0; i < n; i++)
            {
                string[] _temp = Console.ReadLine().Split(' ');
                if (int.Parse(_temp[0]) == 0)
                {
                    in_x.Add(int.Parse(_temp[1]));
                }
                else
                {
                    in_y.Add(int.Parse(_temp[1]));
                }
            }

            // 終点の値をそれぞれ追加する
            in_x.Add(int.Parse(ss[0]));
            in_y.Add(int.Parse(ss[1]));

            // 標準関数の挙動に任せてソートする
            in_x.Sort();
            in_y.Sort();

            // ループ用変数類
            int ans = int.MaxValue;
            int base_x = 0;
            int base_y = 0;

            for (int y = 0; y < in_y.Count; y++)
            {
                for (int x = 0; x < in_x.Count; x++)
                {
                    int _temp_ans = (in_x[x] - base_x) * (in_y[y] - base_y);
                    if (ans > _temp_ans)
                    {
                        ans = _temp_ans;
                    }
                    base_x = in_x[x];
                }
                base_x = 0;
                base_y = in_y[y];
            }
            Console.WriteLine(ans * int.Parse(ss[2])); // 最後に容積化する
        }
    }
}

まとめ

あれ・・・・大変申し訳ないですが、これ、説明するのが微妙に難しいですね・・・・。
伝わりましたでしょうか？考え方の内容が分かりづらい場合、コードを直接参照したほうが早いかもしれません。

今回は解くのはそう苦労しませんでしたが、人に伝えるのが難しいと勉強になってしまいました。