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

当ブログでは順次『paizaオンラインハッカソンVol.7 プログラミングで彼女をつくる』の回答例を上げており、基本的にはC++とSwiftでの解答例を上げている。ソースコードはGitHubでも公開しているので、ソースコードを見たい方はそちらもご確認されたい。今回は眼帯のお題の解答例と解説を上げたい。

今回のお題の目的

ある巻数の本を集めており、現在持っているもののリストと、売っているもののリストを比較して、買うべきもののリストをSSV形式でなおかつ昇順で出力するという問題である。なお、買うべきものがなければ「None」と出力する。

サンプルコード

C++

参考URL: https://github.com/saitomarch/POH7/blob/master/cpp/eyepatch.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(void){
    auto total_cnt = stoi(readline());
    auto have_cnt = stoi(readline());
    auto have_list = split(readline(), ' ');
    auto sell_cnt = stoi(readline());
    auto sell_list = split(readline(), ' ');

    std::vector<int> should_buy_list;
    for (auto sell : sell_list) {
        bool matches = false;
        for (auto have : have_list) {
            if (stoi(sell) == stoi(have)) {
                matches = true;
                break;
            }
        }
        if (!matches) {
            should_buy_list.push_back(stoi(sell));
        }
    }

    sort(should_buy_list.begin(), should_buy_list.end());

    string str = "";
    for (auto should_buy : should_buy_list) {
        if (!str.empty()) {
            str += " ";
        }
        str += to_string(should_buy);
    }
    cout << (str.empty() ? "None" : str) << endl;
    return EXIT_SUCCESS;
}

Swift

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

let totalCnt = Int(readLine()!)!
let haveCnt = Int(readLine()!)!
let haveList = readLine()!.characters.split{$0==" "}.map(String.init)
let sellCnt = Int(readLine()!)!
let sellList = readLine()!.characters.split{$0==" "}.map(String.init)
var shouldBuyList = [Int]()
for (sell) in sellList {
    var matches = false
    for (have) in haveList {
        if (sell == have) {
            matches = true
            break
        }
    }
    if (!matches) {
        shouldBuyList.append(Int(sell)!)
    }
}
shouldBuyList.sortInPlace()
var str = ""
for (shouldBuy) in shouldBuyList {
    if (!str.isEmpty) {
        str += " "
    }
    str += String(shouldBuy)
}
print(str.isEmpty ? "None" : str)

解説

今回のお題では、入力されるものは以下の通りとなっている。

1. 本の合計巻数
2. 持っている本の巻数
3. 持っている本のリスト
4. 売ってっている本の巻数
5. 売っている本のリスト

なお、今回のC++及びSwiftの解法では実際に使うのは3と5だけである。1、2、4についてはC++及びSwiftでは可変長の配列及びforeach文 ((C++では範囲ベースのfor文、Swiftではfor-in文と言われているが、ここではforeach文とする)) を使う関係上、実際には利用しない捨て変数となっている ((一部の言語で必要になると考えられる)) が、ここではひとまず変数として取得している ((整合性チェックで使うことは可能だが、今回は省略している)) 。

今回の解法は簡潔にまとめると以下のようになる。

1. 売っているリストをforeach文で回す(要素A)
   1. 持っているリストをforeach文で回す(要素B)
   2. AとBが一致していたらすでに持っているというフラグを立てて、持っているリストのforeach文を抜ける
   3. 持っているリストのforeach文を抜けた後、持っているフラグが立っていなければ買うべきリストに要素Aを入れる
2. 売っているリストのforeach文を抜けたら、買うべきリストを昇順でソートする
3. 買うべきリストをSSV形式として文字列に変換する ((この時、買うべきリストをforeach文で回すため、出力するための文字列が空白かどうかを判別し、空白でなければスペースを結合するようにする))
4. 結果を出力する

上記の方法で比較的簡潔に答えを出すことができる。

最後に

今回の問題はC++やSwiftにおいては記述の仕方にもよるが不要になる変数が多いが、それに惑わされずに何が必要かをちゃんと理解できていればうまくいけるだろう。

さすがにサンタ服・水着ほどではないが、それなりに頭を使う問題であるため、この辺りはできるようになりたいところである。