[Contest 1]SCPC 2021 Round 1後期
🎈 Intro
大会時間:2021年7月16日(金)15:00~2021年7月17日(土)15:00
生まれて初めてアルゴリズム大会に参加しました.アルゴリズムを学ぶのは333週間しか経っていないので、あまり期待せずに問題を閲覧する気持ちで大会に参加しました.予想通り3・4・53・4・53・4・53・4・5番は当たりもせず222番で塞がれ、試合は終了した.
7月16日を基準として、私の履歴は以下の通りです.
🏆 結果
1日:友達(80/80)
最初は簡単に順番に近づきたいと思っていました.しかし、この場合、後ろの方向を実現するにはタイムアウトする可能性があるので、矢印を双方向に接続すべきだと思います.このように接続すると,資料構造課で習ったグラフのように見え,「接続図の個数」を探す問題である.(白駿11724:接続要素数題参照)
出力:222
/*
You should use the standard input/output
in order to receive a score properly.
Do not use file input and output
Please be very careful.
*/
#include <iostream>
#include <vector>
using namespace std;
int Answer;
vector<vector<int>> edge;
vector<bool> visited;
int N;
int u, v;
int cnt = 0;
int dfs(int cur) {
int result = 0;
if (cur >= N) return 0;
if (visited[cur]) return 0;
visited[cur] = true;
result++;
for (int i = 0; i < edge[cur].size(); i++) {
int there = edge[cur][i];
if (there >= N) continue;
if (visited[there]) continue;
dfs(there);
}
return result;
}
int main(int argc, char** argv)
{
int T, test_case;
/*
The freopen function below opens input.txt file in read only mode, and afterward,
the program will read from input.txt file instead of standard(keyboard) input.
To test your program, you may save input data in input.txt file,
and use freopen function to read from the file when using cin function.
You may remove the comment symbols(//) in the below statement and use it.
Use #include<cstdio> or #include <stdio.h> to use the function in your program.
But before submission, you must remove the freopen function or rewrite comment symbols(//).
*/
// freopen("input.txt", "r", stdin);
cin >> T;
for (test_case = 0; test_case < T; test_case++)
{
Answer = 0;
/////////////////////////////////////////////////////////////////////////////////////////////
cin >> N;
edge.resize(N + 1);
visited.resize(N + 1);
for (int i = 0; i < N; i++) {
cin >> v;
edge[i].push_back(i + v);
if (i+v < N)
edge[i + v].push_back(i); // 양방향 그래프로 만들기
}
for (int i = 0; i < N; i++) {
if (dfs(i) > 0) Answer++;
}
edge.clear();
visited.clear();
/////////////////////////////////////////////////////////////////////////////////////////////
// Print the answer to standard output(screen).
cout << "Case #" << test_case + 1 << endl;
cout << Answer << endl;
}
return 0;//Your program should return 0 on normal termination.
}2番：バイナリ（0/150）
今でもなぜ間違っているのか分からない.テストケースも202020個以上実行したが,反例は見つからなかった.
Case
n, t
B (input)
A (output)
#1
5 1
00111
00011
#2
10 2
1111111000
0111100000
#3
8 3
01110101
00101110
#4
9 6
111000001
001000111
#5
7 1
1011010
0100100
#6
7 2
1111111
0011110
/*
You should use the standard input/output
in order to receive a score properly.
Do not use file input and output
Please be very careful.
*/
#include <iostream>
using namespace std;
string Answer;
int main(int argc, char** argv)
{
int T, test_case;
/*
The freopen function below opens input.txt file in read only mode, and afterward,
the program will read from input.txt file instead of standard(keyboard) input.
To test your program, you may save input data in input.txt file,
and use freopen function to read from the file when using cin function.
You may remove the comment symbols(//) in the below statement and use it.
Use #include<cstdio> or #include <stdio.h> to use the function in your program.
But before submission, you must remove the freopen function or rewrite comment symbols(//).
*/
cin >> T;
for (test_case = 0; test_case < T; test_case++)
{
/////////////////////////////////////////////////////////////////////////////////////////////
string A, B;
int n, t;
cin >> n >> t >> B;
// Step 1. A 초기화 (초기 상태 A: xxxxxxxxxx)
for (int i = 0; i < n; i++) {
A += 'x';
}
//cout << "Step 1) 처음 A: " << A << endl;
// Step 2. 단방향 수열 결정하기
// t가 n/2보다 클 때는 이거만 하면 끝
for (int i = 0; i < t; i++) {
if (i + t > n - 1) continue;
if (B[i] == '1') {
A[i + t] = '1';
}
else {
A[i + t] = '0';
}
}
for (int i = n - t; i < n; i++) {
if (i - t < 0) continue;
if (B[i] == '1') {
A[i - t] = '1';
}
else {
A[i - t] = '0';
}
}
//cout << "Step 2) 단방향 끝부분 넣은 후 A: " << A << endl;
// Step 3. 0 넣기
for (int i = t; i <= n - t - 1; i++) {
if (B[i] == '0') {
if (A[i - t] == 'x') A[i - t] = '0';
if (A[i + t] == 'x') A[i + t] = '0';
}
}
//cout << "Step 3) 0 넣은 후 A: " << A << endl;
// Step 4. 나머지 사이 부분 결정하기 (왼쪽에 1이 없으면 왼쪽 0, 오른쪽 1 / 이미 있으면 오른쪽 1)
for (int i = t; i <= n - t - 1; i++) {
if (B[i] == '1') {
if (A[i - t] == 'x' && A[i + t] == 'x') { // 둘 다 아무것도 없으면
A[i - t] = '0';
A[i + t] = '1';
}
else if (A[i - t] == '0' && A[i + t] == 'x') {
A[i + t] = '1';
}
else if (A[i - t] == 'x' && A[i + t] == '0') {
A[i - t] = '1';
}
else if (A[i - t] == '1' && A[i + t] == 'x') {
A[i + t] = '0';
}
else if (A[i - t] == 'x' && A[i + t] == '1') {
A[i - t] = '0';
}
}
}
//cout << "Step 4) 사이 정한 후 A: " << A << endl;
// 남은 부분 있으면 다 0으로 채우기
for (int i = 0; i < n; i++) {
if (A[i] == 'x') A[i] = '0';
}
Answer = A;
/////////////////////////////////////////////////////////////////////////////////////////////
// Print the answer to standard output(screen).
cout << "Case #" << test_case + 1 << endl;
for (int i = 0; i < n; i++) {
cout << Answer[i] - '0';
}
cout << endl;
}
return 0;//Your program should return 0 on normal termination.
}Reference
この問題について([Contest 1]SCPC 2021 Round 1後期), 我々は、より多くの情報をここで見つけました https://velog.io/@yjwon20/Contests1テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol