paizaオンラインハッカソン7に参加してみた – サンタ服(C++, Swift)

2015.12.27
注意: この記事は1年以上前に掲載されたものです。情報が古い場合がありますのでお気を付け下さい。

当ブログでは順次『paizaオンラインハッカソンVol.7 プログラミングで彼女をつくる』の回答例を上げており、基本的にはC++とSwiftでの解答例を上げている。ソースコードはGitHubでも公開しているので、ソースコードを見たい方はそちらもご確認されたい。今回はカーディガンのお題の解答例と解説を上げたい。今回はもうクリスマスシーズンは終わってしまったが、サンタ服のお題を上げたい。

今回の目的

まず、幅・奥行き・高さ・ケーキを切る回数が入力される。その後、ケーキを切る回数に応じてどの方向 ((ケーキを上から見て縦あるいは横のどちらかのみで、水平方向に切ることはない)) ・どの場所で切るのかが入力される。それをもとに切り分けられたケーキのうち、一番体積が小さいものを当てるものである。

サンプルコード

C++

参考URL: https://github.com/saitomarch/POH7/blob/master/cpp/santa.cpp

#include <iostream>
#include <sstream>
#include <string>
#include <vector>
#include <cstdlib>
using namespace std;
string readline() {
    string str;
    getline(cin, str);
    return str;
}
vector<string> split(const string &str, char sep) {
    vector<string> vec;
    istringstream sstream(str);
    string buf;
    while (getline(sstream, buf, sep)) {
        vec.push_back(buf);
    }
    return vec;
}
int main() {
    auto cake_arr = split(readline(), ' ');

    const auto x = stoi(cake_arr[0]);
    const auto y = stoi(cake_arr[1]);
    const auto z = stoi(cake_arr[2]);
    const auto n = stoi(cake_arr[3]);

    vector<int> cut_x, cut_y;

    for (auto cnt = 0; cnt < n; cnt++) {
        auto cut_arr = split(readline() , ' ');
        switch(stoi(cut_arr[0])) {
        case 0:
            cut_x.push_back(stoi(cut_arr[1]));
            break;
        case 1:
            cut_y.push_back(stoi(cut_arr[1]));
            break;
        default:
            break;
        }
    }

    sort(cut_x.begin(), cut_x.end());
    sort(cut_y.begin(), cut_y.end());

    int w = x, h = y;
    for (int idx = 0; idx <= cut_x.size(); idx++) {
        int tmp_w = ((idx == cut_x.size()) ? x : cut_x[idx]) - ((idx > 0) ? cut_x[idx - 1] : 0);
        if (w > tmp_w) {
            w = tmp_w;
        }
    }
    for (int idx = 0; idx <= cut_y.size(); idx++) {
        int tmp_h = ((idx == cut_y.size()) ? x : cut_y[idx]) - ((idx > 0) ? cut_y[idx - 1] : 0);
        if (h > tmp_h) {
            h = tmp_h;
        }
    }

    cout << w * h * z << endl;

    return EXIT_SUCCESS;
}

Swift

参考URL: https://github.com/saitomarch/POH7/blob/master/swift/santa.swift

let cakearr = readLine()!.characters.split{$0 == " "}.map(String.init)
let x = Int(cakearr[0])!
let y = Int(cakearr[1])!
let z = Int(cakearr[2])!
let cuts = Int(cakearr[3])!

var cut_x = [Int]()
var cut_y = [Int]()

for (var cnt = 0; cnt < cuts; cnt++) {
    let cutarr = readLine()!.characters.split{$0 == " "}.map(String.init)
    switch (Int(cutarr[0])!) {
    case 0:
        cut_x.append(Int(cutarr[1])!)
        break
    case 1:
        cut_y.append(Int(cutarr[1])!)
        break
    default:
        break
    }
}

cut_x.sortInPlace()
cut_y.sortInPlace()

var w = x, h = y

for (var idx = 0; idx <= cut_x.count; idx++) {
    var tmp_w = ((idx == cut_x.count) ? x : cut_x[idx]) - ((idx > 0) ? cut_x[idx - 1] : 0)
    if (w > tmp_w) {
        w = tmp_w
    }
}
for (var idx = 0; idx <= cut_y.count; idx++) {
    var tmp_h = ((idx == cut_y.count) ? y : cut_y[idx]) - ((idx > 0) ? cut_y[idx - 1] : 0)
    if (h > tmp_h) {
        h = tmp_h
    }
}
print (w * h * z)

解説

今回はまずケーキの大きさと切る回数を取得した上で、切る回数を横方向・縦方向別に取得した上でソートした。

その後は、ケーキの大きさと切った場所から幅と奥行きを計算して、最も小さい値になるように計算を行っている。この際のforループでは0スタートとそれぞれの切った回数分以下の範囲になっているため、それぞれの長さの求め方は以下のようになっている。

長さ = (終点であればケーキの一辺の長さ、そうでなければ切った場所) - (始点であれば0、そうでなければ前に切った場所)

これをもとに最小値を取得する。なお、水平方向に切ることはないため、幅と奥行きだけ計算すれば問題ない。

最後は上記の計算で取り出した幅と奥行き、そして高さをかけた値を出力して終わりである。

最後に

今回のお題はこれまでと比較してかなり複雑で難しいものとなっている。特に切り分けた後のケーキの最小値の取り出し方はどうやって計算するかで難儀するだろう。今回当方のやり方では奥行きと幅を分けて計算したが、それ以外の方法も考えられるだろう。

今回は難しいお題だが、自信のある方はぜひチャレンジしてもらいたい.

タイトルとURLをコピーしました