알고리즘 문풀(61)
-
BOJ 14859 세 쌍 서로수
문제 링크 14859번: 세 쌍 서로소 크기가 n인 수열 a1, a2, ..., an이 주어졌을 때, 1 ≤ i < j < k ≤ n 이면서, GCD(ai, aj, ak) = 1인 세 쌍 (i, j, k)의 개수를 구하는 프로그램을 작성하시오. 여기서 GCD는 최대공약수를 의미한다. www.acmicpc.net MAX=106\text{MAX} = 10^6MAX=106 범위의 수가 nnn 개 주어져 있고, 이 중에서 gcd\gcdgcd가 1인 triplet의 개수를 구하는 문제이다. 썸네일 스포 방지를 위한 텍스트입니다. 썸네일 스포 방지를 위한 텍스트입니다. 썸네일 스포 방지를 위한 텍스트입니다. 썸네일 스포 방지를 위한 텍스트입니다. 썸네일 스포 방지를 위한 텍스트입니다. 썸네일 스포 방지를 위한 텍스트입니다. 썸네일 ..
2019.08.17 -
[PS 켠왕 #1] BOJ 10641 The J-th Number
PS에 적당한 시간을 할애하기 위해서, 트위치에서 어려운 문제를 푸는 방송을 시작했다. 방송을 할 때마다 Write-up을 써볼 생각이다. 처음으로 푼 문제는 JAG Spring Contest 2013 I번으로 출제된 The J-th Number이다. 켠왕을 걸 정도로 어려운 문제는 아니었던 것 같지만 11번 틀렸다(...) BOJ 문제 요약 NNN개의 빈 배열이 있는데, 여기에 MMM개의 삽입 쿼리를 먼저 수행한 뒤 QQQ개의 구간 쿼리에 답해야 한다. 삽입 쿼리 : aaa번 이상 bbb번 이하의 배열에 원소 vvv를 삽입한다. 구간 쿼리 : sss번 이상 eee번 이하의 모든 배열에서 jjj번째로 작은 수를 출력한다. 이 수가 존재함은 보장된다. 스포방지선 풀이 1. ..
2019.08.15 -
BOJ 16143 선형대수와 응용
HOLICS 18 문제로 출제된 문제다. 진짜 선형대수 문제인 줄 알고 처박아놨다가 쉬운 문제인 걸 알았다... 문제 링크 스포방지선 썸네일 스포 방지를 위한 텍스트입니다.썸네일 스포 방지를 위한 텍스트입니다.썸네일 스포 방지를 위한 텍스트입니다.썸네일 스포 방지를 위한 텍스트입니다.썸네일 스포 방지를 위한 텍스트입니다.썸네일 스포 방지를 위한 텍스트입니다.썸네일 스포 방지를 위한 텍스트입니다.썸네일 스포 방지를 위한 텍스트입니다.썸네일 스포 방지를 위한 텍스트입니다.썸네일 스포 방지를 위한 텍스트입니다.썸네일 스포 방지를 위한 텍스트입니다.썸네일 스포 방지를 위한 텍스트입니다.썸네일 스포 방지를 위한 텍스트입니다.썸네일 스포 방지를 위한 텍스트입니다.썸네일 스포 방지를 위한 텍스트입니다.썸네일 스포 방..
2019.03.15 -
HYEA cup H - Too Many Traps 풀이
문제 링크 공식 에디토리얼 1년 가까이 틀려 있었던 문제다. 에디토리얼을 읽고도 이해를 못해서... 내가 이해한 대로 다시 써보려고 한다. 문제 요약 수직선상에 MMM개의 이불이 있고, 혜아는 원점 000에 서 있다.혜아는 NNN개의 신발을 가지고 있는데, iii번째 신발을 사용하면 AiA_{i}Ai만큼 +방향으로 갈 수 있다.M<NM < NM<N이 성립할 때, 모든 신발을 한 번씩만 사용하여 이불에 닿지 않고 A1+A2+⋯ANA_{1} + A_{2} + \cdots A_{N}A1+A2+⋯AN으로 갈 수 있겠는가? 있다면 순열을 construct하고, 아니면 -1. 제한 :1≤M<N≤1051 \le M < N \le 10^{5}1≤M<N≤105, 1≤Ai≤1091 \le A_{i} \le 10^{9}1≤Ai≤109, 이불의 위치 \(X_{j} \le 10^{14}..
2019.03.11 -
190105 재활 프로젝트 : Yandex.algorithm QR 후기
A B C D E F CodeForces Gym일부러 집중력이 떨어진 상태에서 짧은 대회를 쳐봤다. 어떤 실수를 얼마나 하는지 보려고..템플릿도 안 켜고, 중간에 엎드려 잘 뻔하고... 결국 집중력 저하로 1시간만에 던졌다.DE는 풀 수 있을 것 같은데, PS를 크게 쉰 이후로 자료구조 구현에 굉장히 오랜 시간이 걸리고 있다. 보완이 필요하다. 풀이는 D E 푼 뒤에 올리는 걸로 하자.
2019.01.05 -
190101 재활 프로젝트 : shake! 2018 후기
문제 링크 (BOJ) 풀이 슬라이드 (slideshare) 이제는 습관처럼 집을 나가는 PS 실력을 되살리기 위해 쉬운 대회를 풀어보기로 했다. 6시간 (밥 1시간) 을 세팅했고 결과는 7 / 8. B는 디스크립션을 오독해서 전혀 다른 문제를 풀어버렸다😡 A B C D E F G H A < C = F = H < B < E < G < D 난이도는 평이한 수준. 괜찮은 문제들 + 좋은 문제 (D) 로 구성되어 있어서 퀄리티도 나쁘지 않다. 다만 돚거해온 훔친 문제 (E, H)가 2개나 들어와 있다는 게 흠이라면 흠. 문제 푸는 감을 다시 살리기에 굉장히 좋은 셋이다. 빡센 자료구조 문제 / 케이스 분석을 해보고 싶었는데 그런 문제는 안 나왔더라... 일단 B를 제외하고 모든 문제를 큰 무리 없이 푼 건 좋았..
2019.01.01