A - Little Artem
Problem - A - Codeforces
codeforces.com
\(n \times m\) 크기의 판이 있다. 각 칸에는 흰색이나 검은색으로 색칠 할 수 있다.
검은색으로 칠한 칸 중에 인접한 칸 중 하나가 적어도 흰색인 칸의 개수를 \(B\),
흰색으로 칠한 칸 중에 인접한 칸 중 하나가 적어도 검은색인 칸의 개수를 \(W\) 라고 하자.
이 때 \(B=W+1\)을 만족하는 색칠을 아무거나 하나 출력해야 한다.
맨 왼쪽 모서리 칸을 흰색으로 칠하고, 나머지를 전부 검은색으로 칠하면 \(B=2, W=1\)로 위 조건을 만족한다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
|
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
ll gcd(ll a, ll b) { for (; b; a %= b, swap(a, b)); return a; }
int main()
{
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
int t; cin >> t;
while (t--)
{
int n, m; cin >> n >> m;
for (int i = 0; i < n; i++)
{
for (int j = 0; j < m; j++)
{
if (i == 0 && j == 0) cout << "W";
else cout << "B";
}
cout << '\n';
}
}
}
|
B - Kind Anton
Problem - B - Codeforces
codeforces.com
길이 \(n\)의 수열 \(a\)와 \(b\)가 주어진다. \(a\)는 집합 \(\{-1,0,1\}\)의 원소로만 구성되어있다.
이 수열에 다음과 같은 연산을 원하는 만큼 할 수 있다.
1. \(1 \le i \lt j \le n\)을 만족하는 두 인덱스 \((i, j)\)를 고른다.
2. \(a_j\)에 \(a_i\)를 더한다.
이 때 수열 \(a\)가 \(b\)와 같도록 할 수 있는지 알아내야 한다.
모든 \(i\) 에 대하여, (\(1 \le i \le n\))
\(a_i = b_i\)라면, 연산을 할 필요가 없다.
\(a_i < b_i\)라면, \(a_j = 1\)인 \(j\)가 존재해야 한다. \((j \lt i)\)
\(a_i > b_i\)라면, \(a_j = -1\)인 \(j\)가 존재해야 한다. \((j \lt i)\)
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
|
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
ll gcd(ll a, ll b) { for (; b; a %= b, swap(a, b)); return a; }
int n;
int a[100001];
int b[100001];
int main()
{
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
int t; cin >> t;
while (t--)
{
cin >> n;
for (int i = 0; i < n; i++) cin >> a[i];
for (int i = 0; i < n; i++) cin >> b[i];
int m1 = 0, p1 = 0;
for (int i = 0; i < n; i++)
{
if (a[i] == 1) p1++;
if (a[i] == -1) m1++;
}
bool ans = true;
for (int i = n - 1; i >= 0; i--)
{
if (a[i] == 1) p1--;
if (a[i] == -1) m1--;
if (a[i] == b[i]) continue;
if (a[i] > b[i])
{
if (m1 <= 0)
{
ans = false;
break;
}
}
else
{
if (p1 <= 0)
{
ans = false;
break;
}
}
}
if (ans) cout << "YES\n";
else cout << "NO\n";
}
}
|
C - Eugene and an array
Problem - C - Codeforces
codeforces.com
어떤 수열의 원소가 1개 이상인 subarray중에 원소의 합이 0인 것이 없다면 이 수열을 좋다고 하자.
수열 \(a\)가 주어졌을 때, 이 수열의 subarray중에 좋은 것들의 개수를 알아내야 한다.
\(psum[x] = \) \(a\)의 앞에서부터 \(x\)개 원소의 합으로 정의하자.
어떤 인덱스 \(i\)에서 \(psum[i] = psum[j]\) 인 \(j(\lt i)\)가 존재한다면, 수열 \(\{a_{j+1}, a_{j+2}, \cdots, a_i\}\) 의 모든 원소의 합이 0이라는 사실을 알 수 있다.
위 식을 만족하는 \(j\)중 가장 큰 값을 \(left_i\)라고 하자.
그러면 \(max_{j \lt i} (left_j) \ge k\)를 만족하는 \(k\)에 대해서,
\(a\)의 subarray \([k, i]\)에는 모든 원소의 합이 0인 subarray가 존재하게 된다.
따라서 답은 \(i - (max_{j \lt i} (left_j)+1)\)의 합이다. \((1 \le i \le n)\)
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
|
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
ll gcd(ll a, ll b) { for (; b; a %= b, swap(a, b)); return a; }
int n;
ll a[200001];
ll psum[200001];
map<ll, ll> mp;
int main()
{
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
cin >> n;
for (int i = 1; i <= n; i++)
{
cin >> a[i];
psum[i] = a[i] + psum[i - 1];
}
ll ans = 0;
ll left = -1;
mp[0] = 0;
for (int i = 1; i <= n; i++)
{
if (mp.count(psum[i]))
{
left = max(left, mp[psum[i]]);
}
mp[psum[i]] = i;
ans += i - (left + 1);
}
cout << ans;
}
|
D - Challenges in school №41
Problem - D - Codeforces
codeforces.com
\(n\)명의 아이들이 한 줄로 서 있다.
모든 아이들은 왼쪽 또는 오른쪽을 바라보고 있는데, 서로를 바라보고 있는 두 아이들은 동시에 머리를 돌려 반대 방향을 바라볼 수 있다.
또한 매 1초마다 최소 한 쌍의 아이들은 이 행동을 해야 한다.
\(k\)가 주어질 때, 정확히 \(k\)초 후에 서로를 바라보고 있는 두 아이들이 더 이상 없도록 할 수 있는지 알아내야 한다.
만약 가능하다면, 그 방법을 한 가지 출력해야 한다.
관찰을 잘 해보면, 많아도 \(n^2\)번의 동작 이후에는 모든 동작이 끝난다는 사실을 알 수 있다. (문제에도 주어진다)
또, 1초마다 할 수 있는 모든 행동을 한 번에 한다면 (이것을 한 단계라고 하자),
많아도 \(n\)초 후에는 모든 동작이 끝난다는 사실도 알 수 있다.
\(k\)가 가질 수 있는 최소값과 최대값을 먼저 구해보자.
1초마다 할 수 있는 모든 행동을 한 번에 했을 때, 단계의 수가 최소값일 것이고,
실제 일어나는 모든 행동의 수가 최대값일 것이다.
주어지는 \(k\)가 이 범위에서 벗어난다면 불가능하다.
그렇지 않다면, 최소값인 경우를 먼저 만든 다음 각 단계를 필요한 만큼 쪼개서 \(k\)가 되도록 채우면 된다.
한 단계에서 한번에 \(n_i\)번의 행동이 일어난다면, 1개씩 쪼개서 최대 \(n_i-1\)번의 행동을 추가할 수 있다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
|
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
ll gcd(ll a, ll b) { for (; b; a %= b, swap(a, b)); return a; }
ll n, k;
string s;
vector <vector <int> > ans;
int main()
{
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
cin >> n >> k;
cin >> s;
ll cnt = 0;
while (true)
{
vector <int> res;
for (int i = 1; i < s.size(); i++)
{
if (s[i - 1] == 'R' && s[i] == 'L')
res.push_back(i);
}
if (res.empty()) break;
ans.push_back(res);
cnt += res.size();
for (int i : res) swap(s[i - 1], s[i]);
}
if (k < ans.size() || k > cnt)
{
cout << -1;
return 0;
}
int sub = k - ans.size();
for (auto& vec : ans)
{
if (sub && vec.size() > 1)
{
int tmp = min(sub, (int)vec.size() - 1);
for (int i = 0; i < tmp; i++)
{
cout << "1 " << vec[i] << '\n';
}
cout << vec.size() - tmp << ' ';
for (int i = tmp; i < vec.size(); i++)
cout << vec[i] << ' ';
cout << '\n';
sub -= tmp;
}
else
{
cout << vec.size() << ' ';
for (auto i : vec)
cout << i << ' ';
cout << '\n';
}
}
}
|
E - Road to 1600
Problem - E - Codeforces
codeforces.com
\(N \times N\) 크기의 체스판에 주어지고, 룩과 퀸이 있다.
체스판에는 \(1\)부터 \(N^2\)까지의 수가 각각 쓰여 있다.
각 말은 다음의 규칙에 맞춰 이동한다.
1. \(1\)이 쓰여진 칸에서 시작한다.
2. 말이 아직 방문하지 않은 칸 중에서, 이동할 수 있는 칸 중 가장 작은 수가 쓰인 칸으로 이동한다.
3. 만약 아직 방문하지 않은 칸이 존재하지만 이동할 수 있는 칸이 없다면, 1 vun을 소모해서 방문하지 않은 칸 중 가장 작은 수가 쓰인 칸으로 이동한다.
4. 모든 칸이 방문되었으면 종료한다.
이 때, 퀸이 규칙에 맞춰 이동했을 때 사용하는 vun보다 룩이 사용하는 vun이 더 적도록 판을 만들어야 한다.
\(n \le 2\)인 경우는 불가능함이 자명하다.
예제를 보면 \(n=4\)인 경우의 답이 나와있는데, 이를 이용하여 \(n \gt 4\)인 경우도 적절히 답을 만들어 낼 수 있음을 알 수 있다.
남은건 \(n=3\)인 경우인데, \(9!\)가지 경우를 전부 검사해서 답을 알아낼 수 있다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
|
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
ll gcd(ll a, ll b) { for (; b; a %= b, swap(a, b)); return a; }
int ex[4][4] = {
{4,3,6,12},
{7,5,9,15},
{14,1,11,10},
{13,8,16,2}
};
int ans[501][501];
int main()
{
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
int n; cin >> n;
if (n < 3)
{
cout << -1;
return 0;
}
if (n == 3)
{
cout << "1 2 4\n";
cout << "5 3 8\n";
cout << "9 6 7\n";
return 0;
}
if (n == 4)
{
for (int i = 0; i < 4; i++)
{
for (int j = 0; j < 4; j++)
cout << ex[i][j] << ' ';
cout << '\n';
}
return 0;
}
int num = 1;
for (int i = 0; i < n; i++)
{
if (i % 2 == 0)
{
for (int j = 0; j < n - 4; j++)
{
ans[n - 1 - i][j] = num++;
}
}
else
{
for (int j = n - 5; j >= 0; j--)
{
ans[n - 1 - i][j] = num++;
}
}
}
for (int i = 0; i < n - 5; i++)
{
if (i % 2 == 0)
{
for (int j = n - 4; j < n; j++)
{
ans[i][j] = num++;
}
}
else
{
for (int j = n - 1; j >= n - 4; j--)
{
ans[i][j] = num++;
}
}
}
if (n % 2 == 1)
{
ans[n - 5][n - 4] = num++;
ans[n - 5][n - 1] = num++;
ans[n - 5][n - 2] = num++;
ans[n - 5][n - 3] = num++;
}
else
{
ans[n - 5][n - 1] = num++;
ans[n - 5][n - 4] = num++;
ans[n - 5][n - 2] = num++;
ans[n - 5][n - 3] = num++;
}
for (int i = 0; i < 4; i++) for (int j = 0; j < 4; j++)
{
ans[n - 4 + i][n - 4 + j] = num - 1 + ex[i][j];
}
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++) cout << ans[i][j] << ' ';
cout << '\n';
}
}
|
F - Kate and imperfection
Problem - F - Codeforces
codeforces.com
\(n\)개의 정수로 이루어진 집합 \(S = \{1,\cdots,n\}\)가 있다.
어떤 부분집합 \(M \subseteq S\)의 모든 순서쌍 \(a,b\)에 대해서 \(gcd(a,b)\)의 최대값을 imperfection이라고 하자.
이 때, 크기가 \(k\)인 부분집합에 대해 가장 작은 imperfection을 알아내야 한다. (\(k \in \{2,\cdots,n\}\))
집합안에 1과 소수만 포함되어 있다면 imperfection이 1이라는 사실은 쉽게 알 수 있다.
여기에서 수를 더 추가하여 imperfection이 1인 상태를 유지하는 것은 불가능하다. 그 수는 적어도 원래 들어있던 소수중 하나로는 나눠떨어질 것이기 때문이다.
같은 방식으로 imperfection이 증가하지 않도록 최대한 수를 추가하고, imperfection이 1 증가할 수밖에 없다면 가능한 한 작은 수를 추가하는 것을 반복하면, 다음과 같은 사실을 알 수 있다.
수 \(x\)가 추가 되었을 때, imperfection은 자기 자신을 제외한 \(x\)의 가장 큰 약수이다.
따라서 \(1\)부터 \(n\)까지 모든 수가 추가되었을 때 imperfection을 구한다음 정렬하면 이 방식으로 구한 답을 얻을 수 있고,
관찰을 잘 해보면 이보다 나은 답을 만드는 것이 불가능하다는 사실도 알 수 있다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
|
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
ll gcd(ll a, ll b) { for (; b; a %= b, swap(a, b)); return a; }
int isPrime[500001];
int n;
int cnt[500001];
int main()
{
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
for (int i = 2; i * i <= 500000; i++)
{
if (isPrime[i] == 0)
{
isPrime[i] = i;
for (int j = i + i; j <= 500000; j += i)
{
if (isPrime[j] == 0) isPrime[j] = i;
else isPrime[j] = min(isPrime[j], i);
}
}
}
cin >> n;
for (int i = 1; i <= n; i++)
{
if (isPrime[i] == 0) isPrime[i] = i;
cnt[i / isPrime[i]]++;
}
for (int i = 1; i <= n; i++)
{
int j = 0;
if (i == 1) j = 1;
for (; j < cnt[i]; j++) cout << i << ' ';
}
}
|
'문제 풀이 > Codeforces' 카테고리의 다른 글
| Codeforces Round #633 (Div. 1, Div. 2) (0) | 2020.04.13 |
|---|---|
| Educational Codeforces Round 85 (0) | 2020.04.12 |
| Codeforces Round #631 (Div. 1, Div. 2) (0) | 2020.04.07 |
| Codeforces Round #630 (Div. 2) (2) | 2020.04.06 |
| Codeforces Round #629 (Div. 3) (0) | 2020.03.30 |