PaizaオンラインハッカソンVol.6に参加してみた(霧島京子ミッション, C++)

PaizaオンラインハッカソンVol.6に参加してみた(六村リオミッション, C++)PaizaオンラインハッカソンVol.6に参加してみた(緑川つばめミッション, C++)に続いて、霧島京子ミッションにも挑戦してみた。個人的にはこれが一番しくじったが・・・。

回答例

[code lang=”cpp”]#include <iostream>
#include <vector>
#include <sstream>

using namespace std;

/// 文字列を分割する
/// @param str 文字列の参照
/// @param sep 分割に使う文字
/// @return 分割後の配列(std::vector)
vector<string> splitStringToVector(const string &str, char sep) {
vector<string> vec;
istringstream sstream(str);
string buf;
while (getline(sstream, buf, sep)) {
vec.push_back(buf);
}
return vec;
}
using namespace std;

int main(void){
// マスの数を取得する
string numOfCellsString;
getline(cin, numOfCellsString);
auto numOfCells = stoi(numOfCellsString);
if (numOfCells < 2 || 100 < numOfCells) {
throw "Invalid numOfCells detected";
}
auto goal = numOfCells – 1;

// マスを取得する
string cellsString;
getline(cin, cellsString);
auto cells = splitStringToVector(cellsString, ‘ ‘);
for (auto cell : cells) {
if (stoi(cell) < -100 || 100 < stoi(cell)) {
throw "Invalid num detected";
}
}

if (numOfCells != cells.size()) {
throw "numOfCells and size of cells.size not match.";
}

// 出目数を取得する
string actsString;
getline(cin, actsString);
auto acts = stoi(actsString);
if (acts < 0 || 100 < acts) {
throw "Invalid acts detected.";
}

// 出目の処理を行う
for (auto act = 0; act < acts; act++) {
// 出目を取得する
string numString;
getline(cin, numString);
auto num = stoi(numString);
std::vector<int> moveLog;

bool finished = false;

int times = 0;
while (true) {
if (num == goal) {
finished = true;
break;
}else if (num < 1 || goal < num) {
finished = false;
break;
}else{
auto moves = stoi(cells.at(num));
if (moves == 0) {
finished = false;
break;
}else{
num += moves;
bool infinity = false;
for (auto moved : moveLog) {
if (num == moved) {
infinity = true;
break;
}
}
if (infinity) {
finished = false;
break;
}else{
moveLog.push_back(num);
}
}
}
times++;
}

if (finished) {
cout << "Yes" << endl;
}else{
cout << "No" << endl;
}
}
return 0;
}[/code]

解説

このコードは、主に以下のフェーズに分かれている。

  1. マスの個数を指定する
  2. マスを作成する
  3. 出目数を設定する
  4. 出目処理を行う

マスの個数を指定する

これについては、単純にstoiを使えば問題ない。

マスを作成する

マスを作成する際は、今回も空白を用いてstd::vectorとして生成する。こうすることであとがラクになる。念のため1で指定したマスの個数と実際に生成したマスが一致しているかどうかを確認して、一致していなければ例外を投げるようにしている。

出目数を設定する

これも入力文字列に単純にstoiすれば問題ない。

出目処理を行う

これが一番の鬼門である。やるべきこととしては、まず出目数を指定した上で、

  1. 出目数でゴールに到達するならゴール、ゴールを超えたならゲームオーバー
  2. 止まったマスを確認して、指定した数の分進む(プラスならゴールよりへ、マイナスならスタートよりへ)
  3. もしゴール以外でこれ以上進めない(数値が0)ならゲームオーバー
  4. まだ進める(0以外)なら、前にも到着したことのあるマスならゴールできないと判断してゲームオーバー、そうでなければ到着したフラグを立てる。
  5. 1に戻る

といった計算を行うようにする。基本的には配列は0スタートであることさえ気をつければクリアできるはずだが、結構難解な部分があるため、注意したほうがいいだろう。

結果

cf: https://paiza.jp/poh/joshibato/kirishima/result/36d0cba3

テストケースはすべて通過、処理時間も0.01秒だった。なお失敗回数は2回で、3回目の通過だった。

最後に

これで当方がC++で書いたPOH Vol.6のコードは全部となる。さらに「え、妻が松江?」松江Ruby会議07協賛 回文作成プログラミングコンテスト|POH6+もあり、Rubyでチャレンジした方は豪華ギフトのチャンスもあるのでぜひチャレンジしてみよう。

ウェブマスター。本ブログでITを中心にいろいろな情報や意見などを提供しております。仕事依頼や相談などについては、Contact Formよりお願いいたします。