TCO13 Round2A

TopCoder

飲み会開けの酔拳チャレンジ。

  • -

300. TheLargestString

問題：同じ長さの文字列s, tから同じ位置の文字を抽出したものを繋げてできる辞書順最大の文字列は？

  • 文字列長を固定すれば、sからは辞書順が最大になるように選ぶのが最善
  • で、sからとった文字列が同じならtからとった文字列が大きいほうが良い
  • なので、文字列ごとにpair(sの部分列, tの部分列)を文字数ごとに持ってDPした
  • 何故かChallengePhaseで5回チャレンジされてビクビクしてた。
class TheLargestString {
public:
    string find(string s, string t) {
        int n = s.size();
        vector< pair<string, string> > cur(n+1, make_pair("-", "-"));
        cur[0] = make_pair("", "");
        for(int i=0;i<n;i++){
            vector< pair<string, string> > next = cur;
            for(int j=0;j<n;j++){
                if(cur[j].first == "-") continue;
                string a = cur[j].first  + s[i];
                string b = cur[j].second + t[i];
                if(next[j+1].first == "-" || next[j+1] < make_pair(a, b))
                    next[j+1] = make_pair(a, b);
            }
            cur = next;
        }
        string res = s+t;
        for(int i=1;i<n;i++){
            res = max(res, cur[i].first + cur[i].second);
        }
        return res;
    }
};

600. TheMagicMatrix

問題：0-9の数字を要素に持つn×nの行列で、各行・列の要素の和の下一桁がすべて等しいものは何個ある？条件として、最大10個の要素の値が固定。

  • n>10なら何も指定されてない1行で辻褄合わせが出来るので求められそう。
  • で、n≦10の場合が分からなくて撃沈。
  • -

結果：AC / -- / -- ，+0, 282.32 pt, 70位
レーティング：2329 -> 2400


相変わらずチャレンジが苦手で、今日も撃墜ガチ勢ぱないと思ってたら終わってしまいました。
1個でも撃墜できてればとも思うのですが、それよりはMedium解きたかった感もあり複雑です。