629점을 받아서 5등을 했다. A,B,C,F,J를 풀었고, E,G,I에서 부분을 긁을 수 있었다. 못 푼 문제들은 에디토리얼이 나오고 풀어볼 것이다. A번 풀이: L이 x일 때, 최적의 배치는 출제자마다 가장 작은 x개의 문제들 중 가장 작은 K개의 문제를 고르는 것이다. 이는 L을 증가시키면서 L번째로 작은 문제를 set에 넣어주고, set의 크기가 K 이하가 되도록 작은 원소만 남겨주면 된다. #include #include #include #include using namespace std; #define int long long vectorproblems[200100]; int poss[200100]; vectorps; multisetx; signed main() { int N, K; ios_b..
서브태스크 1. 가능한 경우는 2가지로, 신발이 뒤집어졌는지 아닌지를 체크하면 된다. 서브태스크 3. -x, x, -x, x와 같은 순열을 만들어야 한다. 이 순열로 만들기 위해서는 각 원소에 대해서, 오른쪽에 있는 가장 가까운 필요한 숫자를 당겨주면 된다. 이는 그냥 하면 N^2인데, 가장 왼쪽 -x는 0 위치, 두번째 왼쪽 -x는 2 위치...인것을 관찰할 수 있고, 이를 통해 NlogN에 풀 수 있다. 서브태스크 4: 첫 신발은 N-1, 두 번째 신발은 N-2...마지막 신발은 0번을 옮겨야 하므로, 정답은 N(N-1)/2이다. 만점 풀이: 신발을 왼쪽으로 순회하면서, 가장 가까운 신발을 매칭하는 전략을 짤 수 있다. 이를 그대로 짜면 서브태스크 5를 맞을 수 있다. 만점을 맞기 위해서는, 우선 매..
jjang36524 계정으로 가서 5솔을 했다. A번: x가 interesting할 조건은 x에다가 1을 더할 때 자리올림이 일어나는 것이다. 자리올림이 없을 때는 합에 1이 더해지지만, 매 자리올림마다 9 하나가 0이 됨으로써 합이 작아지기 때문이다. 자리올림이 일어날 조건은 x를 10으로 나눈 나머지가 9일 때고, 이는 [(x+1)/10의 식으로 구할 수 있다.] #include #include #include using namespace std; int main() { int T; ios_base::sync_with_stdio(false); cin.tie(NULL); cin >> T; while (T--) { int N; cin >> N; cout T; while (T--) { string s,t;..
류호석배 알고리즘 코딩 테스트:시작하고 1시간 24분 뒤에 나갔다. 최종 9등. 1.빌런 호석 0~9까지의 숫자를 디스플레이가 켜져 있는지에 대한 이진수로 나타낸 뒤, 1~N까지의 모든 수를 탐색하면서 X의 i번째 자리 xor 탐색 대상 수의 i번째 자리의 켜진 비트 수의 합(반전 횟수)가 P 이하이면 되고, 이를 구현해주면 된다. 6분 AC. #include #include using namespace std; bool arr[10][7] = { {1,1,1,0,1,1,1},{0,0,1,0,0,0,1},{0,1,1,1,1,1,0},{0,1,1,1,0,1,1},{1,0,1,1,0,0,1},{1,1,0,1,0,1,1},{1,1,0,1,1,1,1},{0,1,1,0,0,0,1},{1,1,1,1,1,1,1},{..
tourist가 만든 대회가 있어서 나가봤고, 총 5문제를 1시간 5분만에 풀어 codingmorning 계정이 레드를 갔다. A번: 어떤 자릿수가 K일 경우, 그 자릿수를 만들기 위해 최소 K개의 수가 있어야 한다. 그리고, 자릿수의 최댓값이 x일 때, x개의 수만 있으면 원래 정수를 표현할 수 있다. 이렇게 만들려면, x개의 수를 만든 뒤, 어떤 자릿수가 k일 때 그 자릿수가 1인 수 k개를 만들어주면 된다. 그러므로 답은 자릿수의 최댓값이다. #include #include #include using namespace std; int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); int T, N, a, b, c, d; cin >> T; whi..
버추얼로 나가서 38분 올솔을 했는데, 뭔가 찝찝하다. 7문제를 푸는 과정에 4틀(이중 2개는 예제를 틀린 것)을 냈다. A번: 각 작업마다 시작했다가 끝난지 여부를 저장해주었다가 시작했다가 끝난 작업이 나오면 NO를 출력해주면 된다. 시작했다가 끝난지의 여부는 A에서 다른 작업으로 바뀐 적이 있는지의 여부와 같고, 이를 구현해주면 된다. #include #include #include #include using namespace std; int f[27]; int main() { int T; ios_base::sync_with_stdio(false); cin.tie(NULL); cin >> T; while (T--) { memset(f, 0, sizeof(f)); int N; cin >> N; stri..
기본적인 구조는 divide and conquer이다. i~j가 non-boring하려면 i>=j이거나, 유일한 원소가 존재하고, 유일한 원소를 기준으로 배열을 나눴을 때 양쪽이 모두 non-boring해야 한다. 구간에서 유일한 원소를 찾으려면 원소마다 자신과 같은 원소가 나오는 왼쪽 위치와 오른쪽 위치를 미리 구해둔 뒤, i~j가 이 안에 포함되는지를 구하면 된다. 하지만, 이런 식으로 divide and conquer를 하면 탐색 N*깊이 N으로 시간초과가 난다. 이를 고치려면 유일한 원소를 찾을 때 가장자리 부분부터 찾아주면 된다. 이러면 깊이가 깊어질 때 탐색하는 시간이 줄어들기 때문에 시간이 줄어들고, 문제를 맞을 수 있다. #include #include #include using names..