SRM680 Round1 Div.2

Medまで早解き出来たからHardに挑戦…と30分程度格闘してイメージが湧きかけたところでMedの深刻なバグに気づいて修正。

残り3分で提出でした。おかげでMedが150点に…

Easy BearPair

問題概要

Bear Limak loves algorithms, especially the ones with words and strings.

Limak's friend recently entered a programming competition and wrote a program. The program contains a string constant s. Limak would now like to challenge the program by making it exceed the time limit. To do that, he must find two different characters in s that are as far apart as possible.

  • Formally, Limak must find two integers i and j with the following properties:
  • Both i and j must be valid indices into s. That is, both numbers must be between 0 and n-1, inclusive, where n is the length of s.
  • The characters s[i] and s[j] must be different.
  • The difference between i and j must be as large as possible.

You are given the string s. If Limak cannot choose any integers with the required properties, return -1. Otherwise, return the largest possible difference between i and j.

文字列sの中で異なる2文字の組み合わせで最も距離の遠いものの距離を答えよ。

解法

自分は各文字最初に出てきた位置と最後に出てきた位置を調べてから距離を出す、というものすごく面倒なことをしました。

|s|≦50なので2重ループを回して、s[i]!=s[j]なら距離を更新すれば終わりです。

#include <bits/stdc++.h>
using namespace std;
class BearPair{
    public:
    int fst[30],sec[30];
    int bigDistance(string s){
        int n=s.size();
        for(int i=0;i<30;i++){
            fst[i]=n;   sec[i]=-1;
        }
        for(int i=0;i<n;i++){
            int num=s[i]-'a';
            fst[num]=min(fst[num],i);
            sec[num]=max(sec[num],i);
        }
        int ret=-1;
        for(int i=0;i<30;i++){
            if(fst[i]==n) continue;
            for(int j=0;j<30;j++){
                if(fst[j]==n) continue;
                if(i==j)      continue;
                ret=max(ret,sec[j]-fst[i]);
            }
        }
        return ret;
    }
};

まあ、こちらの方がO(n)なので文字数が1万字を超えるようならこちらで。

Med BearChairs

問題概要

I guess you have never seen a bear eating at a table. The reason is simple: bears don't use tables. However, they may sometimes decide to sit on a chair while eating.

Bear Limak is a waiter in a huge restaurant for bears. The restaurant has infinitely many chairs. The chairs are arranged in a single long row. In order, they are numbered using all positive integers: 1, 2, 3, ... Chair number 1 is closest to the entrance to the restaurant.

A bear takes a lot of space while eating, and all bears value their personal space. Limak knows that there is a universal constant d with the following meaning: Whenever two bears sit on chairs, their chair numbers must differ by d or more. For example, if d=10, you can have two bears in chairs 47 and 57, but you cannot have bears in chairs 47 and 56.

The restaurant just opened for the day and all chairs are empty. During the day exactly N guests arrived, one at a time. Whenever a guest arrived, Limak assigned them a chair. Each guest stayed in the restaurant in their assigned chair until the end of the day.

Generally, guests don't like to be seated close to the entrance because of the noise from the street. You are given a vector atLeast with N elements: one for each guest, in order. For each i from 0 to N-1, guest i came with a request: "My chair number must be greater than or equal to atLeast[i]."

When seating a guest, Limak always assigns them the smallest available chair number. (That is, the smallest chair number that matches the guest's request and is at least d away from each of the bears who are already in the restaurant.) Return a vector with N elements: for each guest, in the order in which they arrived, the number of the chair where they will be seated.

N人が店に来店するが、それぞれD以上番号が離れた椅子に座りたいらしい。また、それぞれatLeast以上の数字の椅子に座りたいらしい。

来客時に座ることの出来る最も番号の小さい椅子に誘導する決まりになっているので、それに従ってN人それぞれがどの番号の椅子に座るか求めよ。

解法

いわゆるシミュレーション。新しく客がやってきた時に、

  • atLeast+d<(既に座っている人の最小の番号)ならatLeast
  • (誰かが座っている椅子)+d≦atLeast≦(座られている椅子)-dならmax(atLeast,椅子+d)

雑ですが大体こんな感じです。

#include <bits/stdc++.h>
using namespace std;
class BearChairs{
    public:
    vector<int> findPositions(vector<int> atLeast,int d){
        int n=atLeast.size();
        vector<int> ret,used;
        ret.push_back(atLeast[0]); used.push_back(atLeast[0]);
        for(int i=1;i<n;i++){
            if(atLeast[i]+d<=used[0]){
                ret.push_back(atLeast[i]);
                used.insert(used.begin(),atLeast[i]);
            }
            else{
                bool flag=true;
                for(int j=1;j<i;j++){
                    int p=used[j-1]+d,q=used[j]-d;
                    if(q<p)    continue;
                    if(q<atLeast[i])   continue;
                    flag=false;
                    int t=max(p,atLeast[i]);
                    ret.push_back(t);
                    used.insert(used.begin()+j,t);
                    break;
                }
                if(flag){
                    int q=max(atLeast[i],used[i-1]+d);
                    ret.push_back(q);
                    used.push_back(q);
                }
            }
        }
        return ret;
    }
};

Challengeで最初はatLeast、座られている椅子を番号の小さい順にループを回し、-d〜+dの範囲内にatLeastがあれば+dまでatLeastを変えていく手法がいい考え方だと納得させられた。

感想

1149->1159(highest)。

正直Medでバグを埋め込まなければ1200超えたんじゃないかと思うから悔しい。