전형적인 Dynamic Programming 문제... 라고 생각했는데,

사실 DP부분은 너무 간단한거라(전형적인 2차원) 아무 생각 없이 제출했다가 틀렸다.

내가 실수한 부분은 정렬 순서를 잘못 생각한 것이었는데,

다음 중 옳은 접근은 어떤 것일까?

1. 각 선분(구름)을 오른쪽 끝 좌표 기준으로(같을 경우 왼쪽 끝을 기준, 오름차순) 오름차순 정렬한다.

2. 각 선분(구름)을 왼쪽 끝 좌표 기준으로(같을 경우 오른쪽 끝을 기준, 오름차순) 오름차순 정렬한다. 

DP부분은 정말정말 쉽지만 그래도 모른다면...


 Statistics for Single Round Match 605 > Round 1 > Room 34
 SubmissionsDefensesChallengesSystemPointRatings
CodersQnty  /  Points  Qnty  /  Points  Qnty  /  PointsTestTotal  Old  /  New
kcy1019 ]1220.23  00.00  7275.00-220.23275.00  12511411
Darklander1229.37  00.00  00.000.00229.37  18881929
lxhimo2434.08  1-206.28  00.000.00227.80  20792082
shibly1203.31  00.00  00.000.00203.31  13371416
Persian.Gulf1199.06  00.00  00.000.00199.06  15321574
midrux1197.66  00.00  00.000.00197.66  13001380
PugachAG1175.44  00.00  00.000.00175.44  14501491
jimon931167.82  10.00  00.000.00167.82  13871416
nnahas1117.41  00.00  00.000.00117.41  13551356
tomlau175.00  10.00  225.000.00100.00  12001218
foraml192.70  00.00  00.000.0092.70  12081240
SwitchCase1159.94  1-159.94  150.000.0050.00  13711353
wily1178.79  00.00  00.00-178.790.00  15431434
sasha.socha1196.66  1-196.66  00.000.000.00  13501285
ghooo1169.34  1-169.34  00.000.000.00  13271264
XaCaHaa1142.24  1-142.24  00.000.000.00  13091252
Ariza1189.48  1-189.48  00.000.000.00  12941242
Vetteru1131.61  1-131.61  00.000.000.00  12951241
elfus1163.53  1-163.53  00.000.000.00  12921233
Den.sergeyev1102.14  00.00  00.00-102.140.00  12261135
 Problem Information for kcy1019
 Problems
Class NameMethod NameDifficultyCoding TimeStatusPoints
AlienAndHamburgersgetNumberLevel One0:10:44.298Failed System Test220.23
AlienAndSetDiv1getNumberLevel Two0:44:26.421Opened0.00
AlienAndPermutationgetNumberLevel Three0:12:59.917Opened0.00
 Challenges
ChallengerDefendantProblemSucceededChallenge TimePoints 
kcy1019tomlauAlienAndHamburgersNo01:40.005-25.00details
kcy1019VetteruAlienAndHamburgersYes04:48.64850.00details
kcy1019SwitchCaseAlienAndHamburgersYes05:46.08050.00details
kcy1019elfusAlienAndHamburgersYes07:46.84550.00details
kcy1019ArizaAlienAndHamburgersYes08:35.70650.00details
kcy1019ghoooAlienAndHamburgersYes09:30.85750.00details
kcy1019sasha.sochaAlienAndHamburgersYes13:27.54250.00details

그리디이긴 한데 잘못된 그리디를 생각해서 틀렸는데.. 다행히도 챌린지 덕분에 살았다!!!

다음엔 문제도 잘 풀었으면 ㅠㅠ

팬 서비스

채점: http://www.acmicpc.net/problem/1416

길이가 2 * K인 티켓이 있는데, 이 티켓이 다음 두 조건중 하나를 만족하면 당첨 티켓이라고 한다:

1. 앞쪽 K자리의 각 자리 수의 합(e.g.123 -> 1+2+3)이 뒤쪽 K자리의 것과 같다.

2. 홀수 번째 인덱스(1, 3, ...)의 각 자리 수의 합과 짝수 번째 인덱스(0, 2, ...)의 각 자리 수의 합이 같다.

티켓 절반의 길이 K와 티켓에 사용되는 숫자 목록이 주어질 때, 당첨 티켓이 몇 가지인지 구하라(modulo 999983).

(생각해보니까.. 엄청 간단한 문제였는데, 너무 단순하게 생각해서 많은 TLE를 겪었다 ㅜㅜ)


05. 19. 2013.

아깝다 ㅋㅋ 450짜리도 생각까지 제대로 했는데,

무언가 구현에서 문제가 발생한건지 sysfail ㅜ_ㅜ

어쨌든 오랜만의 성공적인 매치! 레이팅이 1494가 되었다.

이제 다시 옐로로 올라가야지!

250

워드프로세서를 이용해서 vector <string> 에 적은 대로 한 줄씩 출력하고싶다.

(vector의 크기 <= 50, 각각의 길이 <= 50)

