소개

지난주 콘테스트에서 무사히 하늘색이 되었기 때문에, 지금까지 한 일의 되돌아보기를 겸해 기사를 정리합니다.

자기소개

도쿄 공업 대학 지구 행성 과학과 졸업
졸론에서 파이썬 라이브러리를 사용한 것만으로 대학에서는별로 프로그래밍하지 않았습니다.

새로운 졸업생으로 IT 계열사에 입사하고 업무에서 파이썬을 배우기 시작했습니다. 그래서 파이썬과 프로그래밍의 지식을 높이기 위해 atcoder를 시작했습니다.

도코 대학을 넣을 정도로 고등학교 수학이 가능했기 때문에 (대학 수학, 물리학에 튕겨졌지만), 순조롭게
하늘색까지는 늘렸습니다.

사용중인 라이브러리 치트 시트 중에서 완전히 copipe가 아닌 것을 던지는 github

하늘색까지 한 알고리즘

프로덕션에서 실제로 사용하여 풀어서 속도에 기여한 것

・bit전 탐색
· 누적 합
· 배열 이분 탐색 (bisect 모듈)
・함수 이분 탐색(순환식)
· unionfind
・역원
・약수 관련
・주기성에 주목하는 테크
・세그나무
· 지연 세그 나무
・간단한 dp

정진했지만 프로덕션에서 나오지 않았거나 할 수 없었던 것

· BFS, DFS (wizard in maze를 풀 수 없었다)
・다이크스트라
・척추
· 우선 순위가있는 대기열

이름만 알지 못했던 것

・워셜 플로이드
・베르만포드
· 흐름 관련
・전역 나무
・고속 푸리에 변환계

하늘색까지 해 느낀 파이썬 경쟁 프로의 장점 단점

다중배 길이 정수

이것이 가장 크다! 푸는 시간도 소중한 경프로에서 오버플로우라는 생각 요소가 1개 줄어드는 것은 크다! 특히 가장 느낀 것은 Road to Millionaire
h tps // 아 t 여기 r. jp / 이런 sts / m 소소 치온 s2020 / sks / m_ 소 치온 s2020_d
이었다. 이것은, 제약이 작으면서 대답이 방대해질 수 있으므로, 오버플로 할 수 있다고 하는 함정이 있는 문제입니다만, python세는 아무것도 생각하지 않고 탐욕하는 것만으로 AC 할 수 있습니다. 진짜 문제가 실생활과 관련되어 있기 때문에 비현실적이지만 금이 방대하게 늘어날 가능성을 간과하기 쉽지요. 게다가 이 콘테스트는 나머지 2문제가 너무 높은 벽이 되어 있어, 파랑까지는 D까지의 빨리 풀어서 승부가 정해지는 회였습니다. SNS에서는 오버플로를 눈치채지 못하고 30분이나 시간을 녹인 보고도 있었습니다만, 이것만으로 수백도 파포가 바뀔 수 있는 무서운 문제입니다. 이런 사람의 파포를 빨았는지, 당시 갈색이면서 27분으로 4 완성해 파랑 파포를 내는 데 성공했습니다.

또, 다배장 정수 특유의 테크로서, bool 열을 1 개의 정수로서 가지는 테크가 있습니다. 이렇게 하면 기술이 편해지거나 매우 큰 정수배 고속화가 됩니다.
h tps // 아 t 여기 r. jp / 이런 sts / 아 bc147 / 스 b 미시 온 s / 16047068
이것은이 기술을 사용하여 파이썬에서 80ms로 해결 한 대답이지만, bool을 개별적으로 배열로 사용하면 80ms가 TLE가됩니다.

풍부한 라이브러리, 함수

pow(a,-1,mod) 로 역원이 고속으로 나오는 것은 어색합니다.
itertools의 product로 bit 연산 몰라도 bit 전 탐색할 수 있는 것도 편리합니다.
numpy,scipy,networkx도 매우 유용합니다.

jupyter notebook

인터랙티브하게 프로그램의 검증을 할 수 있으므로, 특히 시작한 파이썬 문법 우로 기억의 무렵에는 신세를 졌습니다. (C++에 비슷한 것이 있는지는 모르지만)

느린

뭐 이것은 어쩔 수 없습니다만, numpy, numba, pypy 등 고속화할 수 있는 수법이나, 선인의 지혜가 가득 있으므로, 아무래도 늦지 않는 문제는 거의 없기 때문에 어떻게 됩니다.

개인 결론, 의견

프로그래밍 초보자가 경쟁 프로를 시작하는 언어는 C++과 파이썬의 두 가지 선택이라면 나는 파이썬을 추론한다.

미래를 향해

다음의 목표는 파랑입니다만, 과연 잠시 시간이 걸릴 것 같기 때문에 기장에 노력합니다.