티스토리

레프네 약방

검색하기

블로그 홈

레프네 약방

tamref.com/m

졸업하고 싶다

구독자: 11

방명록 방문하기

주요 글 목록

제 3회 IDTCup 개최 후기 어제 끝난 제 3회 IDTCup의 후기이다. 무려 21명이 운영진이었고, 참가자는 20명에 불과한 대회였지만 그래도 준비 과정을 적어본다. 부족한 운영 능력에도 불구하고 열심히 검수/참가해주신 분들에게 감사를 표한다. Special thanks to jhhope1. 넋두리 대회에 대한 구상이 구체적으로 나온 건 12월 전후인 것 같다. 이때는 그래도 ICPC를 다시 나가고 싶다는 생각이 있었고. 올해 휴학을 할지 말지 정해진 부분이 없었기 때문에 PS에 대한 관심이 별로 식지 않았던 때였다. 그 사이에 이렇게 급격하게 PS에 무관심해질 줄은 몰랐다. 그래서인지 막판에는 즐겁다기보단 일로 느껴져서 부담되는 부분도 있었다. 출제자들 모두 PS에 대한 관심이 떨어진 상태라, 좋은 대회를 만들자기보다는 그냥 내.. 공감수 4 댓글수 0 2021. 5. 10.
ACM-ICPC 2020 Seoul Regional 후기 ICPC를 마무리하면서 2020의 PS 일정은 사실상 마무리되었다. 11/12 solve 3등으로 전체 대회를 마무리했다. 굉장히 좋은 성적을 거뒀지만, 제 역할을 못한 것 같아서 많이 아쉽다. 기대한 것도 있었고... 대회 준비 팀 구성은 작년과 같이 imeimi / jhhope1 / TAMREF로 구성된 3인팀이었다. 사실 예선 때까지만 해도 거의 기대를 하지 않았다. 학기 일정을 소화하기에도 많이 벅찼고 PS를 거의 손도 대지 않았다. 그런데 솔직히 팀원이 imeimi인데ㅋㅋㅋㅋ 월파 욕심이 안 나기 어렵다. 폼이 많이 떨어진 상태에서 예선을 봤는데 생각보다 가능성이 보여서(??) jhhope1이 실력을 좀 키우자는 이야기를 했다. 결국 내가 아는 문제들을 즈홒한테 던져주고, 즈홒은 풀이를 짜고, .. 공감수 17 댓글수 3 2020. 11. 15.
UCPC 2020 본선 후기 고3 때를 포함해서 3번째 UCPC. ICPC멤버 그대로 (imeimi2000, jhhope1, TAMREF) 완전탐색 원툴 16등 도전합니다팀으로 참가했다. 최종 성적은 10 / 12 solve 5등으로, 역대 UCPC 중에서는 제일 좋은 성적이 나왔다. 팀연습이라고는 UCPC 예선밖에 없었는데 결과는 별로 나쁘지 않았다 ㅋㅋ 기억나는대로 타임라인을 재구성해본다. 약한 스포일러가 있으니 주의. 초반 (0~1시간) 내가 앞, 이멘이 중간, 즈홒이 뒤를 맡았다. A에 후원사 로고가 붙어있는 걸 발견했지만 뭔가 "제일 쉬운 문제"로 불릴 정도는 아닌 것 같아서 B랑 C를 보고 있었다. 한창 복잡한 지문을 읽고 있는데 스코어보드에 초록색 A들이 쫙 깔리기 시작했다. 정신 차리고 보니 쉬운 문제더라. 트리에서 .. 공감수 10 댓글수 0 2020. 8. 1.
ICPC Seoul Regional 2019 후기 스코어보드는 여기서 볼 수 있다. 5, 6위팀과 페널티 4분이라는 근소한 차이로 전체 4등 / 90팀으로 대회를 마무리했다. 예선 본선 모두 4등이다. 팀원은 imeimi, TAMREF, jhhope1. A Bus With No Drivers 팀처럼 컴공과가 한 명밖에 없는 팀이다 ㅋㅋ 팀 전략, 사전 연습, 팀노트 즈홒(jhhope1)은 풀이를 내는 능력이 뛰어난 데 비해 아직 구현이 익숙하지 않았고, 나는 코딩이 빠른 편이지만 풀이를 잘 못 만들었다. imeimi는 단점이 없다. 그냥 이멘이다 ㅋㅋㅋ 그래서 즈홒은 코딩을 잡지 않았고, 내가 Soulless Coding Machine 역할을 하면서 즈홒과 이멘이 주는 풀이를 구현하는 위주의 전략을 사용했다. 레드코더 2 ~ 2.5명 정도가 팀에서 낼 .. 공감수 9 댓글수 1 2019. 11. 13.
IOI 2014 Holiday 문제 링크 10076번: 휴가 문제 지안지아는 타이완에서의 휴가를 계획하고 있다. 휴가동안 지안지아는 도시에서 도시로 이동하고 도시 안의 관광지들을 방문할 것이다. 타이완에는 하나의 고속도로를 따라서 개의 도시들이 위치한다. 이 도시들은 순서대로 0부터 n-1까지의 번호가 붙어있다. 임의의 i(0 < i < n-1)에 대해서, 도시 i의 인접한 도시는 도시 i-1과 i+1이다. 도시 0과 인접한 도시는 도시 1뿐이고, 도시 n-1과 인접한 도시는 도시 n-2뿐이다. 각 도시에는 여러 www.acmicpc.net PS-hell 스터디에서 가장 먼저 해결한 문제다. 문제 내용 길이 \(n\)의 선형 배열 \(a[0\ldots n-1]\)가 있다. \(s\)번째 entry에서 시작해서 한 턴에 다음의 동작들을.. 공감수 0 댓글수 0 2019. 8. 29.
[PS 켠왕 #1] BOJ 10641 The J-th Number PS에 적당한 시간을 할애하기 위해서, 트위치에서 어려운 문제를 푸는 방송을 시작했다. 방송을 할 때마다 Write-up을 써볼 생각이다. 처음으로 푼 문제는 JAG Spring Contest 2013 I번으로 출제된 The J-th Number이다. 켠왕을 걸 정도로 어려운 문제는 아니었던 것 같지만 11번 틀렸다(...) BOJ 문제 요약 \(N\)개의 빈 배열이 있는데, 여기에 \(M\)개의 삽입 쿼리를 먼저 수행한 뒤 \(Q\)개의 구간 쿼리에 답해야 한다. 삽입 쿼리 : \(a\)번 이상 \(b\)번 이하의 배열에 원소 \(v\)를 삽입한다. 구간 쿼리 : \(s\)번 이상 \(e\)번 이하의 모든 배열에서 \(j\)번째로 작은 수를 출력한다. 이 수가 존재함은 보장된다. 스포방지선 풀이 1. .. 공감수 0 댓글수 0 2019. 8. 15.
NYPC 2018 넋두리 상 탄 주변 블로거 1상 탄 주변 블로거 2상 탄 주변 블로거 3 이 셋 중에 하나는 후기를 올릴 것 같다. 문제 풀이는 저 갓갓들이 올리거나, 아니면 공홈에 빠른 시간 내로 업로드될 것 같으니 대회 문제 풀이가 궁금하다면 저 링크들로. 이 글은 탐레프가 어떻게 고등학교 대회 커리어 마지막 대회를 말아먹었는지에 관한 tmi 꾸러미에 더 가깝다. 대회 문제보다는 대회장 모습, 멘탈의 변화 등을 중심으로 기록한 일종의 일기? D - 1. 예선에 민컷도 나오고, Plane sweeping도 나오고, 작년엔 HLD / 센트로이드도 나왔으니 이번엔 분명 어디서 굴러먹던 근본 없는 고인물 문제가 나올 거라고 예상했다. 그래서 제대로 구현한 적이 없었던 센트로이드, Hopcroft - Karp 이분매칭, Li - C.. 공감수 2 댓글수 3 2018. 10. 28.
[추석맞이 폴란드 스터디] 180925 진도 겨우겨우 맞추는 탐레프 추하다~ 풀이 형식 문제 제목 : POI N / N+1 년의 경우 POI(N+1)으로 표기.문제 난이도 : 일반적인 Codeforces 난이도 기준. Div2A~B, Div1A~D.문제 분류 : 그 문제를 푸는 데 필요한 주관적인 KW.문제 풀이 : (tmi가 포함된) 문제 풀이. - 문제 요약이 없습니다. 첨부한 링크를 먼저 보고 와주세요. 오늘 푼 문제 (1 / Total 11) POI96. Agents (Div1C)Spoiler alert!This section is intentionally left blank. POI96. AgentsTag : SCC, Topological Sort 왜 \(n\)은 3000일까? note) 디스크립션에 중대한 오타가 있다. 출력이 NI.. 공감수 0 댓글수 0 2018. 9. 26.
[추석맞이 폴란드 스터디] 180924 겨우겨우 두 문제를 풀어냈다. 진도 따라잡기도 벅찰 거 왜 한다고 해서... 오늘 푼 문제들 (2 / Total 10) POI96. Knights (Div1A) POI98. One-sequences (Div1A) 고민중인 문제들 POI96. CastlePOI04. 스타 대회 Spoiler Alert.This section is intentionally left blank. POI96. Knights Tag : DP, Bitmask Description에 심각한 오류가 있다. 문제에서 주어지는 set Z는 나이트가 있어야 할 곳이 아니라 있으면 안되는 곳이다. 현재 ko_osaga님이 지적해둔 상태. 보드의 세로가 3밖에 안되기 때문에 자연스럽게 3 * n DP를 생각해볼 수 있다.하지만 체스보드에 놓여 .. 공감수 0 댓글수 0 2018. 9. 25.
[추석맞이 폴란드 스터디] 180923 일의 우선순위를 정해야 하는 시점.입시 + 시험공부 + NN스터디 + POI스터디 + QM스터디 + 그 사건 + CubbyMath + 졸업논문 + 과제 = ??? 풀이 형식 문제 제목 : POI N / N+1 년의 경우 POI(N+1)으로 표기.문제 난이도 : 일반적인 Codeforces 난이도 기준. Div2A~B, Div1A~D.문제 분류 : 그 문제를 푸는 데 필요한 주관적인 KW.문제 풀이 : (tmi가 포함된) 문제 풀이. - 문제 요약이 없습니다. 첨부한 링크를 먼저 보고 와주세요. 오늘 푼 문제 (1 / Total 8) POI04. 동굴 탐험 (Div1C) POI04. 동굴 탐험 Tag : Multi-Source Dijkstra, Binary Expansion, Disjoint - Set H.. 공감수 0 댓글수 4 2018. 9. 24.
[추석맞이 폴란드 스터디] 180922 ko_osaga님이 주최하는 추석맞이 POI 스터디에 참여했다!목표는 1일 2솔브로 잡았다. 물론 오늘은 쉬운 문제 위주로 풀다 보니 오버페이스를 해버렸지만... 풀이 형식 문제 제목 : POI N / N+1 년의 경우 POI(N+1)으로 표기.문제 난이도 : 일반적인 Codeforces 난이도 기준. Div2A~B, Div1A~D.문제 분류 : 그 문제를 푸는 데 필요한 주관적인 KW.문제 풀이 : (tmi가 포함된) 문제 풀이. - 문제 요약이 없습니다. 첨부한 링크를 먼저 보고 와주세요. 오늘 푼 문제들 (7 / Total 7) POI96. Rods (Div1A) POI96. Rooks (Div1A)POI96. Fibonacci Words (Div1B)POI97. Canoes (Div2B)POI97.. 공감수 0 댓글수 0 2018. 9. 22.
IOI 2018 풀이 (제작중) Yandex 채점(Day 1) 현재 스코어 100 / 600. 과연 추가할 수 있을런지는 모르겠다...myungwoo님의 블로그에서 (아마) 모든 문제의 풀이를 확인할 수 있다. 아직은 보지 않은 상태. 18.09.05 P1 solved. P1. Combo 꽤 괜찮은 interactive 문제. IOI치고 너무 쉬워서 만점자가 240명 가까이 나왔다는 게 유일한 흠이다.길이 \(N\)인 미지의 문자열 \(S\)가 주어진다.\(S\)에 주어진 특징은 A, B, X, Y 4개의 문자로 이루어져 있다는 것이고, \(S\)의 첫번째 문자는 \(S\) 안에서 다시 등장하지 않는다는 것이다. 이 때 다음의 함수 press(p)를 최대 \(N+2\)번 호출하여 \(S\)를 찾아야 한다 : 길이가 \(4N\) 이하인 .. 공감수 1 댓글수 1 2018. 9. 5.
제 2회 소프트콘 후기 소프트콘 할 때는 항상 다른 일이 있는 상태로 도서관에 있게 되더라... 최근 친 대회중에 가장 돌돌 말린 것 같아서 간단하게 후기를 쓰기로 했다. 눈을 준 건 ABCDE. 그 중 ABCD를 풀었고 등수는 13등이다. 도서관에서 굳이 서브태스크까지 긁고 싶지는 않아서 더 건드리진 않았다. A. 스승님 찾기 (n,m) = (0,0)인 경우 답은 0이다.gcd(n,m) = 1인 경우 정의에 따라 1번만에 갈 수 있다.gcd(n,m) != 1인 경우 (0,0) -> (n-1,1) -> (n,m)으로 2번만에 갈 수 있다. B. 명상 방해꾼 그냥 brute force + prefix sum...이라기보단 모든 방해꾼을 다 더한 놈을 가지고 다니면 된다.지문 독해를 잘못해서 쫄았다. 교내경시의 트라우마가 스멀스멀.. 공감수 0 댓글수 0 2018. 8. 13.
자기곱 (COI 2008) 백준 링크 This section is intentionally left blank. 굉장히 좋은 문제라고 생각한다. 처음에 필요한 관찰들도 좋았고, 구현도 잘만 하면 깔끔한 문제. 정수 \(x\)의 자릿수 곱을 \(p(x)\)라고 하자. 첫 번째 관찰은 \(p(x) 0\)이므로 0이 있는 경우는 제외한다) 가능한 소인수는 \(2,3,5,7\) 뿐이고, \(2^{e_1}3^{e_2.. 공감수 0 댓글수 1 2018. 8. 2.
UCPC 2018 후기 imeimi, Diuven과 함께 unofficial contestant로 참가했다. 팀명은 InDexedTree로 정했었는데 강제로 Challenge-SSHS로 변경당했다. 결과는 9solve + 52팀 중 7등. (스코어보드엔 반영되지 않았다)페널티를 신경썼으면 바로 앞의 TCG를 잡을 수도 있었을 것 같고, 또 반대로 바로 뒤의 DeltaMAX 팀이 무리하게 기만만 안했어도 우리가 질 수 있었다는 생각이 든다.온사이트 대회는 정말 꿀잼이었고 팀 조합도 괜찮아서 대학 가서도 계속 시도해보고픈 팀이었다. 민폐가 되지 않을 수 있다는 전제 하에 말이지 ㅁㄴㅇㄹ 전략도 괜찮았고, 팀 전체적으로 봤을 때는 성공한 운영이었지만 개인 Contestant로는 조금 아쉬운 마음이 남아서 후기를 작성하기로 했다. 의.. 공감수 4 댓글수 0 2018. 7. 30.
CERC 2012 (미완성) (17.11.23 시작)푼 거라곤 D 하나지만... (그것마저도 솔루션 까봄) 앞으로 업데이트됩니다. BOJ 번호는 3405 ~ 3415. A. Kingdoms B. Who wants to live forever? C. Chemist's vow Tag : Implementation, Dynamic Programming http://icpc.me/3408 주기율표 원소들을 웹에서 긁어서 스트링 배열에 저장한다. 한 글자 원소는 14개, 나머지 원소는 100개가 나온다. (2016년에 추가된 Nh, Mc, Ts, Og는 사용하면 안된다!) 입력 문자열을 \(S\)라고 두고,\(dp[x][i]\)를 \(x\)글자짜리 원소를 사용해서 \(S_{1}\cdots S_{i}\)를 만들 수 있는가? 와 같은 boole.. 공감수 0 댓글수 0 2018. 7. 23.
JOI 2012 final round #5 - JOI 국가의 행사 BOJ 링크 내가 아는 풀이만 3개다. 3개 다 멋진 풀이라서 공유하기로 한다. 3개 풀이 모두 다익스트라 전처리가 필요하다. 대신 시작 정점이 축제가 열리는 K개의 정점 모두다! 다익스트라는 시작 정점이 꼭 하나일 필요가 없다. 납득이 가지 않는다면 시작 정점들을 모두 하나의 큰 정점으로 연결한다고 생각해 보자. 시작 정점이 1개인 다익스트라로 바뀐다. 구현도 간단하다. 맨 처음 heap에 (cost = 0, vertex = 시작 정점)을 넣을 때 K개를 다 넣고 일반적인 다익스트라를 돌리면 된다. 이 과정이 끝나면 모든 정점 \(v\)에 대해 축제가 열리는 정점까지의 최단거리인 \(d[v]\)를 얻는다. 이제 쿼리를 오프라인으로 처리할 건데, 처리 방법이 3개의 풀이에서 모두 조금씩 다르다. 1. S.. 공감수 1 댓글수 2 2018. 7. 21.
요리 강좌 - KOI 2017 고등부 #3 문제 링크 : http://boj.kr/14869 This section is intentionally left blank. Tag : Dynamic Programming, Sliding window, Deque, Pigeon hole principle(...) \(dp(i,j)\) : 학원 \(i\)에서 \(j\)번째 강좌를 들었을 때의 최소 비용. 즉 우리가 구하고자 하는 답. \(S(i,j)\) : 학원 \(i\)에서 강좌를 \(1\)부터 \(j\)까지 다 들을 때 드는 비용의 총합. 즉, 비용 배열의 부분합.\(B_i\) : 학원 \(i\)의 불허용 학원. 다음과 같은 dp 식이 성립한다. (엄밀히는 예외가 좀 있지만 뒤에서 처리하자)$$ dp(i,j) = \min_{\begin{cases} k\.. 공감수 2 댓글수 3 2018. 1. 24.
RCC Final round C - Eleventh Birthday Lobelia, RickMcCoy 와 함께 연습한 대회다. (팀명 : Red Lung)나는 C를 잡았는데, 결과는 1 solve로 초라했지만 대회가 끝나고 1시간 가량 더 잡아서 풀어냈다.(애초에 QR을 치려고 했는데 내가 예약을 FR로 잘못한 걸 나중에서야 알았다...) \(n\)장의 서로 다른 카드에 숫자 \(a_1, a_2, \cdots a_n\)이 적혀 있다. (\(1 \le a_i \le 10^{9}\)) 이 카드들을 적당히 한 줄로 길게 이어붙여 만든 큰 숫자가 \(11\)의 배수가 되는 경우의 수를 \(119 \times 2^{23} + 1\)로 나눈 나머지를 구하여라. Tag : Combinatorics, Dynamic Programming, FFT, DP optimization with .. 공감수 0 댓글수 0 2018. 1. 6.
Codeforces Goodbye 2017 Contest http://codeforces.com/contest/908 Result : A, B, C(+3), D (4 / 8) Rating Change :1985 -> 2046 (+61, 343rd place) Editorial : This section is intentionally left blank. A. New Year and Counting Cards (04 : 52) Tag : Implementation A 답게 간단한 문제이다. 모든 홀수와 모음의 개수가 답이 된다. 대회에서는 문제 해석 + 코드 세팅하느라 시간을 많이 잡아먹었다. B. New Year and Buggy Bot (20 : 24) Tag : Brute - Force B 답게 간단하...지만 일단 그리드이기 때문에 코딩이 빡친다. 다양한.. 공감수 0 댓글수 0 2017. 12. 30.
Codechef 2017 November LunchTime https://www.codechef.com/LTIME54 1. Smart Strategy (SMRSTR) Tag : Implementation, Number Theory \(N\)개의 수 \(D_1 , \cdots , D_N \)이 있을 때, \(Q\)개의 정수 \(X_1 , \cdots , X_Q \)에 대해 다음 과정을 수행하는 프로그램 작성하여라. procedure f(X):for i = 1 .. N:X = floor ( X / D[i] )return X \(1 \le \text{TESTCASE} \le 1,000\)\(1 \le N \le 10^5, \ \sum N \le 3 \cdot 10^{5} \)\(1 \le Q \le 10^5, \ \sum Q \le 3 \cdot 10^{5} \)\(.. 공감수 0 댓글수 0 2017. 11. 26.
CodeForces #447 (Div.2 Only) 링크 두 번째 인생...코포. Solved : 4 / 5 Rank : 29 (Official)51 (Including Unofficial) Rating Change : 1738 -> 1895 (파들파들) A. QAQ (00 : 02) Tag : Implementation 어떤 문자열이 주어졌을 때 그 문자열의 'QAQ' subsequence 개수를 묻는 문제. Q가 나올 때마다 개수를 더해 주면서 A가 나오면 (지금까지 나온 Q 수) * (앞으로 나올 Q 수) 를 답에 더해 주면 된다. Complexity : \(O(n)\) B. Ralph and His Magic Field (00 : 34) Tag : Combinatorics, Number Theory 쉬운 수올 문제. 였으나... 알아보지 못하고 백.. 공감수 0 댓글수 1 2017. 11. 20.
Codeforces Round 433 Div.2 문제 : http://codeforces.com/contest/854A. Fraction \(n \le 1000\)이기 때문에 다양한 풀이가 가능하다. 나는 생각을 최대한 안 하는 풀이인 Brute-force로 짰다. Complexity : \(O(n lg n)\) B. Maxim Buys an Apartment ㅂㄷㅂㄷㅂㄷㅂㄷㅂㄷㅂㄷㅂㄷㅂㄷmin : 한 쪽에 아파트를 모두 몰아 놓았을 때이다. \(k=0 \vee k=n\)일 때 0, 아니면 1.max : 그리디하게 2,5,8,....번째 아파트를 inhabited로 설정해 주면 \(min(2k,n-k)\)이 최대가 됨을 쉽게 증명할 수 있는데, 코딩할 때 생각을 너무 안 해서 System Test에서 참교육을 당했다. 으아아아아아아아 Complexit.. 공감수 0 댓글수 1 2017. 9. 7.
[IOI 2016] Detecting Molecules 풀이 문제 : http://oj.uz/problem/view/IOI16_molecules바로 100점 풀이.바로 100점으로 넘어가는 이유는 rkm0959의 풀이를 컨닝했기 때문. 일단 주어진 배열의 값들을 정렬한 값의 인덱스를 \(i_1, i_2, \cdots , i_n\)으로 정의한다. 이제 수학이다. \(Pro(k)\)를 다음과 같은 알고리즘으로 정의하자:\(P(k) := w_{i_1} + \cdots + w_{i_k}, \ S(k) := w_{i_n} + \cdots w_{i_{n-k+1}} \) case 1) \(P(k) > u \) : terminate (답이 없다) case 2) \(P(k) or S(k) \in [l,u] \) : terminate (둘 중 [l,u]에 들어 있는 놈이 답이다) .. 공감수 0 댓글수 1 2017. 8. 9.
APIO 2015 Jakarta Skyscrapers 풀이 문제 보기http://acmicpc.net/problem/10847http://oj.uz/problem/view/APIO15_skyscraper 1. Problem Statement \(N\) 개의 건물 위에 \(M\)마리의 도게가 있는데, 각 도게는 한 번의 움직임으로 정확히 \(p_{0},p_{1},...p_{M-1}\)만큼 이동할 수 있다.이 때 건물 \(s\)에서 시작해서 \(e\)로 릴레이하면서 갈 때, 점프의 최소 횟수를 알고 싶다. 2. Subtask2 - 36점 (\(N,M \le 2,000\)) Subtask1은 백트래킹이다. 짠 적도 없고, 설명하기 까다로운 만큼 넘어가자. 기본적으로 이 문제의 풀이는 다익스트라 알고리즘이다.겨울학교에서 이 문제랑 비슷하게 생긴 문제를 못 푼 기억이 있.. 공감수 2 댓글수 0 2017. 7. 13.

문의안내

티스토리
로그인
고객센터

티스토리는 카카오에서 사랑을 담아 만듭니다.