これも場合分けを丁寧に...

問題概要

高橋君は無限に広い 2 次元平面上に住んでいて、N 日間の旅行をします。高橋君の旅程は長さ N の文字列 S であり、はじめは家にいます。

$i$ 日目には、

S[i] = 'N' なら北へ
S[i] = 'W' なら西へ
S[i] = 'S' なら南へ
S[i] = 'E' なら東へ

移動します。

高橋君は、各日の移動距離は決めていません。各日の移動距離をうまく決めることで、高橋君が N 日間の旅程をすべて消化したときに家にいるようにできるかどうか判定してください。

制約

$1 \le N \le 1000$

考えたこと

「各日程の移動距離は決めていない」と言われたら考えるべきこととして、

細かいことは後で調整が効く

という構造がありそうだということがあると思う。例えば

S = "NNNNNSN" とかだとしたら、'N' のところをどんな風に進んだとしても 'S' のところをうまく調節すれば戻って来れる。
S = "NNNSNSN" とかみたいに 'S' が 2 個あっても尚更。
ダメなのは S = "NNNNN" みたいな場合。どうやっても最終地点は北の方向に動いてしまう。つまり 'N' と 'S' の両方があるか、両方ともないか、であれば OK で、片方だけあるのはダメ

以上は南北についての考察だったが、東西についても一緒。まとめると

'N' と 'S' について、「両方登場する」「両方とも登場しない」
'W' と 'E' について、「両方登場する」「両方とも登場しない」

が Yes になる必要十分条件である。

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

bool solve(const string &S) {
    map<char,int> ma; // あるなら 1、ないなら 0
    for (int i = 0; i < S.size(); ++i){
        if (ma.count(S[i])) ma[S[i]] = 1;
        else ma[S[i]] = 1;
    }
    if (ma['N'] != ma['S']) return false;
    if (ma['W'] != ma['E']) return false;
    return true;
}

int main() {
    string S; cin >> S;
    if (solve(S)) cout << "Yes" << endl;
    else cout << "No" << endl;
}

追記 1

この問題のもう一つの典型構造として

x 軸と y 軸は独立に考えて良い

というのがある。これはあらゆる難易度帯で超頻出の考え方となる。

追記 2

この手の Yes/No 判定問題では、

bool solve() {

}

int main() {
  if (solve()) cout << "Yes" << endl;
  else cout << "No" << endl;
}

という風に Yes/No を判定する bool 関数を作っておくと便利な印象がある。その理由は

明らかに "No" な場合を最初に return false; として弾いてしまいやすい

というのがすごくある。

けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

AtCoder AGC 003 A - Wanna go back home (茶色, 200 点)

問題概要

制約

考えたこと

追記 1

追記 2