20230806 업다운 랜디

s#100.. !solved_by:p_jun *g4

30분 3문제

 

G4 16472 고냥이 - 7분

두 포인터 좀 헷걸려서 시간을 많이 날렸다

#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 arr[30];

int main() {
    ios::sync_with_stdio(0); cin.tie(0), cout.tie(0);
    int n; cin >> n;
    string s; cin >> s;
    int l = 0, r = 0;
    int ans = 0;
    int cnt = 0;
    while (r < s.length()) {
        if (cnt <= n) {
            ans = max(ans, r - l);
            if (!arr[s[r] - 'a']) cnt++;
            arr[s[r] - 'a']++;
            r++;
        }
        else {
            arr[s[l] - 'a']--;
            if (!arr[s[l] - 'a']) cnt--;
            l++;
        }
    }
    if (cnt <= n) ans = max(ans, r - l);
    cout << ans << '\n';
}

G3 2571 색종이 - 3 -12분 30초

이상하게 인덱싱 실수를 해서 시간을 많이 날렸다

#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 arr[105][105];
int cal(int x1, int y1, int x2, int y2) {
    return arr[x1][y1] - arr[x2 - 1][y1] - arr[x1][y2 - 1] + arr[x2 - 1][y2 - 1];
}
int main() {
    ios::sync_with_stdio(0); cin.tie(0), cout.tie(0);
    int n; cin >> n;
    for (int i = 0; i < n; i++) {
        int x, y; cin >> x >> y;
        for (int j = x; j < x + 10; j++) for (int k = y; k < y + 10; k++)
            arr[j][k] = 1;
    }

    for (int i = 1; i < 101; i++) {
        for (int j = 1; j < 101; j++) arr[j][i] += arr[j - 1][i];
        for (int j = 1; j < 101; j++) arr[j][i] += arr[j][i - 1];
    }
    int ans = 0;
    for (int x1 = 1; x1 < 101; x1++) for (int y1 = 1; y1 < 101; y1++) for (int x2 = x1; x2 < 101; x2++) for (int y2 = y1; y2 < 101; y2++)
        if (cal(x1, y1, x2, y2) == (x1 - x2 + 1) * (y1 - y2 + 1))
            ans = max(ans, (x1 - x2 + 1) * (y1 - y2 + 1));
    cout << ans << '\n';
}

G2 9007 카누 선수 - 9분 3초

18114 블랙 프라이데이 이 문제가 기억나서 쉽게 접근할 수 있었다

구현에 걸리는 시간과 정확도가 부족한게 느껴진다

#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 k, n; cin >> k >> n;
    vector<int> v[4];
    for (int i = 0; i < 4; i++) v[i].resize(n);
    for (int k = 0; k < 4; k++) for (int i = 0; i < n; i++)
        cin >> v[k][i];

    vector<int> t;
    for (int i = 0; i < n; i++) for (int j = 0; j < n; j++)
        t.push_back(v[0][i] + v[1][j]);
    sort(t.begin(), t.end());

    int ans = t[0] + v[2][0] + v[3][0];
    for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) {
        int tmp = v[2][i] + v[3][j];
        int rm = k - tmp;
        int idx = lower_bound(t.begin(), t.end(), rm) - t.begin();
        int midx = idx - 1;

        if (idx < n * n && idx >= 0) {
            int now = tmp + t[idx];
            int g = abs(now - k);
            int val = abs(ans - k);
            if (val > g) ans = now;
            if (val == g) ans = min(ans, now);
        }
        if (midx < n * n && midx >= 0) {
            int now = tmp + t[midx];
            int g = abs(now - k);
            int val = abs(ans - k);
            if (val > g) ans = now;
            if (val == g) ans = min(ans, now);
        }
    }
    cout << ans << '\n';
}

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