hogecoder

tsutaj 競技プログラミングの記録

TopCoder SRM 694 Div 2

TopCoder 文字列 動的計画法

今日初めてTopCoderに出てみた。
以前Arenaに入って提出は何回かしてたのだけど、まだ不慣れで最初の方はコンパイルエラー出しまくった。 今度はすんなり提出できたらいいかな・・・

というわけで、解いたものを載っける。

※追記: 作問者のHiro180さんが解説スライドを投稿しているようです。こんなクソザコ記事よりもこっちのほうが参考になると思うぜ！

www.slideshare.net

MakingPairs (Easy)

問題→ TopCoder Statistics - Problem Statement
各要素を2で割って足すだけ。提出に不慣れなせいで正解扱いになるまで40分くらい要した

#include <iostream>
#include <vector>
using namespace std;

class MakingPairs {
    public:
    int get(vector<int> card) {
        int ret = 0;
        for(int i = 0; i< card.size(); i++) ret += card[i] / 2;
        return ret;
    }
};

DistinguishableSetDiv2 (Med)

問題→ TopCoder Statistics - Problem Statement
時間内に解ききれなかった。反省。
制約が緩いので全部なめたら解けます。部分文字列はビットで処理すると楽そう、ということでビット演算をやってみた。まだ慣れないな・・・(蟻本のビットDPを参考にしつつ書いた)

#include <bits/stdc++.h>
#define rep(i,a,n) for(int i=a;i<n;i++)

using namespace std;
class DistinguishableSetDiv2 {
public:
    int count(vector <string> answer) {
        int ret = 0;
        int l = answer[0].length();
        rep(i,0,1 << l) {
            set<string> s;
            rep(k,0,answer.size()) {
                string str = "";
                rep(j,0,l) {
                    if(i & 1 << j) str += answer[k][j];
                }
                s.insert(str);
            }
            if(s.size() == answer.size()) ret++;
            s.clear();
        }
        return ret;
    }
};

後で気づいたけど、DistinguishableSetDiv1(Div1のMed)だと制約がこれより厳しいので、このままだとTLEする模様。余裕があれば追記したい。

UpDownNess (Hard)

問題→ TopCoder Statistics - Problem Statement
まだやってないので解いたら追記しようかな。
※追記: 解きました。

数字の小さい方から順に挿入して数列を作ることを考える。数字 i を左から k 番目に挿入したとすると、lo-hi-lo tripleは k \times (i - 1 - k)増えることになる。なぜなら、この時点で数列内にある i以外の数字は全て i 未満であるので、
\left\{ i の左側にある数字, i , iの右側にある数字 \right\}
の組み合わせが必ずlo-hi-lo tripleになるからだ。 dp\left[i\right]\left[j\right] = 2 〜 i までの数字を挿入した時にlo-hi-lo tripleが j とできる組み合わせ、となるようなDPテーブルをつくってこの遷移が書ければ正解となる。

#include <bits/stdc++.h>
#define rep(i,a,n) for(int i=a;i<n;i++)
#define MOD 1000000007

using namespace std;
class UpDownNess {
public:
    int count(int N, int K) {
        int dp[51][5001];
        memset(dp, 0, sizeof(dp));
        dp[1][0] = 1;

        rep(i,2,N+1) rep(j,0,K+1) {
            rep(k,0,i) {
                if(j >= k*(i-1-k))
                    dp[i][j] = (dp[i][j] + dp[i-1][j - k*(i-1-k)]) % MOD;
            }
        }
        return dp[N][K] % MOD;
    }
};

そういえば、TopCoderを解くにあたってプラグインを使ってる人が結構多いらしい。確かにArenaに直で打ち込むのはとても不便なのでそのへんについても調べようかなあ、という感じ。