소심야채

https://codeforces.com/contest/1775/problem/B Problem - B - Codeforces codeforces.com 위 문제를 풀다 새로 알게 된 주의사항이 있어 포스팅하게 되었습니다. [개요] 1. 해당 문제는 어느 코포문제와 마찬가지로 테스트케이스로 이루어진 문제입니다. 2. 문제에 대한 풀이로 O(k) 풀이를 작성하였습니다. "k in all tests does not exceed 10^5" 자신있게 제출해본 결과 [문제의 코드] 더보기 #include using namespace std; const int MAX_N = 2e5 + 5; int n, k, cnt[MAX_N]; void solve() { memset(cnt, 0, sizeof(cnt)); cin ..

https://codeforces.com/contest/1768/problem/D Problem - D - Codeforces codeforces.com 문제풀이 n개의 중복되지 않는 정수가 주어질때 정확히 한 개의 inversion이 존재하는 순열 만드는 (두 원소를 스왑)최소횟수 구하는 문제이다. 여기서 inversion이란 두 인덱스 i,j와 순열 p가 주어졌을때 $$i p_{j}$$ 인 조건을 만족하는 경우를 뜻한다. 1. n개의 원소로 구성된 순열중에서 inversion이 1개로 구성된 순열의 경우의 수는 n-1이다. inversion이 존재하지 않는 순열은 (1) < (2) < ... < (n-1) < (n) 인 경우로 유일하다. 위 순열에서 inversion이 한 번만 나타나려면 (2,1) ..