20230805 업다운 랜디

s#100.. !solved_by:p_jun *g5

30분 3문제

 

G5 16925 문자열 추측 + 22분 19초

내가 너무 싫어하는 구현, 문자열 문제

접미사와 접두사 S, P 인걸 반대로 출력해 시간을 너무 날렸다

맞왜틀로 시간만 태웠다

그냥 나온대로 구현하면 된다

#include <iostream>
#include <iomanip>
#include <algorithm>
#include <vector>
#include <string>
#include <cstring>
#include <stack>
#include <queue>
#include <deque>
#include<set>
#include<map>
#include<cassert>
using namespace std;
using ll = long long;
#define MOD 1000000007
const ll INF = 987654321;
const int MX = 500005;

int n;
vector<pair<string, int>> v;

int is_p(string a, string b) {
    for (int i = 0; i < a.length(); i++) {
        if (b[i] != a[i]) return 0;
    }
    return 1;
}

int is_s(string a, string b) {
    for (int i = 0; i < a.length(); i++) {
        if (b[b.length() - i - 1] != a[a.length() - i - 1]) return 0;
    }
    return 1;
}

void sol(string s) {
    string ans = "";
    ans.resize(n * 2 - 2);
    for (int i = 0; i < n * 2 - 2; i += 2) {
        if (is_p(v[i].first, s) && is_s(v[i + 1].first, s)) {
            ans[v[i].second] = 'P';
            ans[v[i + 1].second] = 'S';
        }
        else if (is_s(v[i].first, s) && is_p(v[i + 1].first, s)) {
            ans[v[i].second] = 'S';
            ans[v[i + 1].second] = 'P';
        }
        else return;
    }
    cout << s << '\n';
    cout << ans << '\n';
    exit(0);
}

bool cmp(pair<string, int>& a, pair<string, int>& b) {
    return a.first.length() < b.first.length();
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0), cout.tie(0);
    cin >> n;
    v.resize(n * 2 - 2);
    for (int i = 0; i < n * 2 - 2; i++) {
        cin >> v[i].first;
        v[i].second = i;
    }
    sort(v.begin(), v.end(), cmp);
    string tmp1 = v[2 * n - 3].first, tmp2 = v[2 * n - 4].first;
    string str1 = tmp1 + tmp2.back(), str2 = tmp2 + tmp1.back();
    sol(str1);
    sol(str2);
}

S1 20167 꿈틀꿈틀 호석 애벌레 - 기능성 -12분 22초

그냥 문제 지문이 뭔가 이상하다

다 소화시키면 연속으로 못 먹는 줄 알고 시간을 날렸다

구현 좀 더 이쁘게 가능할거 같은데 귀찮으니 패스

#include <iostream>
#include <iomanip>
#include <algorithm>
#include <vector>
#include <string>
#include <cstring>
#include <stack>
#include <queue>
#include <deque>
#include<set>
#include<map>
#include<cassert>
using namespace std;
using ll = long long;
#define MOD 1000000007
const ll INF = 987654321;
const int MX = 500005;

int n, k;
vector<int> v;

int sol(int pos, int b, int f) {
    if (pos == n) return max(0, b - k);
    if (f == 1) {
        b += v[pos];
        if (b >= k)
            return b - k + sol(pos + 1, 0, 2);
        return sol(pos + 1, b, 1);
    }
    int ret = 0;
    if (v[pos] >= k) return max(sol(pos + 1, 0, 0) + v[pos] - k, sol(pos + 1, b, 0));
    return max(sol(pos + 1, b + v[pos], 1), sol(pos + 1, b, 0));
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0), cout.tie(0);
    cin >> n >> k;
    v.resize(n);
    for (int i = 0; i < n; i++) cin >> v[i];
    cout << sol(0, 0, 0) << '\n';
}

G5 9011 순서 -21분 27초

그냥 보고 이거네 하고 풀었다

#include <iostream>
#include <iomanip>
#include <algorithm>
#include <vector>
#include <string>
#include <cstring>
#include <stack>
#include <queue>
#include <deque>
#include<set>
#include<map>
#include<cassert>
using namespace std;
using ll = long long;
#define MOD 1000000007
const ll INF = 987654321;
const int MX = 500005;

void sol() {
    int n; cin >> n;
    vector<int> v(n);
    vector<int> p(n + 1);
    for (int i = 0; i < n; i++) cin >> v[i];
    reverse(v.begin(), v.end());
    vector<int> ans(n);
    for (int i = 0; i < n; i++) {
        int cnt = 0;
        int num = 0;
        for (int j = 0; j < n; j++) {
            if (cnt == v[i]) {
                for (int k = j; k < n; k++) {
                    if (p[k + 1]) continue;
                    num = k + 1;
                    break;
                }
                break;
            }
            if (!p[j + 1]) cnt++;
        }
        p[num] = 1;
        if (!num) {
            cout << "IMPOSSIBLE" << '\n';
            return;
        }
        ans[n - 1 - i] = num;
    }
    for (int i = 0; i < n; i++) cout << ans[i] << " ";
    cout << '\n';
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0), cout.tie(0);
    int tc; cin >> tc;
    while (tc--) sol();
}