Codeforces Round #389 (Div. 2, Rated, Based on Technocup 2017 - Elimination Round 3)

Codeforces Round #389 (Div. 2, Rated, Based on Technocup 2017 - Elimination Round 3): http://codeforces.com/contest/752

A. Santa Claus and a Place in a Class

n,m,k가 주어지는데, 전체 책상이 m행 n열만큼 있고 여기서 k번 자리에 앉는다는 뜻.

아래 그림을 보면 이해가 쉽다.

예를 들어, 4 3 9라고 하면 초록색 책상을 의미한다.

lane이 4개 desk가 3줄 있는 곳에서 9번 책상은 2행 2열 왼쪽 책상이다. 그래서 답을 2 2 L로 하면 되고,

파란색의 경우는 4 3 24로 물어보고 답은 4 3 R이라 출력하면 된다.

빨리 풀려고 제대로 계산안하고 대충 때려넣다가 계속 답이 제대로 안나와서 결국 펜 잡고 계산을 정확하게 했음 ㅠㅠ

역시 그냥 정공법이 항상 평균은 보장해주는 것 같다.

#include <cstdio> using namespace std; int main() { int n,m,k; scanf("%d%d%d",&n,&m,&k); return 0&printf("%d %d %c",(k-1)/(2*m)+1, ((k-1)%(2*m))/2+1, "LR"[((k-1)%(2*m))%2]); }

B. Santa Claus and Keyboard Check

두 문자열이 주어지는데 이게 키보드가 삐꾸라서 원래 A라는 문자열이 쳐져야 되는게, B라는 문자열이 쳐졌다고 한다.

근데, 이런 경우라면 반드시 각 문자들은 다른 문자와 1:1 matching이 되어야 한다.

helloworld
ehoolwlroz

위에서 두 문자열을 보면, (h,e), (l,o), (d,z) 이렇게 3개가 매칭되는 것을 알 수 있다.

만약 1:1 매칭이 되지 않는 경우는 -1을 출력하고 다른 문자와 매칭되는 경우가 전혀 없는 경우는 0을 출력하면 됐다.

근데, 이거 한참 D풀고 있는데 핵당했다고 메세지가 떴다.

D는 이따가 얘기할거지만, 거의 다 푼거 같아서 빨리 D를 해결하고 B를 보려고 했는데,

아놔.. 결국 5분 남겨놓고 B 핵당한거 체크하다가 B,D둘다 놓쳐버렸다 ㅠㅠ

나중에 핵 당한거 확인해보니 한번에 맞추기 참 까다로운 문제였다.

특히 핵 안당하고 맞춘사람은 정말 몇명 없었고,

system 채점에서 안나간 사람들도 전체에 반도 안됐다.

밑에는 나중에 수정해서 AC를 받은 코드다.

#include <cstring> #include <string> #include <iostream> #include <map> #include <set> using namespace std; map<char, char> mp; set<char> eq; bool chk[27]; int main() { ios::sync_with_stdio(false); cin.tie(0); string a, b; cin >> a >> b; int n = a.size(); for(int i=0; i<n; i++) { if(a[i]==b[i]) { if(mp.count(a[i])||mp.count(b[i])) return 0&printf("-1"); eq.insert(a[i]); eq.insert(b[i]); continue; } else { if(eq.count(a[i])||eq.count(b[i])) return 0&printf("-1"); if(mp.count(a[i])&&mp.count(b[i])) { if(mp[a[i]]!=b[i]) return 0&printf("-1"); } else if(mp.count(a[i]) || mp.count(b[i])) { return 0&printf("-1"); } else { mp[a[i]]=b[i]; mp[b[i]]=a[i]; } } } printf("%lu\n", mp.size()/2); for(auto &p: mp) { if(chk[p.first-'a']&&chk[p.second-'a']) { } else { printf("%c %c\n",p.first,p.second); chk[p.first-'a']=chk[p.second-'a']=true; } } return 0; }

C. Santa Claus and Robot

무슨 말인지 잘 해석을 못해서 좀 고생했다.

문제 자체는 상당히 쉬웠는데, pretest에서 어떤 테케 하나를 제공하지 않았다면,

아주 크리스마스가 핵 축제가 될뻔한 문제였다. ㅋㅋ

,

문제는 로봇이 항상 최단거리로만 움직인다.

그래서 원래 좌표를 딱딱 지정해주면 로봇이 알아서 최단거리로 움직인다는 건데,

그렇게 명령을 내렸던 좌표값들 적어둔걸 어디다 잃어버렸다고 한다.

그런데, 로봇이 지나온 길은 다 알고 있음.

그럼 그러한 좌표들이 최소한 몇개냐~? 하는게 질문이었다.

당근 왼쪽으로 움직이다가 한번이라도 오른쪽으로 움직이려고 하면, +1을 하면 되는 문제

다만 L에서 U로 가다가 R이 나왔다고 하면, 그냥 R빼고 남은 모든 방향을 초기화 해야 된다.

(어설프게 R,U나 R,D와 같이 2개만 초기화 하면 WA를 받는다.)

왜 그런지는 해보면 알거임.

나도 해당 테케를 고려하지 않아 한번 WA를 받았지만, 바로 고쳐서 AC를 받을 수 있었다.

