IPSC 2015 Problem S – Solitaire

接龍啊…

小測資照著題目做就可以過，但大測資不行，必須優化，可以優化成 O(n)。

該如何優化呢？為了解釋，我們先簡化問題，不考慮花色，於是題目變成：

一連續正整數序列，打亂後，求最少須要「遍歷序列」幾次才可以整理好所有數字。

例如：

4 1 8 2 5 6 3 7 9

需要三次遍歷，分別為：

1 2 3
4 5 6 7
8 9

根據題意，一次遍歷挑出來的這些數字一定會是連續的，所以可以有這個想法：

從左到右處理每一項，當在處理 a[i] 時，如果 a[i]-1 已經出現過了，那麼 a[i] 必會在 a[i]-1 被挑出去的那次遍歷裡被挑出去。

這可以用 開一個大陣列，記錄各個值有沒有出現過 的方法來得到 O(1) 的時間複雜度，也就是說，用空間換取時間。

再來我們得找出每次遍歷的第一個數字是誰。跟前述同樣的想法：

在處理 a[i] 時，如果 a[i] - 1 還沒出現過，那麼它就是這次遍歷的第一個值。

因為每次遍歷的第一個數字，必為上次遍歷挑出來的那些數字中，最大的那個數字再加一。如果要整理好 a[i] ，則必需要增加一次遍歷，才會／能把 a[i] 挑出來。

綜合上述兩個論述，及第一次遍歷第一個數字必為 1 的事實，想得知最少要遍歷幾次，可以寫成以下式子：

int cnt = 0;
bool ob[MAX_VALUE]; // occurred before, each item default false

for (int& x : data) {
    ob[x] = true;
    
	if (x == 1)
		cnt++;
	else if (ob[x-1])
		continue;
	else
		cnt++;
}

我們再考慮原題目，可以發現顏色之間互不影響，所以可以直接改寫，最後的結果就是各顏色所需最少遍歷次數的最大值，程式碼請參文末。

Code

naive:

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

typedef pair<char, int> P;

int main() {
    ios::sync_with_stdio(false);

    int T;
    cin >> T;

    while (T--) {
        int N;
        cin >> N;

        vector<P> data(N);

        for (int i = 0; i < 4 * N; i++) {
            string inp;
            cin >> inp;

            int rank = stoi(inp.substr(1, inp.length() - 1));
            char color = inp[0];

            data.push_back(P(color, rank));
        }

        int s_slot = 0;
        int h_slot = 0;
        int d_slot = 0;
        int c_slot = 0;

        int cnt = 0;
        while (s_slot + h_slot + d_slot + c_slot != 4*N) {
            vector<P> discard;

            for (P& card : data) {
                int rank = card.second;
                char color = card.first;

                if (color == 'S' && s_slot == rank - 1)
                    s_slot++;
                else if (color == 'H' && h_slot == rank - 1)
                    h_slot++;
                else if (color == 'D' && d_slot == rank - 1)
                    d_slot++;
                else if (color == 'C' && c_slot == rank - 1)
                    c_slot++;
                else
                    discard.push_back(card);
            }

            cnt++;
            data = discard;
        }

        cout << cnt << "\n";
    }

    return 0;
}

AC Code

#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
#include <algorithm>

using namespace std;

bool ob[4][150000+1];
int cnt[4];

int main() {
    ios::sync_with_stdio(false);

    int T;
    cin >> T;

    while (T--) {
        int N;
        cin >> N;

        memset(ob, false, sizeof(ob));
        memset(cnt, 0, sizeof(cnt));

        for (int i = 0; i < 4 * N; i++) {
            string inp;
            cin >> inp;

            const static string colors = "SHDC";
            int color = colors.find(inp[0]);
            int rank = stoi(inp.substr(1, inp.length() - 1));

            ob[color][rank] = true;

            if (rank == 1)
                cnt[color]++;
            else if (ob[color][rank-1])
                continue;
            else
                cnt[color]++;
        }

        cout << *max_element(cnt, cnt+4) << "\n";
    }

    return 0;
}

amoshyc/ipsc_2015_s.md

IPSC 2015 Problem S – Solitaire

Code