P4 16975 수열과 쿼리 21

19분 6초
구간 변경이 요구되는 문제다. 느리게 갱신되는 세그먼트 트리를 사용하면 풀릴 것이 보였다.

using pll = pair<ll,ll>;
#define value first
#define lazy second

class segment {
public:
    vector<pll> tree; //tree[node] := a[start ~ end] 의 합, first: sum, second: lazy

    segment() {}
    segment(int size) {
        this->resize(size);
    }
    void resize(int size) {
        size = (int) floor(log2(size)) + 2;
        size = pow(2, size);
        tree.resize(size, pll(0,0));
    }
    ll init(vector<ll> &a, int node, int start, int end) {
        if(start == end) return tree[node].value = a[start];
        else return tree[node].value = init(a, 2 * node, start, (start + end) / 2) +
                                 init(a, 2 * node + 1, (start + end) / 2 + 1, end);
    }
    ll sum(int node, int start, int end, int left, int right) {
        if(right < start || end < left) return 0;

        if(tree[node].lazy != 0) {
            tree[node].value += tree[node].lazy * (end - start + 1);
            if (start != end) {
                tree[2 * node].lazy += tree[node].lazy;
                tree[2 * node + 1].lazy += tree[node].lazy;
            }
            tree[node].lazy = 0;
        }
        if(left <= start && end <= right) return tree[node].value;
        return sum(node * 2, start, (start + end) / 2, left, right) +
               sum(node * 2 + 1, (start + end) / 2 + 1, end, left, right);
    }
    void update(int node, int start, int end, int left, int right, ll diff) {
        if(right < start || end < left) return;
        if(left <= start && end <= right) tree[node].lazy += diff;
        else if(start != end) {
            update(node * 2, start, (start + end) / 2, left, right, diff);
            update(node * 2 + 1, (start + end) / 2 + 1, end, left, right, diff);
        }
    }
};

P4 5670 휴대폰 자판

1시간 34분 36초
보자마자 Trie인 걸 알았으나 일반적인 정적 배열로 child를 만들면 메모리 초과가 된다. vector나 unordered_map으로 구현하면 이를 해결할 수 있다.

class Trie {
public:
    bool terminal = false;
    unordered_map<char, Trie*> child;

    void insert(const char* key) {
        if(*key == 0) terminal = true;
        else {
            if (!child[*key]) child[*key] = new Trie();
            child[*key]->insert(key + 1);
        }
    }
    int solve(const char* key) {
        if(*key == 0) return 0;
        return child[*key]->solve(key+1) + (this->child.size() + this->terminal > 1);
    }
};

map으로 뻘짓을 많이 해서 시간이 오래 걸렸다. 앞으로도 Trie를 사용할 때 정적배열이 아닌 map을 사용하는 것이 좋을 듯 하다.

추가로, 소수점 fix할 때 사용하는 코드가 있다. 소수점 2번째 자리까지 반올림하여 나타내는 코드다. 이걸 제대로 못 해서 솔브를 못 받을 뻔 했다.

cout << fixed; cout.precision(2);

P4 14939 불 끄기

1시간 31분 39초
전구의 상태를 저장하는 비트마스킹으로 푸는 문제였다.
생각 자체는 빨리 했으나 구현력이 부족해서 시간을 많이 소모했다. grid 격자 이동에 좀 취약한 듯 하다.
왼쪽 위 -> 오른쪽 아래로만 이동한다고 규칙을 정한다.
(i,j)의 전구 스위치를 누른다고 했을 때가 (i-1,j)의 전구를 변화시킬 수 있는 마지막 찬스임을 생각하면 어렵지 않다. (i-1,j) ~ (i+1,j) 까지의 on/off를 비트마스킹을 저장해서 넘겨줬다.
위에서의 제한(규칙)으로 인해 경우의 수가 상당히 많이 줄어들기 때문에 dp를 사용할 필요가 없다.(사실 메모리 문제 때문에 쓸 수도 없다.)
나머지는 비트마스킹과 맵 이동을 잘 구현할 수 있는가의 문제다.

bool grid[10][10];

int add(int here, int bulb) {
    int ni = (here+11) / 10, nj = (here+11) % 10;
    int nv = (ni >= 10) ? 0 : grid[ni][nj];
    return (bulb)/2 + nv*(1<<20);
}
// 전구 on-off는 xor 연산을 이용하면 간단해진다. 
// 0으로 xor을 하면 원래 값을 내보내주고, 1로 xor을 하면 반대값이 되기 때문에
// 값을 변하게 하고 싶은 위치만 1을 넣고 xor을 하면 된다.
int turn(int here, int bulb) {
    int i = here/10, j = here%10;
    int turnBulb = (1<<0) + (1<<9) + (1<<10) + (1<<11) + (1<<20);
    if(i == 0) turnBulb -= (1<<0);
    if(j == 0) turnBulb -= (1<<9);
    if(i == 9) turnBulb -= (1<<20);
    if(j == 9) turnBulb -= (1<<11);
    return add(here, bulb ^ turnBulb);
}

// bulb는 2^21 크기의 이진수(0~20)
int solve(int here, int bulb) {
    int i = here/10;
    if(i == 10) return (bulb == 0) ? 0 : INF; // base
    if(i == 0) return min(solve(here+1, add(here, bulb)), solve(here+1, turn(here, bulb)) + 1); // first line
    bool on = bulb % 2; // 윗칸 on-off 여부 확인
    if(on) {
        return solve(here+1, turn(here, bulb)) + 1;
    }
    else return solve(here+1, add(here,bulb));
}