JMK 쓸모없는 vitamin electric nihility

ACM ICPC 2001 Seoul

어제 애들이 PS 에서 돌길래 따라 돌아 보았다. --; 7문제 푼 시점에서 마지막 문제를 놓고 할까 말까 고민하다가 '에잇 다풀어야지 난 멋있으니까 'ㅡ')r' 하고 달라붙어서 결국 풀었다. ㅠ.ㅠ 8/1242. 한 시간 있다 시작했으니 실제로는 8/762. 당시 원석이형 성준이형 태형이형 팀네는 7/646. 하지만 8년전의 대회잖아 기쁘지 않아 ㅠㅠㅋㅋㅋㅋㅋㅋㅋ

(more)

IPSC2009 기록

끝나고 뒷풀이 겸 해서 참가자들끼리 간단히 맥주 한 잔 하고 컴실 들어와서 잤다. 'ㅡ')r 8시간동안 잠도 한번 안깨고 쿨쿨 잤음. 기억이 사라지기 전에 얼른 기록.

• 문제세트
• 솔루션

문제 맞은 순서

• A1 (6), A2 (8) (JM)
• B1 (15), B2 (16) (스탱)
• D1 (24) (JM)
• G1 (39) (JM)
• E1 (40), E2 (41) (스탱)
• J1 (61) (JM)
• K1 (88+10), K2 (93) (JM)
• D2 (119-40) (일루)
• L1 (142) (JM)
• M1 (170) (JM)
• F1 (189) (스탱)
• J2 (281+40) (JM)
• I1 (299+20) (일루)

초반에는 A, B 조낸 빨리 풀고 실수로 내가 D1 맞아버리면서 - _ -; 비교적 잘 나갔다. G1 이랑 E 를 풀었을 40분쯤까지는 거의 3위권 안을 유지하고 있었지만.. 120분 정도까지는 그래도 10위권 유지하고 있었다. 후반에 내가 L1 과 J2 에 말리면서 순위가 점점 하락.. -_-; 마지막에 J2 I1 을 풀어서 결국 15위로 올라가고 끝났다. 돌이켜보면 G2, M2 를 못 푼 게 제일 아쉬움. 둘 중에 하나라도 풀었으면 7등, 둘 다 풀었으면 5등 막 이런데 ;ㅁ;

갭이 줄어들긴 하지만 여전히 갭은 있다는 것을 깨다른 하루엿따 [...]

문제별 기록 - 스크롤의 압박 ...

IPSC 2009 over

Korean teams ranklist:

15) Andromeda Express 23 1620 A1 A2 B1 B2 D1 D2+ E1 E2 F1 G1 I1** J1 J2** K1* K2 L1 M1
54) Concept Export to Andromeda 19 941 A1 A2 B1 B2 D1 D2++(..)(7) E1 E2* G1 G2 J1 K1 K2
66) HectoPascal^3^ 19 2019 A1 A2** B1 B2 D1 D2+ E1 E2* G1* G2 J1** K1 K2
67) MaybeIDoNot 19 2101 A1 A2***** B1 C1*** C2*** D1 D2 E1 E2 F1 G1 J1* K1 K2
70) ICU Old Boys 18 1003 A1 A2 B1 B2 D1 D2 E1 E2 G1 J1 K1 K2 M1*
85) Korean Idol 17 1009 A1 A2* B1 B2 D1 D2 E1 E2 G1 J1* K1 K2
88) Easy problem to easy solution 17 1181 A1 A2 B1* B2 D1 D2 E1 E2 G1 J1* K1 K2*
95) LimeOrange 17 1483 A1 A2 B1** B2 D1 D2 E1 E2* G1 J1 K1*** K2*
115) EOS 16 1400 A1 A2 B1** B2** D1 D2 E1 E2 J1* K1** K2
151) Failed System Test 14 747 A1 A2 B1 D1++(...)(9) D2 E1 E2 G1 K1 K2
212) Proofs from THE BOOK 11 563 A1 A2 D1 D2 E1 G1 K1 K2
229) Pray 10 714 A1 A2 D1 D2 E1** E2* F1
240) re. Fin. 10 1163 A1 A2 D1 D2 E1* E2 J1
248) KNSSM 9 594 A1 A2 D1 D2 E1 E2
314) mathica 7 756 A1 A2 D1 D2 E1
329) labyrinth 6 118 A1* A2 D1 D2
331) Chaika 6 157 A1* A2 D1 D2
399) nangsik 4 433 A1 A2 J1
402) petitkan 4 615 A1 D1 D2
406) Virus 3 39 A1 A2
460) ckebabo 1 37 A1 아.... 졸려.

