Codeforces Round #390 (Div. 2)

Codeforces Round #390 (Div. 2): http://codeforces.com/contest/754

새해 첫 코포~!

A. Lesha and array splitting

와 이 문제 정말... 사람들도 엄청 틀렸고, 나도 WA 한번 받고 핵도 한번 당했다. ㅠㅠ

0이 되지 않도록 구간을 나누는 문제였다.

내가 고려하지 않은 테케는 0이 연속적으로 나오는 아래와 같은 경우였다.

input

6
0 0 0 5 0 0

output

YES
1
1 6

한참이 지나서야 AC를 받긴 했지만, 이 문제 때문에 레이팅이라도 소폭 상승할 수 있었다.

#include <cstdio>
#include <vector>
using namespace std;
typedef pair<int,int> pii;
vector<pii> v;
int main() {
    int n; scanf("%d", &n);
    int s=1, sum=0, x;
    for(int i=1; i<=n; i++) {
        scanf("%d", &x);
        if(sum+x!=0) sum+=x;
        else {
            if(sum==0) continue;
            sum=x;
            v.push_back({s,i-1});
            s=i;
        }
    }
    if(sum==0) return 0&puts("NO");
    v.push_back({s,n});
    puts("YES");
    printf("%lu\n", v.size());
    for(auto &p: v) {
        printf("%d %d\n", p.first, p.second);
    }
    return 0;
}

B. Ilya and tic-tac-toe game

A번 문제에 비하면 너무너무 쉬웠으나,(A번도 어려운건 아니지만.. ㅠ)

이런 문제 코딩하는데 좀 시간이 걸린다.

물론 한 부분 코딩한 다음 전부 복붙을 하긴 했지만...

일단 이런문제보면 생각보다도 무식하게 빨리 키보드를 두들길 생각만 한다.

뭐 그래도 이 방법이 나한테는 아직까지 제일 좋은 것 같다. (괜히 생각하면 핵이나 먹는다 ㅠ)

이것도 해석하는데 뻘짓을 좀 했는데,

주인공이 항상 X로 플레이 한다는 걸 Xs라는 사람과 플레이를 하고, Xs라는 사람은 항상 x를 둔다고 착각했다. - _-;;

아이고... 영어 어떡하냐

아무튼 주인공은 x를 둔다고 한다.

그래서 3개 연속으로 x를 둘 수 있는지 찾는 문제다.

#include <cstdio>
#include <string>
#include <cstring>
#include <iostream>
using namespace std;
string b[4];
bool hchk(int r, int c) {
    if(b[r][c]=='o') return false;
    else if(b[r][c]=='x') {
        if(b[r][c+1]=='.'&&b[r][c+2]=='x') return true;
        if(b[r][c+1]=='x'&&b[r][c+2]=='.') return true;
    } else {
        if(b[r][c+1]=='x'&&b[r][c+2]=='x') return true;
    }
    return false;
}
bool vchk(int r, int c) {
    if(b[r][c]=='o') return false;
    else if(b[r][c]=='x') {
        if(b[r+1][c]=='.'&&b[r+2][c]=='x') return true;
        if(b[r+1][c]=='x'&&b[r+2][c]=='.') return true;
    } else {
        if(b[r+1][c]=='x'&&b[r+2][c]=='x') return true;
    }
    return false;
}
bool rdiachk(int r, int c) {
    if(b[r][c]=='o') return false;
    else if(b[r][c]=='x') {
        if(b[r+1][c+1]=='.'&&b[r+2][c+2]=='x') return true;
        if(b[r+1][c+1]=='x'&&b[r+2][c+2]=='.') return true;
    } else {
        if(b[r+1][c+1]=='x'&&b[r+2][c+2]=='x') return true;
    }
    return false;
}
bool ldiachk(int r, int c) {
    if(b[r][c]=='o') return false;
    else if(b[r][c]=='x') {
        if(b[r+1][c-1]=='.'&&b[r+2][c-2]=='x') return true;
        if(b[r+1][c-1]=='x'&&b[r+2][c-2]=='.') return true;
    } else {
        if(b[r+1][c-1]=='x'&&b[r+2][c-2]=='x') return true;
    }
    return false;
}
 
int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    for(int i=0; i<4; i++) cin >> b[i];
 
    for(int r=0; r<4; r++) {
        for(int c=0; c<2; c++) {
            if(hchk(r,c)) return 0&puts("YES");
        }
    }
    for(int r=0; r<2; r++) {
        for(int c=0; c<4; c++) {
            if(vchk(r,c)) return 0&puts("YES");
        }
    }
    for(int r=0; r<2; r++) {
        for(int c=0; c<2; c++) {
            if(rdiachk(r,c)) return 0&puts("YES");
        }
        for(int c=2; c<4; c++) {
            if(ldiachk(r,c)) return 0&puts("YES");
        }
    }
    puts("NO");
    return 0;
}

C. Vladik and chat

아, 이 문제가 너무 아쉬웠다.

채팅을 하는데 ?에 해당하는 사람이 누구인지를 맞추는 문제였다.

맨 처음에 채팅에 참여하는 사람들의 이름이 주어진다.

