AGC003 A - Wanna go back home

備忘録

問題

atcoder.jp

回答

import sys
import os
import math
import bisect
import itertools
import collections
import heapq
import queue
import array
import time
import numpy as np
from numpy import linalg as LA

# 時々使う
# import numpy as np
# from decimal import Decimal, ROUND_HALF_UP
# from scipy.sparse.csgraph import csgraph_from_dense, floyd_warshall
# from collections import defaultdict, deque

# 再帰の制限設定
sys.setrecursionlimit(10000000)


def ii(): return int(sys.stdin.buffer.readline().rstrip())
def il(): return list(map(int, sys.stdin.buffer.readline().split()))
def fl(): return list(map(float, sys.stdin.buffer.readline().split()))
def iln(n): return [int(sys.stdin.buffer.readline().rstrip())
                    for _ in range(n)]


def iss(): return sys.stdin.buffer.readline().decode().rstrip()
def sl(): return list(map(str, sys.stdin.buffer.readline().decode().split()))
def isn(n): return [sys.stdin.buffer.readline().decode().rstrip()
                    for _ in range(n)]


def lcm(x, y): return (x * y) // math.gcd(x, y)


# MOD = 10 ** 9 + 7
MOD = 998244353
INF = float('inf')


def main():
    if os.getenv("LOCAL"):
        sys.stdin = open("input.txt", "r")

    S = iss()
    cnt = collections.Counter(S)
    if cnt['N'] > 0 and cnt['S'] == 0:
        print('No')
    elif cnt['S'] > 0 and cnt['N'] == 0:
        print('No')
    elif cnt['E'] > 0 and cnt['W'] == 0:
        print('No')
    elif cnt['W'] > 0 and cnt['E'] == 0:
        print('No')
    else:
        print('Yes')


if __name__ == '__main__':
    main()

考え方

必ず元の地点に戻る必要があるため、
進む方向と逆方向の移動が必ず必要になります。

例えば、北に進む必要がある場合、何日目かに必ず南へ進む必要があります。
この時、一度に進む距離は全て任意に選ぶことが出来ます。
そのため、北に何度進もうが一度南へ移動出来れば必ず元の地点に戻ることが出来ます。

つまり、進む必要がある方向と逆方向の移動が存在している場合には必ず元の地点に戻ることが出来ます。
あとは進む4方向の全てのパターンをケース分けすることで、回答できます。

---

他の方の回答を見ていたらスマートで分かりやすいものがありました。
結局のところ、NとS、WとEの方向が一度でもあればもう片方も必要で、
一度もなければもう片方も必要ないと判定することで簡単にケースわけ出来ます。

    S = iss()
    n, w, s, e = 'N' in S, 'W' in S, 'S' in S, 'E' in S
    print('Yes' if (n == s) and (w == e) else 'No')