G2 풀었으면 숙원의 탑텐인데 까비.

아는 사람만 웃긴 개그

IPSC 가 내일 저녁. IRC 에서 Andromeda Express 팀의 대화.

<Nana^> 그래프는 나에게 맡기3
<Nana^> ㅋㅋㅋㅋㅋㅋㅋㅋ
<JM^laptop> ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ
<JM^laptop> 수학문젠 제게 맡기시죠
<Nana^> 헐 ㅋㅋㅋㅋ
<Nana^> 날 그렇게 못믿나 ㅋㅋㅋㅋ
<Nana^> ㅋㅋ
<JM^laptop> ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ

Segment Tree (modified)

A Segment Tree maintains a set of intervals, where ends of every interval lie on one of the predetermined points P. Therefore, there are O(P^2) possible intervals. The major use of a segment tree is to do ranged queries; therefore, it's more or less like binary interval trees, but with sparse coordinates.

For each node, this implementation maintains the size of the union of all intervals within the range that this node covers (ooh long sentence). This is handful for calculating the area of the union of rectangles on a 2D plane.

(more)

IPSC 2006 연습

토요일의 대회에 대비해 조금 연습해 보자. 첫 서너 시간 정도만..

이렇게 써놓고 5시간 다 돌았다. -_-; 결과는 20/1345. 당시 스탠딩 에 비춰 보면, 15등 성적. Single-person team 중에서는 1등 성적 (2006년의 페사마에게 이겼다 -_ -;). 이거 포스팅 하면서 L1 소스코드 L2 에 돌려보니 그냥 나오네 -_-;; 이거 냈었으면 탑 텐이구만. ㅋㅋㅋ

계속 성장하고 있다는 생각이 들어서 다행이다.

거의 다 파이썬으로 풀었는데 C++ 만큼은 아니지만 코딩이 자연스러워지고 있어서 좋다.

소스보기 ...

SRM427 Div 1 연습

옛날에 풀었던 것 같은데.. 음.. --;; 모르겠다. C# 으로 돌아봤다. 냐옹

(more)

동적 계획법 챕터 차례

Contents of my Dynamic Programming Chapter:

1. 도입 introduction
2. 메모이제이션 memoization
3. 전통적 최적화 문제들 classic optimization problems
4. 최적화 문제의 실제 답 계산하기 reconstructing solutions to optimization problems
5. 경우의 수 세기 counting with Dynamic Programming
6. 최적화 문제의 최적해 수 세기 counting number of optimal solutions for optimization problems
7. 확률 계산하기 probabilities
8. 정수 외의 입력에 대한 메모이제이션 memoization for inputs other than integers
9. 계산 게임 computational games
10. 다른 테크닉들 other techniques
    • 반복적 동적 계획법 iterative Dynamic Programming
    • 공간 복잡도 줄이기 reducing space complexity
    • 선형 변환 점화식을 행렬로 바꿔 풀기 solving recurrences formed as linear transformation
    • 자주 하는 실수들 common pitfalls

프로그래밍 대회 밖에서는 그렇게 자주 중요하진 않은 주제이지만 동적 계획법엔 여러 모로 애착이 많다. DPJM 의 모든 걸 담으려고 생각은 하는데, 생각처럼 쉽지 않다. 스스로가 아는 것을 계속해서 고치고, 새로 깨닫고 있다. 분량 면에서 압도적인 챕터가 될 것 같다.

Despite the fact that dynamic programming is hardly the most important algo/data structure technique outside the programming contest world, I do have a deep interest, or even affection, for dynamic programming problems. I am trying to put everything I know about DP in this chapter, but it's not really easy; I do keep realizing new things about what I've known, so I constantly reorganize. This chapter is going to be the longest, and has the largest stack of exercise problems so far.

謹弔

삼가 고인의 명복을 빕니다. 당신의 죽음을 잊지 않겠습니다.