Codeforces: Round 190 div 2 C
12331 ワード
Problem:
==============================================================================================================
Fox Ciel has a robot on a 2D plane. Initially it is located in (0, 0). Fox Ciel code a command to it. The command was represented by string
s. Each character of
s is one move operation. There are four move operations at all:
'U': go up, (x, y) → (x, y+1); 'D': go down, (x, y) → (x, y-1); 'L': go left, (x, y) → (x-1, y); 'R': go right, (x, y) → (x+1, y).
The robot will do the operations in s from left to right, and repeat it infinite times. Help Fox Ciel to determine if after some steps the robot will located in (a, b).
Input
The first line contains two integers a and b, ( - 109 ≤ a, b ≤ 109). The second line contains a string s (1 ≤ |s| ≤ 100, s only contains characters 'U', 'D', 'L', 'R') — the command.
Output
Print "Yes"if the robot will be located at (a, b), and "No"otherwise.
Sample test(s)
input
output
input
output
input
output
input
output
Note
In the first and second test case, command string is "RU", so the robot will go right, then go up, then right, and then up and so on.
The locations of its moves are (0, 0) → (1, 0) → (1, 1) → (2, 1) → (2, 2) → ...
So it can reach (2, 2) but not (1, 2).
==============================================================================================================
この問題はいくつかの間違いを犯した.
1. set.Insert操作には<オペレータがあるので、setで自分で定義した新しい構造であれば、この新しい構造を<記号で再ロードします.この点はこの問題をする過程で長い時間をかけて原因を探して、根本的な原因はやはりstlの関数の原理に対する理解が足りないことです.
2.最初の考え方は間違っていて、本来の考えはforループをして、i=0からi=max(des.x,des.y)+s.size()+1まで、ループの中でそれぞれの歩いた点に終点かどうかを聞いています.明らかにこの考えはビッグデータには通らない.
3. move.xとmove.y==0の場合は考慮せず,合計4つの場合に分けた.最初は単純に考えていなかった==0の場合
4.ビッグデータの検証はデータオーバーフローに注意し、最初は1 llを追加するのを忘れます.
5.moveの方向がdesの方向に合っていることを考慮していないので、desが必要です.y*1ll*move.y>=0という条件
これらの間違いはdebugの時に何度も現れて、私も気が狂っています.自分の考えはまだ厳密ではない.
主な考え方をお話しします.
各s動作後に踏むことができる点セットを収集し、ここでsetscopeとし、このs動作後の点が最終的にどの点にあるかを算出し、ここでmoveとすると、毎回のs動作後の点の方向がmoveとなり、原点は0,0となる.
x(i)+n*move.x = des.x;
y(i)+n*move.y = des.y;
この方程式を解くと(des.x-x(i)*move.y = (des.x-y(i))*move.x,注意(des.x-x(i)%move.x == 0.
経験:数学はアルゴリズムの問題をする良い手伝いで、数学は多くのpre-jobをすることができて、プログラムに多くの便利さをもたらすことができます.最適化を始めるときはできるだけ数学の仕事をたくさんします.
最後にコードセグメントを貼り付ける
==============================================================================================================
Fox Ciel has a robot on a 2D plane. Initially it is located in (0, 0). Fox Ciel code a command to it. The command was represented by string
s. Each character of
s is one move operation. There are four move operations at all:
The robot will do the operations in s from left to right, and repeat it infinite times. Help Fox Ciel to determine if after some steps the robot will located in (a, b).
Input
The first line contains two integers a and b, ( - 109 ≤ a, b ≤ 109). The second line contains a string s (1 ≤ |s| ≤ 100, s only contains characters 'U', 'D', 'L', 'R') — the command.
Output
Print "Yes"if the robot will be located at (a, b), and "No"otherwise.
Sample test(s)
input
2 2
RUoutput
Yesinput
1 2
RUoutput
Noinput
-1 1000000000
LRRLUoutput
Yesinput
0 0
Doutput
YesNote
In the first and second test case, command string is "RU", so the robot will go right, then go up, then right, and then up and so on.
The locations of its moves are (0, 0) → (1, 0) → (1, 1) → (2, 1) → (2, 2) → ...
So it can reach (2, 2) but not (1, 2).
==============================================================================================================
この問題はいくつかの間違いを犯した.
1. set.Insert操作には<オペレータがあるので、setで自分で定義した新しい構造であれば、この新しい構造を<記号で再ロードします.この点はこの問題をする過程で長い時間をかけて原因を探して、根本的な原因はやはりstlの関数の原理に対する理解が足りないことです.
2.最初の考え方は間違っていて、本来の考えはforループをして、i=0からi=max(des.x,des.y)+s.size()+1まで、ループの中でそれぞれの歩いた点に終点かどうかを聞いています.明らかにこの考えはビッグデータには通らない.
3. move.xとmove.y==0の場合は考慮せず,合計4つの場合に分けた.最初は単純に考えていなかった==0の場合
4.ビッグデータの検証はデータオーバーフローに注意し、最初は1 llを追加するのを忘れます.
5.moveの方向がdesの方向に合っていることを考慮していないので、desが必要です.y*1ll*move.y>=0という条件
これらの間違いはdebugの時に何度も現れて、私も気が狂っています.自分の考えはまだ厳密ではない.
主な考え方をお話しします.
各s動作後に踏むことができる点セットを収集し、ここでset
x(i)+n*move.x = des.x;
y(i)+n*move.y = des.y;
この方程式を解くと(des.x-x(i)*move.y = (des.x-y(i))*move.x,注意(des.x-x(i)%move.x == 0.
経験:数学はアルゴリズムの問題をする良い手伝いで、数学は多くのpre-jobをすることができて、プログラムに多くの便利さをもたらすことができます.最適化を始めるときはできるだけ数学の仕事をたくさんします.
最後にコードセグメントを貼り付ける
1 #include <iostream>
2 #include <fstream>
3 #include <string>
4 #include <map>
5 #include <vector>
6 #include <set>
7 #include <algorithm>
8 #include <queue>
9 #include <math.h>
10
11 #define modulo 1000000007
12
13 using namespace std;
14
15 struct node {
16 int x;
17 int y;
18 node(int a, int b) : x(a), y(b) { }
19 node() : x(0), y(0) { }
20
21 };
22
23 bool operator<(const node &a, const node &b) {
24 return a.x == b.x? a.y < b.y : a.x < b.x;
25 }
26
27 int main() {
28 map<char, int> dir;
29 dir['U'] = 0;
30 dir['D'] = 1;
31 dir['L'] = 2;
32 dir['R'] = 3;
33 int dirdir[4][2] = {{0, 1}, {0, -1}, {-1, 0}, {1, 0}};
34 node des;
35 cin >> des.x >> des.y;
36 string s;
37 cin >> s;
38 set<node> scope;
39 scope.insert(node(0, 0));
40 node move(0, 0);
41 for (int i = 0; i < s.size(); i++) {
42 move.x += dirdir[dir[s[i]]][0];
43 move.y += dirdir[dir[s[i]]][1];
44 scope.insert(move);
45 }
46 node source(0, 0);
47 bool flag = false;
48 for (set<node>::iterator it = scope.begin(); it != scope.end(); it++) {
49 if (move.x == 0 && move.y == 0) flag |= ((*it).x == des.x && (*it).y == des.y);
50 else if (move.x == 0 && move.y != 0) flag |= ((*it).x == des.x && (des.y-(*it).y)%move.y == 0 && des.y*1ll*move.y >= 0);
51 else if (move.x != 0 && move.y == 0) flag |= ((*it).y == des.y && (des.x-(*it).x)%move.x == 0 && des.x*1ll*move.x >= 0);
52 else if (((des.x-(*it).x)*1ll*move.y == (des.y-(*it).y)*1ll*move.x) && (des.x-(*it).x)%move.x == 0 && (des.y-(*it).y)%move.y == 0 && (des.x-(*it).x)*1ll*move.x >= 0) flag = true;
53 if (flag) break;
54 }
55 if (flag) cout << "Yes" << endl;
56 else cout << "No" << endl;
57
58 return 0;
59 }