2024. 2. 28. 03:31ㆍCompetitive Programming/Codeforces
처음으로 Codeforces 후기를 남긴다. 그린을 넘어 민트로 향한 지 꽤 됐는데 지금에서야 후기를 남기는 이유는 D번 때문이다.
solved.ac 디스코드에서 소위 답 맞춰보기를 하는데 나만 풀이방식이 달라서 핵 당해서 터질까 염려되었는데, 결국에는 옳다는 게 증명되는 바람에 한 숨 돌릴 수 있었던 것.

5문제, 227분의 페널티로 전체 2572등으로 마무리하였다. 아직 오픈핵 진행 중이라 레이팅이나 등수가 변동할 수는 있겠는데, 그 때 맞춰서 업데이트 해 보도록 하겠다.

UPD) 참가 대상 중 1827등을 거두었다.

반성할 점
B를 풀 때 머리로 풀려다가 WA 하나를 적립한 점. 심지어 바로 옆에 종이도 있었는데 천천히 머리를 식힐 생각을 하지 않고 무작정 이러면 되겠지 식으로 풀어서 결과적으로 시간도 낭비하고 틀리지 않았어야 할 곳에서 틀렸다.
그리고 E를 짤 때 차분하지 않은 상태에서 짠 것. 평정심 없이 급하게 짜다 보니 예제도 안 나오는 상황에 맞닥트렸고, 심지어 변수 이름마저 잘못 쓴 케이스도 잡지 못한 채 한참동안 헤메었다.
마지막으로 D를 풀 때 증명되지 않은 풀이를 마구잡이로 사용한 것. 옳은 풀이였어서 다행이지, 그렇지 않았다면 맞왜틀을 외치며 페널티를 적립하거나 천운을 타고 통과했더라도 핵당해서 틀리게 되었을 것이다.
조금만 더 잘 했으면 블루까지 더 빠르게 갈 수 있었는데, 오히려 블루 가기 전에 이런 반성할 점을 발견한 것만으로도 충분히 좋은 성과라고 생각한다. 게다가 그러면서 레이팅까지 챙겼으니 금상첨화라.
0:01 A AC
def solve():
N = int(input())
print(sum(map(lambda x: abs(int(x)),input().split())))
for _ in range(int(input())): solve()
그냥 음수를 한 쪽에 몰아넣은 다음에 그 쪽 부분만 부호를 반전시켜 주면 최대로 만들 수 있다. 그냥 모든 원소에 절댓값 씌워서 더해 주면 바로 맞을 수 있다.
0:20 B AC (+1)
def solve():
N = int(input())
l = list(map(int,input().split()))
a = [0,0]
for i in l:
if i%3 == 1: a[0] += 1
elif i%3 == 2: a[1] += 1
if a[0]%3 == a[1]%3: return 0
if a[0] == 0: return a[1]%3
if a[1] == 0: return min(1,a[0]%3)
else: return 1
for _ in range(int(input())): print(solve())
3의 배수는 존재 유무가 답에 전혀 영향을 끼치지 않는다. 3으로 나눈 나머지만 관리하여도 충분하고, 1의 수와 2의 수가 답에 직접적인 영향을 미친다.
1과 2가 같은 수만큼 존재할 경우 1+2로 상쇄된다. 그렇지 않을 경우 1과 2를 3으로 나눈 나머지로 관리해 줘야 하는데, 각 케이스마다 종이에 써 가면서 합이 3의 배수가 되도록 몇 번의 연산으로 가능한지 체크해 주면 된다.
2가 두 개일 때만 1이 3N개 있느냐 아예 없느냐로 답이 갈리는데, 이는 1이 3N개 있으면 1을 하나 지워서 2 두 개를 1+2로 곧 3의 배수로 만들 수 있기 때문이다. 케이스워크 잘 해 주면 된다.
0:27 C AC
from sys import stdin
input = stdin.readline
def solve():
a,b,l = map(int,input().split())
ans = set()
for i in range(20):
for j in range(20):
if l%((a**i)*(b**j)) == 0: ans.add((a**i)*(b**j))
print(len(ans))
for _ in range(int(input())): solve()
정말 이래도 되나 싶은 브루트 포스 문제. 시간제한이 5초라는 걸 못 보고 이런저런 정수론적 지식을 이용하려고 했으나,
1:29 D AC (+2)
from math import gcd
from sys import stdin
input = stdin.readline
def solve():
N = int(input())
l = list(map(int,input().split()))
if N == 2:
print('YES' if l[0]!=l[1] else 'NO')
else:
g = gcd(*l)
l = [i//g for i in l]
cnt = sum(1 for i in l if i==1)
if cnt > 1: print('NO'); return
else: print('YES')
for _ in range(int(input())): solve()
이게 대망의 그 문제다. 사풀로 뚫었다고 생각했지만 실제로는 정해였던 풀이. 반성은 반성 나름이고 맞힌 건 맞힌 거다.
그 다음 배열을 순회하며 1의 갯수를 체크한다. 만약 1이 2개 이상이면 앞에 어떤 수가 와도 반드시 0이 되는
왜 그럴까? 배열이
그렇지 않다면, 곧 1이 0개라면 우선
따라서 수열을 적당히 재배열해
1:00 E AC
from bisect import bisect_left
from sys import stdin
input = stdin.readline
def solve():
N = int(input()); answer = []
array = list(map(int,input().split()))
prefix = [0]
for i in range(N): prefix.append(prefix[-1]+array[i])
for _ in range(int(input())):
l,u = map(int,input().split());
left = l
r = N
while r-l > 1:
mid = (l+r)//2
t = prefix[mid]-prefix[left-1]-u
if t < 0: l = mid
elif t > 0: r = mid
else: answer.append(mid); break
else:
ll = prefix[l]-prefix[left-1]-u
rr = prefix[r]-prefix[left-1]-u
if abs(ll)<abs(rr): answer.append(l)
else: answer.append(r)
print(*answer)
for _ in range(int(input())): solve()
문제에서 쿼리마다 구해 줘야 하는 값은 다음 식이 최소가 되게 하는
이 값은
왼쪽 끝이 고정되어 있으니 이분탐색을 생각해 볼 만 하다. 부분합이 정확하게
'Competitive Programming > Codeforces' 카테고리의 다른 글
Codeforces Round 937 (Div. 4) (0) | 2024.03.29 |
---|---|
Codeforces Round 930 (Div. 2) (0) | 2024.03.01 |