TopCoder SRM 615 Div1
こんにちはtatsyです。今回もSRMの解説やります。
Easy (250点)
問題
アメーバがいて、アメーバのエサとなるゼリーが列になって最大200個並んでいる。アメーバは自分と同じ大きさのゼリーと出会うと、そのゼリーを食べて大きさが2倍になる。このとき、任意の大きさのアメーバからスタートして、ゼリーの列を通過後に現れることのないアメーバの大きさの場合の数を答えよ。
解法
まず、単純なポイントとして、ゼリーの列に出てこない大きさのアメーバは現れることが可能。なので、ゼリーの大きさをsetにつっこんで、uniqueをとる。
そのそれぞれをゼリーの列に通して、結果の大きさをuniqueした列から削る。そうすれば答えがでる。
とても簡単な気がしたけど、以外にみんな答えるの遅かった。コンテスト終わった後、Pythonなら1行でかけるといっている人がいたw
以下正解のコードです。
#include <fstream>
#include <sstream>
#include <string>
#include <algorithm>
#include <functional>
#include <numeric>
#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;
typedef long long lint;
typedef pair<lint,lint> pll;
#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
class AmebaDiv1 {
public:
lint check(lint a, vector<int> X) {
REP(i,X.size()) {
if(a == X[i]) {
a *= 2;
}
}
return a;
}
int count(vector <int> X) {
set<lint> s;
REP(i,X.size()) {
s.insert(X[i]);
}
vector<int> v(ALL(s));
REP(i,v.size()) {
lint res = check(v[i], X);
set<lint>::iterator it = s.find(res);
if(it != s.end()) {
s.erase(it);
}
}
return s.size();
}
};
Medium (550点)
問題
ある散歩好きのシカが道路で結ばれた街を歩き回っている。今、街0からスタートして街n-1にちょうど時刻Tのときに到着したい。街全体は無向グラフのようになっていて、行き来にかかる時間は同じである。このような散歩が可能な場合にはPossible、不可能な場合にはImpossibleという文字列を返せ。
解法
まず、この問題内容からして、dp[街の番号][到達距離]というようなDP表を更新していくんだろうなと思った。ただ、この問題で与えられているTは最大が10^18もあるので、普通にDP表を持つことはできない。
残り10分くらいになって、道を通るときの所要時間の最大値が10000までだから、これをどうにか利用すれば小さい表で問題が解けるのかな？と思ったが、そのままタイムアップ。
この問題で気づくべきポイントは、「ある時間Tぴったりでn-1に到達できる」ということは「ある時間mで街0に戻ってくるような経路がある場合にS ≡ T (mod m)でn-1に到達できる経路が存在する」ことと同値だということです。
なぜなら両者はT – km = Sとなる0以上の整数kが存在することと同値だからです。なので、実際に持つべきDP表はずっと小さくて、せいぜいdp[51][10001]くらいを持てばよいことになります。
あとは経路のあまりを管理しながら、dpをしていくだけです。上のポイントはあまり直感的ではないですが、これさえ気づければ典型DP問題だったと思います。
以下がコードです。
#include <fstream>
#include <sstream>
#include <string>
#include <algorithm>
#include <functional>
#include <numeric>
#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;
typedef long long lint;
typedef pair<lint,lint> pll;
#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
const lint INF = 1ll << 60;
const int N_MAX = 55;
vector<pll> G[N_MAX];
bool vis[N_MAX][20011];
typedef tuple<lint,lint,lint> Node;
class LongLongTripDiv1 {
public:
bool check(lint mod, lint t, int n) {
memset(vis, 0, sizeof(vis));
priority_queue<Node, vector<Node>, greater<Node> > que;
que.push(Node(0, 0, 0));
while(!que.empty()) {
Node nd = que.top();
lint dist = get<0>(nd);
lint pos = get<1>(nd);
lint rem = get<2>(nd);
que.pop();
if(vis[pos][rem]) continue;
vis[pos][rem] = true;
if(pos == n-1 && dist <= t && rem == t % mod) return true;
REP(i,G[pos].size()) {
lint npos = G[pos][i].first;
lint nrem = (rem + G[pos][i].second) % mod;
lint ndst = min(INF, dist + G[pos][i].second);
que.push(Node(ndst, npos, nrem));
}
}
return false;
}
string isAble(int N, vector <int> A, vector <int> B, vector <int> D, long long T) {
REP(i,N_MAX) {
G[i].clear();
}
REP(i,A.size()) {
G[A[i]].push_back(pll(B[i], D[i]));
G[B[i]].push_back(pll(A[i], D[i]));
}
if(G[0].empty()) return "Impossible";
return check(2 * G[0][0].second, T, N) ? "Possible" : "Impossible";
}
};
まとめ
今回はEasyを10分くらいで早解きしたら過去最高順位を出して、レートが120近くも上がりました。今回は結構簡単な問題だった気がしたのですが、これは練習の成果ということでしょうかね？
TCOが明日に控えているので、この調子でレートを上げていきたいところです。まぁ、レートも重要ですが、そろそろMediumを通したいところですね。
というわけで、今日はここまでにします。最後までお読みいただきありがとうございました。