그런데 이 워드프로세서는 백스페이스가 없고(...), 버퍼에 한 글자 붙이기,

버퍼를 지금까지 존재했던 모든 버퍼의 상태중 하나로 되돌리기,

그리고 버퍼를 한 줄로 출력하기(단, 버퍼는 비워지지 않는다)

 총 3가지의 기능만 지원한다.

최소한 버튼을 몇 번 눌러야 원하는 출력을 만들 수 있을까?

(처음에 버퍼는 빈 상태이고, 되돌리기시 버튼 2번을 눌러야 하며,

출력시 한 번을 눌러야 하고, 당연히 한 글자 붙이기도 버튼을

한 번 눌러야 한다)

450

총 N ( N <= 50 )개의 가게가 있고, 그 가게들중 0 ~ M - 1 (M <= 16) 번째 가게가

Interesting한데, 그 가게들의 개점/폐점 시간과 구매하는데

걸리는 시간이 주어지고, 가게들간에 존재하는 양방향 도로가

소요 시간과 함께 주어질때, 최대 몇 개의 물건을 구매할 수 있을까?

(단, 시작은 N-1번 도시에서 하고, 물건 구매는

개점 <= (도착시간) <= 폐점 시간에 할 수 있고, 구매하는 시간 동안은

움직일 수 없으며, 한 가게에서는 한 개의 물건만 살 수 있다)

1000

'Computer' 카테고리의 다른 글

C언어 기본 - 동적할당  (1) 2013.06.30
SOCKS5 Tunneling by PuTTY  (0) 2013.06.30
TopCoder SRM 579 Div1  (0) 2013.05.19
생활코딩  (0) 2013.04.09
TopCoder SRM 575 Div1  (0) 2013.04.07
VIM으로 euc-kr을 utf-8로 바꾸는 방법.  (1) 2013.03.21

역시 옐로는 아직 내가 있을 곳이 아니다 ㅋㅋㅋㅋㅋㅋㅋ

올라가자마자 블루로 po강등wer매치..

아아ㅏㅏㅏㅏ250게임따위를 틀리다니 멍청이ㅜㅜ


250

John과 Brus가 수를 가지고 게임을 합니다 (John이 먼저 시작).

각자의 차례에서 할 수 있는 행동은 현재의 수에서

현재 수의 약수중 1과 자기 자신이 아닌 약수 하나를 빼는것입니다.

만일 자신의 차례에서 소수를 만난다면 패배!.. ㅜㅜ 으앙..

두 명 모두 최선을 다해서 게임을 진행할 때, 승자를 맞춰보세요. (N은 10^18 이하의 자연수)

500

1000

'Computer' 카테고리의 다른 글

TopCoder SRM 579 Div1  (0) 2013.05.19
생활코딩  (0) 2013.04.09
TopCoder SRM 575 Div1  (0) 2013.04.07
VIM으로 euc-kr을 utf-8로 바꾸는 방법.  (1) 2013.03.21
TopCoder SRM 571 Div1  (0) 2013.02.20
수강신청 매크로 ㅋㅋ  (0) 2013.02.14

2013. 02. 20.

아 또 풀었는데 떨어졌다 ㅜㅜ 슬슬 하기싫어지는 그런느낌.

엄~~~~~청나게 쉬운 문제인데 왜이렇게 못풀었을까.. 실력이 제자리를 맴도는건가 싶다.

이걸 어떡해야할지 참..ㅜㅜ

이 기세라면 계속 풀어도 그린을 가는 신비한 상황도 무리가 아닐것 같다.


250

파일명을 숫자 순서가 아닌 사전 순서대로

(1.mp3, 10.mp3, 11.mp3, 12.mp3, 13.mp3, ..., 2.mp3, 20.mp3, 21.mp3, ..., 27.mp3)

정렬하는 mp3 플레이어가 있다.

이 mp3플레이어에 1.mp3 ~ N.mp3 까지 넣었을 때, 첫 50개 파일의 이름을 구하여라.

(1 ≤ N ≤ 1,000,000,000) 

500

1000

'Computer' 카테고리의 다른 글

TopCoder SRM 575 Div1  (0) 2013.04.07
VIM으로 euc-kr을 utf-8로 바꾸는 방법.  (1) 2013.03.21
TopCoder SRM 571 Div1  (0) 2013.02.20
수강신청 매크로 ㅋㅋ  (0) 2013.02.14
TopCoder SRM 570 Div1  (0) 2013.02.14
TopCoder SRM 569 Div1  (0) 2013.02.07

2013. 02. 13.

아 요즘 ㅋㅋ......왜 풀어도 레이팅이 10씩 꾸준히 떨어지는걸까.......아....

250이 기하라서 긴장해서 좀 실수해서 늦은 감이 있다.. 250따위에 쫄지 말자!!ㅜㅜ


250

양수 배열 a와 양수 T (T <= 10억) 가 주어질 때, 다음 문제를 해결하라!

2차원 평면에 로봇이 임의의 방향을 바라보고 있다.

그리고 1시간마다 모든 a[i]에 대해 다음과 같은 일을 한다:

