TopCoder Memo@kagamiz

ものすごく眠い中参加しました.

結果 : o-- +0/-0 143.42 pts 1494 → 1508 (+14) !!黄色!!

250 UndoHistory

問題文 -> コチラ

問題概要 :

複雑な仕様のエディタがある.

タイプ+クリック数の最小値を求めよ.

解法 :

問題文で記述しているとおりに実装するだけ. 最初にbuffer に"" を詰めておけば怖いことはない.

"複雑な仕様" を微妙に読み違えていて亀コーディングしましたが, Systest は通ったしよかったよかった...

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cfloat>
#include <map>
#include <utility>
#include <set>
#include <iostream>
#include <memory>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <sstream>
#include <complex>
#include <stack>
#include <queue>
#include <deque>

using namespace std;

typedef long long lint;

class UndoHistory {
  public:
    int minPresses(vector <string> l)
    {
      int res = l.size();
      vector<string> buffers;
      
      buffers.push_back("");
      
      string prevstr = "";
      for (int i = 0; i < l.size(); i++){
          int idx = -1;
          for (int j = l[i].size(); (int)l[i].size() - j >= 0; j--){
            for (int k = 0; k < buffers.size(); k++){
              if (l[i].substr(0, j) == buffers[k]){
                idx = j;
              }
              if (~idx) break;
            }
            if (~idx) break;
          }
          
          int cost1 = (l[i].size() >= prevstr.size() && l[i].substr(0, prevstr.size()) == prevstr) ? l[i].size() - prevstr.size() : 9999999;
          int cost2 = l[i].size() - idx + 2;
          
          if (cost1 < cost2){
            res += cost1;
            for (int j = prevstr.size(); j < l[i].size(); j++)
              buffers.push_back(l[i].substr(0, j + 1));
          }
          else {
            res += cost2;
            for (int j = idx; j < l[i].size(); j++){
              buffers.push_back(l[i].substr(0, j + 1));
            }
          }
          
          prevstr = l[i];
      }
      
      return (res);
    }
  
    

}; 

450 TravellingPurchasingMan

問題文 -> コチラ

問題概要 :

N 個のお店があって, 0 から N - 1 までの番号がついている. あなたは0 から M - 1 番目までのお店に興味がある.

また, いくつかの店間には重み付きの無向辺がはられている.

0 ≦ x ≦ M - 1 を満たすx について, 時刻A[x] から B[x] の間にC[x] 時間滞在すればあなたはその店で満足できる.

店 N - 1 から出発するとき, 満足できる店の最大値を求めよ.

1 ≦ N ≦ 50, 1 ≦ M ≦ min(N, 16)

解法 :

M 頂点だけのグラフに縮約して, Warshall-Floyd + bitDP で十分.

しかし, 癖で店番号をデクリメントしていてサンプルが通らなかった... ザンネン

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cfloat>
#include <map>
#include <utility>
#include <set>
#include <iostream>
#include <memory>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <sstream>
#include <complex>
#include <stack>
#include <queue>
#include <deque>

using namespace std;

typedef long long lint;

int st[64], en[64], stay[64];

struct Edge {
	int to, cost;
	Edge(int to, int cost) : to(to), cost(cost) {}
};

int mask;
vector<Edge> G[64];
int dp[64][1 << 16];

class TravellingPurchasingMan {
	public:
		int maxStores(int N, vector <string> iStores, vector <string> rds)
		{
			int res = 0;
			
			for (int i = 0; i < iStores.size(); i++){
				sscanf(iStores[i].c_str(), "%d %d %d", st + i, en + i, stay + i);
			}
			
			int cst[64][64];
			
			for (int i = 0; i < 64; i++){
				for (int j = 0; j < 64; j++)
					cst[i][j] = 1000000000;
				cst[i][i] = 0;
			}
			
			for (int i = 0; i < rds.size(); i++){
				int a, b, c;
				sscanf(rds[i].c_str(), "%d %d %d", &a, &b, &c);
				cst[a][b] = c;
				cst[b][a] = c;
			}
			
			for (int k = 0; k < N; k++)
				for (int i = 0; i < N; i++)
					for (int j = 0; j < N; j++)
						cst[i][j] = min(cst[i][j], cst[i][k] + cst[k][j]);
			
			for (int i = 0; i < 64; i++)
				G[i].clear();
			
			for (int i = 0; i < iStores.size(); i++){
				for (int j = 0; j < iStores.size(); j++){
					if (cst[i][j] != 1000000000)
						G[i].push_back(Edge(j, cst[i][j]));
				}
			}
			
			mask = (1 << iStores.size()) - 1;
			
			for (int i = 0; i < 64; i++)
				for (int j = 0; j < 1 << 16; j++)
					dp[i][j] = 1000000000;
			
			for (int i = 0; i < iStores.size(); i++){
				if (cst[N - 1][i] <= en[i]){
					dp[i][1 << i] = max(st[i], cst[N - 1][i]) + stay[i];
				}
			}
			
			
			for (int j = 0; j < 1 << (iStores.size()); j++){
				for (int i = 0; i < iStores.size(); i++){
					if (dp[i][j] != 1000000000){
						res = max(res, __builtin_popcount(j));
						for (int k = 0; k < G[i].size(); k++){
							if (dp[i][j] + G[i][k].cost <= en[G[i][k].to]){
								dp[G[i][k].to][j | ((1ll << G[i][k].to) & mask)] = min(dp[G[i][k].to][j | ((1ll << G[i][k].to) & mask)],
																			       max(dp[i][j] + G[i][k].cost, st[G[i][k].to]) + stay[G[i][k].to]);
							}
						}
					}
				}
			}
			
			
			return (res);
		}
};

ツイートする