https://codeforces.com/contest/1647
Dashboard - Codeforces Round #777 (Div. 2) - Codeforces
codeforces.com
멸망.
결국 그린까지 떨어지는구나.
잭팟 라운드였는데
터진 건 나였고.
A.
212121... 이런 식으로 2로 시작해서 최대한 길게 출력하는 게 좋으므로 "21"을 얼마나 출력할 수 있는지에 초점을 두면 된다.
그래서 n을 3으로 나눈 나머지가 0이면 n/3회만큼 "21"을 출력하고, 나머지가 2이면 n/3회만큼 "21"을 출력하고 마지막에 2를 추가로 출력해준다.
그런데 나머지가 1인 경우에는 2121...21을 출력한 후에 다시 1이 나올 수 없으므로 이때는 1212...1이 답이 된다.
int main() {
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int tc; cin >> tc;
while (tc--) {
int n; cin >> n;
if (n % 3 == 0) {
for (int i = 0; i < n / 3; ++i) {
cout << "21";
}
}
else if (n % 3 == 1) {
for (int i = 0; i < n / 3; ++i) {
cout << "12";
}
cout << "1";
}
else {
for (int i = 0; i < n / 3; ++i) {
cout << "21";
}
cout << "2";
}
cout << kEndl;
}
}빠르게 풀고 기분이 좋았다.
이때까지는.
B.
최근에 C보다 B에서 더 막혔던 적이 많아서 불안했는데 불안이 현실이 되었다.
삽질을 심하게 했다.
학회 내 코포 스터디에서 원래 매주 금요일마다 버추얼을 도는데, 오늘처럼 라이브 대회가 있는 날에는 라이브에 참가한다.
그래서 끝나고 스터디에서 문제 풀이했는데, 추첨해서 당첨되신 Rebro님이 풀이해주셨다.
결론적으로는 인접한 1들로 만들어진 집합이 직사각형이면 되는 거다.
음. 여기까지는 생각했다.
이걸 어떻게 구현하느냐가 문제인데,
BFS로 인접한 1들로 만들어진 집합을 구하고, 거기에 속한 원소들 들에 대해 행과 열의 최댓값과 최솟값을 구한다.
이 집합이 직사각형이라는 건 결국 '(행 최댓값 - 행 최솟값 + 1) * (열 최댓값 - 열 최솟값 + 1) == 집합에 속한 1의 개수'라는 것과 동치이다.
진짜 깔끔하다...
bool InBound(const pair<int, int>& cur, const int& n, const int& m) {
return 0 <= cur.first && cur.first < n && 0 <= cur.second && cur.second < m;
}
int main() {
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int tc; cin >> tc;
while (tc--) {
int n, m; cin >> n >> m;
vector<vector<int>> arr(n, vector<int>(m));
for (int i = 0; i < n; ++i) {
string s; cin >> s;
for (int j = 0; j < m; ++j) {
arr[i][j] = s[j] - '0';
}
}
bool ans = true;
vector<vector<bool>> visited(n, vector<bool>(m));
vector<pair<int, int>> move = { {-1, 0}, {1, 0}, {0, -1}, {0, 1} };
for (int i = 0; i < n && ans; ++i) {
for (int j = 0; j < m && ans; ++j) {
if (arr[i][j] == 1 && !visited[i][j]) {
visited[i][j] = true;
queue<pair<int, int>> que;
que.push({ i, j });
int miny, maxy, minx, maxx;
miny = maxy = i;
minx = maxx = j;
int cnt = 1;
while (!que.empty()) {
pair<int, int> cur = que.front();
que.pop();
for (const pair<int, int>& dir : move) {
pair<int, int> next = { cur.first + dir.first, cur.second + dir.second };
if (InBound(next, n, m) && arr[next.first][next.second] == 1 && !visited[next.first][next.second]) {
visited[next.first][next.second] = true;
que.push(next);
miny = min(miny, next.first);
maxy = max(maxy, next.first);
minx = min(minx, next.second);
maxx = max(maxx, next.second);
++cnt;
}
}
}
if ((maxy - miny + 1) * (maxx - minx + 1) != cnt) {
ans = false;
break;
}
}
}
}
cout << (ans ? "YES" : "NO") << kEndl;
}
}문제에서 n, m의 합이 최대 777이라고 하는 걸 보고 'O(n^3) 풀이가 가능하다는 의미군!'이라는 생각에 사로잡혀있었던 거 같다. ㅠㅠ
C.
이 문제에서는 'Note that you do not need to minimize the number of operations.'라는 게 포인트다.
어떤 칸을 검은색으로 만들기 위해서는 그 검은 칸의 왼쪽 칸에 1*2 크기의 operation을 하거나 그 위 칸에서 2 *1 크기의 operation을 하면 된다.
그러므로 불가능한 상황은 (1, 1)에 검은색이 있는 경우뿐이다.
그리고 다른 검은 칸들은 차례를 정해 하나씩 칠해나가면 된다.
나는 가장 아래 행부터 오른쪽에서 왼쪽으로 이동하면서 1 * 2 크기의 operation을 해주고, 가장 왼쪽 열에 검은 칸이 있는 경우에는 그 위 칸에서 2 * 1 크기의 operation을 했다.
int main() {
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int tc; cin >> tc;
while (tc--) {
int n, m; cin >> n >> m;
vector<vector<int>> arr(n + 1, vector<int>(m + 1));
for (int i = 1; i <= n; ++i) {
string s; cin >> s;
for (int j = 1; j <= m; ++j) {
arr[i][j] = s[j - 1] - '0';
}
}
if (arr[1][1] == 1) {
cout << -1 << kEndl;
continue;
}
vector<pair<pair<int, int>, pair<int, int>>> ans;
for (int i = n; i > 0; --i) {
for (int j = m; j > 0; --j) {
if (arr[i][j] == 1) {
if (j > 1) {
ans.push_back({ {i, j - 1}, {i, j} });
}
else {
ans.push_back({ { i - 1, j }, { i, j } });
}
}
}
}
cout << ans.size() << kEndl;
for (int i = 0; i < ans.size(); ++i) {
const pair<int, int>& start = ans[i].first;
const pair<int, int>& end = ans[i].second;
cout << start.first << ' ' << start.second << ' ' << end.first << ' ' << end.second << kEndl;
}
}
}