#include <cstdio> #include <algorithm> #include <cstring> #include <string> #include <vector> #include <iostream> #include <map> using namespace std; map<char,int> mp; bool chk[5]; int main() { ios::sync_with_stdio(false); cin.tie(0); string s; int n; cin>>n; cin >> s; mp['L']=0; mp['R']=1; mp['D']=2; mp['U']=3; int cnt=1; for(int i=0; i<s.size(); i++) { chk[mp[s[i]]]=true; if(chk[mp[s[i]]^1]) { cnt++; int x = mp[s[i]]; if(x==0) chk[1]=chk[2]=chk[3]=false; else if(x==1) chk[0]=chk[2]=chk[3]=false; else if(x==2) chk[0]=chk[1]=chk[3]=false; else if(x==3) chk[0]=chk[1]=chk[2]=false; } } printf("%d", cnt); return 0; }

D. Santa Claus and a Palindrome

처음에 k, n이 주어진다.

k개의 문자열과 모든 문자열의 길이는 n이라는 뜻이다.

문자열 옆에는 beauty가 주어지는데,

주어진 문자열들을 사용해서 팰린드롬을 만들고, 이때 이 팰린드롬의 뷰티값은 사용한 모든 문자열들의 뷰티 합이고

이 뷰티 값은 항상 0이상이어야 한다.

나는 이 문제를 trie를 사용해서 접근했다.

스트링 들어오면 그걸 뒤집어서 trie에서 검색하고,

트라이에 해당 스트링이 있으면 그 스트링에 해당되는 고유번호를

지금 입력받은 스트링에도 부여해서 trie에 insert해주고

나중에 그러한 고유번호끼리 묶어서 2개씩 짝지어 beauty를 맥스로 만들려고 했다.

그런데 해보면 알겠지만, 문제가 상당히 많다.

그리고 나중에 콘테 다 끝나고 사람들 코드를 좀 봤는데,

트라이로 푼 사람을 한명도 못봤다 ㅠㅠㅠㅠ

또, 매번 트라이라고 생각되는 문제를 접할 때 마다 항상 문제가 됐던 부분이 있는데,

삭제가 항상 문제다... 결국 나는 트라이 할때마다 삭제를 제대로 구현해본 적이 한번도 없는데

뭔가 삭제를 깔끔하게 해결하는 방법을 아직도 잘 모르겠다.

삭제를 하고 나면 트라이에 그 지저분한 흔적들이 남는거 같아서...

그렇다고 메모리 allocation 한거를 delete하자니 시간이 오래 걸릴 것 같고...

아무튼 결국 제대로 된 답도 안나와서 submit도 못했다.

일단은 답을 수정할 때까지 완전 엉망진창인 소스를 올려본다.

빠른 시일내로 해결해야지 ㅠㅠ

#include <cstdio> #include <string> #include <cstring> #include <vector> #include <algorithm> #include <iostream> #include <map> #include <set> using namespace std; int cnt=1; const int mask=0x10000000; struct TrieNode{ TrieNode *room[26]; int tno; //bool isTerminal; TrieNode():tno(0){ memset(room, 0, sizeof(room)); } ~TrieNode() { for(int i=0; i<26; i++) { if(room[i]) delete room[i]; } } int& insert(const char *s, int t, bool flag) { if(*s==0) { //if(flag) tno|=flag; if(tno) return tno; else { if(t) tno=t; else tno=cnt++; if(flag) tno|=mask; return tno; } } int x = *s-'a'; if(!room[x]) room[x]=new TrieNode(); return room[x]->insert(s+1,t,flag); } int find(const char *s) { if(*s==0) return tno; int x=s[0]-'a'; if(room[x]) return room[x]->find(s+1); else return 0; } }; vector<int> v[100001]; map<int,int> mp; set<int> st,hubo; typedef long long ll; int main() { ios::sync_with_stdio(false); cin.tie(0); TrieNode tn; int k,n; cin>>k>>n; string s,r; int b; vector<int> tno,tno2; for(int i=0; i<k; i++) { cin>>s>>b; r=s; reverse(r.begin(),r.end()); int tno = tn.find(r.c_str()); if(tno>=mask) { tno-=mask; st.insert(tno); } if(tno) v[tno].push_back(b); else v[cnt].push_back(b); mp[b]++; tn.insert(s.c_str(),tno,(r==s)); } auto cmp = [&](int i, int j)->bool{ return i>j; }; ll ans=0LL; for(int i=1; i<cnt; i++) { sort(v[i].begin(), v[i].end(), cmp); for(int j=0; j+1<v[i].size(); j+=2) { if(v[i][j]+v[i][j+1]>0) { printf("%d, %d\n", v[i][j], v[i][j+1]); ans+=v[i][j]+v[i][j+1]; } else if(v[i][j]>0&&st.count(i)) { hubo.insert(v[i][j]); break; } else break; } } if(hubo.size()>0){ auto it = hubo.end(); it--; if(*it>0) ans+=(*it); } printf("%lld", ans); return 0; }

E. Santa Claus and Tangerines

이 문제는 보지도 못했다. 근데 D보다 AC받은 사람이 더 많았다. ㅡ,.ㅡ;;

또, D와 마찬가지로 시스템에서 나가기 쉬운 문제였던 것 같다.

아무튼 오늘 풀어봐야겠다.

F. Santa Clauses and a Soccer Championship

당근 아직 못봤다. ㅋㅋ

# 최종 스코어 #

아직 2016 Good Bye contest가 남긴 했지만, 그 콘테스트가 23시 35분에 있으니까 다 보고 나면 새해가 된다.

결국 올해는 green에서 마무리 하는구나 ㅠㅠ

그래도 새해 첫 스타트는 깔끔하게 cyan에서 시작하기를...

그리고 2017에는 blue좀 달아보자 ㅠㅠ! 제바알~