AtCoder Beginner Contest 291 問題Cの失敗例と正解例
問題はhttps://atcoder.jp/contests/abc291/tasks/abc291_cを参照。
まず失敗例から書いていく。私が考えたのは(0,0)を00と2桁の数で表そうとした。つまり10の位がx座標で1の位がy座標である。そしてlというリストに入れていき、if len(l)==len(set(l)):で重複した要素を除いたリストの長さが元のリストに等しいとき(同じ位置にいたことがないとき)"No"と出力し、それ以外のとき"Yes"と出力する。実際のコードはpythonで書くと
N=int(input()) S=input() l=[0] xy=0 for i in range(N): if S[i]=='R': xy=xy+10 l.append(xy) if S[i]=='L': xy=xy-10 l.append(xy) if S[i]=='U': xy=xy+1 l.append(xy) if S[i]=='D': xy=xy-1 l.append(xy) #print(l) if len(l)==len(set(l)): #set(l)でlの一意なものつまり1つしかない値をリストとする。 print("No") else: print("Yes")
しかしこれだと例えば(0,0)→(1,0)→(1,-1)と動くとすると上のコードでは0→10→9となってしまいうまくいかない。
次にこれを修正する事を考える。具体的には10の位、1の位で表すのではなく素直に[x,y]として2次元のリストとして考える。修正したものは
N=int(input()) S=input() l=[[0,0]] x=0 y=0 for i in range(N): if S[i]=='R': x=x+1 l.append([x,y]) if S[i]=='L': x=x-1 l.append([x,y]) if S[i]=='U': y=y+1 l.append([x,y]) if S[i]=='D': y=y-1 l.append([x,y]) if len(l)==len(set(map(tuple, l))): print("No") else: print("Yes")
ここでif len(l)==len(set(map(tuple, l))): ではlは2次元のリストなのでそのままsetは使えない。よってmap(tuple,l)でlをタプルにしてset()を使い重複しているものを消している(1つしかない値を残す)。
これが正解例となる。