문제
https://codeforces.com/gym/101806
Dashboard - 2018 KAIST RUN Spring Contest - Codeforces
codeforces.com
https://www.acmicpc.net/category/detail/1874
2018 KAIST RUN Spring Contest
15769 P PuyoPuyo 서브태스크스페셜 저지출처다국어 50 170 31.250%
www.acmicpc.net
2021.08.16 전체 P~Z 11문제 7솔 RTUX 5문제 언솔
문제 해설
https://drive.google.com/open?id=17Sgx0VODLTdrfQhIQrAf5kHWiiwG--Q2
editorial.pdf
drive.google.com
P. Puyo Puyo
문제
테트리스의 가장 마지막 상태를 입력으로 받는다. 마지막 상태를 나타낼 수 있도록 테트리스를 잘 쌓는 과정을 출력해라.
테트리스 블록은 2칸짜리고 상하좌우로 4개 이상 연결되면 터진다.
풀이
짝수개의 블록이 세로로 길게 쌓여 있다면 블록/2번의 쌓음으로 해당 줄을 만들 수 있다.
홀수개의 블록이 세로로 길게 쌓여 있다면 한칸을 만든 후 나머지 짝수개의 칸은 위와 같이 만들 수 있다.
한칸을 만드는 방법은 제일 아래칸과 다른 색으로 위의 5칸을 채우는 것(3번의 과정 필요)
한줄씩 만들면 홀수개 블록 한칸짜리 만들 때 옆의 짝수든 홀수든 칸에서 4개 이상 겹쳐서 터지는 경우가 있다.
한칸씩 만들고 짝수칸 한줄씩 만들면 된다.
소스코드
#include <bits/stdc++.h>
using namespace std;
struct data{int x, y, z, w;};
vector<data> pr;
vector<int> v[30];
int main(){
int R, C, K;
scanf("%d%d%d",&R,&C,&K);
for(int i=0; i<R; ++i){
for(int j=0; j<C; ++j){
int e;
scanf("%d",&e);
if(!e) continue;
//printf("%d %d %d\n",i,j,e);
v[j].push_back(e);
}
}
for(int j=0; j<C; ++j){
int n=v[j].size();
//printf("%d\n",n);
if(n&1){ // 1칸 만들고
pr.push_back({1,j,(v[j][n-1]==1)+1,v[j][n-1]});
pr.push_back({1,j,(v[j][n-1]==1)+1,(v[j][n-1]==1)+1});
pr.push_back({1,j,(v[j][n-1]==1)+1,(v[j][n-1]==1)+1});
}
}
for(int j=0; j<C; ++j){
int n=v[j].size();
//printf("%d\n",n);
if(n&1){ // 2칸씩
for(int i=n-3; i>=0; i-=2) pr.push_back({1,j,v[j][i],v[j][i+1]});
}
else{ // 2칸씩
for(int i=n-2; i>=0; i-=2) pr.push_back({1,j,v[j][i],v[j][i+1]});
}
}
printf("%d\n",pr.size());
for(int i=0; i<pr.size(); ++i){
printf("%d %d %d %d\n",pr[i].x,pr[i].y+1,pr[i].z,pr[i].w);
}
}
Q. QueryreuQ
문제
제목만 봐도 Palindrome 문제..
풀이
소스코드
R. Recipe
문제
CHT를 사용하는 문제일거같았는데 Li때문에 솔루션이 생각나지 않았다.
풀이
소스코드
S. Segmentation
문제
풀이
소스코드
T. Touch The Sky
문제
스케쥴링
풀이
소스코드
U. United States of Eurasia
문제
Convexhull + Rotating Calipers
풀이
소스코드
V. Voronoi Diagram
문제
그래프에서 중점이 되는 정점들이 있을 때 간선 상의 위치들은 중점이 되는 점들 중 가장 가까운 점에 분류된다. 거리가 같다면 번호가 더 작은 점에 분류된다.
설명이 조금 복잡한데
1, 2가 각각 정점집합에 포함된 정점이고 검은 수가 해당 간선의 총 길이일 때 간선들은 붉은색(1에 포함됨)과 푸른색(2에 포함됨)으로 나뉜다.
풀이
처음에 문제를 잘못 생각해서 이상하게 나눴다가 틀린부분 메우는 식으로 코드를 짜서 코드가 엄청 더러워졌다.
다익스트라(Dijkstra)를 사용해서 거리가 가장 짧고 연결된 번호가 가장 짧은 점부터 시작해서 돌아본다.
한 간선은 최대 2개의 정점집합으로 나눠지므로 결과값은 ~.0이거나 ~.5이다. 2배해두고 나중에 절반으로 나눠서 뒤에 소수점 붙여주었다.
z간선에 대해 분류를 한다. (x, y에 대해선 이미 처리가 되었다고 생각하자.)
전체 길이는 (x+z+y)
붉은점에 포함될 길이 = 전체길이/2 - x 이지만, 2배를 한다고 했으므로 z+y-x
푸른점에 포함될 길이 = 전체길이/2 - y 이지만, 2배를 한다고 했으므로 z+x-y
소스코드
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N=5e5;
bool V[N], vis[N];
struct data{ll w, z, i, c;};
inline bool operator<(const data a,const data b){return a.z>b.z || (a.z==b.z && a.i>b.i);}
vector<data> e[N];
priority_queue<data> pq;
ll F[N], pr[N], L[N];
int main(){
ll n, m, k;
scanf("%lld%lld",&n,&m);
for(ll i=0; i<m; ++i){
ll x, y, z;
scanf("%lld%lld%lld",&x,&y,&z);
e[x].push_back({y,z,i,i});
e[y].push_back({x,z,i,i});
}
scanf("%lld",&k);
for(ll i=0; i<k; ++i){
ll v;
scanf("%lld",&v);
vis[v]=1;
F[v]=v;
for(auto w:e[v]){
if(!V[w.i]){
V[w.i]=1;
pq.push({w.w,w.z,v,w.z});
//printf("%d %d %d\n",w.w,w.z,v);
}
}
}
//puts("");
while(pq.size()){
data t=pq.top();
pq.pop();
//printf("%d %d %d %d\n",t.w,t.z,t.i,t.c);
if(F[t.w]==t.w){
pr[t.i]+=t.c+L[t.w] - (t.z-t.c);
pr[F[t.w]]+=t.z - L[t.w];
}
else{
if(!vis[t.w]){
L[t.w]=t.z;
F[t.w]=t.i;
pr[t.i]+=t.c<<1;
vis[t.w]=1;
for(auto w:e[t.w]){
if(!V[w.i]){
//printf("%d / ",w.w);
V[w.i]=1;
pq.push({w.w,t.z+w.z,t.i,w.z});
}
}
//printf("%d\n",t.w);
}
else{
pr[t.i]+=t.c+L[t.w] - (t.z-t.c);
pr[F[t.w]]+=t.z - L[t.w];
//printf("%d %d | %d %d\n",t.c+L[t.w] - (t.z-t.c), t.z - L[t.w],t.i,F[t.w]);
}
}
//printf("%d %d\n",pr[1],pr[2]);
}
for(ll i=1; i<=n; ++i){
if(F[i]==i) {
printf("%lld",pr[i]>>1);
puts(pr[i]&1?".5":".0");
}
}
}
W. Winter Olympic Games
문제
풀이
소스코드
X. Xtreme NP-hard Problem?!
문제
풀이
소스코드
Y. Yut Nori
문제
진짜 윷놀이 문제
2사람이 플레이 말은 4개씩 (1번사람 말 : ABCD, 2번사람 말 : abcd)
윷놀이 과정을 입력받고 해당 턴의 상태를 출력하라
풀이
구현문제.
쉬운데 구현하기 너무 싫다.
인덱스에 대해서 dx, dy선언 바로 아래 주석에 적어두었다.
소스코드
#include <bits/stdc++.h>
using namespace std;
int mp[31][5]={
{ 2, 3, 4, 5, 6}, // 0
{ 2, 3, 4, 5, 6}, // 1
{ 3, 4, 5, 6, 7}, // 2
{ 4, 5, 6, 7, 8}, // 3
{ 5, 6, 7, 8, 9}, // 4
{ 6, 7, 8, 9,10}, // 5
{21,22,23,24,25}, // 6
{ 8, 9,10,11,12}, // 7
{ 9,10,11,12,13}, // 8
{10,11,12,13,14}, // 9
{11,12,13,14,15}, // 10
{26,27,23,28,29}, // 11
{13,14,15,16,17}, // 12
{14,15,16,17,18}, // 13
{15,16,17,18,19}, // 14
{16,17,18,19,20}, // 15
{17,18,19,20,30}, // 16
{18,19,20,30,31}, // 17
{19,20,30,31,31}, // 18
{20,30,31,31,31}, // 19
{30,31,31,31,31}, // 20
{22,23,24,25,16}, // 21
{23,24,25,16,17}, // 22
{28,29,30,31,31}, // 23
{25,16,17,18,19}, // 24
{16,17,18,19,20}, // 25
{27,23,28,29,30}, // 26
{23,28,29,30,31}, // 27
{29,30,31,31,31}, // 28
{30,31,31,31,31}, // 29
{31,31,31,31,31} // 30
};
int dx[31]={30,30,24,18,12, 6, 0, 0, 0, 0, 0, 0, 6,12,18,24,30,30,30,30,30, 5,10,15,20,25, 5,10,20,25,30};
int dy[31]={30,30,30,30,30,30,30,24,18,12, 6, 0, 0, 0, 0, 0, 0, 6,12,18,24,25,20,15,10, 5, 5,10,20,25,30};
/*
11 10 9 8 7 6
12 26 21 5
13 27 22 4
23
14 24 28 3
15 25 29 2
16 17 18 19 20 1(30)
*/
int ch(char h){
if(h=='A') return 1;
if(h=='B') return 2;
if(h=='C') return 3;
if(h=='D') return 4;
if(h=='a') return 5;
if(h=='b') return 6;
if(h=='c') return 7;
if(h=='d') return 8;
}
int now[30][2], mal[10];
char pr[33][33]={
"..----..----..----..----..----..",
".. .. .. .. .. ..",
"| \\ / |",
"| \\ / |",
"| \\ / |",
"| .. .. |",
".. .. .. ..",
".. \\ / ..",
"| \\ / |",
"| \\ / |",
"| .. .. |",
"| .. .. |",
".. \\ / ..",
".. \\ / ..",
"| \\ / |",
"| .. |",
"| .. |",
"| / \\ |",
".. / \\ ..",
".. / \\ ..",
"| .. .. |",
"| .. .. |",
"| / \\ |",
"| / \\ |",
".. / \\ ..",
".. .. .. ..",
"| .. .. |",
"| / \\ |",
"| / \\ |",
"| / \\ |",
".. .. .. .. .. ..",
"..----..----..----..----..----.."
};
int main(){
int n;
scanf("%d",&n);
for(int i=0; i<n; ++i){
char h, yut[4];
scanf("\n%c %s",&h,yut);
int m=ch(h);
int B=(yut[0]=='B')+(yut[1]=='B')+(yut[2]=='B')+(yut[3]=='B');
int F=(yut[0]=='F')+(yut[1]=='F')+(yut[2]=='F')+(yut[3]=='F');
int G=(F+4)%5;
int D=mp[mal[m]][G], S=mal[m];
if(S>30) continue;
if(m<5){
if(D>30){
for(int i=1; i<5; ++i) if(mal[i]==S) mal[i]=D;
continue;
}
for(int i=5; i<9; ++i) if(mal[i]==D) mal[i]=0;
if(!mal[m]) mal[m]=D;
else for(int i=1; i<5; ++i) if(mal[i]==S) mal[i]=D;
}
else{
if(D>30){
for(int i=5; i<9; ++i) if(mal[i]==S) mal[i]=D;
continue;
}
for(int i=1; i<5; ++i) if(mal[i]==D) mal[i]=0;
if(!mal[m]) mal[m]=D;
else for(int i=5; i<9; ++i) if(mal[i]==S) mal[i]=D;
}
}
int T, x, y;
T=mal[1], x=dx[T], y=dy[T]; if(1<T && T<31) pr[x][y]='A';
T=mal[2], x=dx[T], y=dy[T]; if(1<T && T<31) pr[x][y+1]='B';
T=mal[3], x=dx[T], y=dy[T]; if(1<T && T<31) pr[x+1][y]='C';
T=mal[4], x=dx[T], y=dy[T]; if(1<T && T<31) pr[x+1][y+1]='D';
T=mal[5], x=dx[T], y=dy[T]; if(1<T && T<31) pr[x][y]='a';
T=mal[6], x=dx[T], y=dy[T]; if(1<T && T<31) pr[x][y+1]='b';
T=mal[7], x=dx[T], y=dy[T]; if(1<T && T<31) pr[x+1][y]='c';
T=mal[8], x=dx[T], y=dy[T]; if(1<T && T<31) pr[x+1][y+1]='d';
for(int i=0; i<32; ++i){
puts(pr[i]);
}
}
Z. Zigzag
문제
풀이
소스코드
