Mister雑記

競プロやります。

AGC003-A 「Wanna go back home」 (200)

問題リンク

概要

N, E, W, Sからなる文字列 Sが与えられる。

高橋くんは |S|日の旅行計画を立てており、 i日目には S i文字目の方角へ正の距離だけ直進する。

各日程の移動距離を適切に設定することで、旅行後に高橋くんが最初にいた場所に戻ってくることが可能か判定せよ。

制約

  •  1 \leq |S| \leq 1000

解説

 S中に文字Nが出たとしよう。このとき、一度もSが出てこないとゴール地点はどうやってもスタート地点より北側にあることになる。逆に、一度でもSが出ればNとSでの移動距離の総和を一致させることで常にゴールとスタートの南北座標を一致させられる。

これはEとWでも同じことである。よって、各方角について出てきたかどうかを記録して、NとS、EとWそれぞれについてその情報が一致していればOKとなる。

実装例

#include <iostream>
#include <string>
using namespace std;

int main() {
    string S;
    cin >> S;

    const string way = "EWSN";
    bool dir[4];
    fill(dir, dir + 4, false);
    for (char c : S) {
        for (int i = 0; i < 4; ++i) {
            if (c == way[i]) dir[i] = true;
        }
    }

    if (dir[0] == dir[1] && dir[2] == dir[3]) {
        cout << "Yes" << endl;
    } else {
        cout << "No" << endl;
    }
    return 0;
}

感想

  • 「bool型のXORってどうやって出すんだっけ?」とか思っていた時期が私にもありました。
    • 答えは上のコードの通り。