채팅 문구에 본인이 이름이 들어가면 안되므로 이 조건에 맞춰서 ?를 결정하면 되었다.

근데, 맞는거 같은데 틀렸다고 뜸... ㅠ

나중에 끝나고 나서 봤더니 86번 테케에서 오지게 틀리고 있었다.

끝나고 나서도 2시간을 넘게 코드를 봤지만, 틀린 부분을 찾을 수가 없어서

결국 테케를 캐기 시작했다. ㅋㅋㅋㅋ

코포 보면 틀렸을 때 답이 어떻게 다른지 보여주는데

그 부분에 입력받은 테케를 출력하도록 했다.

86번 테케에서만 나가니까, 해당 테케가 입력으로 들어온 경우에만 그렇게 동작하도록 만듦...ㅋ

나중에 알고보니 1e9와 같은 문자는 1이라는 숫자가 들어왔으므로 1e9는 문자가 될 수 없다는 걸 알았는데,

e9마저도 무시해야하는줄은 몰랐다.

?: 1e9e7?abc d,.dab18

이런 채팅 문구가 들어오면, ?에 들어갈 수 없는 사람은 abc, d, 그리고 dab18이었다.

한번 숫자가 들어온 경우 구분자('.' ',' '!' '?' ' ')가 들어오기 전까지 모든 문자는 무시해야 했었다. ㅠㅠ

코드는 아래와 같다. (AC받은 코드)

#include <cstdio>
#include <iostream>
#include <string>
#include <cstring>
#include <algorithm>
#include <vector>
#include <cctype>
#include <map>
using namespace std;
char nps[110][110];
vector<string> name, chat;
vector<int> ans;
map<string, int> mp;
int n,m,e;
bool chk[110][110], ccc[110];
int dp[110][110], par[110][110];
int f(int x, int y) {
    int &ret = dp[x][y];
    if(ret) return ret;
    else ret=2;
    if(x>=m-1) {
        if(nps[x][y]=='0') {
            e=y;
            return ret=1;
        } else return ret=2;
    }
 
    for(int i=0; i<n; i++) {
        if(i==y) continue;
        if(nps[x+1][i]=='0') {
            ret |= f(x+1,i);
            if(ret&1) par[x+1][i]=y;
        }
    }
    return ret;
}
int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    int tc; cin >> tc;
    while(tc--) {
        memset(chk, false, sizeof(chk));
        memset(ccc, false, sizeof(ccc));
        memset(dp, 0, sizeof(dp));
        memset(par, -1, sizeof(par));
        memset(nps, '0', sizeof(nps));
        ans.clear(); mp.clear();
 
        cin >> n;
        name.clear(); name.resize(n);
        for(int i=0; i<n; i++) {
            cin >> name[i];
            mp[name[i]]=i;
        }
 
        string buf, tmpName;
        cin >> m; getline(cin,buf);
        chat.clear(); chat.resize(m, string());
 
        for(int i=0; i<m; i++) {
            bool ignor=false;
            getline(cin, chat[i]);
            int k=0; for(; k<chat[i].size(); k++) {
                if(chat[i][k]==':') {
                    tmpName=chat[i].substr(0,k);
                    break;
                }
            }
 
            string x="";
            if(tmpName=="?") {
                ccc[i]=true;
                for(;k<=chat[i].size(); k++) {
                    if(isalpha(chat[i][k])&&!ignor) x+=chat[i][k];
                    else if(isdigit(chat[i][k])) {
                        if(x=="") {
                            ignor=true;
                            continue;
                        } else x+=chat[i][k];
                    } else {
                        ignor=false;
                        if(x=="") continue;
                        if(mp.count(x)) nps[i][mp[x]]='1';
                        x="";
                    }
                }
            } else {
                if(mp.count(tmpName)) {
                    int idx=mp[tmpName];
                    for(int k=0; k<n; k++) {
                        if(k==idx) nps[i][k]='0';
                        else nps[i][k]='1';
                    }
                }
            }
        }
 
        bool good = false;
        for(int i=0; i<n; i++) {
            if(nps[0][i]=='0') {
                if(f(0,i)&1) {
                    good = true;
                    for(int j=e, X=m-1; X>0; j=par[X--][j]) ans.push_back(j);
                    ans.push_back(i);
                    break;
                }
            }
        }
        if(!good) puts("Impossible");
        else {
            reverse(ans.begin(), ans.end());
            for(int i=0; i<m; i++) {
                if(ccc[i]) printf("%s%s\n", name[ans[i]].c_str(), chat[i].substr(1, chat[i].size()-1).c_str());
                else printf("%s\n", chat[i].c_str());
            }
        }
    }
    return 0;
}

D. Fedor and coupons

C번 문제보다 상대적으로 쉬운 문제였던 것 같은데, 아직 문제도 못읽어봤다.

C번 문제보다 푼 사람이 2배나 많았음... ㅋㅋ

E. Dasha and cyclic table

당연히 못읽어봄.

# 최종 스코어 # (Rank: 1786/4001)

드디어 다시 cyan 색깔을 되찾았다. ㅠㅠ