방학근황

가장 큰일은 몇가지가 있기도 하고 없기도 하다...

역시나 ps로 인생을 낭비해버린 방학이었다.

 

ps인생에 어느정도 큰 방점을 하나 찍었는데, 코포 퍼플을 달았다.

하지만 참여하는 모든 현실적인 대회마다 망하면서 남는게 없는 그런 방학이기도 하다.

이후부터는 우울한 후기가 될수도 있는데... 보기 싫으신 분들은 뒤로 가기 눌러주세요..

 

 

 

SCPC

2번문제에서 크게 말려서, 하다가 현타와서 그냥 도망갔다.

틀리면 안되는 문제였고, 심지어 풀이도 올바르게 짰었다. 
아마 코딩미스땜에 틀렸는데, 나는 풀이자체가 틀린줄 알고 풀이를 바꾸는 짓을 해버렸고, 2번 solve수

보다가 그냥 나갔다. 올해 수상가능성이 낮다고는 생각했지만 제일 큰 대회중 하나 인만큼 정말 힘들었다.
내년에는 잘하고 싶다.

 

 

 

 

 

 

Google CodeJam round2

또 망했다. (이건 방학 맞나..?) 

이건 좀 옛날일인거 같기도 하다. 생각해보니 방학은 아닌듯?
일단 1번문제에서 날려먹었는데, 1번이 실버 5정도 interactive 였다.

근데, 입출력형식을 잘못써서 1시간 쓰고 망해버렸다.

진짜 현타가 너무 왔지만... 어차피 round3는 가도 파이널 가기 어려운걸 알았기에 그려러니 했다.

 

 

 

 

 

 

 

UCPC 

예선은 그래도 평타쳤다. 본선을 내가 너무 트롤짓 해버렸다. 츠바메가에시 솔직히 풀었어야 하는 플레4따리 문제고, (세그트리인거 감안하면 진짜 무조건 풀었어야 한다.) 밋인더미들이라는 풀이까지도 나왔는데 j번 못푼거는 진짜 아닌거 같다. 그래도 팀원들이 분전해줘서 고마웠다. 망해서 후기가 짧다.

현타 +1스택

 

 

 

 

 

 

 

 

 

 

SUAPC

잘하는 팀이 없다보니 어거지로 1등이 된 느낌. 팀원들 다 평타는 친 것 같은데... 팀의 고질적인 문제가 나와버렸다. 어려운 문제를 못푸는 문제.(이건 당연한건가..?) 보통 시간이 남으면 다른팀들은 어려운 문제에 오랜 시간을 쏟아 1문제정도는 쓱싹하던데 우리팀은 다이아에 벽이라도 있는듯 연습셋 할때마다 다이아에서 막힌다. 아쉬웠던 점은 mcmf는 무조건 풀었어야 했고, 다꾸도 풀이는 쉽게 나오는 문제였고 풀수있었는데 내가 망설였다. (금광 세그 case work인걸 설마 냈을까, 맞더라도 내가 시간안에 구현할 수 있을까를 고민했다.) 지금 생각해보면 우리팀이 쉬운걸 빨리 밀어서 3시간 정도가 남았는데 잡았더라면 충분히 가능했을거 같기도 하다...  I번은 구현인데... 솔직히 나는 지금 줘도 못풀거 같다. 하드한 구현 문제는 진짜.. 너무 힘들다. 선인장문제는 내가 bcc를 아예 공부를 안해서 도와줄수가 없엇다. 지금 보니 나는 다꾸를 잡는게 맞았던 것 같다. 시도라도 해볼걸...

 팀적으로 보면 너무 못해서, 힘들었는데 1등이라 그나마 위안이 됐다.

 

다음엔 다이아 푼다!

 

 

 

 

 

 

 

현대모비스 대회

최근에 본 구데기 대회.

