月別: 2011年5月

ものすごく久しぶりのTopCoder.

250

あわてんぼさんが
“this is merely an example. be careful. this is a new sentence.”
みたいに頭文字を大文字にしないで書いた文がinputとして与えられるので、
“This is merely an example. Be careful. This is a new sentence.”
と正しくCapitalizeした文を返しなさい

シンプルにCapitalize必要かどうかフラグ持ちながら走査。

class SentenceCapitalizerInator {
public:
    string fixCaps(string paragraph) {
        string result = paragraph;
        bool needCapitalize = true;
        REP(i, SZ(result)) {
            if (needCapitalize && result[i] != ' ') {
                result[i] = result[i] + ('A' - 'a');
                needCapitalize = false;
            } else if (result[i] == '.') {
                needCapitalize = true;
            }
        }
        return result;
    }
};

人の解答見てtoUpperCaseの存在を思い出した///
一応Pass。

500

{1, 3, 2} という数列は1 + 3 + 2 = 1 * 3 * 2 積と和が等しくなっていて、こういうのをPerfect Sequenceと呼ぶ。
ある数列が与えられた時、そのうちの1つだけ数字を変えて完全数列が作れるかどうかを”Yes”/”No”で返せ
例えば、{1, 3, 4} は最後の要素を2に変えればPerfect SequenceなのでYes
{1, 4, 2, 4, 2, 4}はどの要素を変えてもPerfect SequenceにならないのでNo
{1, 2, 3} はすでにPerfect Sequenceになっててどれかを変えると崩れてしまうのでNo

やっかいなのが、数列の要素数は50個以下ながら、数列の各要素が0以上10^9以下なこと。
ふつうに積を求めてるとすぐオーバーフローするので、それに気をつけながら提出したつもりながら、

{1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000}

っていう典型的な境界テストで正しい答えを返せずあえなく撃沈…

class PerfectSequences {
public:
    string fixIt(vector <int> seq) {

        if (SZ(seq) == 1) return "Yes";
        
        int sum = 0;
        REP(i, SZ(seq)) sum += seq[i];

        int curPro = 1;
        REP(i, SZ(seq)) {
            curPro *= seq[i];
            if (curPro > sum) break;
        }
        if (curPro == sum) return "No";

        REP(i, SZ(seq)) {
            int curSum = sum - seq[i];
            int product = 1;
            REP(j, SZ(seq)) {
                if (i != j) {
                    if (seq[j] == 0) {
                        if (curSum == 0)
                            return "Yes";
                        else
                            goto LAST;
                    } else {
                        product *= seq[j];
                        if (product > curSum) goto LAST;
                    }
                }
            }
            if (product == 1) {
                continue;
            } else {
                if (curSum % (product - 1) == 0) {
                    return "Yes";
                }
            }
LAST:
            cerr << curSum << "/" << product << endl;
        }
        return "No";
    }
};

コーナーケースの処理をいかにきっちり書けるかが問われてるのか、それともスマートな解法があるのか…
後で考えてみよー

900
開かず。

スコアは243.29(250) + 0(500) + 0(900) – 25.00(チャレンジ失敗w) = 218.29
Ratingは 835 -> 833
J2生活はまだまだ続く