[AtCoder] ABC 344 후기

https://atcoder.jp/contests/abc344/tasks

Tasks - Toyota Programming Contest 2024#3（AtCoder Beginner Contest 344）

 

---

2024.03.09

개강하니까 되게 뭐가 바쁘다..

오전 수업 때문에 잠을 일찍 자다보니 코포도 거의 못하고... 버츄얼이라도 돌릴까 해봤는데.. 뭐가 할게 많다 허허..

그래도 ABC는 매주 토요일 밤이다 보니까 주말 약속만 없으면 웬만하면 할 수 있을 듯 하다.

더군다나 개인 프로젝트도 하고있다 보니까.. PS에 시간을 쏟기가 쉽지 않음 ;

 

그래도 오늘은 ABC 첫 5솔을 했다! 레이팅은 +140!

근데 자꾸 이상한짓을 많이해서 어이없게 패널티를 받아가지구... 조금 아쉽긴하다.. 

 

특히 마지막 문제는 계속 고민하다가 끝나기 2분전에 제출했다 ㄷㄷㄷ 틀렸으면 진짜 오열했을 듯 ㅋㅋ

앳코더도 얼른 그린 찍고싶당 ㅎㅎㅎ

---

A. Spoiler (09:59)

이상하게 삽질했던 문제;

split 함수 구현해서 첫번째랑 마지막거만 출력하게 했는데 자꾸 런타임 에러가 나는거다...

그래서 걍 문자열 돌면서 | 나오면 출력안하고 다시 | 이 나오면 출력하도록 했다...

패널티 2개 받은거 다 RE다....

 

#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++)
typedef long long ll;
typedef pair<int,int> pii;
int dx[] = {0,0,1,-1};
int dy[] = {1,-1,0,0};
/*------------------------------*/

int main(){
    ios::sync_with_stdio(0); cin.tie(0);
    string str; cin>>str;
    bool flag = 0;
    rep(i,0,str.length()){
        if(str[i]=='|'){
            int j=i+1;
            while(str[j]!='|') j++;
            i=j;
        }
        else cout<<str[i];

    }

}

 

 

---

B. Delimiter (11:33)

이건 그래도 삽질 안했다 ? 

그냥 다 입력받고 reverse 때리면 끝

 

#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++)
typedef long long ll;
typedef pair<int,int> pii;
int dx[] = {0,0,1,-1};
int dy[] = {1,-1,0,0};
/*------------------------------*/

int main(){
    ios::sync_with_stdio(0); cin.tie(0);
    vector<int> v;
    int x;
    while(1){
        cin>>x;
        v.push_back(x);
        if(x==0) break;
    }
    reverse(v.begin(),v.end());
    rep(i,0,v.size()) cout<<v[i]<<'\n';

}

 

 

---

C. A+B+C (23:58)

그냥 브루트포스.

a,b,c 배열에 대해서 3중 for문으로 합을 set에 저장하고, 입력에 맞춰서 yes, no 출력

다른 방법이 있을 줄 알았는데, a,b,c값이 작아서 충분히 돌아가더라..

#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++)
typedef long long ll;
typedef pair<int,int> pii;
int dx[] = {0,0,1,-1};
int dy[] = {1,-1,0,0};
/*------------------------------*/

int main(){
    ios::sync_with_stdio(0); cin.tie(0);
    ll a,b,c;
    vector<ll> va,vb,vc;
    cin>>a; va.resize(a);
    rep(i,0,a) cin>>va[i];
    cin>>b; vb.resize(b);
    rep(i,0,b) cin>>vb[i];
    cin>>c; vc.resize(c);
    rep(i,0,c) cin>>vc[i];

    set<ll> s;
    rep(i,0,a) rep(j,0,b) rep(k,0,c) s.insert(va[i]+vb[j]+vc[k]);

    ll x; cin>>x;
    rep(i,0,x){
        ll val; cin>>val;
        if(s.find(val)==s.end()) cout<<"No\n";
        else cout<<"Yes\n";
    }
    

}

 

 

