BaaaaaaaarkingDog
코딩, 해킹
[Codeforces] Round #583

https://codeforces.com/contest/1214

 

A - Optimal Currency Exchange (Code)

 

설명이 너무 이해하기 어렵게 써져있어서 짜증났습니다. 결론적으로 그냥 $d, 5e$로 $n$을 잘 나누어가져 최대한 남는 것이 적도록 하는 문제이고 $O(n)$에 해결이 가능합니다.

 

B - Badges (Code)

 

얘도 좀 난해하게 써져있었는데 그냥 $O(n)$을 다 해보면 됩니다. B가 더 쉬운데 왜 A와 B의 순서가 이렇게 되어있는지 이해가 안갔습니다.

 

C - Bad Sequence (Code)

 

그냥 가장 오른쪽의 ( 하나를 제일 앞으로 옮기는게 최적임을 쉽게 알 수 있고, 이에 따라 코드를 작성하면 됩니다. 더 나아가 생각해보면 +1 -1을 붙이는 방식으로 계산할 때 -1 밑으로 가지 않고 전체의 합이 0이 되면 무조건 가능함도 알 수 있습니다.

 

E - Petya and Construction Set (Code)

 

거리가 먼 순으로 정렬해놓고 일단 홀수들을 일자로 늘어놓은 뒤 짝수를 어떻게 연결하면 될지를 고민해보면 답을 알아낼 수 있을 것입니다.

 

D 맞왜틀ㅡㅡ

 

'알고리즘 > Codeforces' 카테고리의 다른 글

[Codeforces] Round #584  (0) 2019.09.29
[Codeforces] Round #583  (0) 2019.09.19
[Codeforces] Manthan, Codefest 19  (0) 2019.09.19
[Codeforces] Codeforces Global Round 4  (0) 2019.07.23
[Codeforces] Round #569 Div. 1  (0) 2019.06.26
[Codeforces] Round #562 Div. 1  (0) 2019.06.20
[Codeforces] Round #556 Div. 1  (0) 2019.06.20
  Comments
댓글 쓰기
[Codeforces] Manthan, Codefest 19

https://codeforces.com/contest/1208

 

A - XORinacci (Code)

 

주기가 3인게 자명합니다.

 

B - Uniqueness (Code)

 

모든 l, r에 대해 다 해보면 되는데 l을 고정하고 r을 오른쪽으로 늘려가면서 누적시키는 방법으로 해야 $O(N^2)$에 해결할 수 있습니다.

 

C - Magic Grid (Code)

 

그다지 엄밀한 증명 없이 그냥 4*4 단위 칸을 쓰면 되겠다고 생각헀고 실제로 맞았습니다. 왜 맞는지는 아직도 잘 모르겠네요ㅎㅎ..

 

D - Restore Permutation (Code)

 

Segment Tree를 이용해 뒤에서부터 현재 x라는 수가 왔을 때 $s_i$가 일치하는 x를 이진탐색으로 찾으면 됩니다.

 

E - Let Them Slide (Code)

 

segment tree를 하나 들고다니면서 각 가로에 대해 최댓값이 움직일 수 있는 부분은 그냥 업데이트 시키고, 나머지 부분은 따로 처리를 해주고 뭐 그런식으로 경우를 잘 나눠서 해결하면 됩니다. 구현에서 실수를 하기 쉬웠습니다.

 

'알고리즘 > Codeforces' 카테고리의 다른 글

[Codeforces] Round #584  (0) 2019.09.29
[Codeforces] Round #583  (0) 2019.09.19
[Codeforces] Manthan, Codefest 19  (0) 2019.09.19
[Codeforces] Codeforces Global Round 4  (0) 2019.07.23
[Codeforces] Round #569 Div. 1  (0) 2019.06.26
[Codeforces] Round #562 Div. 1  (0) 2019.06.20
[Codeforces] Round #556 Div. 1  (0) 2019.06.20
  Comments
댓글 쓰기
[BOJ] 10464번: XOR

https://www.acmicpc.net/problem/10464

 

이런 류의 문제는 늘 참 뭔가 까다롭지만, 재귀적으로 잘 해결하면 됩니다.

 

예를 들어 1부터 10110101(2) 까지의 XOR값을 구하고 싶다고 할 때, 1부터 1111111(2)까지의 XOR값은 0이니 떼버리고 뭐 그런식으로 구했습니다.

 

https://github.com/blisstoner/BOJ/blob/master/10464.cpp

'알고리즘 > BOJ' 카테고리의 다른 글

[BOJ] 15293번: Knapsack Cryptosystem  (0) 2019.10.21
[BOJ] 15896번: &+ +&  (0) 2019.10.15
[BOJ] 17513번: Hilbert's Hotel  (0) 2019.10.15
[BOJ] 10464번: XOR  (0) 2019.09.12
[BOJ] 16685번: XOR 포커  (0) 2019.09.12
[BOJ] 11191번: XOR Maximization  (0) 2019.09.12
[BOJ] 4798번: Dirichlet's Theorem  (0) 2019.09.11
  Comments
댓글 쓰기