AtCoder Beginner Contest 306 후기 (ABC 306 4솔)

ABC305는 친구생일에 술먹고 노느라 스킵했다

 

ABC306은 또 Unrated처리되었다 왜이러냐증말

 

이번 앳코더 ABCD번 문제는 매우 쉬웠고 빨리 풀었다

대신 E는 뭔가 쉬운듯하면서 안 풀리고

F는 아이디어가 생각이 안남..,..

 

ABCDE를 안정적으로 풀고 F도 간간히 풀 수 있어야 민트에 올라갈 수 있을 텐데 말이다

앳코더 복기랑 업솔빙을 많이 해야 하는데 자꾸 귀찮아서 미룬다

 

 

 

A - 쉬움

문자열의 모든 원소를 순회하면서 2번씩 출력하기만 하면 된다

 

B - 오버플로우를 조심하자 / 비트연산

첫 제출에 실수해서 5분패널티를먹었다

2^63의 숫자를 표현하기 위해선 64비트짜리 자료형을 사용해야 하고 이 경우 C++에서는 uint64를 쓰거나 아님 파이썬으로 풀어야 한다

bigint??도 아마 가능할텐데 듣기만 하고 써본적이 없다

 

C - 여러가지 방법이 있음 난 set

어떤 숫자가 2번째로 등장하는 위치를 파악하고 그때 그 숫자를 출력하기만 하면 된다

정말 여러가지 방법이 있겠다 bitset을 이용해 숫자가 등장할때마다 toggle 하면 내 코드와 아이디어는 동일하지만 공간복잡도가 많이 개선된 코드를 만들 수 있을 것이다

아님 배열을 만들어놓고 그 숫자가 몇번째 등장했는지 카운트하는 방법도 있겠다

 

D - 쉬운 DP

예제가 친절해서 오답 제출 없이 넘길 수 있었다

그냥 2차원 dp이고 아이디어도 어렵지 않다

 

E - pq 아니면 모노톤큐??

이번 앳코더의 ABCD번이 매우 쉬워서 E나 F중 한문제에 시간을 무한히 박아서 풀 수 있을 줄 알았는데 아니더라

안풀림

 

에디토리얼

 

업솔빙

 

F - 아이디어를 모르겠음

일단 문제설명 읽어보니까 모든 집합은 Disjoint set임

그리고 N에 대해 NC2번 함수를 계산해야함 이건 10000*9999/2 = 대략 5000 0000 번 -> 0.5초

M의 원소가 100개이고 집합 2개 합치면 200개일거임

 

200개 원소가 있는 배열을 정렬하는 시간복잡도 -> 200 * log(200)

이걸 그냥 5000 0000번 하면 시간초과가 날테니깐 뭔가 처리를 해야함

그래서 어떤 테크닉?? 이 필요할 것 같은데 그게 뭔지 모르겠다

 

에디토리얼

 

업솔빙