PS - OJ 검색 결과

해당 글 40건

Codeforces Round #443 (Div. 1) A. Short Program

Codeforces Round #443 (Div. 1) A. Short Program 나는 왜 이런문제를 못푸는지 모르겠다.하... 이 코포셋이 나온지는 6주나 지났는데,요즘 한 두달간 뻘짓만 하다가 다시 정신차리고 문제를 풀기 시작했다. 일단 이 문제는 xor, and, or 연산을 하는데,문제에서 주어지는 최대 50만개의 연산을 진행한 뒤이 값과 똑같은 값을 출력하는 5개 이하의 XOR, AND, OR 연산 조합을 출력해야한다. 이 문제의 핵심은 다음과 같다.1. 0과 AND 연산을 한다면 반드시 0이 출력되어야 한다.2. 1과 OR 연산을 한다면 반드시 1이 출력되어야 한다.3. 임의의 x번째 비트가 AND와 OR연산의 영향을 받지 않을 때에만 XOR 연산의 영향을 받는다. 이 3가지만 고려하면 문..
PS - OJ/Codeforces 2017. 12. 10. 17:17

Codeforces Round #439 (Div. 2) E. The Untended Antiquity

E. The Untended Antiquityhttp://codeforces.com/contest/869/problem/E div2이지만 무려 E번 문제다.근데 E번 문제치고는 쉽게 풀 수 있었던 것 같다.2D Fenwick + 적절한 random값으로 풀 수 있었다. 일단 문제는 직사각형 평면에 사각형을 그리고 지우는 것을 반복하다가 틈틈이 쿼리가 들어온다.쿼리는 두점을 찍고 두점을 연결할 때 평면에 그린 사각형들의 모서리를 지나지 않고 연결할 수 있으면 Yes, 아니면 No를 출력해야 하는 문제였다. 일단 아래의 입력을 예제로 한번 더 설명하자면, Examplesinput5 6 5 1 2 2 4 5 1 3 3 3 3 3 4 4 1 1 2 2 2 4 5 3 1 1 4 4 outputNo Yes 맨 위의..
PS - OJ/Codeforces 2017. 10. 12. 22:19

Codeforces Round #439 (Div. 2) C. The Intriguing Obsession

C. The Intriguing Obsessionhttp://codeforces.com/contest/869/problem/C (이 문제 너무 어려웠다 ㅠ.ㅠ 콘테중엔 나도 못풀었는데, 해설은 codeforces tutorial을 참고했다.)(참고로 이 문제를 풀려면 페르마 소정리를 알고 있어야 한다. 모른다면 dp로 해결하는 수밖에 없다.) 이 문제는 경우의 수를 구하는 문제다. 섬이 3종류가 있고 섬들 간에 다리를 놓으려고 한다.단 다리를 놓을 때 같은 색깔의 섬들은 최소 3의 길이가 되도록 놓아야 한다. (다리 하나는 길이 1을 의미한다.)각 섬을 직접적으로 연결하는 다리는 하나만 놓을 수 있다.(a,b를 직접적으로 연결하는 다리는 2개 이상 놓을 수 없다.) 입력은 다음과 같다.Examplesin..
PS - OJ/Codeforces 2017. 10. 9. 18:23

Codeforces Round #438 (Div.1 + Div.2) D. Huge Strings

D. Huge Stringshttp://codeforces.com/contest/868/problem/D 이 문제는 cubelover님 덕분에 완전히 이해할 수 있었다. mx가 얼마 되지 않는다는 것을 이해하고 나면, 구현은 어렵지 않다.문제 정황상 대충 작을거로는 처음부터 짐작이 되는데... 이유는 정확히 모르겠고,내가 생각했던 값은 충분히 시간안에 구할 수 없을만큼 큰데 어떻게 해야할지 모르겠어서걍 대충 만들어서 제출해봤는데 콘테중에는 AC받았음... but 역시나 시스페일 먹었다. 일단 핵심은 스트링을 2개 붙여봐야 길이가 k인 부분스트링(substring)이 새롭게 만들어지는 개수는 k-1개가 최대라는 거다.이해가 안가면 그림을 그려서 길이가 k보다 큰 스트링 2개를 붙인다음에 새롭게 만들어지는 ..
PS - OJ/Codeforces 2017. 10. 6. 17:16

Codeforces Round #438 (Div.1 + Div.2) C. Qualification Rounds

C. Qualification Roundshttp://codeforces.com/contest/868/problem/C 자꾸 형식에 맞춰서 쓰다보니 PS관련 블로그 쓰는게 귀찮아서 더 안쓰는 거 같다.그래서 그냥 내 맘대로 끄적이려구 한다... 이 문제는 첫 번째 줄에 n, k가 주어지는데,n은 문제 수고 k는 팀 수라고 한다. 그 다음 n개의 줄에는 각 문제에 대해 풀 수 있는 팀과 풀 수 없는 팀이 표기되는데,1이면 풀 수 있고 0이면 풀 수 없다. 이런 n개의 문제 셋에서 아무거나 몇개 골라서어떤 팀도 전체 문제 중에 반 넘게 풀 수 있는 경우가 생기면 NOT interesting하다고 한다.그래서 interesting하게 문제 셋을 구성 할 수 있으면 YES를 출력하고 아니면 NO를 출력하는 문제..
PS - OJ/Codeforces 2017. 10. 6. 16:03

