글쓴이 ·0개의 댓글

[이 글은 이전에 쓰던 블로그에서 작성된 이후 새 블로그로 이전된 글입니다.]

올해 정보올림피아드에서 유일하게 못 풀었었던 수족관 문제에 재도전해서 다시 풀었다. 풀이는 대회 때랑 동일했다. 결국 남들과 약간 풀이가 다르기는 했지만 동일한 풀이였다. (최대부터 선택하는 것과 최소부터 제외하는 것)

다시 짜는 문제긴 했지만 코딩은 꽤 걸렸다. 대회 때처럼 시간 제한 두고 짜는게 아니라 그냥 느긋한 마음으로 짰는데, 실수를 몇 번 했다. 리넘버링을 하느냐 안 하느냐 등의 사소한 부분도 몇 번인가 바뀌었다. 다행히 실수한 부분을 예제랑 손으로 만든 데이터에서 전부 찾아서 AC는 한 번에 받을 수 있었다.

나는 3KB 정도를 짰는데, 학교에서 같이 나왔던 참가자 중에 1KB 이내로 짠 사람이 있는 것으로 알고 있다. 어떤 부분이 다른지 궁금하다.

며칠 전에는 한국 정보올림피아드 개최 며칠 전에 있었던 경기도 대표 소집 교육 때 나왔던 일본 국가대표 선발고사에 나왔던 문제들을 다시 풀었다. 그 때는 세 문제 중에 한 문제 밖에 풀지 못했었는데, 세 문제를 다 풀 수 있었다.

이전에 풀지 못했던 문제를 풀 수 있게 된다는 건 굉장히 기분 좋은 일인 것 같다. 내가 그 때에 비해 성장했다는 확실한 지표를 보여 주기 때문이다. 그 기간동안 헛살았던 건 아니구나 싶으면서 큰 성취감을 느낄 수 있다.

이번 주 토요일에 국제 정보올림피아드에 나가는 한국 대표를 선발하는 선발고사가 있다. 워낙 잘 하는 사람이 많아서 확실하게 된다고 장담은 못 하지만, 떨어지더라도 ‘아쉬움은 있어도 후회는 없도록’ 준비하고 있다.

선발고사 준비한다고 입시 대비하는 방학 중 프로그램 신청도 안 하고 학교에서 지원해주는 일본 공대 캠프 신청도 날짜가 겹쳐서 못 했다. 포기한 게 많은 만큼 얻는 것도 있으면 좋겠다.

+
수족관 문제
oj.uz

일본 국가대표 선발고사 문제
1
2
3

여기에서 풀어 보실 수 있습니다.

글쓴이 ·0개의 댓글

[이 글은 이전에 쓰던 블로그에서 작성된 이후 새 블로그로 이전된 글입니다.]

이름이 헷갈리게 네이밍 되어 있는데, lower_bound는 목표를 집어 넣을 수 있는 최소 위치를 upper_bound는 목표를 집어 넣을 수 있는 최대 위치를 반환해주기 때문에 이런 이름이 붙었다.

다르게 말하면
lower_bound는 목표보다 작지 않은 최소 원소를, upper_bound는 목표보다 큰 최소 원소를 반환해준다.

예를 들어, {1, 2, 3, 3, 3, 4, 5}에서 3을 각각 lower_bound, upper_bound로 검색했을 때
lower_bound는 세 개의 3 중 첫 번째 3의 위치를 반환해주며 upper_bound는 4의 위치를 반환해준다.

C++ 레퍼런스 참고
lower bound
upper bound

글쓴이 ·0개의 댓글

[이 글은 이전에 쓰던 블로그에서 작성된 이후 새 블로그로 이전된 글입니다.]

#include <cstdio>
 
int n, line, res;
 
//ld is \, rd is /
void solve(int level, int horizon, int ld, int rd){
    if(level == n) res++;
    else {
        int ok = (~(horizon | ld | rd)) & line, i;
        while(ok){
            i = ok & -ok;
 
            solve(level+1, horizon | i, (ld | i)>>1, (rd | i)<<1);
 
            ok ^= i;
        }
    }
}
 
int main(){
    scanf("%d", &n);
 
    line = (1<<n)-1;
 
    solve(0, 0, 0, 0);
    printf("%d\n", res);
 
    return 0;
}

글쓴이 ·0개의 댓글

[이 글은 이전에 쓰던 블로그에서 작성된 이후 새 블로그로 이전된 글입니다.]

아침에는 어젯밤 늦게(2시) 잤던 관계로 살짝 피곤했습니다. 저는 아침에 잘 일어나는 편이라 제 때 일어났는데 나머지 두 명은 거의 좀비였음 ㅋㅋ

