220912 문제 풀이 기록

*800 | 1702A. Round Down the Price

풀이 시간: 무려 +12분

시도 횟수: 무려 2회

체감 난이도: B3

풀이 쓸 의향: 下

풀이

1. while (ans*10 <= n) ans*=10;
2. cout << n-ans << "\n";

여담: 문제를 잘못읽고 냈다가 안보고 B풀고 나서 다시품

 

 

 

*800 | 1702B. Polycarp Writes a String from Memory

풀이 시간: 10분

시도 횟수: 1회

체감 난이도: B1

풀이 쓸 의향: 下

풀이

단순 브루트포싱 및 구현.

여담: string 관련 구현을 너무 못하는...

 

 

 

*1100 | 1702C. Train and Queries

풀이 시간: 13분

시도 횟수: 1회

체감 난이도: S1

풀이 쓸 의향: 下

풀이

map으로 가장 왼쪽 / 오른쪽 저장해놓은 상태에서 풀기

여담: 단순 map 구현 문젠데 생각보다 오래걸려버림 ㅠ

 

 

 

*1000 | 1702D. Not a Cheap String

풀이 시간: 5분

시도 횟수: 1회

체감 난이도: S3

풀이 쓸 의향: 下

풀이

greedy하게 가장 높은 비용의 letter 하나씩 빼기

여담: C>>D Forces..

 

 

 

*1600 | 1702E. Split Into Two Sets

풀이 시간: 30분

시도 횟수: 2회

체감 난이도: G3

풀이 쓸 의향: 中

풀이

그래프로 구현하여 그래프 노드 개수가 전부 짝수면 YES, 아니면 NO

여담: 참신한 문제

 

 

 

*1700 | 1702F. Equate Multisets

풀이 시간: 40분

시도 횟수: 4회

체감 난이도: G3

풀이 쓸 의향: 下

풀이

배열 a의 원소가 모두 홀수가 될때까지 전부 2로 나눠준 뒤, b를 계속 나누면서 a의 원소가 되는지 확인. multiset 쓰면 편함.

여담: a의 원소가 짝수면 무조건 되는줄 착각하고 -1, multiset 1일때 고려 안해서 -2;

 

 

 

*800? | 1729A. Two Elevators

풀이 시간: 무려 6분

시도 횟수: 무려 2회

체감 난이도: B3

풀이 쓸 의향: 下

풀이

단순 구현

여담: 문제 잘못 읽고 -1;

 

 

 

*800? | 1729B. Decode String

풀이 시간: 7분

시도 횟수: 1회

체감 난이도: B1

풀이 쓸 의향: 下

풀이

단순 구현

여담: string 구현이 좀 귀찮음

 

 

 

*1000? | 1729C. Jumping on Tiles

풀이 시간: 무려 20분

시도 횟수: 무려 2회

체감 난이도: S4

풀이 쓸 의향: 下

풀이

(시작점, 끝점)이 오름차순이면 오름차순 모든 letter 순회, 내림차순이면 내림차순으로 순회;

여담: 내림차순 처리 안해놓고 왜틀렸는지 몰라서 시간 좀 많이 날림...

 

 

 

*1100? | 1729D. Friends and the Restaurant

풀이 시간: 10분

시도 횟수: 1회

체감 난이도: S1??

풀이 쓸 의향: 下

풀이

[갖고 있는 돈 - 내야 하는 돈] 오름차순 정렬해두고 투포인터 그리디

여담: 풀이 시간 < 구현 시간 < 문제 이해 시간

 

 

 

*1600???? | 1729E. Guess the Cycle Size

풀이 시간: 50분!!!!!!!

시도 횟수: 무려 12회;

체감 난이도: X

풀이 쓸 의향: 下

풀이

(1 2) / (2 1),  (2 3) / (3 2) ... 같이 (a b) (b a) 번갈아 쿼리 날리면 1/2^25 확률로 틀리니 사실상 맞음

여담: 이건... 쉬운데.... 뭐지 이게;

 

 

 

*1800 | 1729F. Kirei and the Linear Function

풀이 시간: 1시간

시도 횟수: 무려? 6회

체감 난이도: G1

풀이 쓸 의향: 下

풀이

(a*b)%c = ((a%c) * (b%c))%c, (a+b)%c = (a%c + b%c)%c이며, 9로 나눈 나머지는 항상 모든 자리수의 합을 9로 나눈 나머지와 같다는 사실을 이용하자.

부분합을 활용해 각 테스트케이스마다 각 시작점에서의 substring을 9로 나눈 나머지를 알 수 있고, 나머지 값은 0부터 8까지이므로 각 쿼리마다 9^2 순회 돌면서 확인하면 됨.

여담: 초기화를 쿼리 while안이 아니라 TC while안에서 바꿔주는 기열찐빠짓을 저지르는 바람에 시간 안에 못풀었음....

아 아직도 화나네 ㅋㅋㅋㅋㅋㅋㅋ