[Codeforces] Round 957 (Div. 3) 후기
https://codeforces.com/contest/1992
Dashboard - Codeforces Round 957 (Div. 3) - Codeforces
codeforces.com
2024.07.21
콘테스트를 친건 7월 11일이었는데... 요즘 이것저것 한다고 미뤘다가 열흘만에 드디어 포스팅..
방학 동안에 학교에 알고리즘 동아리 사람들 몇명이랑 코포 스터디하면서 코포 연습중인데
확실히 혼자 하는 것보다 아는 사람이랑 날짜 정해놓고 문제 얘기하면서 공부하는게 도움이 꽤 되는 것 같다.
요즘 스터디하면서 딥2도 종종 하고있는데.. 2솔도 간당간당한 수준이라.. 퍼포 떨어질까봐 버츄얼로만 돌리는 중..
각설하고, 이번 Div.3에선 간만에 5솔을 했고, 드디어 민트를 달성했다!
A. Only Pluses (00:05)
그냥 브루트포스. 3중 for문 돌려서 풀었다.
다른 풀이로는 a,b,c중 제일 작은 수에 1씩 더하는 연산을 5번 반복해서 풀 수도 있다.
오랜만에 풀어서 그런가 괜히 복잡하게 생각하는 바람에 1번 푸는데 좀 오래 걸렸다..
#include<bits/stdc++.h>
using namespace std;
#define X first
#define Y second
#define rep(i,x,y) for(int i=x;i<y;i++)
#define all(x) begin(x),end(x)
#define rall(x) rbegin(x),rend(x)
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef tuple<int,int,int> tiii;
int dx[] = {0,0,1,-1};
int dy[] = {1,-1,0,0};
/*----------------------*/
int main(){
ios::sync_with_stdio(0); cin.tie(0);
int t; cin>>t;
while(t--){
int a,b,c; cin>>a>>b>>c;
int ans = 0;
for(int i=0;i<=5;i++){
for(int j=0;j<=5;j++){
for(int k=0;k<=5;k++){
if(i+j+k >5) continue;
ans = max(ans, (a+i)*(b+j)*(c+k));
}
}
}
cout<<ans<<'\n';
}
}
B. Angry Monk (00:10)
가장 큰 수 하나를 남겨두고, 남은 모든수를 1로 쪼개고, 큰 수에 합치는 연산이 최적이다.
전체 합을 sum, 가장 큰 수가 mx라고 할때, 합치는 연산은 sum-mx번 진행되고, 쪼개는 연산은 원소 a에 대해서 a-1번만 진행하면 되므로, 이를 구하면 끝
#include<bits/stdc++.h>
using namespace std;
#define X first
#define Y second
#define rep(i,x,y) for(int i=x;i<y;i++)
#define all(x) begin(x),end(x)
#define rall(x) rbegin(x),rend(x)
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef tuple<int,int,int> tiii;
int dx[] = {0,0,1,-1};
int dy[] = {1,-1,0,0};
/*----------------------*/
int main(){
ios::sync_with_stdio(0); cin.tie(0);
int t; cin>>t;
while(t--){
int n,m; cin>>n>>m;
vector<int> v(m);
rep(i,0,m) cin>>v[i];
sort(rall(v));
int ans = n-v[0];
rep(i,1,m) ans+=v[i]-1;
cout<<ans<<'\n';
}
}
C. Gorilla and Permutation (00:25)
손도 못대고 있다가, 예제를 보고 감을 잡았는데,
입력의 n,m,k에 대해서, 식을 최대화 하기 위해선 ∑ f(i)를 최대한 크게, ∑g(i)는 최대한 작게 해야되므로,
순열의 앞엔 n부터 k까지, 순열의 뒤엔 1부터 m까지 배치하고, 그 중간을 아무렇게나 채워주면 우리가 구하고자 하는 순열을 찾아낼 수 있다.
#include<bits/stdc++.h>
using namespace std;
#define X first
#define Y second
#define rep(i,x,y) for(int i=x;i<y;i++)
#define all(x) begin(x),end(x)
#define rall(x) rbegin(x),rend(x)
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef tuple<int,int,int> tiii;
int dx[] = {0,0,1,-1};
int dy[] = {1,-1,0,0};
/*----------------------*/
int main(){
ios::sync_with_stdio(0); cin.tie(0);
int t; cin>>t;
while(t--){
int n,m,k; cin>>n>>m>>k;
vector<int> v;
for(int i=n;i>=k;i--) v.push_back(i);
for(int i=m+1;i<=k-1;i++) v.push_back(i);
for(int i=1;i<=m;i++) v.push_back(i);
rep(i,0,v.size()) cout<<v[i]<<' ';
cout<<'\n';
}
}
D. Test of Love (01:01)
dp로 풀었다. dp[i] = (위치 i까지 도달했을 때, 가능한 최소 수영 거리)
m값이 크지 않아서, O(n*m)시간에 dp 테이블을 채울 수 있고,
최종적으로 목적지에 도달했을때 수영거리와 k값을 비교하여 출력한다.
이때 편의를 위해서 입력의 string의 가장 앞과 가장 뒤에 통나무(L)을 추가해주었다.
#include<bits/stdc++.h>
using namespace std;
#define X first
#define Y second
#define rep(i,x,y) for(int i=x;i<y;i++)
#define all(x) begin(x),end(x)
#define rall(x) rbegin(x),rend(x)
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef tuple<int,int,int> tiii;
int dx[] = {0,0,1,-1};
int dy[] = {1,-1,0,0};
/*----------------------*/
int main(){
ios::sync_with_stdio(0); cin.tie(0);
int t; cin>>t;
while(t--){
int n,m,k; cin>>n>>m>>k;
string str; cin>>str;
str = "L"+str; str+="L";
vector<int> state(str.length(),2e9); //i까지 왔을때 최소 수영 거리
state[0] = 0;
rep(i,0,str.length()){
if(state[i]==2e9) continue;
if(str[i]=='C') continue;
if(str[i]=='L'){
rep(j,1,m+1){
if(i+j >= str.length()) break;
state[i+j] = min(state[i+j], state[i]);
}
}
if(str[i]=='W'){
state[i+1] = min(state[i+1],state[i]+1);
}
}
if(state[str.length()-1]<=k) cout<<"YES\n";
else cout<<"NO\n";
}
}
E. Novice's Mistake (01:40)
처음엔 그냥 브루트포스로 돌려서 제출했다가, 시간초과가 나는바람에... n값이 100밖에 안되니까 그냥 전처리해주었다..
처음 제출 했던 코드는 이거
#include<bits/stdc++.h>
using namespace std;
#define X first
#define Y second
#define rep(i,x,y) for(int i=x;i<y;i++)
#define all(x) begin(x),end(x)
#define rall(x) rbegin(x),rend(x)
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef tuple<int,int,int> tiii;
int dx[] = {0,0,1,-1};
int dy[] = {1,-1,0,0};
/*----------------------*/
int main(){
ios::sync_with_stdio(0); cin.tie(0);
int t; cin>>t;
while(t--){
int n; cin>>n;
string strN = to_string(n);
int l = strN.length();
vector<pii> ans;
//n*a-b 의 최대는 999,999
for(int a=1;a<=10'000;a++){
int r = min(10'000,a*n);
for(int b=1;b<=r;b++){
if(l*a<=b) continue;
if(l*a-b>6) continue;
string str = "";
rep(i,0,a-(b/l)) str+=strN;
rep(i,0,b%l) str.pop_back();
if(stoll(str)==n*a-b){
ans.push_back({a,b});
}
}
}
cout<<ans.size()<<'\n';
rep(i,0,ans.size()) cout<<ans[i].X<<' '<<ans[i].Y<<'\n';
}
이 로직대로 n = 1 ~ 100까지 돌려서 결과값을 구하고, 하드코딩했다..
#include<bits/stdc++.h>
using namespace std;
#define X first
#define Y second
#define rep(i,x,y) for(int i=x;i<y;i++)
#define all(x) begin(x),end(x)
#define rall(x) rbegin(x),rend(x)
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef tuple<int,int,int> tiii;
int dx[] = {0,0,1,-1};
int dy[] = {1,-1,0,0};
/*----------------------*/
vector<pii> ans[101];
void init(){
ans[2] = {{20,18},{219,216},{2218,2214}};
ans[3] = {{165,162}};
ans[4] = {{14,12},{147,144},{1480,1476}};
ans[5] = {{138,135}};
ans[7] = {{129,126}};
ans[10] = {{1262,2519}};
ans[11] = {{12,21},{123,242},{1234,2463}};
ans[13] = {{119,234}};
ans[14] = {{1178,2351}};
ans[16] = {{1154,2303}};
ans[18] = {{1136,2267}};
ans[20] = {{112,220}};
ans[21] = {{11,19}};
ans[24] = {{110,216}};
ans[35] = {{107,210}};
ans[68] = {{104,204}};
ans[90] = {{1033,2061}};
ans[94] = {{1032,2059}};
}
int main(){
ios::sync_with_stdio(0); cin.tie(0);
for(int a=2;a<=10'000;a++){
ans[1].push_back({a,a-1});
}
init();
int t; cin>>t;
while(t--){
int n; cin>>n;
cout<<ans[n].size()<<'\n';
rep(i,0,ans[n].size()){
cout<<ans[n][i].X<<' '<<ans[n][i].Y<<'\n';
}
}
}
AC를 받고나서도.. "아씨.. 이게 맞나?" 싶긴 했지만.. 그래도 맞았으면 된거 아닐까?
나중에 스터디원한테 어떻게 풀었는지 물어봤는데, 관찰 잘 해서 식 뽑아내면 브루트포스 구간을 줄일 수 있다고 한다.
자기 풀이 식 보여주셨는데.. 수학 너무 싫다.. 힝