Google Code Jam Round.1C

結果

A-small/large,B-small,C-small
535/4482でR1通過!

開始前にsmallは全部通して、largeどれか1個通せば通ると思っていたので
想定通りのスコアが取れてよかった。

以下時系列順に

A-small

とりあえずsmall全部通さなければ、という考えがあったので
全探索して通す。初め1文字の場合を忘れていて1WA。

B-small

BFSすると最大で4方向+500回とかで終わらなそう、枝狩り実装するのもめんどい、
ということで2回逆方向に進むと1マス任意の方向に進める、というのを用いる。
smallは|x|,|y|<100という制限があるので500手以内に辿りつけるのでok。
いくら急いでいたとはいえとても汚いコードで悲しい。

int main(){
    int cases;

    cin >> cases;
    for(int x=1;x<=cases;x++){
        int dx, dy;
        cin >> dx >> dy;
        string ret = "";

        if(dx > 0){
            dx--;
            ret += 'E';
            while(dx > 0){
                ret += "WE";
                dx--;
            }
        }else if(dx < 0){
            dx++;
            ret += 'W';
            while(dx < 0){
                ret += "EW";
                dx++;
            }
        }
        if(dy > 0){
            while(dy > 0){
                dy--;
                ret+= "SN";
            }
        }else if(dy < 0){
            while(dy < 0){
                ret += "NS";
                dy++;
            }
        }
        cout << "Case #" << x << ": " << ret << endl;
    }
}

largeはどうやると効率良く移動できるのか思いつかないのでパス。

C-small

問題分長い…
とりあえずsmallはたかだか100回しか攻撃が来ないので、
それを先に計算して1日ずつ処理していけばいいと思って実装してみる。

• >Sampleあわない。

Then the second tribe attacks three times, each time at height 8 - on day 10 it hits [2,3] (this succeeds, for example at position 2.5, where the Wall has still height 0)

この部分を読んでなかった。wallをmapでwall[位置]=高さと実装していたので
このままでは2と3の間が表現できない。

• >どうせ攻撃範囲は整数で与えられるんだから2倍してやればよくね
• >sample合った
• >提出
• >correct!

比較的実装量が多いものの一発で通せてよかった。

class attack{
public:
    int str;
    int day;
    int w;
    int e;
    
    attack(){};
    attack(int _str, int _day, int _w, int _e):
        str(_str), day(_day), w(_w), e(_e){};

    bool operator <(const attack arg) const{
        return day < arg.day;
    }
    
};

int main(){
    int cases;
    cin >> cases;
    for(int x=1;x<=cases;x++){
        vector<attack> attacks;
        int n, ret = 0;
        map<int,int> wall;
        cin >> n;
        for(int i=0;i<n;i++){
            int d,num,w,e,s,dd,dp,ds;
            cin >> d >> num >> w >> e >> s >> dd >> dp >> ds;
            for(int j=0;j<num;j++){
                attacks.push_back(attack(s+ds*j, d+dd*j, (w+dp*j)*2, (e+dp*j)*2));
            }
            sort(attacks.begin(), attacks.end());
        }

        for(int i=0;i<(int)attacks.size();i++){
            int end = i;
            for(int j=i;j<(int)attacks.size();j++){
                if(attacks[j].day == attacks[i].day){
                    end = j;
                }else{
                    break;
                }
            }

            map<int,int> attacked;

            for(int it = i; it <= end; it++){
                bool suc = false;
                for(int k = attacks[it].w * 2; k <= attacks[it].e * 2; k++){
                    if(attacks[it].str > wall[k]){
                        suc = true;
                        attacked[k] = max(attacked[k], attacks[it].str);
                    }
                }
                if(suc) ret++;
            }

            //update walls
            map<int,int>::iterator it = attacked.begin();

            while(it != attacked.end()){
                wall[(*it).first] = (*it).second;
                ++it;
            }
            i = end;
        }
        cout << "Case #" << x << ": " << ret << endl;
    }
}

A-large

残り1時間、解けそうなのはこれしかない。
制限的にO(N)かO(NlogN)だろうなぁと思う。
とりあえず終わりの文字に注目してsampleにあるtsetse/2というケースを書きだしてみると

tsetse
------
ts
tse
tset
tsets
 sets
  ets
   ts
tsetse
 setse
  etse
   tse

となる。こういうのをいくつかのケースでやってみると、
位置i(1-indexed)で終わる条件を満たす部分文字列の個数をa[i]としたとき、ある位置iの文字が

• 母音またはi番目を含めて前から連続する数がn個未満の場合

　a[i]=a[i-1]

• それ以外の場合

　a[i]=i-n+1
になっていることに気づき、書き、smallのinputで試して全探索と一致することを確かめsubmit。
結果的に通ってよかった。

まとめ

去年はR2で1200位ぐらい、small全部通せばよかったと書いているので
今回と同様にsmall全部+1個largeを目標にしてがんばる。