TopCoder SRM 579 Div1
少し遅くなりましたが、今回のSRM579も解説をしていきたいと思います。
今回はEasyとMiddleを解説します。僕はどちらもSystem Testで落ちましたが。
この記事に書かれているコードはちゃんと通るコードなので、そこはご心配なく。
Easy (250点)
この問題はウィンドウとバッファがあるテキストエディタを扱う問題です。
あなたが文字を打っていくとバッファに文字がたまっていき、Enterを押すとウィンドウにバッファ内の文字が表示されます。
このテキストエディタにはUndo機能が付いていて、あなたが1文字打つたびに、その時のバッファ内の文字がUndo履歴に保存されます。
マウスの2回クリックすると、バッファ内の文字をUndo履歴の中の好きな文字列に変更できます。
さて、与えられた文字列群を表示するのに、最も少ないキータイプ数はいくつでしょう？
というのが問題です。
この問題を解く鍵はある文字列を打ち終わった時に、
- 今バッファ内にある文字から続けて打ち始めるのか
- Undo履歴内の文字列から打ち始めるのか
を決めるところにあります。
Undo履歴の文字列を使うにはマウスを2回クリックする必要があります。ですから、その2回のタイプをしても、そのまま打ち始めるよりは少ないタイプ数で文字列を打てる時にUndoを使います。
実際には、そのまま打ち始められる場合というのは限られています。それは前に打った文字列が次に打つ文字列の先頭に来ている場合だけです。ここを正確にプログラミングできれば、大して難しい問題ではないです(僕は間違えたけど)。
#include <sstream>
#include <string>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
#include <bitset>
#include <queue>
#include <stack>
#include <utility>
#include <cstring>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cctype>
using namespace std;
#define rep(i,n) for(int i=0; i<n; i++)
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef long long ll;
class UndoHistory {
public:
set<string> undo;
int findFromUndo(string line) {
int length = line.size();
while(length--) {
set<string>::iterator it = undo.find(line);
if(it != undo.end()) {
return length+1;
}
line = line.substr(0, length);
}
return 0;
}
bool partMatch(string line, string last) {
int length = last.size();
if(line.substr(0, length) == last) return true;
return false;
}
int typeLines(string line, string last) {
int length = line.size();
int p = findFromUndo(line);
int press = 2;
if(partMatch(line, last)) {
int q = last.size();
if(length - p + 2 > length - q) {
p = q;
press = 0;
}
}
string buf = line.substr(0, p);
for(int i=p; i<length; i++) {
buf.push_back(line[i]);
undo.insert(buf);
press++;
}
return press + 1;
}
int minPresses(vector <string> lines) {
int nLines = lines.size();
undo.clear();
int ans = 0;
string last = "";
rep(i, nLines) {
ans += typeLines(lines[i], last);
last = lines[i];
}
return ans;
}
}
僕の場合はUndoの履歴をsetに保存しています。その中の文字列で最もタイプ数が少なくて済みそうなものをまず見つけてきます。
一方で、前にうった文字列から打ち始められるときは、そうした場合に必要なタイプ数を履歴を使う場合と比較し、少ない方を採用します。
あとは文字列を打ち進めながら、Undo履歴に打った文字列を保存していくだけです。
Undoを使うのに必要なタイプ2回やEnterキーのタイプ1回を飛ばさないように注意してください。
Middle (450点)
この問題は、ある男の人が面白そうなお店を回って買い物をしようとするとき、できるだけ多くのお店を回る方法を見つける問題です。
問題の設定は次のようになっています。
- お店は最大50店舗与えられる
- 各店舗には開店時間、閉店時間、買い物にかかる時間が与えられている
- 50店舗のうち最大16店舗が面白そうなお店である
- 50店舗のお店の中の2店舗の間には道があるペアがいくつかある
最初男の人は50店舗のお店の一番最後のお店にいます。その状況から面白そうなお店を効率よく回った時に最大何店舗回れるかを計算します。
この問題で注目すべきポイントは面白そうなお店が最大16店舗である点です。16店舗のお店に行ったか行かないかの情報をすべて保存したとしても$2^{16} \approx 10^5$なので、状態を記録しておくことができます。
この状態をメモ化して、あとは深さ優先探索でお店を回る順番をすべて調べます。この時に一番多く回れる回り方が答えになるわけです。
この時もう一つポイントがあって、あるお店にいるとき、次のあるお店に行けるかどうかをどう判定する方法です。いちいち最短経路探索をするのは無駄が多いので、最大50店舗のすべてのお店の間の最短経路をワーシャル・フロイド法で計算しておきます。
それではコードを見てみます。
#include <sstream>
#include <string>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
#include <bitset>
#include <queue>
#include <stack>
#include <utility>
#include <cstring>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cctype>
using namespace std;
#define rep(i,n) for(int i=0; i<n; i++)
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef long long ll;
typedef bitset<16> bs;
struct int3 {
int x, y, z;
};
const int N_STATE = 1 << 16;
int dp[N_STATE][51];
int dist[51][51];
class TravellingPurchasingMan {
public:
void warshall_floyd(int n, vector<int3>& roads) {
memset(dist, -1, sizeof(int) * 51 * 51);
for(int i=0; i<51; i++) {
dist[i][i] = 0;
}
for(int i=0; i<roads.size(); i++) {
int f = roads[i].x;
int t = roads[i].y;
dist[f][t] = dist[t][f] = roads[i].z;
}
for(int k=0; k<n; k++) {
for(int i=0; i<n; i++) {
for(int j=0; j<n; j++) {
if(i == j) continue;
if(dist[i][k] >= 0 && dist[k][j] >= 0) {
if(dist[i][j] < 0 || dist[i][j] > dist[i][k] + dist[k][j]) {
dist[i][j] = dist[i][k] + dist[k][j];
}
}
}
}
}
}
int3 getTriplet(string s) {
stringstream ss;
ss << s;
int3 ret;
ss>>ret.x>>ret.y>>ret.z;
return ret;
}
void dfs(bs& state, int pos, int nt, vector<int3>& stores) {
int sid = state.to_ulong();
if(dp[sid][pos] < 0 || dp[sid][pos] > nt) {
dp[sid][pos] = nt;
} else {
return;
}
for(int i=0; i<stores.size(); i++) {
if(!state[i]) {
if(dist[pos][i] < 0) continue;
int fin = nt + dist[pos][i];
if(fin < stores[i].x) {
fin = stores[i].x + stores[i].z;
} else if(fin <= stores[i].y) {
fin += stores[i].z;
} else {
continue;
}
state.set(i);
dfs(state, i, fin, stores);
state.reset(i);
}
}
}
int bitCount(int n) {
int cnt = 0;
while(n != 0) {
cnt += (n & 0x01);
n >>= 1;
}
return cnt;
}
int solve(int n, vector<int3>& stores, vector<int3>& roads) {
warshall_floyd(n, roads);
memset(&dp[0][0], -1, sizeof(int) * N_STATE * 51);
int pos = n-1;
bs state;
dfs(state, pos, 0, stores);
int maxval = 0;
for(int i=0; i<N_STATE; i++) {
for(int j=0; j<n; j++) {
if(dp[i][j] >= 0) {
int cnt = bitCount(i);
maxval = max(maxval, cnt);
}
}
}
return maxval;
}
int maxStores(int N, vector <string> stores, vector <string> roads) {
int nStore = stores.size();
int nRoads = roads.size();
vector<int3> storeList(nStore);
vector<int3> roadList(nRoads);
for(int i=0; i<nStore; i++) {
storeList[i] = getTriplet(stores[i]);
}
for(int i=0; i<nRoads; i++) {
roadList[i] = getTriplet(roads[i]);
}
int ans = solve(N, storeList, roadList);
return ans;
}
};
こうしてみると、スペースで区切られた文字列から数字を抜き出す処理なんかも、意外と面倒ですね。
次のお店に行けるかどうかのチェックも<=なのか<なのかを間違えるとコードが通らないので注意してください。
まとめ
今回はEasyもMiddleも雰囲気解けそうだったのでテンションあがりましたが、結果、どちらも通らないという・・・。細かな実装を正確にできる能力を身に着けないといけないですね。
次解けなかったらいよいよDiv2落ちが見えてきそうなので、次も頑張ります。