(2020년 10월 4일에 작성한 글입니다.)
Dashboard - Codeforces Round #674 (Div. 3) - Codeforces
codeforces.com
A.
적당히 관계식 찾으면 되는 문제
int main()
{
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int T;
int N, X;
int i;
cin >> T;
while (T--) {
cin >> N >> X;
if (N <= 2) {
cout << 1 << '\n';
continue;
}
cout << (N - 2 + X - 1) / X + 1 << '\n';
}
return 0;
}
B.
이걸 한 번에 못 맞췄다는게 좀 아쉽다.
a b
c d
이렇게 네 개의 숫자가 있을때,
b == c인 타일이 하나라도 있으면 된다. 끝.
그 하나의 타일을 쭉 붙인다고 하면
a b a b a b a b
c d c d c d c d
a b a b a b a b
c d c d c d c d
a b a b a b a b
c d c d c d c d
a b a b a b a b
c d c d c d c d
가운데의 a d a d a d a d 라인을 기준으로
a는 a끼리, d는 d끼리 매치되기 때문에 대칭이 성립하고,
b, c끼리 위치가 대칭되기 때문에 b == c여야 한다.
이걸 한 번에 못 맞았다니 아쉽다.
int main()
{
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int T;
int N, M;
int a, b, c, d;
bool ans;
int i;
cin >> T;
while (T--) {
cin >> N >> M;
ans = false;
for (i = 0; i < N; i++) {
cin >> a >> b >> c >> d;
if (b == c) {
ans = true;
}
}
if (M % 2 == 1 || ans == false) {
cout << "NO" << '\n';
}
else {
cout << "YES" << '\n';
}
}
return 0;
}
C.
이 문제의 포인트는
'Your task is to find the minimum number of moves required to obtain the array with the sum at least n'
"at least"가 포인트다!!!!
딱 n이 될 때를 찾을 필요가 없다...
그래서 나는
정수 k에 대해 (1 -> k까지 되는 횟수) + (k를 복사했을 때 그 합이 n이 되는 횟수)를 구했고
이것의 최소를 구해서 ans에 저장해나갔다.
근데 ans가 (k - 1)보다 작다면
더 이상 확인을 할 필요가 없다.
k 이상의 수는, 1 -> k가 되기 위한 횟수가, 지금 구한 ans보다 크니까
앞으로 절대 ans보다 작은 값이 나올 수 없기 때문.
이렇게 하면 된다.
int main()
{
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int T;
int N;
int cnt;
int i;
cin >> T;
while (T--) {
cin >> N;
cnt = int_inf;
for (i = 1; i <= N && cnt > i - 1; i++) {
cnt = min(cnt, (i - 1) + (N - 1) / i);
}
cout << cnt << '\n';
}
return 0;
}
E.
가위바위보.
이기는 maximum 횟수는
이길 수 있는 모든 상황을 다 더하면 되니까 쉬운데
minimum이 문제였다.
이길 수 있도록 하는 자원을, 비겨서 없애는거랑 져서 없애는 두 가지 방법이 있는데
이거 선후관계를 어떻게 해야할 지 모르겠어서
그냥 다 확인해봤다.
(3 * 2)! 로 720가지이기 때문에 전체 경우의 수가 그렇게 큰 것도 아니었어서...
그래서 permutation 돌려서 풀었다ㅎㅎ
int getWin(vector<vector<int>> arr)
{
int ret = 0;
int min_;
int i;
for (i = 0; i < 3; i++) {
ret += min(arr[0][i], arr[1][(i + 1) % 3]);
}
return ret;
}
int minWin(vector<int> turn, vector<vector<int>> arr)
{
//0: 바위 비김, 1: 가위 비김, 2: 보 비김
//3: 바위 짐, 4: 가위 짐, 5: 보 짐
int temp;
int i, k;
for (i = 0; i < 6; i++) {
if (0 <= turn[i] && turn[i] <= 2) {
k = turn[i];
temp = min(arr[0][k], arr[1][k]);
arr[0][k] -= temp;
arr[1][k] -= temp;
}
else {
k = turn[i] - 3;
temp = min(arr[0][k], arr[1][(k + 2) % 3]);
arr[0][k] -= temp;
arr[1][(k + 2) % 3] -= temp;
}
}
return getWin(arr);
}
int main()
{
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int N;
vector<vector<int>> init(2, vector<int>(3));
int min_cnt, temp;
int i, j;
cin >> N;
for (i = 0; i < 2; i++) {
for (j = 0; j < 3; j++) {
cin >> init[i][j];
}
}
min_cnt = int_inf;
vector<int> turn = { 0, 1, 2, 3, 4, 5 };
do {
temp = minWin(turn, init);
min_cnt = min(min_cnt, temp);
} while (next_permutation(turn.begin(), turn.end()));
cout << min_cnt << ' ' << getWin(init) << '\n';
return 0;
}