AtCoder 갈색 (400)이 될 때까지 한 일

안녕하세요, yukad2입니다.
이 기사에서는 내가 AtCoder에서 Rating : 400이 될 때까지 공부 한 것을 요약합니다.

0. 첫 콘테스트 전



중학생 때 C++ 게임 프로그래밍에 도전했지만 if, for가 이해할 수 있는 정도의 지식이었습니다.
대학 1년에 학습한 Ruby가 (C에 비해) 매우 쓰기 쉬웠기 때문에, 프로그래밍의 연습도 겸해 경기 프로그래밍을 시작했습니다.
1. chokudai 님의 기사 을 읽고, 취활까지(2년 이내)에 초록~물색을 목표로 했습니다.
2. 코드 테스트에서 입출력을 확인했습니다.
3. 과거 질문을 여러 번 풀었습니다.

1. 콘테스트



첫 번째
3완 Perf:681
두 번째
2 완료 Perf:244
세 번째
2완 Perf:196

전혀 할 수 없다고 초조함을 느끼고 과거 질문으로 알고리즘과 데이터 구조의 기초를 공부했습니다.

2. 공부한 것



for 2중 3중


h = 3; w = 3;
arr=[[1, 2, 3], [4, 5, 6], [7, 8, 9]]
h.times{|i|
    w.times{|j|
        puts arr[i][j]
    }
}

공부한 것은 아니지만 필수이므로. Ruby이므로 Array#each 쪽을 자주 사용하고 있었습니다.

bit 전체 탐색



Ruby에서는 Array#combination를 사용하여 구현했습니다. 벤치 마크는 가지고 있지 않지만 ABC의 300 점 상당하면 거기까지 시간이 힘든 문제는 없다고 생각하기 때문에 ...
n = 5
arr=[1, 2, 3, 4, 5]
(n+1).times{|i|
     arr.combination(i){|item|
        p item
    }
}


최대 공약수(GCD)


a = 3
b = 6
p 3.gcd(6)

최대 공약수를 구하는 메소드가 표준에 있습니다. (2020/11/21 추가)

약수 열거


n = 30
ans = []
(1..Math.sqrt(n).to_i).each{|i|
    if n % i == 0
        ans << i
        ans << n / i
    end
}
p ans.uniq.sort

$O(log(n))$
위의 코드는 $\sqrt n$가 정수인 경우는 $\sqrt n$가 중복되므로 주의가 필요합니다. ( uniq 에서 중복을 지워 출력)

Hash (연상 배열)


all = Hash.new
all["hoge"] = 1
all["huga"] = 3
p all

몰랐기 때문에 전혀 싸울 수 없었던 문제가있었습니다.

기타 과거 질문



6문제가 되고 나서의 C문제를 확실히 풀 수 있도록 연습했습니다.
과거 질문을 풀 때 AtCoderProblems를 참고로 위에서 차례로 풀었습니다.
AtCoder Problems

3. 결과



9번째 콘테스트에서 갈색이 되었습니다. 사이의 공백은 대학과 아르바이트가 너무 바빠서 거의 문제를 해결하지 못했습니다.
다음은 초록 목표로 감바리마스!

좋은 웹페이지 즐겨찾기