TopCoder SRM 593 Div1
今回のSRMはEasyが結構実装量が多かったです。最後まで答えがなかなか合わなくて提出できたけどChallengeされてしまいました。気を取り直して解説行きます。
今回の問題は
- Easy: 探索 + 条件把握
- Medium: DP
という感じの問題構成でした。
Easy (250点)
この問題は最大50×50のボード上のマスのいくつかにXが書かれていて、Xと書かれたマスを隣り合ったマスが違う色で塗られるように塗った時、必要な色は何色かを答える問題。
まず前提として当たり前ですが任意の地図は4色あれば塗り分けられるので答えは0以上4以下の整数です。
さらに問題の制約から絶対に3色あれば塗り分けられます。なので0色、1色、2色をつかって塗り分けられるかを順に調べます。もしダメなら3色必要というわけです。
塗り分けの可否を調べる方法は次のようになります。
0色で塗り分ける場合
ボード上にXがひとつもなければ0色で塗り分けられます。
1色で塗り分ける場合
ボード上のXが隣り合っていなければ1色で塗り分けられます。
2色で塗り分ける場合
2色は上の2つよりは少し複雑です。まずXと書いてあるマスから隣り合うマスでXと書かれたものをたどっていき、最初に選んだマスからの距離を調べます。
これを全てのXマスについてやったあとで、ボード上にあるマスに割り当てられた距離を隣り合ったマスで比較します。
このとき隣り合う2つのXマスの距離を2で割った余りが一致していると2色で塗り分けることができません。
実際のコードは以下のようになります。
#include <fstream>
#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>
#include <climits>
using namespace std;
#define REP(i,n) for(int i=0; i<n; i++)
#define REPP(i,s,e) for(int i=s; i<=e; i++)
#define MP(x,y) make_pair(x, y)
#define ALL(a) (a).begin(), (a).end()
#define PRT(a) cerr << #a << " = " << (a) << endl
#define PRT2(a, b) cerr << #a << " = " << (a) << ", " << #b << " = " << (b) << endl
typedef pair<int,int> P;
typedef long long LL;
int dist[55][55];
int di[6] = { -1, -1, 0, 0, 1, 1 };
int dj[6] = { 0, 1, -1, 1, -1, 0 };
class HexagonalBoard {
public:
int n, m;
vector<string> board;
bool check0() {
for(int i=0; i<n; i++) {
for(int j=0; j<m; j++) {
if(board[i][j] == 'X') return false;
}
}
return true;
}
bool check1() {
for(int i=0; i<n; i++) {
for(int j=0; j<m; j++) {
if(board[i][j] == 'X') {
for(int k=0; k<6; k++) {
int ii = i + di[k];
int jj = j + dj[k];
if(ii >= 0 && jj >= 0 && ii < n && jj < m) {
if(board[ii][jj] == 'X') return false;
}
}
}
}
}
return true;
}
void bfs(int r, int c) {
queue<pair<P,int> > que;
que.push(MP(P(r,c), 0));
dist[r][c] = 0;
while(!que.empty()) {
pair<P,int> p = que.front();
que.pop();
for(int k=0; k<6; k++) {
int ii = p.first.first+ di[k];
int jj = p.first.second + dj[k];
if(ii >= 0 && jj >= 0 && ii < n && jj < m) {
if(board[ii][jj] == 'X' && dist[ii][jj] < 0) {
dist[ii][jj] = p.second + 1;
que.push(MP(P(ii,jj), p.second+1));
}
}
}
}
}
bool check2() {
memset(dist, -1, sizeof(dist));
for(int i=0; i<n; i++) {
for(int j=0; j<m; j++) {
if(dist[i][j] < 0 && board[i][j] == 'X') {
bfs(i, j);
}
}
}
for(int i=0; i<n; i++) {
for(int j=0; j<m; j++) {
if(board[i][j] == 'X') {
for(int k=0; k<6; k++) {
int ii = i + di[k];
int jj = j + dj[k];
if(ii >= 0 && jj >= 0 && ii < n && jj < m) {
if(dist[i][j] % 2 == dist[ii][jj] % 2) return false;
}
}
}
}
}
return true;
}
int minColors(vector <string> board) {
this->n = board.size();
this->m = board[0].size();
this->board = board;
if(check0())
return 0;
if(check1())
return 1;
if(check2())
return 2;
return 3;
}
}
この問題、最初は隣しているマスの集合に分けて、その集合がそれぞれ何色で塗り分けられるかを普通に深さ優先でやっていたのですが、上のやり方の方がスマートですね。
これが3色で塗り分ける場合も調べないといけないとなると、普通に深さ優先で調べる必要があると思います。
Medium (450点)
この問題はある女の人(?)がペットを選ぶためにペットたちにリレーレースをさせるという謎設定の問題です。
ペットが何匹かいて、そのペットがコース1周をするのにかかる時間の下限と上限が与えられています。
このペットたちを2チームに分けたとき、最悪のケースで2チームの所要時間差が最小になる場合を見つけて、その差を返すのが目標です。
当たり前のことですがチームの分け方が決まれば、最悪のタイム差が求まります。
つまりSとTという2チームに分かれたとすればタイム差は
- abs((チームSについて上限の合計) – (チームTについて下限の合計))
- abs((チームSについて下限の合計) – (チームTについて上限の合計))
のどちらか大きい方になります。
これは片方のチームについて上限と下限の和を足し合わせたものから、全員の下限の合計あるいは全員の上限の合計を引いたものの絶対値に等しいことがわかります。
ですので、DPをつかって片方のチームについて上限と下限の和を足し合わせると、どういう数が出てくる可能性があるかを調べます。
DP表dp[i][t]はi番目のペットまで使ったときに上限と下限の和を足し合わせていったら、tという数ができるかできないかをbool値で持ちます。
実際には1つ前のペットまでの情報まであればいいのでiは0か1を動かしてやります。
DP表の更新は、前の状態で実現可能なtは実現可能であり、前の状態で実現可能なものにi番目のペットの下限と上限の和を足したものも実現可能です。
こうして更新してやったら、最後に下限の合計、上限の合計との差を調べて、タイム差が一番小さくなるようなものを見つけ出します。
コードは以下のようになります。
#include <fstream>
#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>
#include <climits>
using namespace std;
#define REP(i,n) for(int i=0; i<n; i++)
#define REPP(i,s,e) for(int i=s; i<=e; i++)
#define ALL(a) (a).begin(), (a).end()
#define PRT(a) cerr << #a << " = " << (a) << endl
#define PRT2(a, b) cerr << #a << " = " << (a) << ", " << #b << " = " << (b) << endl
typedef pair<int,int> P;
typedef long long LL;
const int MAX_N = 1000011;
bool dp[2][MAX_N];
int total[55];
class MayTheBestPetWin {
public:
int calc(vector <int> A, vector <int> B) {
int n = A.size();
int sumA = 0;
int sumB = 0;
for(int i=0; i<n; i++) {
sumA += A[i];
sumB += B[i];
total[i] = A[i] + B[i];
}
memset(dp, 0, sizeof(dp));
dp[0][0] = true;
int bit = 0;
for(int i=0; i<n; i++) {
for(int j=0; j<MAX_N; j++) {
if(!dp[bit][j]) continue;
dp[bit^1][j] = true;
dp[bit^1][j+total[i]] = true;
}
bit ^= 1;
}
int res = MAX_N+1;
for(int i=0; i<MAX_N; i++) {
if(dp[bit][i]) {
int diff = max(abs(i - sumA), abs(i - sumB));
res = min(res, diff);
}
}
return res;
}
}
実装量がEasyよりも少ないじゃないか、というツッコミはおいておいて、450点問題くらいの難易度ではないかと思います。
ちなみにDP表に現れるtの最大値は下限の最大値10000と上限の最大値10000を合計して20000が50匹分なので10^6までは出てくる可能性があります。
まとめ
最近は結構練習しているのですが、本番になると解けない。今回はCodeforces、AtCoder、SRMと連戦でしたがどれもまともにできなかったな…
次もがんばります。
最後までお読みいただきありがとうございました。