(2021년 2월 6일에 작성한 글입니다.)
Dashboard - Codeforces Round #699 (Div. 2) - Codeforces
codeforces.com
진짜... 화가 너무 많이 났다
그래서 끝나고 나서도 한참동안
화가 많이 났다...
지금 끝난지 40분정도 지났는데
많이 가라 앉음...
집에 마카롱이 있어서 다행이다
이거 쓰고 먹어야지
홍차도 마셔야지
늦게 자야지
A.
R, L, U, D의 개수를 센 다음에
X > 0 이면 X <= R, X < 0 이면 -X <= L
Y > 0 이면 Y <= U, Y < 0 이면 -Y <= D
X, Y에 대해 모두 만족하면 YES다.
구현하는 데 시간이 좀 걸렸는데
학회 선배님 코드를 보니
-L <= X <= R && -D <= Y <= U 이면 된다...
갓...
int main()
{
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int TC;
cin >> TC;
while (TC--) {
int X, Y;
string s;
cin >> X >> Y;
cin >> s;
int cnt[4]{};
for (int i = 0; s[i]; i++) {
if (s[i] == 'R') {
cnt[0]++;
}
else if (s[i] == 'L') {
cnt[1]++;
}
else if (s[i] == 'U') {
cnt[2]++;
}
else {
cnt[3]++;
}
}
bool flag = true;
if (X > 0) {
if (cnt[0] < X) {
flag = false;
}
}
else if(X < 0) {
if (cnt[1] < abs(X)) {
flag = false;
}
}
if (Y > 0) {
if (cnt[2] < Y) {
flag = false;
}
}
else if(Y < 0) {
if (cnt[3] < -Y) {
flag = false;
}
}
if (flag) {
cout << "YES" << ENDL;
}
else {
cout << "NO" << ENDL;
}
}
return 0;
}
B.
n이 작기 때문에 그냥 다 해보면 된다.
근데 K가 커서 K번 다 반복하면 시간초과가 날 줄 알고
모든 높이가 최댓값과 동일해질때 까지의 개수를 세고
만약 그것보다 K가 크면 불가능하다는 의미니까 -1 출력,
아닌 경우에 대해 살펴보는 방식으로 했는데...
이것도.. 다른 분들 코드를 보니까
그냥 K번 체크 하면서
만약 넣을 곳이 없을 때 break하게 하면 된다.
그럼 내가 따로 처리해준 부분도 저절로 처리 된다.
갓갓....
bool check(vector<ll>& arr, int& N)
{
for (int i = 1; i < N; i++) {
if (arr[i - 1] < arr[i]) {
return true;
break;
}
}
return false;
}
int main()
{
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int TC;
cin >> TC;
while (TC--) {
int N;
ll K;
cin >> N >> K;
vector<ll> arr(N + 5);
for (int i = 0; i < N; i++) {
cin >> arr[i];
}
if (!check(arr, N)) {
cout << -1 << ENDL;
continue;
}
ll max_ = *max_element(arr.begin(), arr.begin() + N);
ll need = 0;
for (int i = 0; i < N; i++) {
need += max_ - arr[i];
}
if (K - need > 0) {
cout << -1 << ENDL;
continue;
}
while (K-- > 1) {
for (int i = 0; i < N; i++) {
if (arr[i] < arr[i + 1]) {
arr[i]++;
break;
}
}
if (!check(arr, N)) {
cout << -1 << ENDL;
break;
}
}
for (int i = 0; i < N; i++) {
if (arr[i] < arr[i + 1]) {
cout << i + 1 << ENDL;
break;
}
}
}
return 0;
}
C.
문제의 C번이다
우선
맨 마지막에 칠하는 색깔에 주목해야 한다.
만약 중간에, 칠할 곳이 없는 경우엔
맨 마지막에 칠할 예정인 곳에 칠하면 된다.
어차피 색은 덮이니까.
그래서 우선 맨 마지막에 칠할 곳이 어딘지 저장해둔다.(변수명 here)
(여기서 주의할 점은 마지막으로 칠하는 색의 위치가
현재 색이랑 원하는 색이 이미 같은 곳일수도 있다는거다
이 부분 체크해야 함)
그리고 현재 색이랑 원하는 색이 다른 애들은
que를 저장하는 vector에 정리해놓는다.
그리고 painter를 한 명씩 체크하면서
만약 색을 칠해야 하는 곳이 있다면 (if (!que[color].empty()))
거기를 칠하고 (ans[i] = que[color].front(); que[color].pop())
없다면 맨 마지막에 칠할 곳에 칠하면 된다.(ans[i] = here)
마지막으로 덜 칠해진 게 있는지 확인하기 위해
모든 색을 돌면서 queue가 비었는지 확인한다.
만약 덜 빈 곳이 있다면 NO 출력.
런타임에러를 받은 이유는
if (now[i] == want[i]) okay[want[i]] = i;
를 저장하는 벡터 okay를 만들었는데
이 벡터의 크기를 N이 아닌 M으로 잡았다....
.
.
.
더 웃긴건 내가 분명 out of range 문제일거라고 생각해서
몇 번이나 관련 부분을 확인했다는거지.
근데 결국 우너빈이 찾아줬다...
vector<queue<int>> que;
int main()
{
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int TC;
cin >> TC;
while (TC--) {
int N, M;
cin >> N >> M;
vector<int> now(N + 5), want(N + 5);
que.clear(); que.resize(N + 5);
for (int i = 1; i <= N; i++) {
cin >> now[i];
}
for (int i = 1; i <= N; i++) {
cin >> want[i];
if (now[i] != want[i]) {
que[want[i]].push(i);
}
}
vector<int> painter(M + 5);
for (int i = 1; i <= M; i++) {
cin >> painter[i];
}
int here = -1;
if (!que[painter[M]].empty()) {
here = que[painter[M]].front();
que[painter[M]].pop();
}
else {
for (int i = 1; i <= N; i++) {
if (now[i] == want[i] && want[i] == painter[M]) {
here = i;
break;
}
}
}
if (here == -1) {
cout << "NO" << ENDL;
continue;
}
vector<int> ans(M + 5);
for (int i = 1; i <= M - 1; i++) {
int color = painter[i];
if (!que[color].empty()) {
ans[i] = que[color].front();
que[color].pop();
}
else {
ans[i] = here;
}
}
ans[M] = here;
bool flag = false;
for (int i = 1; i <= N; i++) {
if (!que[i].empty()) {
flag = true;
break;
}
}
if (flag) {
cout << "NO" << ENDL;
}
else {
cout << "YES" << ENDL;
for (int i = 1; i <= M; i++) {
cout << ans[i] << ' ';
}
cout << ENDL;
}
}
return 0;
}