scpc 본선도 광탈하는 퍼플따리인 내가 올라갈거 같지는 않아서 그냥 저냥 편안한 마음으로 쳤는데, D번에서 디닉박아서 거의 맞은거 보고 기분이 내심 좋았다. 플로우 안하는 내가 느끼기엔 너무 재밌었다.

근데 그래프 모델링을 틀렸는데(ㅋㅋ)109.5점까지 어떻게 갔을까 (좀 더 자세히 말하자면 N-M개의 정점을 매칭하는데, max flow가 N이 나와야 되는데, M이 되게 모델링을 했다. 즉 남는 정점이 있을수도 있다는 것)

역시 프로그래머스에서 하는 대회 답다. 

C번 보니까 쉽고, 만점이면 올라간대서 빡세게 쳤으면 올라갔을지도?

근데 아쉽진 않다. 대회가 구데기라 180분 대회에 30분 프리즈 되는거 보고, 어차피 상 못탈거 같기는 했다.

 

 

 

 

 

 

 

 

신촌모의고사 출제

첫 출제인 만큼, 열심히 하려고 노력했었던 것 같은데, 너무 어려운 일이라는 걸 다시 느꼈다.

일단 나는 polygon 못쓰겠더라. boj stack 만만세.

체커를 짜는건 힘들었고, 데이터 만드는게 너무 힘들었다. 그래도 어떻게 하다보니까 요령이 생기기는 한거 같다.

 

permutation making

나는 너무 쉬운 문제라고 생각을 했는데(...) 그렇지 만도 않은가 보다.

실버5정도 문제로 예상을 하고 낸 문제 였는데, 난이도가 딱 잘낸거 같아서 만족스럽다.

 

그래프 트리 분할

원래는 단절점을 정해로 생각해 낸 문제였는데... 확인 도중 쉬운 풀이가 발견되어서 지금처럼 수정되었다.

바꾸고 나서도 잘 낸 문제 같다. 본대회에서 tle코드가 뚫리는 (...)사태가 하나 일어났는데, 순위에 영향을 미치지는 않아서 다행이었다.

 

신촌 수열과 쿼리

typical한 segtree문제다. nlogn으로 바꿨으면 아마 0solve가 나오고 중급 대회는 지금도 망했지만 더 망해버렸을 거 같다. 여러가지 풀이가 있는 문제중 parametric search에 seg를 섞는걸 나는 굉장히 좋아하는데, (ex)k번째 수 찾기.) 나는 몰랐는데 작년에도 비슷한 세그가 나왔대서 조금 슬펐다. 다음에는 멋진 쿼리 문제를 또 만들 기회가 있으면 만들고 싶다. 설렌다.

 

전체적인 후기.

검수진분들은 정말 멋지다. 갓이다. 도움을 많이 받았고, 정말 많은 일들을 해주신다고 생각한다.

출제진 분들도 마찬가지이다.

 

초급반은 정말 황밸셋인거 같다. 밸런스는 황밸이지만 새로운 유형은 많이 없다. 개인적으로 아쉬웠던 점은 A번 그냥 함정을 없애는게 나았을거 같다는 생각을 하기도 한다. (나는 너무 쉬워서 걱정이었는데 참가자들한테는 괜한 걱정이었나 보다.) 그래프 트리 분할이 다익스트라보다 티어가 높은데, 우리 예측이랑 달랐다. 음식준비는 생각보다 typical하지 않았나보다. (완전탐색 + 이분탐색) 

 

21학번 친구들이나 동기들이 열심히 해줘서 좋았다. seoin0110이 graph tree분할을 굉장히 아쉽게 틀렸는데... 너무 아쉬웠고, 멘토를 맡고 있는 친구들이 열심히 해줘서 좋았다. 성적과 별개로 다들 흥미를 잃지 않았으면 좋겠다.

중급반은 스코어보드부터 알 수 있듯이 약간 뒤틀려 있는 셋이다. B를 다른 문제로 바꾸는게 나았던 것 같다. 개인셋에서 구현이 있는 문제들은 확실히 재고해볼 필요가 있다. C는 검수할때 정말 많이 틀렸던 문제다. 잘 낸 문제인거 같다.

