Isa@Diary

ソフトウェア開発やってます。プログラミングとか、US生活とかについて書きます。

Codeforces #135(Div.2)

Codeforces Graph BFS Greedy

結果

ooxo-(+0/-0) 2708pts 204th
レートは1604->1691(+87)

前回Aしか解けないとかいう失態を犯したので昇格はお預けである。
しかしCFのDiv.1はかなり難しいイメージがあるのでDiv.2がいいのかもしれない…

A(219A)　k-String

出現回数カウントして全部mod n == 0ならok、出力は適当に

B(219B)　Special Offer! Super Price 999 Bourles!

p,dが与えられて\{x|p-d\leq x\leq p\}なるxのうち
下から連続する9の数が最も多いものを返す。複数ある場合は最大のxを返す。

下から1,2,3...個9を並べた数のうち、pより小さい最大の数を調べてそれが上記の範囲に入っているか
調べてやれば良い。

例:p=12345678なら
12345669
12345599
12344999
12339999
12299999
11999999
 9999999
の全てについて調べればよい。

0個の場合を数え忘れていて1WA…。

int main(){
    std::ios_base::sync_with_stdio(false);

    ll p;
    ll d;
    ll ret = -1, cand, base;
    cin >> p >> d;
    for(int i=1;i<18;i++){
        cand = 0;
        base = 1;
        for(int j=0;j<i;j++){
            cand *= 10;
            cand += 9;
            base *= 10;
        }
        cand += (p / base) * base;
        if(cand > p) cand -= base;
        //cerr << cand << endl;
        if(p - cand <= d){
            ret = cand;
        }
    }
    if(ret == -1){
        cout << p << endl;
    }else{
        cout << ret << endl;
    }
}

C(219C)　Color Stripe

初めメモ化再帰っぽいなーと思ったもののうまく書けないので方針転換。->DP解もあったようだ。
終了直前にk=2の場合でhackされてｵﾜﾀ。危ないなと思ったらちゃんとテストしないといけない。
2個以上続いていたら変更しないといけない。
2個の場合はどちらでもいいから変更すればよい。
3個の場合はAAA->AA+Aと考えて初めのペアの後方を変えればいい。3種類以上の文字があれば
必ず左右どちらとも被らない文字が存在する。

あとは帰納的にいけると感じたので前からGreedyに実装。
k=2の場合は
ABABAB...かBABABA...になるのでどっちが小さいか試せばいい。
->あとで通しました。

int n,k;
string str;
int ret = 0;
int main(){
    std::ios_base::sync_with_stdio(false);
    cin >> n >> k >> str;

    int len = str.size();
    if(k == 2){
        int tmp[2] = {0,0};
        string tmpstr = "";
        for(int i=0;i<len;i++){
            if(i%2 == 0){
                if(str[i] == 'A'){
                    tmp[0]++;
                }else{
                    tmp[1]++;
                }
            }else{
                if(str[i] == 'A'){
                    tmp[1]++;
                }else{
                    tmp[0]++;
                }
            }
        }
        if(tmp[0] < tmp[1]){
            ret = tmp[0];
            for(int i=0;i<len;i++){
                tmpstr += (i%2)?'A':'B';
            }
        }else{
            ret = tmp[1];
            for(int i=0;i<len;i++){
                tmpstr += (i%2)?'B':'A';
            }
        }
        str = tmpstr;
    }else{
        for(int i=0;i<len;i++){
            int p = i;
            if(str[p] == str[p+1]){
                ret++;
                for(int i=0;i<k;i++){
                    if(p+2 < len){
                        if(str[p] != i+'A' && str[p+2] != i+'A'){
                            str[p+1] = i+'A';
                        }
                    }else{
                        if(str[p] != i+'A'){
                            str[p+1] = i+'A';
                        }
                    }
                }
            }
        }
    }
    cout << ret << endl;
    cout << str << endl;
}

D(219D)　Choosing Capital for Treeland

まったく同じ事してた。
方向ないんじゃないの？とか思ってたし、

We know that if we don't take the direction of the roads into consideration, we can get from any city to any other one.

これ読み落としてて(正確には読んだけど忘れた)連結じゃなかったらどうしよう、とか思ってた。

BFS1回でテーブルを作ったあとそのテーブルを舐めればいいのでO(n)?
BFSでやる作業は

  • A)任意の頂点(1でよい)をcapitalとしたときに何本inverseする必要があるかを計算
  • B)全ての頂点に対して,0から初めて始点から順方向の辺を通ったら+1,逆方向の辺を通ったら-1

という値を計算しておく。例として

頂点index  1 <----- 2 <----- 3 -----> 4
A          2
B[index]   0        -1       -2      -1

こういうものができる。Bの値は「1から頂点kにcapitalを動かしたときに何本inverseすべき辺の数が変化するか」なので、A+B[k]の値がkを頂点にした時にinverseする必要のある本数になる。
あとは適当に。

vector<pair<int,int> > edges[200001];
vector<int> vs;
int costs[200001];
int diff[200001];
int res = 1 << 29;
int n;
int main(){
    std::ios_base::sync_with_stdio(false);
    int s,t;
    cin >> n;
    for(int i=0;i<n-1;i++){
        cin >> s >> t;
        edges[s].PB(MP(t,0));
        edges[t].PB(MP(s,1));
    }

    deque<pair<int,int> > q;
    bool visited[n+1];
    int pos;
    int tmpcost;
    int cost = 0;
    memset(visited, false, sizeof(visited));
    q.PB(MP(1,0));
    while(!q.empty()){
        pos = q.front().first;
        tmpcost = q.front().second;
        q.pop_front();
        visited[pos] = true;
        diff[pos] = tmpcost;
        for(int i=0;i<(int)edges[pos].size();i++){
            if(visited[edges[pos][i].first] == false){
                if(edges[pos][i].second == 1){
                    q.PB(MP(edges[pos][i].first,tmpcost-1));
                    cost++;
                }else{
                    q.PB(MP(edges[pos][i].first,tmpcost+1));
                }
            }
        }
    }
    int mincost = 1<< 29;
    for(int i=1;i<n+1;i++){
        mincost = min(mincost, cost + diff[i]);
    }
    for(int i=1;i<n+1;i++){
        if(cost + diff[i] == mincost){
            vs.PB(i);
        }
    }
    sort(vs.begin(), vs.end());
    cout << mincost << endl;
    for(int i=0;i<(int)vs.size();i++){
        if(i) cout << " ";
        cout << vs[i];
    }
    cout << endl;
}