---

D. String Bags (50:26)

백트래킹인데 DP?를 곁들인..

처음엔 그냥 무지성 백트래킹 돌렸는데 TLE가 났다.

근데 도무지 다른 방법이 생각이 안나서 DP로 가지치기 좀 하니까 AC받넹 ㅎ

 

재귀함수의 인자는 "현재 상태에서 stridx까지 만들었고, idx번째 가방을 탐색중이며, pay만큼 돈을 냈다."를 의미한다.

그리고 cache배열로 이미 방문한 상태에 대해서 가지치기를 진행하였다.

 

근데 코드를 잘못짜는 바람에.. 2번 TLE나고... 심지어 제출을 C번으로 잘못해서 C번에 패널티도 생겼다...

코포는 첫테케 통과 못하면 패널티 안주던데 앳코더는.... 흠ㅠㅠㅠㅠㅠㅠㅠ

 

#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++)
typedef long long ll;
typedef pair<int,int> pii;
int dx[] = {0,0,1,-1};
int dy[] = {1,-1,0,0};
/*------------------------------*/

string str;
int n;
int ans = 2e9;
vector<set<string>> v;
bool chk(int stridx, string pat){
    if(pat.length() > str.length()+stridx) return 0;
    for(int i=0;i<pat.length();i++){
        if(str[stridx+i]!=pat[i]) return 0;
    }
    return 1;
}
int cache[101][101][101];
void func(int stridx, int idx, int pay){
    if(idx==n){
        if(stridx!=str.length()) return;
        ans = min(ans,pay);
        return;
    }
    int& ret = cache[stridx][idx][pay];
    if(ret!=-1) return;

    ret = 1;
    for(auto cur : v[idx]){
        if(chk(stridx, cur)){
            func(stridx+cur.length(),idx+1,pay+1);
        }
    }
    func(stridx,idx+1,pay);
}

int main(){
    ios::sync_with_stdio(0); cin.tie(0);
    memset(cache,-1,sizeof(cache));
    cin>>str;
    cin>>n;
    v.resize(n);
    rep(i,0,n){
        int x; cin>>x;
        rep(j,0,x){
            string s; cin>>s;
            v[i].insert(s);
        }
    } 
    func(0,0,0);
    if(ans==2e9) cout<<-1<<'\n';
    else cout<<ans<<'\n';

}

 

 

---

E. Insert or Erase (98:33)

지금까지 PS하면서 링크드 리스트를 한번도 안써왔다가 이번문제에서 처음 썼다...

List에 함수가 뭐가 있는지도 몰라서 구글링하면서 풀었다 ;;;

 

map에 val이라는 원소가 list의 어느 위치에 있는지에 대한 포인터를 저장하고, 

쿼리에 따라서 포인터도 잘 바꿔주면 됐다.

 

링크드리스트를 알면 쉽게 풀고, 아니라면 어려웠을 듯한 문제였다.

체감상 D보다 E가 더 쉬웠던 것 같다.

#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++)
typedef long long ll;
typedef pair<int,int> pii;
int dx[] = {0,0,1,-1};
int dy[] = {1,-1,0,0};
/*------------------------------*/

int main(){
    ios::sync_with_stdio(0); cin.tie(0);
    int n; cin>>n;
    list<int> li;
    map<int,list<int>::iterator> ptr;
    rep(i,0,n){
        int x;cin>>x;
        li.push_back(x);
        ptr[x] = prev(li.end());
    }


    int m; cin>>m;
    rep(i,0,m){
        int x; cin>>x;
        if(x==1){
            int a,b;
            cin>>a>>b;
            li.insert(next(ptr[a]),b);
            ptr[b] = (next(ptr[a]));
        }
        else{
            int a;
            cin>>a;
            li.erase(ptr[a]);
            ptr[a]=li.end();
        }

    }
    for(auto i=li.begin();i!=li.end();i++){
        cout<<*i<<' ';
    }
    cout<<'\n';

}