TIL 2018-12-16
오늘 배운 것 & 한 것
algorithm
cf 1093 - Educational Round 56
C까지 풀어서 좀 많이 풀었나 했는데 문제가 G까지 있다…
D를 풀 뻔 했는데 vscode로 cpp 디버깅하는게 너무 느려서 실패했다. 확실히 아이디어는 꽤 금방 알아냈는데 아쉽다. 오히려 js로 풀었으면 빨리 풀었을까? 아니 아마 큰 수 곱셈이 있어서 틀려버릴듯. 이건 나중에 확인해볼 가치는 있다.
A.
B.
C.
그리디 문제.
int s = 0;
const int MAXN = 100006;
// const int MAXN = 16;
ll bs[MAXN+6];
ll as[MAXN*2+6];
void solve()
{
int n; cin >> n;
// 중간까지는 ai에 할당가능한 최소값 할당하고, 이후부터는 최대 할당?
// 어차피 ai 하나를 선택하면 다른 하나는 결정됨.
// ai와 a(i+1)을 같은 값으로 할당해서는 안되는 경우가 어떤 기준으로 생기지?
// 두 번째 예제를 보면, 0 0 1 1 1 2에서 어떤 숫자도 건드릴 수 없다.
// 두 번째 0을 1로 바꾸면 뒤의 1을 0으로 해야 해서 틀려지고, 그건 쉬운 조건이지만,
// 세 번째 1을 0으로 바꾸면 4번째 1이 2가 되는데, 이것이 그 뒤의 1보다 커지므로 또 모순이 된다. 이 부분이 어렵다.
// 일종의 그리디로 보인다. ai를 어떤 값으로 해놓고 a(n-i+1)의 값이 그 뒷값보다 커지지 않았다면 될 것이다. 어차피 답이 분명 존재한다 했으므로 그리디로 하면 될 것.
// 그리디로 하고있기 때문에 내 생각에 ai쪽에서는 모순이 생기지 않을 것이다. 뒤쪽에서만 모순이 생길 것이다. 근데 이렇게 curval을 1씩 증가시키면 10^18번 정도에 비례해 실행될텐데 괜찮을까? 절대 안 괜찮다. 1억번당 1초라고 보면 10^18하는데는 굉장히 오래걸리게 된다.
// 따라서 뒤쪽의 관계를 읽어서 최대한 적게 증가시키는 값을 한 번에 찾아줘야 한다.
ll curval = 0;
as[n] = 9223372036854775807ll - 5;
as[n+1] = 9223372036854775807ll - 5;
for(int i = 0; i < n/2; i++){
cin >> bs[i];
bool assigned = false;
while(!assigned){
as[i] = curval;
as[n - i-1] = bs[i] - curval;
if(as[n - i-1] <= as[n - i]){
// 모순 없는 경우
assigned = true;
} else {
//모순 있는 경우: curval 증가
// as[n-i] 가 as[n-i+1]보다 큰 만큼.
curval += as[n-i-1] - as[n-i];
}
}
}
for(int i = 0; i < n; i++){
cout << as[i] << ' ';
}
}
D.
그래프 문제.
const int MAXN = 300004;
// const int MAXN = 16;
int types[MAXN+6];
ll ans = 0;
int type1 = 0;
int type2 = 0;
bool fail = false;
vector<int> adj[MAXN];
bool visited[MAXN];
void dfs(int vertex, int targetType){
if(types[vertex] != 0 && types[vertex] != targetType){
fail = true;
return;
}
if(visited[vertex]){
return;
}
visited[vertex] = true;
if(targetType == 1){
type1++;
} else {
type2++;
}
types[vertex] = targetType;
for(int v : adj[vertex]){
if(targetType == 1){
dfs(v, 2);
} else {
dfs(v, 1);
}
}
}
void solve()
{
int T; cin >> T;
for(int t = 0; t < T; t++){
int n,m;
cin >> n >> m;
// 각 vertex에 숫자 1,2,3중 하나를 할당해서,
// 모든 각각의 edge에 대해 연결된 vertex들의 숫자의 합이 홀수.
// 일단, 짝수 숫자 할당은 아무 영향도 주지 않는다.
// 홀수 vertex가 홀수 개 있어야 합이 홀수가 된다.
// 즉 모든 간선에 대해 연결된 정점들이 합이 홀수가...
// 근데 간선에 연결된 정점은 두개잖아? 그러니 당연히
// 홀수인 정점은 딱 하나여야 하네.
// 그러면 차수 문제일 가능성이 높다! 왜냐하면,
// 단 하나라도 인접한 두 정점이 모두 홀수거나 짝수여서는 안되기 때문!
// 그래프가 그럼 임의의 한 정점에 대해 홀수로 시작한 그래프/짝수로 시작한 그래프 딱 두 가지로 사실상 타입이 나뉘어질거 같다.
// dfs로 해도 될까? 이번 정점이 모순이 있는지 확인하려면 어떻게 해야 하지?
// 일단 모든 정점을 타입을 0으로 시작한 뒤,
// 정점에 도달하면 타입을 갖고있는지 확인하여,
// 할당하려던 타입을 갖고있다면 내버려 둔다,
// 잘못된 타입이라면 답은 0이 된다. 즉시 종료
// 타입이 없다면 타입을 할당해 준다.
// 처음 시작 정점을 아무거나 잡아서
// 타입 1로 한 번 순회, 2로 한 번 순회해준다.
// 순회를 하면서, 타입 1이 몇개인지, 2가 몇개인지 카운트해준다
// 생각해보니, visited여도 잘못된 타입 할당하려 하는지 확인하기 위해 1번씩은 중첩 방문 해야할거 같은데, 그러면 너무 느려지려나?
for(int i = 0; i < m; i++){
int u, v;
cin >> u >> v;
adj[u].push_back(v);
adj[v].push_back(u);
}
type1 = 0;
type2 = 0;
memset(visited, false, sizeof(visited));
memset(types, 0, sizeof(types));
fail = false;
dfs(1, 1);
if(fail) {
cout << '0' << endl;
continue;
} else {
ans = power(2, type1);
// cout << ans << endl;
}
type1 = 0;
type2 = 0;
memset(visited, false, sizeof(visited));
memset(types, 0, sizeof(types));
fail = false;
dfs(1, 2);
if(fail) {
cout << '0' << endl;
continue;
} else {
ans += power(2, type1);
cout << ans << endl;
}
}
}
늦어서 아직 제출은 못했지만 맞을거라 기대한다.
역시 틀렸다. 단일 컴포넌트도 아니고, 고치더라도 풀이 방식도 틀릴거같음. 아래는 덧글에 나온 설명
설명에 단일 컴포넌트 또는 connected라고 안되어있으면 결국 안될 수 있다고가 아니라 분명히 안되어 있다고 생각하고 풀어야함.
If graph contain odd cycle, answer is zero as no valid assignment can exist.
Otherwise, let us find 2-coloring of each connected component in graph. Say, x nodes are colored red while y nodes are colored black. There are exactly pow(2,x) +pow(2,y) ways to color this component. Take product of this for all components.
Reason of pow(2,x)+pow(2,y). You need sum of edges to be odd. So, one of the value on edge is 2 and other value is either 1 or 3. pow(2,x) assume we assign all red colored nodes with either 1 or 3, giving pow(2,x) choices. Same for y.
vscode로 cpp 디버깅
사실상 너무 안좋다. 호버해서 하나라도 배열길이가 긴 배열 등을 봐버리면 버벅대기 시작하면서 더 이상 진행이 안 된다. 그냥 tasks.json 수정해서 컴파일 및 실행 자동화로 출력값 비교해서 하는게 나을 듯.
디버깅 없이 직접 실행 스크립트 짜기
- tasks.json 이용
아래와 같이 tasks.json작성하고, 단축키에 group.kind 이름으로 연결한다. (workbench.actions.tasks.<groupName>)
isDefault옵션을 주면 그 그룹네임을 실행시켰을때 바로 실행하며, 안 주면 그 그룹네임의 task들 중 무엇을 실행할건지 선택해서 실행하게 된다. 조금 실망스러운건 그룹네임이 build아니면 test 두 가지만 가능한거 같다.
📂
tasks.json
{
"label": "build and execute cpp without debug",
"command": ".",
"dependsOn":["build cpp without debug"],
"group": {
"kind": "test",
"isDefault": true
},
"options": {
"cwd": "${fileDirname}"
},
"args": [
"${fileDirname}\\${fileBasenameNoExtension}",
"TestMode"
]
},
- 파워셸 스크립트 이용
📂
executeCpp.ps1
Write-Host "Starting $($args).cpp";
Write-Host "Compiling" -ForegroundColor Yellow -BackgroundColor DarkGreen;
g++ ./$args.cpp -o ./$args;
Write-Host "Running" -ForegroundColor Yellow -BackgroundColor DarkGreen;
. ./$args.exe TestMode;
Write-Host "Done" -ForegroundColor Yellow -BackgroundColor DarkGreen;
이렇게 짜고, vscode에서 다음과 같이 tasks.json에 쓴다.
📂
tasks.json
{
"label": "build and execute cpp without debug using pwsh script",
"command": "...\\executeCpp.ps1",
"group": {
"kind": "test",
"isDefault": true
},
"options": {
"cwd": "${fileDirname}"
},
"args": [
"${fileBasenameNoExtension}"
]
}
물론 이 경우 이전 task는 없애거나 group을 없애줘야 한다.
📂
keybindings.json
{
"key": "ctrl+r ctrl+r",
"command": "workbench.action.tasks.test"
},
boj
2606 - 바이러스
그냥 1번 기준으로 dfs돌림. 문제가 원하는 답이 1번을 통해 전염되는 수이므로 count-1 해야함.
Comments