삼성 서티 시험(삼성 소프트웨어 검정) 준비하기

약 9개월 전 알고리즘 문제풀이(PS - Problem Solving) 시작하기라는 글을 포스팅 한적이 있다. (http://plzrun.tistory.com/entry/알고리즘-문제풀이PS-시작하기) 하지만 나처럼 PS 자체에 대해 관심이 있다기 보다는 잠깐의 취업 준비를 위해 공부하는 사람들이 많다는 것을 알게 되었다. "삼성에서 소프트웨어 시험을 본다고 해서 준비하려고 하는데, 어디부터 시작하고 어디까지 어디까지 공부해야 하나요?"와 같은 질문글이 많았기 때문이다. 사실 나는 이런 질문들을 그다지 좋아하지 않는데, 그 이유는 영어를 잘하는 방법을 묻는 것이 아니라 오픽 시험점수나 토익 시험점수를 잘 받는 방법을 물어보는 것과 같다고 생각하기 때문이다. 하지만 이제서야 이런 시험이 있고 그것이 꽤 만..
PS - OJ/BOJ 2017. 9. 6. 21:45

BOJ 2424 부산의 해적 (BOI - Baltic Olympiad in Informatics 2011)

BOJ 2424 부산의 해적(BOI - Baltic Olympiad in Informatics 2011 Treasures and Vikings)원본 출처: http://www.math.bas.bg/infos/files/2011-06-25-A6.pdf 먼저 BOJ문제 설명에 원본 문제에는 들어있는 Input Data 2개가 빠져있는데,문제 설명에서 제대로 언급하지 않고 있어서 문제를 푸는데 꼭 필요한 입력값이라 생각된다. 혹시라도 맞게 푼 것 같은데, 계속 틀린다면 이 부분을 의심해 보시길. 2번째 입력데이터와 3번째 입력데이터를 보면 뭐가 문제인지 알 수 있다.처음에 바이킹이 나 자신을 보고 있는 것은 괜찮다. (바로 도망가면 됨)하지만 그 다음 턴부터는 바이킹이 나를 보고 있으면 나는 반드시 죽어야 한..
PS - OJ/BOJ 2017. 6. 6. 15:22

2017 Google CodeJam Qual

드디어 2017 Google CodeJam이 시작됐다. 2017.04.08 08:00 AM ~ 2017.04.09 10:00 AM (KST) 1,2번을 풀고3번 봤는데 small문제가 2개나 있었다.그냥 max heap써서 간단하게 해결했는데, large문제는 맞게 짠거 같은데, 자꾸 틀린 결과가 나온다 ㅠ방법은 k값이 짝수인지 홀수인지에 따라서트리를 그릴 때 부모노드의 왼쪽 자식인지 오른쪽 자식인지를 판별할 수 있는데,이 방식으로 루트노드까지 그리고 나면 다시 원래 지점까지 타고 내려오면서 계산하는 방식을 취했다.어제 새벽 5시까지 고민하다가...그냥 거기서 포기했다. ㅠㅠㅠㅠㅠㅠㅠㅠ D번 문제는 보지도 않음. 그래도 작년 이맘 때 쯤엔 막 PS시작해서 퀄문제도 힘들게 풀었는데, 지금은 그 정도는 아닌..
PS - OJ/Google Code Jam 2017. 4. 10. 00:03

Codeforces Round #405 (Div. 2) C

Codeforces Round #405 (Div. 2)C. Bear and Different Nameshttp://codeforces.com/contest/791/problem/C input8 3 NO NO YES YES YES NO outputAdam Bob Bob Cpqepqwer Limak Adam Bob Adam위의 예제를 보고 얘기하면 쉽다.첫 입력 8은 output에서 나와야 하는 단어는 8개라는 의미다.그다음 입력 3은 3개씩 본다는 의미다. 출력의 1,2,3번째 단어를 보면 2,3번째 단어가 Bob으로 겹친다.그럼 NO이다.2,3,4번째 봐도 2,3번째 단어가 Bob으로 겹치니까 또 NO임...그래서 인풋에서 첫번째 2개가 NO라는 의미(당연히 하나도 안겹치면 YES인 셈이다.) 그래서 N..
PS - OJ/Codeforces 2017. 3. 19. 15:44

Codeforces Round #405 (Div. 2) B

Codeforces Round #405 (Div. 2)B. Bear and Friendship Conditionhttp://codeforces.com/contest/791/problem/B 그래프가 주어진다.노드 개수는 15만개이고 간선개수도 최대 15만개를 넘지 않는다. (두 정점간 간선은 두개 이상 존재할 수 없다.) 1,2,3이 친구라면 1-2, 2-3, 1-3 모두 연결되어있어야 친구다.4명이 존재하면 4번 친구는 그냥 혼자 있거나 친구가 있어야 하는 그런 문제였다. 그러니까... 부분그래프가 완전그래프를 그리는지를 판별하는 거였는데,정점개수가 n개가 친구를 먹으려면 각 정점마다 n-1개의 간선이 있는지 보면 된다. 문제는 ㅠ.. 난 그냥 모든 정점의 간선개수가 같다고 풀어버려서 4분 남기고 핵먹..
PS - OJ/Codeforces 2017. 3. 19. 15:24