paizaオンラインハッカソン Vol.5に参加してみた。今回は前回の記事『paizaオンラインハッカソン Vol.5に参加してみた』に続いて、ミッションMINAMIのコードを書いてみた。詳細については、これから述べたい。
ミッションMINAMI
サンプルコード
[code lang=”cpp”]#include <iostream>
#include <sstream>
#include <vector>
using namespace std;
vector<int> split(const string &str) {
vector<int> vec;
char sep = ‘ ‘;
stringstream sstream(str);
string buf;
while (getline(sstream, buf, sep)) {
vec.push_back(stoi(buf));
}
return vec;
}
struct Info {
int rows;
int columns;
Info(int _rows, int _columns) {
const int MIN = 0;
const int MAX = 20;
if (rows < MIN || MAX < rows || columns < MIN || MAX < columns) {
throw "invalid rows and/or columns";
}
rows = _rows;
columns = _columns;
}
};
int main(void){
// テーブル情報を取得
string infostr;
getline(cin, infostr);
auto infoArr = split(infostr);
enum {
COLUMNS = 0,
ROWS,
};
Info info(infoArr[ROWS], infoArr[COLUMNS]);
// テーブルを作成
int table[info.rows][info.columns];
for (int row = 0; row < info.rows; row++) {
string rowStr;
getline(cin, rowStr);
auto rowArr = split(rowStr);
for (int column = 0; column < info.columns; column++) {
table[row][column] = rowArr[column];
}
}
// 爆発させて、爆発させたあとの個数を取得する
int explodedNums[info.columns];
for (auto &item : explodedNums) {
item = 0;
}
for (auto row : table) {
for (int column = 0; column < info.columns; column++) {
if (row[column] == 1) {
explodedNums[column] += 1;
}
}
}
// テーブルに展開する(落下済みのため、下からテーブルを代入する)
int explodedTable[info.rows][info.columns];
for (int row = info.rows; row > 0; row–) {
auto &rowItems = explodedTable[row – 1];
for (int column = 0; column < info.columns; column++) {
if (explodedNums[column] > 0) {
rowItems[column] = 1;
explodedNums[column] -= 1;
}else{
rowItems[column] = 0;
}
}
}
// 出力する
for (auto &rowItems : explodedTable) {
string rowStr = "";
for (auto item : rowItems) {
if (rowStr.length() > 0) {
rowStr += " ";
}
rowStr += to_string(item);
}
cout << rowStr << endl;
}
return 0;
}[/code]
解説
いわゆる落ちものパズルの要領で、爆発したら落ちるのを利用して、落ちた後の状態を出力する問題だが、私の場合は、以下の手順を踏んでみた。
- フィールドのサイズを取得して、それを元にフィールドを作成
- 爆発させた後のそれぞれのカラムの爆弾の個数をセットする
- 2をもとに、爆弾を配置し直して、出力
この方法は一旦爆弾の個数を取得した上で再配置している以上、効率的とは言えず、複数の色があった時に対応できない問題があるが、今回の課題をクリアするにあたっては問題とならないため、この方法を用いた。色情報がある場合は、別の方法をしなければならないだろう。
今回の場合、C++では文字列の分割や数値・文字列変換がわかればクリアはさほど難しくはないだろう。
結果
cf. ミッションMINAMIの結果
すべてのテストケースで0.01秒だった。普通に書く分には動作速度は意識する必要はないだろう。
今回はC++が比較的容易にコードが書けるようだったので、当方はC++で記述した。プログラミングを学習している人はどういう要件が求められていて、どうやったら実現できるのかを考えてやってみるとよいだろう。
ウェブマスター。本ブログでITを中心にいろいろな情報や意見などを提供しています。主にスマートフォン向けアプリやウェブアプリの開発を携わっています。ご用の方はコメントかコンタクトフォームにて。