- 바라보는 방향으로 a[i]칸 이동한다.

- 오른쪽으로 90도씩 a[i]번 회전한다.

이 때, 로봇이 T시간 뒤에 있는 위치와 원래 위치의

맨하탄 거리 (L1-metric distance)를 구하여라.

*맨하탄 거리 : |x1-x2| + |y1-y2|

500

1000

'Computer' 카테고리의 다른 글

TopCoder SRM 571 Div1  (0) 2013.02.20
수강신청 매크로 ㅋㅋ  (0) 2013.02.14
TopCoder SRM 570 Div1  (0) 2013.02.14
TopCoder SRM 569 Div1  (0) 2013.02.07
TopCoder SRM 568 Div1  (0) 2013.01.30
연쇄 행렬곱의 최적 순서를 찾는 알고리즘  (1) 2013.01.27

2013. 02. 07.

250..맞긴 맞았는데 틀렸다고 생각하고 있어서 늦게 내고,

챌에 모든걸 건다! 하고 혼신의 챌을 했으나 -25.

그린 가야지 헤헤 드디어 마음에 안정이 찾아오네!

하면서 놀다가 보니까

내 솔루션이 맞았다!.. 나도 분명 틀릴거라고 생각했는데!

물론 그래도 레이팅은 떨어졌다..ㅜㅜ


..아 ㅋㅋ 아깝다.. 거의 다 간단하게, 빠르게 생각했었는데.

난 아무래도 생각을 정리하는 연습이 아직 덜 된것 같다.


250

길이가 같은 N (1 ~ 50) 개의 길이가 M(1 ~ 50)인 비트 스트링 (이진수 문자열) 이 주어진다.

그리고 어떤 기계에 이 문자열들 중 두 개를 골라서 모두 돌려볼 수 있고,

이 기계는 두 문자열의 각 비트 (0번째 비트, 1번째 비트, ... ) 에 대해

XOR, OR, AND 중 하나를 한 결과를 표시한다.

(그러니까, 0번째 비트는 XOR, 1번째 비트는 AND, 이럴 수 있다는 말)

이 기계가 각 비트 에 대해 무슨 연산을 하는지 확실히 알아내려면

몇 개의 비트 스트링이 더 필요한가?

500

1000

'Computer' 카테고리의 다른 글

수강신청 매크로 ㅋㅋ  (0) 2013.02.14
TopCoder SRM 570 Div1  (0) 2013.02.14
TopCoder SRM 569 Div1  (0) 2013.02.07
TopCoder SRM 568 Div1  (0) 2013.01.30
연쇄 행렬곱의 최적 순서를 찾는 알고리즘  (1) 2013.01.27
TopCoder SRM 567 Div1  (2) 2013.01.21

2013. 01. 30.

아...얼마만에 받아보는 빵점인가!!!

레이팅 떨어지는 소리가 들려온다... 그린이 날 부른다..

여러분

INFINITE 를 (1<<25)처럼 작은 수로 잡는 버릇을 버립시다.

최소 (1<<29)부터 시작해야될거같아요..

아....250.....아오....................걍 다돌리는 쉬운 문젠데.....

왜.....................inf를 1<<25로하는 멍청한짓을...........아.....

250

0, 1, ... , N-1의 번호가 붙어있는 상자가 있고,

이 상자들에 들어있는 빨간공, 파란공, 초록공의 개수가 주어졌을 때,

공을 한 상자에서 한 개씩 꺼내서 다른 한 상자로 옮기는 행위를 최소 몇 번이나 해야

각 상자별로 한 가지 색의 공만 남게 할 수 있는가?


500


1000

'Computer' 카테고리의 다른 글

TopCoder SRM 570 Div1  (0) 2013.02.14
TopCoder SRM 569 Div1  (0) 2013.02.07
TopCoder SRM 568 Div1  (0) 2013.01.30
연쇄 행렬곱의 최적 순서를 찾는 알고리즘  (1) 2013.01.27
TopCoder SRM 567 Div1  (2) 2013.01.21
TopCoder SRM 566 Div2  (2) 2013.01.13

*col[i] 는 i번째 행렬의 열의 개수, col[0] 은 1번째 행렬의 행의 개수로 채워두자.

d[i][j] = min { d[i][k]+d[k+1][j] + col[i-1]*col[k]*col[j] | i <= k < j, i<j }

d[i][i] = 0

*위의 식에서 col[i-1]은 i번째 행렬의 행의 개수이다

 (행렬 곱셈의 조건을 생각해보면 당연하다).

'Computer' 카테고리의 다른 글

TopCoder SRM 569 Div1  (0) 2013.02.07
TopCoder SRM 568 Div1  (0) 2013.01.30
연쇄 행렬곱의 최적 순서를 찾는 알고리즘  (1) 2013.01.27
TopCoder SRM 567 Div1  (2) 2013.01.21
TopCoder SRM 566 Div2  (2) 2013.01.13
Christmas Tree Drawer  (0) 2012.12.25
  1. meguro 2013.08.11 23:23 신고

    쒸트라쏀