D는 내 문제고 A다음으로 많이 풀린 문제여서 행복했다. 여담으로 top down + parametric search시간이 빡세다는 의견이 있는데 검수진 분들 제일 느린코드가 1700ms 나오길래 걱정 없을 줄 알았다... ㅠㅠ 
뭐 안되면 $o(nlogn)$짜시던지!

 

중급반은 1bin에게 미안한 셋이었다. 다음에는 더 좋은 셋을 내도록 할게! 

 

 

 

 

 

solved.ac/ boj 

다이아 2를 찍었고, 2100문제를 찍었다. 

새로운 고급 알고리즘으로 pst, pbs,slope trick,mobius inversion,z 을 공부했다.
방학기간에 비하면 그렇게 많이 공부하지는 않았다. 연습셋 하면서 생각보다 많이 안나온다는걸 깨달아서 일까? 

올해가 icpc가 끝나면 flow,geometry를 집중적으로 파볼 생각이다. flow를 어차피 원빈이가 풀거니까 하고 공부를 안했는데, 의외로 flow로 뚫리는 문제가 많아서 flow자체에 흥미가 생겼다. 기하는 연습셋에 맨날 있는데, 안하기에는 너무 major한 분야라는걸 깨달았다. 문자열보다 훨씬 많이 나오는 듯 하다. 

 

pst는 작년 기출이기도 하고 구현이 은근 쉬워서 놀랐다.

 

pbs도 마찬가지로 구현이 쉬워서 놀랐다.

 

slope trick은 이해는 했는데, 응용 문제가 개어렵다. 어차피 안나올거 같아서 공부 깊게는 안할예정 ㅋㅋ!

 

mobius inversion은 정말 사기다.  마치 seg 처음 배울때처럼 문제들 날먹이 가능하다. 연습셋하다가 coprime integers라는 문제를 만났는데, 이때는 포함배제로 커버가 가능해서 공부는 안했었다. 그러다가 코포에서 한번 더 나와서 그냥 공부했다. (물론 이 문제도 포함배제로 가능하지만... 그냥 mobius쓰자...) 

 

z는 아무것도 없는데 패턴매칭이 kmp보다 짧다. 그건 신기했다. 코포에서 한번 봤다.

 

 

 

 

 

 

 

 

코드포스

코드포스 점수 올리는 법을 알아냈다...!

 

무엇인지 아는가?

 

코드포스 문제를 푸는 것 이다.

 

업솔빙? 중요하기는 하다. 근데 그것보다 중요한건 코드포스 문제를 푸는 것이다.

나는 블루에서 정말 오래있었고 고통스러워 했는데 (부캐까지하면 rated round 70번 이나 해서 퍼플이 된 것 같다.)

정말 재능이 없는 거에 한탄하면서 열심히 노력했는데, 노력의 방향성이 어찌보면 뒤틀려 있었던 것 같기도 하다.

코포 점수를 올리려면? 코포 문제를 풀면 된다.

위에 사진을 가지고 온 이유는 내가 코포 문제를 꾸준히 풀고 있다는 것을 보여주고 싶어서 잔디를 가져왔다.

코포 티어는 올리고 싶은데 연습은 백준으로 했었다. 이것만 해도 될줄 알고 말이다. 

가장 효율적인건 역시, 코포 문제를 푸는 것이다. 블루 탈출할때는 1700~2200문제들을 problem set에서 잡고 푸는 연습을 많이 했다. 지금도 하루에 한문제 이상 새 문제를 풀려고 노력하고 virtual contest는 1주일에 1번 하고 있다.

 

실력은 계단인거 같기도 하다.

본캐 퍼플을 달고 바로 부캐 퍼플을 달았기 때문에 그걸 좀 느꼈다. 그것도 5번의 round만에...
위에서 언급했다시피 70번 동안 죽을둥 살둥 힘들게 퍼플 단거에 비해 허무하게 올라갔다. (물론 내가 잘 보기도 했다.)

