101 Hack May'15 - へなちょここーだー

いやー全然ダメでした。205/556位、完答は1問のみと厳しい結果でした。悔しかったのでModerateまでは大会後にEditorialを見ずに解いた感じでは3問完答までは少なくともいけた・・・。まぁ、前回初参戦でbronze medalをとったので完全に浮かれてた自分が悪いんですけどねw

Counting Good Partitions of a String (Easy)

えーと。この問題は大会終了後まで問題文の意味が理解出来ませんでした。kの値を最大化するものだと思っていて、なぜ1000を法にして解かないといけないんだろうとか思っていました。Discussionsを見ると同じ勘違いをしてる人がいますね。（私も納得いかなくて書き込んでるのはここだけの秘密w）
大会終了後に解いたコードを紹介

int n = str.size(), count = 0, ch[26];
    for(int i = 0; i < 26; i++){
        ch[i] = 0;
    }
    for(int i = 0; i < n; i++){
        ch[str[i] - 'a']++;
    }
    ch[str[0] - 'a'] = 1;
    int result = 1;
    for(int i = 0; i < 26; i++){
        if(ch[i] > 0){
            result = result * ch[i] % 1000;
            count++;
        }
    }
    cout << result << endl;

まず、全ての文字が何回登場しているかをchに記録。例えば、aが3個あるならそのうち１つをpartitionの先頭にするためresultを3倍。ただし、inputの最初にくる文字は必ずpartitionの最初になるため1通り。これを1000を法にして計算すると解けました。

Devu, Amit, and Good Integers (Easy)

今大会で唯一解けた問題。

cin >> n >> l >> r;
        for(int i = 0; i < n; i++){
            cin >> tmp;
            if(tmp > r){
                a[i] = tmp - r;
            } else if (tmp < l){
                a[i] = l - tmp;
            } else {
                a[i] = 0;
            }
        }
        sort(a, a + n);
        for(int i = 1; i < n; i++){
            a[i] = a[i] + a[i - 1];
        }
        for(int i = 0; i < n; i++){
            if(i)
                cout << " ";
            cout << a[n - i - 1];
        }
        cout << endl;

まずは、入力された数字に何回操作を行う必要があるかをaに格納します。そしてこれをソート。次にa[i]=a[i]+a[i-1]の漸化式でその前にある時間を足し合わせることでa[i]はi+1個の数字をgood integerにするための操作数になります。そして、k個の数字を選ぶと少なくとも1個はgood integerであるということはn-k+1個のgood integerがあればいいためaを逆順に出力して終了。

Devu and a Wonderful Game (Moderate)

今大会はEasyで時間を使いすぎて、この問題を解き始めたときには時間がほとんど残っておらず、しかも急いで書き上げたコードはwhileの処理をミスってSample Inputは通ったもののそれ以外では無限ループに陥ってTLE。
まずは、何も操作を行うことなく風船は割れていくので残る風船の個数を出力する関数をつくりました。

int convert(string str){
    string tmp;
    int n;
    while(true){
        n = str.size();
        if(n == 0 || n == 1)
            break;
        tmp = "";
        if(str[0] != str[1])
            tmp += str[0];
        for(int i = 1; i < n - 1; i++){
            if(str[i] != str[i - 1] && str[i] != str[i + 1])
                tmp += str[i];
        }
        if(str[n - 2] != str[n - 1])
            tmp += str[n - 1];
        if(n == tmp.size()){
            break;
        }
        str = tmp;
    }
    return n;
}

正直もっとスマートなコードに直せる気がするのですが現時点ではこんな感じです。他の人のコードをみて勉強してみるかな。そして、結果を出力する部分。

cin >> str;
int len = convert(str);
if(len <= 2){
    cout << 0 << " " << 0 << endl;
} else {
    cout << 1 << " " << ceil((double) (len - 2)/4) << endl;
}

3つ以上の風船が残ったときに注目。真ん中の風船2つを交換すれば残りの風船は1つ以下になります。また、端にある風船とその隣の風船を交換すれば4つの風船が割れ、これが一回の操作で割る風船の最小値となります（風船が4つ以上残っていると仮定した場合ですが）。これを考慮して最大の操作数はceil((double) (len - 2)/4)と天井関数を使ってみました。でも天井関数を使わなくても出来ますねw

とりあえず、解いたのはここまで。まだまだへなちょこだと実感した大会でした。