아침은 숙박했던 숙소에서 제공해줬는데 빵과 오렌지 주스, 주먹밥, 샐러드 등이 나오더군요. 처음에 간단하게 주먹밥과 반찬을 먹은 뒤 빵을 먹었습니다. 아침 먹고 짐을 싸고 내려와서 대회장 가는 차 안에서 모자란 잠을 약간 보충했습니다.

대회장에서는 대회 시작 전까지 강당에 모여서 대회 시간까지 기다렸습니다. 어제 예비소집 때 오지 않았던 설곽팀이랑 구경을 위해 부산에서 온 계절학교 친구랑 만나서 수다를 좀 떨다가 대회장에 들어갔습니다.

초반에 코딩 빠른 지학이가 쉬운 문제(A, G, I, L, K)를 초고속으로 짜서 적은 패널티를 만들어 놓고, 중반에 제가 J를 짜는 동안 옆에서 수학 잘하는 석환이가 수학 문제(C) 일반항을 유도하는 전략을 썼습니다. F는 그림만 보고 어려운 문제인 줄 알고 넘겼는데 지학이가 풀었습니다. 총 합을 최소화해야 하는 줄 알고 또 어려운 문제인 줄 알았는데 알고보니 최대값의 최소화여서 파라메트릭으로 쉽게 짜더군요.

그 동안 석환이가 C 일반항 유도에 성공해서 AC를 받았습니다. C를 모든 팀 중 최초로 맞춰서 다른 팀이 7문제였는데 저희 팀이 8문제로 1시간 가량 1위를 유지했었습니다. 옵저버라서 안 보였지만.

그 뒤로는 E를 제가 짜고 B를 지학이가 짜면서 서로 번갈아가면서 코딩 막힐 때 마다 자리를 바꾸면서 코딩했습니다. 코드 인쇄하면 가져다 주는데 그게 디버깅에 큰 도움이 됐습니다. 제가 E를 마무리해서 9문제가 되고, 어제 언급한 도쿄대 팀도 9 문제로 한동안 2위에 있었는데 도쿄대 팀이 10문제로 치고 올라가더군요. E 풀고 나서 D를 풀다가 화장실에 간 사이 후배가 B를 AC 시켰고, 10 문제를 풀었습니다.

D를 석환이의 방법대로 제가 코딩을 했는데 자꾸 TLE가 나서 좀 큰 데이터를 직접 넣어 본 결과 처리를 잘못해서 N^2 커팅을 유도했엇는데 실수로 N^3으로 짰다는 걸 발견했습니다. 그게 마감 4분전이라 열심히 고쳤는데 결국 틀렸습니다. 나중에 풀이를 들어보니 O(N)이라더군요.

옵저버 성적을 언급하지 말라는 얘기가 있었는데 푼 문제 수는 풍선도 주고 했으니 아마도 말해도 되는 것 같습니다. 패널티는 비밀입니다.

대회 끝나고는 네이버의 음성인식 강좌 및 NHN 홍보, 넥슨의 ‘게임의 재미를 구성하는 세 가지 축’이라는 강의를 들려주더군요. 넥슨 강의는 NDC 가서 직접 들었던 거 두 번째 듣는거라 재미가 없었습니다.

네이버 음성인식 알고리즘은 흥미롭기는 했는데 5시간 연속 코딩하고 와서 지쳐 있는데 듣는 강의라 정말 말 그대로 더 이상은 Naver… Zzz

강의 다음에는 풀이가 진행되었습니다. PPT는 영어인데 한국어로 풀이를 해서 외국 팀들은 못 듣지 않았을까… 풀이를 듣고도 D랑 H는 아직 어떻게 풀어야 되는지 모르겠더군요. 나중에 다시 풀어봐야 할 듯.

풀이 끝나고 스코어보드 프리즈 된 뒤 어떻게 변했는지 보여주는게 있었는데 이게 꿀잼이었습니다. 글로 잘 설명은 못하겠는데 막 틀렸다 맞았다 바뀌는걸 긴장감 있게 조절하더군요. 많이 틀리면서 꾸준히 제출하면 막 박수쳐주고 그랬음. 대부분 많이 틀리면 결국 틀렸지만…

대회 끝나고 거기서 출장뷔페를 먹고 돌아왔습니다. 쇼고 무라이는 역시나 오늘도 대식가. 학교에 9시 반 쯤 도착하고 12시 쯤 집에 도착했네요.

여튼 좋은 성적을 거둬서 기분이 좋습니다. 정말 재밌는 이틀이었습니다. 이 기세로 IOI도 나갈 수 있으면 좋겠네요 ㅠㅠ

ps) 알고스팟 채팅방 눈팅하다가 방금 H 풀이를 이해했네요. 문자열 어려워…