지금은 가장 최근 라운드를 조져서 부캐는 다시 블루이기는 한데... 뭐 어쨌든 실력은 확실하게 올라간거 같다.

이전까지는 블딱 실력이였다면 지금은 1950~2000점 정도의 실력이 꾸준히 나오는 cp러가 된거 같다.

 

또 최근에 느끼는 건, 확실히 icpc != codeforce이다.

어려운 문제를 잘 푸는것과, 코포처럼 쉬운 문제를 빠르게 미는거는 다른 이야기 이다.

모두다 잘해지자.

 

 

 

 

 

 

 

 

 

팀연습

 

1주일에 2번 팀연습을 했다. 코포 gym에서도 많이 했고 백준 연습셋에서도 많이 했다.

팀연습 전략은 어느정도 세워진거 같다.. 

개인적으로 느끼는 팀원들의 장점이다.

 

1bin

 진짜 ps의 재능 그 자체. 접지 않는다면 레드를 꼭 갈 인재. 강점에서 굉장히 강함.(?!)

1bin은 ps에 노력 정말 많이 했다. 그리고 재능도 확실히 보답해줬다. 1년도 안되서 오렌지를 찍었고 솔직히 내가 보기에 라운드만 잘타면 레드도 갈거 같다. 1bin의 장점은 그래프,애드혹,그리디 이 3가지 능지 문제에서 확실히 탑을 찍고 다 패버린다.

 

 강점에서 굉장히 강하다는거에 대해 좀 설명을 하자면, 평균 능력치가 3이라면, 잘하는 분야가 나오면 30정도의 효율성으로 뚝배기를 패버린다. 코포 연습셋 돌때보면 혼자 잡더니 한 플레2~1 그래프를 초반에 잡더니 갑자기 풀려있다. (gym에서도 10팀안쪽 밖에 안 풀린 타이밍에) 정말 잘 팬다. 그리디나 애드혹 문제에서의 장점도 있다. 나같은 경우는 그리디나 애드혹에서 굉장히 기복이 심한데 1bin은 자신의 풀이를 믿을 수 있다. 즉 맞는다고 생각을 하면 어느정도 증명을 하고 들어간 상태고 풀이에 믿음이 있다. 그래서 그리디나 애드혹 맡기면 잘 안말린다. 굳.

구현도 잘한다. 사실 구현은 내가 하는게 맞는데 이상하게 연습셋 으로 문제 배분을 할때 1bin이 구현 문제 있는걸 가져간다. 운이 없나 보다.

 

단점은 말릴때가 가끔 있다. 물론 말릴때는 누구나 있기는 한데 1bin은 풀이는 맞는데 틀리는 현상이 자주 나와서 더 말리는거 같다. 풀이도 안나오는 사람이 많은데 정말 대단한거 같다. suapc때도 그랬고, 내가 그래서 반례를 자주 찾아주려고 노력한다. 우리팀의 전력 60%를 담당한다. 

 

gumgood
 경험많은 검-갓은 우리팀의 기둥이다. 일단 우리팀의 유일한 기하 청소부이며 (기하 쓰레기통)  거의 모든 알고리즘을 접해보신적이 있어서 정말 좋다. 검굿님은 정말 8각형 능력치를 가지고 있다. 뭐하나 빠지는 부분이 없고, 알고리즘 적인 부분, 발상적, 지능적인 부분, 다 뛰어난 팀원이다. 특히 가끔 경험에서 우러러나오는 짬으로 우리에게 풀이를 던지실때가 있는데 그때마다 감탄한다. (log mcmf라던지...) 게다가 설명을 굉장히 잘하신다. 이것도 굉장히 좋은 부분인데 쉬운 문제 다 밀고 어려운 문제를 고민하는 타이밍일때, 1 + 2 로 나눠서 풀게 되는경우가 많은데, 보통은 나랑 껌님이 2가 된다. 이때 껌님이 생각하는걸 설명해주실때 굉장히 전달이 잘 된다. 

 

 또 최근에 느낀건데 세그문제를 굉장히 잘하신다. 기하는 플레 3까지는 안정적으로 미시는 것 같다. 사실 1bin과 내가 둘다 못해서 혼자 열심히 하시는데 미안하기도 하다.  알고리즘적인 부분이 확실히 강해서, 잘 패신다. 이번에 red shift 로 world final에 가시는데 건승하시면 좋겠다!

 우리팀의 전력의 39%를 담당한다.

 

