Topcoder SRM 579 div1

250 UndoHistory

前のをそのまま引き継ぐ場合と、バッファから読む場合を試して、キーが短くなるほうを選択すればよい。
実は、undoバッファには一行書くごとにそのprefixをすべて入れてしまってよいことはすぐにわかる。

#include <iostream>
#include <iomanip>
#include <vector>
#include <set>
#include <utility>
#include <numeric>
#include <algorithm>
#include <functional>
#include <cctype>
#include <complex>
#include <string>
#include <sstream>

using namespace std;

#define all(c) c.begin(),c.end()
#define rall(c) c.rbegin(),c.rend()
#define rep(i,n) for(unsigned int i=0;i<(n);i++)
#define tr(it,container) for(typeof(container.begin()) it = container.begin(); \
                             it != container.end(); ++it)
#define mp(a,b) make_pair((a),(b))

typedef long long ll;
typedef complex<double> P;
const int dx[] = {1,0,-1,0};
const int dy[] = {0,-1,0,1};
const double EPS = 1e-9;
const int days[] = {31,28,31,30,31,30,31,31,30,31,30,31};
const int daysleap[] = {31,29,31,30,31,30,31,31,30,31,30,31};

class UndoHistory {
public:
    int minPresses(vector <string> lines) {
        set<string> hist;
        hist.insert("");
        int cnt = 0;
        for(int i=0;i<lines.size();i++){
            string line = lines[i];
            if(i != 0){
                // refresh + write it.
                int mincnt = line.size()+2;
                if(lines[i-1].size() <= line.size() and lines[i-1] == line.substr(0,lines[i-1].size())){
                    mincnt = min(mincnt,(int)(line.size()-lines[i-1].size()));
                }
                string prefix = "";
                for(int j=0;j<=line.size();j++){
                    if(hist.find(line.substr(0,j)) != hist.end()){
                        if(prefix.size() <= line.substr(0,j).size()){
                            prefix = line.substr(0,j);
                        }
                    }
                }
                mincnt = min((int)(line.size()-prefix.size()+2),mincnt);
                for(int j=0;j<=line.size();j++){
                    hist.insert(line.substr(0,j));
                }
                cnt += mincnt;
            }else{
                for(int j=0;j<=line.size();j++){
                    hist.insert(line.substr(0,j));
                }
                cnt += line.size();
            }
            // enter.
            cnt++;
        }
        return cnt;
    }
};

450 TravellingPurchasingMan
問題名の通り、巡回セールスマンのアレ。
ワーシャルフロイドしてからのbitDP.
本番では、 ループの順番をまちがえてしんでしまった。
この手の問題は、集合を表すbitのループが先だった。

const int INF = 70480001;
struct Store{
    int open,end,time;
    Store(int open,int end,int time) : open(open),end(end),time(time) {};
};

class TravellingPurchasingMan {
    public:
        int maxStores(int N, vector <string> interestingStores, vector <string> roads) {
            vector<vector<int> > dist(N,vector<int>(N,INF));
            int M = interestingStores.size();
            for(int i=0;i<N;i++){
                dist[i][i] = 0;
            }
            for(int i=0;i<roads.size();i++){
                stringstream ss;
                ss << roads[i];
                int a,b,length;
                ss >> a >> b >> length;
                dist[a][b] = length;
                dist[b][a] = length;
            }
            vector<Store> intr;
            for(int i=0;i<M;i++){
                stringstream ss;
                ss << interestingStores[i];
                int open,end,time;
                ss >> open >> end >> time;
                intr.push_back(Store(open,end,time));
            }
            for(int k=0;k<N;k++){
                for(int i=0;i<N;i++){
                    for(int j=0;j<N;j++){
                        dist[i][j] = min(dist[i][j],dist[i][k]+dist[k][j]);
                    }
                }
            }
            vector<vector<int> > DP(M,vector<int>(1 << M,INF));
            for(int i=0;i<M;i++){
                DP[i][0] = dist[N-1][i];
            }

            for(int j=0;j<(1<<M);j++){
                for(int i=0;i<M;i++){
                    if(DP[i][j] == INF) continue;
                    for(int next=0;next<M;next++){
                        if(!(j & (1 << next))){
                            if(dist[i][next] == INF) continue;
                            int now = DP[i][j] + dist[i][next];
                            Store s = intr[next];
                            if(now > s.end) continue;
                            DP[next][j | (1 << next)] = min(DP[next][j|(1 << next)],max(s.open,now)+s.time);
                        }
                    }
                }
            }

            int ret = 0;
            for(int i=0;i<M;i++){
                for(int j=0;j<(1<<M);j++){
                    if(DP[i][j] != INF){
                        int cnt = 0;
                        for(int k=0;k<M;k++){
                            if(j & (1 << k)){
                                cnt++;
                            }
                        }
                        ret = max(ret,cnt);
                    }
                }
            }
            return ret;
        }
};