[뒤돌아보기] 처음!경업자로부터 한 달의 시간을 얻다

저는 RNS입니다.
10월 10일에 처음으로 프로 경연에 참가했습니다.
처음에는 시간 제한이었어요.
케아리 스미스, 폭풍우인 줄 몰랐어.
똑똑히 기억하다
세 번째 경기까지 비슷했던 것 같아요.
벽에 엄청 부딪혔어요.
벌써 한 달이 지났네요.
드디어 최초의 색깔로 물들었습니다.
최근 4, 5, 6회 시합은 나로 하여금 개선과 학습의 효과를 실감하게 했다
지금 300분 이하의 문제는 30초 정도면 해결이 됩니다.
제 목표는 2021년 3월까지 연한 파란색이 되는 거예요.
언어는 골랑에서만 할 수 있을 것 같아요.
이번 기사에서
뭘 건드렸는지 알아요?
어떻게 개선되었는가(주로 Golang 상황)
나는 남고 싶다
프로 경기에 처음 출전하시는 분들에게 참고가 되었으면 좋겠습니다.

주의: 나의 수준감

나는 대학에서 정보공학을 전공한다
지금 엔지니어 하고 있어요.
따라서 수학, 도표 이론, 프로그램 설계에 대해 결코 낯설지 않다

AtCoder 소개

https://atcoder.jp/users/rns

이제 본론.
우선 지금까지의 문제에서 나온 거예요.
제가 알고 있던 지식이 이거였어요.

O(n)의 뜻

2분 탐색

도표 이론에서의 너비 우선, 깊이 우선, X

유클리드의 상호제곱법

가장 빠른 소수 판정

bit 연산

이것에 관해서는 나는 언급하지 않겠다
저는 뭐든지 다 필요할 것 같아요.
여기서부터는 새로 배운 것들의 일람과 해설입니다.

모르면서 풀 수 없는 벽

모듈 꼴찌

프리미엄 케어

Union-Find

next_permutation

익숙하지 않으면 어려운 벽

동적 기획법

알고 보면 편해요.

Segment Tree

제곱분할

모듈 역수

일단 깜짝 놀란 건 이거예요.
mod의 세계에서 나눗셈,
어떻게

7 / 2 (mod 3)

나 이거 몰라.3.5 (mod 3)도 7 mod 3 / 2 = 0.5mod의 세계에서도 너무 적어요.
왜 그런지 모르겠어요.
mod의 나눗셈은 역원의 곱셈으로 처리한다
곰곰이 생각해 보면, 줄을 서 있는 세계에서도 거슬러 올라가는 느낌이 든다.
이 역원은 모듈 꼴찌입니다.
계산하고 싶은 사람은 Google로 오세요.
Combination과mod가 얽힐 때도 필요해요.nCr = n!(n-r)!/r!//mod의 세계에서!필요에 따라 나누다

넘쳐흐르다

골랑에서 사연입니다.
Golang으로 Pow와 log를 보통 계산하면...
math 라이브러리 사용
math 라이브러리의 출력은 flat64 형식
따라서 마지막으로 이 라이브러리를 출력합니다
int로 돌아가려면 넘침이 있습니다

int(math.Pow(10, 17)) // 100000000000000000
int(math.Pow(10, 18)) // 1000000000000000000
int(math.Pow(10, 19)) // -9223372036854775808

간단한 해결 방법
math 라이브러리의 주요 동작은
직접 설치하세요.
거의 뭐 Pow log fact죠.
또한 사전 감법, 제법 등은 당연히 필요하다
평균 샘플

(a + b) / 2 // x
a + (b - a) / 2 // o

Union-Find

나는 처음으로 죽어도 구해주지 않는 것을 보았다
요소를 분리하여 처리할 때 매우 편리하다
대체로 필요한 것이기 때문에 필수적이다
보글보글 나오니까 이름만 소개하는 정도.

next_permutation

가끔 열거하고 싶다nPr이 함수는 C++의 내장 함수입니다.
매개 변수로 정렬된 사전 순서에 따라 다음 정렬을 되돌려줍니다
ex. next_permutation(123) -> 132
당일 0부터 설치하면 시간이 없어요.
미리 준비해라

동적 기획법

저는 주로 고속화를 위해서라고 생각해요.
점차적 n항의 그림을 구하다
An = An-1 + b
이때 (여러 번 계산해야 할 수 있음) An-1
미리 계산한 결과
An 빠른 탐색
그 자체가 쉬워요.
언제 쓸 수 있는지, 어떻게 입식할 수 있는지가 매우 중요하다
설치 방법은 대략 두 가지가 있다
비고화 귀속과 for문
내 수준에 무슨 차이가 있는지 모르겠다
아무래도 이 문제는 이쪽이 더 쉽게 실시할 수 있을 것 같아요.
이런 느낌.

Segment Tree 및 제곱 분할

이것은 수조 원소가 자주 사용하는 고속화 기술이다
두 요소 모두 n 으로 나누어야 한다
그 구간에 결과를 캐시하는 인상을 주다
꼭 필요한 건 아닌 것 같은데 살살해주세요

Golang 환경 개선

지금부터 골랑에서 프로 경기를 진행하도록 하겠습니다.
개선된 거 썼어요.

Golang은 기술량이 많아요.

Golang은 기본 for 및 if로 기술합니다.
수조의 최대 값을 계산하려면 3줄이 필요하다

max := 0
for i := 0; i < n; i++ {
    if arr[i] > max { max = arr[i] }
}

그래서 통용되는 방법은요.
사전 준비가 필요하다
왜냐하면 퀴즈는 시간과의 경기니까요.
저는 임의가 아니라 필수라고 생각해요.

파일 변경 사항 감지 및 자동 실행

realize라는 프로그램 라이브러리 사용
파일을 저장할 때마다 gorun이 실행 중입니다
이것도 필수라고 생각해요.
테두리 상황의 수정을 수정한 후에 집행하다
여러 번 반복되니까 (나만 있을 수도 있겠지 웃음)

Local에서만 print 함수 준비

func d(r ...interface{}) {
    if os.Getenv("RNS") == "true" {
        fmt.Println(r...)
    }
}

디버그 함수를 제출하기 전에 삭제
지우는 것을 잊고 처벌을 받다
환경 변수를 설정하여 로컬 값을 결정합니다.
만약 AtCoder 운영자가 이 보도를 읽었다면
실행 환경에서 이 환경 변수를 설정하지 마십시오.

끝맺다

지금까지 이달이었습니다.
알고 또 방법을 강구하는 일이다
빨리 연한 파란색이 되기 위해서.
하루에 500~600점 문제 해결
같은 색인 분들이 팔로우 해주시면 좋을 것 같아요.
만약 시합 전문 선수라면 나는 회답할 것이다