TIOJ-2019

,

D.番茄大戰爭

https://tioj.ck.tp.edu.tw/problems/2019

Description

兩個人在玩剪刀石頭布，而他們兩個人玩了$T$個回合。兩個人（此處稱為小奕和小安）各自有一個「策略」，分別為兩個字串$A$和$B$。兩個字串皆由R、P、S三個字元組成，分別代表小奕和小安會出石頭、布、剪刀。兩個人都會根據他們的「策略」出題，在第$i$個回合，小奕將會出$A _ {i \mod {|A|}}$，而小安將出$B _ {i \mod{|B|}}$，從$i = 0$開始。請輸出：經過$T$個回合後，兩人分別贏了幾局，平手了幾局。

保證滿足：$1 \leq T \leq 10^9$，$1 \leq |A|, |B| \leq 10^6$，且$A, B$由R、P、S三個字元組成。

Solution

首先，看到$1 \leq T \leq 10^9$當然想說直接給他寫個$\mathcal{O}(T)$，寫了五分鐘之後傳上去——AC——了前幾筆，之後就TLE了。所以，當然就來想怪做法嘍！

先假設$|A| \leq |B|$。第一個想法就是，對於$A$裏頭的每一個字元$A_i$，我都看一次我會遇到哪些字元（$B_i, B _ {i + |A|}, B _ {i + 2\times|A|}, \dots$，也就是所有滿足$(i + k|A|) \mod{|B|} \leq T$的$B _ {(i + k|A|)\mod{|B|}}$，然後再$\mathcal{O}(1)$更新答案。這樣複雜度依然為$\mathcal{O}(T)$，因為還是每一個時間點都有戳到一次，只是改變順序而已了。不過！這個順序很重要，因為可以優化！

若我們看$A_i$，我們先考慮它會遇到那些$B$的字元$$B_i, B _ {i + |A|}, B _ {i + 2\times|A|}, \dots $$，也就是所有的$B _ {i + k|A| \mod{|B|}}$。可以知道，這樣分可以將$B$的所有字元分成若干個相斥的群組$G_t$！具體做法就是，先看$A_i$，如果$B_i$尚未在一個群組裡面，就創立一個新的群組然後將所有的$B _ {i + k|A|}$加進去這個群組裡面。現在，就想要用這個新的資料儲存方式來加快我們的運算。

同樣的，我們將注意力集中於$A$的字元$A_i$。如果知道這個字元會被掃到幾次（假設是$k$），那是不是可以從$B_i$在其所屬的群組$G$的位子開始爬$k$次（超過邊界就回到$0$）來計算？這樣就會有累加的感覺了，所以下一步就是——對各個群組計算其各個出法（剪刀石頭布）的前綴！所以，我們可以定義$S(i, j, k)$為第$i$個群組中，符號為$j$（以$0,1,2$表示，對應到剪刀石頭布各一），前$k$個位置的前綴和。

大致的想法知道了，就可以開始去處理細節了！這題細節頗多，彷彿魚刺，得小心！不過，越多魚刺的魚往往更為鮮甜，勿以此而退縮！

AC code

對不起有點亂qwq 至少目前跑的比baluteshih快啦XD

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103

#include <iostream>
#include <string.h>
#include <utility>
#include <vector>
#define pii pair<int,int>
#define F first
#define S second
#define ericxiao ios_base::sync_with_stdio(0);cin.tie(0);
using namespace std;

const int maxN = 1e6 + 10;

int T, gc = 0;
string a, b;

inline int getId(char c){
    if(c == 'R') return 0;
    if(c == 'P') return 1;
    if(c == 'S') return 2;
    return -1;
}

vector<pii> where;
vector<int> groups[maxN];
vector<int> pre[maxN][3]; //ijk: ith group, jth symbol, kth prefix
int main(){
    ericxiao;
    cin >> T >> a >> b;
    bool hS = false;
    if(a.length() > b.length()){
        swap(a, b);
        hS = true;
    }
    where.resize(b.length());
    fill(where.begin(), where.end(), pii({-1, -1}));
    int cg, ind, w = 0, l = 0, d = 0;
    for(int i = 0; i < a.length(); i++){
        if(where[i].F != -1) continue;
        cg = gc++, ind = i;
        while(where[ind].F == -1){
            where[ind] = {cg, groups[cg].size()};
            groups[cg].push_back(ind);
            ind = ( ind + a.length() ) % b.length();
        }
    }
    for(int g = 0; g < gc; g++){
        pre[g][0].resize(groups[g].size());
        pre[g][1].resize(groups[g].size());
        pre[g][2].resize(groups[g].size());
        pre[g][0][0] = pre[g][1][0] = pre[g][2][0] = 0;
        pre[g][getId(b[groups[g][0]])][0]++;
        for(int i = 1; i < groups[g].size(); i++){
            for(int j = 0; j < 3; j++) pre[g][j][i] = pre[g][j][i - 1];
            pre[g][getId(b[groups[g][i]])][i]++;
        }
    }
    int jf, tlt, rem, frqs[3], myId;
    for(int i = 0; i < a.length(); i++){
        if(i >= T) continue;
        jf = (T - i - 1) / a.length() + 1;
        //ijk: ith group, jth symbol, kth prefix
        //group index: groups[where[i].F]
        //position in group: where[i].S
        //want to loop forward (T - i) / a.length() times
        //total loop time:
        /*
        (group.size() - [group pos]) + tlt * |group| <= jf
        tlt = (jf - group.size() + [group pos]) / |group|
        remaining number to go: jf - ((group.size() - [group pos]) + tlt * |group|)
        */
        if(jf + where[i].S >= groups[where[i].F].size()){
            tlt = (jf - (groups[where[i].F].size() - where[i].S)) / groups[where[i].F].size();
            rem = jf - (groups[where[i].F].size() - where[i].S + tlt * groups[where[i].F].size());
            for(int j = 0; j < 3; j++){
                frqs[j] = pre[where[i].F][j][groups[where[i].F].size() - 1] * (tlt + 1) + (rem ? pre[where[i].F][j][rem - 1] : 0) - (where[i].S ? pre[where[i].F][j][where[i].S - 1] : 0);
            }
        } else {
            for(int j = 0; j < 3; j++){
                frqs[j] = pre[where[i].F][j][jf + where[i].S - 1] - (where[i].S ? pre[where[i].F][j][where[i].S - 1] : 0);
            }
        }

        myId = getId(a[i]);
        w += frqs[(myId + 2) % 3];
        l += frqs[(myId + 1) % 3];
        d += frqs[(myId) % 3];
    }
    if(!hS){
        cout << w << " " << l << " " << d << endl;
    } else {
        cout << l << " " << w << " " << d << endl;
    }

    /*
    100
    RRR
    PPPP

    1
    S
    RPPPSPPRSS
    */
}
comments powered by Disqus