djs100201

버스 승객,응원을 담당한다.

일단 나는 내가봐도 기복이 심하다. 잘 풀때는 또 잘 푸는것 같다가도 못풀때는 못푼다. 남들 다푸는거 까지는 다 푸는 팀원이고, 껌굿님이 능력치가 8각형이라면, 나는 8각이 다 약한 팀원이다! (ㅋㅋ) 

그래도 장점을 뽑자면 확률이나 게임, dp같이 수학섞인 문제들에서 그나마 강한 편이다. 

확실히 이 3가지 유형이 나오는 문제에서는 꽤 잘할때도 있다

가끔 팀연습중에서 위3개가 나오면 열심히 1인분 하기도 한다!

 

https://www.acmicpc.net/problem/17539 

https://www.acmicpc.net/problem/21341

https://www.acmicpc.net/problem/16187

등등 이런거..?

 

플레5까지 남들 다 푸는거는 푸는 팀원인데... 나는 내가 봐도 어려운걸 너무 못푼다. 보통 시간이 오래 걸리면 어려운걸 해결해내가는 사람도 있는데, 나는 그렇지 못하고 어려운 문제에 풀이를 떠올릴 생각도 못하는 경우도 가끔 있다.

장점중에 하나는 양치기를 많이 한 덕분인지 풀이 방향성은 잘 맞는다는 점도 있다.

 

https://www.acmicpc.net/problem/16575

이 문제도 오일러 회로로 접근하는 방향성도 잡았고, ucpc에서도 meet in the middle인거, 등등... 방향성은 나름 잘 맞는다. 방향 맞으면 뭐하냐 문제를 맞춰야지!

 

icpc전까지 dp최적화, 정수론, 문자열, fft 위주로 공부할 생각이다. 캐리할 생각보다는 서포터의 마음가짐으로 버스타면서 도와줄 생각을 해야겠다. 팀전력의 1%를 담당한다..! 버스 좋다!

 

 

 

마무리

 

방학은 끝나가고~~ 실제로 끝났다.

방학때는 놀아야 되는데... 코시국이 너무 강해져서 못논게 많이 아쉽다.

여러가지 개발 공부를 하기로 마음먹었는데 안했다..! ㅋㅋ

나는 어쩔수 없는 ps러인가 보다.

유일하게 공부한 거는, 정수론 공부는 약간 했다. 

 

방학전인거 같기는 한데... 시카고를 봤었다. 재밌었다. 감명깊었다.(정말로)

아쉬웠던 점은 너무 멀리있어서 배우분들이 잘 안보였다 ㅠ_ㅠ

 

블랙위도우를 봤었다.

재밌었는데... 엄청 재밌지는 않았다.

 

신촌 게임하는데도 2번 갔었다.

둘이서 한번, minigb가  초밥사줘서 한번

재밌었다. 솔직히 너무 재밌었다.

야구 빠따 치는게 재밌는듯!

 

오버워치를 다시 시작했다.

롤처럼 사람들이 욕을 많이 안해서 좋다.

실력이 옜날보다 훨씬 못해졌는데

오히려 티어 욕심이 없으니 더 좋은거 같기도 하다.

 

lck 결승을 suapc끝나고 다같이 본것도 좋은 추억이었다.

 

아 방학때 알바도 열심히 했다.

곧 그만둘 생각이다. 초딩들 가르치기 힘들다...

 

이번 학기에는 더 열심히 살자. 

끝.