TopCoder SRM 617 Div1
こんにちは、あいかわらずSRMの調子は低調のtatsyです。
今回はSRM617です。問題はEasyが割り算ゲー、Mediumが貪欲＋深さ優先となっております。それでは早速いきます。
Easy (250点)
問題
横幅がnのケーキがある。あなたはこれから来る友人に平等にケーキを切り分けたいが、友人が何人来るかは定かではない。友人が来る人数はnの約数のうち1とnを除いた数のどれかであることが分かっている。このとき、どの人数が着ても対応できるようなケーキの切り分け方をすると、最小何ピースに分けておかなければならないか？
解法
この問題のポイントはケーキを切り分ける位置をどこに設定すべきかということです。ある人数kに対応するためにはk, 2k, 3k, … , mk = nの場所に切り目を入れればよいことが分かります。
なので、nの全ての約数(正確には素因数)について、切り目を入れて、そのuniqueをとれば切り目の数が分かります。ピースの数は切り目の数+1なのでそれが答えです。
#include <fstream>
#include <sstream>
#include <string>
#include <algorithm>
#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 MyLongCake {
public:
int cut(int n) {
set<int> s;
for(int i=2; i*i<=n; i++) {
if(n % i == 0) {
s.insert(i);
s.insert(n / i);
}
}
vector<int> div(ALL(s));
s.clear();
REP(i,div.size()) {
for(int d=div[i]; d<n; d+=div[i]) {
s.insert(d);
}
}
return (int)s.size() + 1;
}
};
Medium (500点)
問題
会社の社員が50人いる。50人のうち毎日2人選ばれ、そのうち1人がイルカのおもちゃ、もう1人がパイのおもちゃをもらえる。何日間かが経過したあとで、各社員が自分のもらったイルカのおもちゃの数とパイのおもちゃの数の差の絶対値を計算した。この絶対値の50人分の合計を最小にするために、各日で2人がもらえるおもちゃの種類を入れ替えたらどうなるかを考える。最小値をあたえるようなおもちゃの渡し方を答えよ。
解法
まず、各社員がもらうおもちゃの数が合計mこであるなら、その半分がイルカでもう半分がパイだったら絶対値は最小になる(奇数だと1個余るけどとりあえず気にしない)。
なので、ある社員がもっているおもちゃを交互にイルカ、パイ、イルカ、パイ・・・となるように渡し方を調整していく。
i日目に社員AとBがおもちゃをもらっている時、Aがイルカをもらわなければならないことにすると、Bはパイをもらわなければならないので、これを再帰的に変更していく。
結論から言うと、先頭の社員から貪欲に絶対値が最小になるよう渡し方を調整していくと最小値になる。実際にはうしろの方の社員にしわ寄せがいきそうなのだが、イルカ→パイ→イルカ→という鎖構造があって、その両端のどちらかが影響をうけることになるので、頭からやっていっても問題ないのだと思う。実はこのあたりの部分は良く分かっていない。
#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
typedef pair<int,int> pii;
struct state {
int to, day, toy;
};
vector<int> res;
vector<state> edge[55];
bool used[1011];
class PieOrDolphin {
public:
bool dfs(int cur, int which) {
REP(i,edge[cur].size()) {
int to = edge[cur][i].to;
int day = edge[cur][i].day;
int toy = edge[cur][i].toy;
if(used[day]) continue;
used[day] = true;
res[day] = 1;
if(which < 0) res[day] = 3 - res[day];
if(toy < 0) res[day] = 3 - res[day];
dfs(to, which);
return true;
}
return false;
}
vector <int> Distribute(vector <int> A, vector <int> B) {
int n = A.size();
res.assign(n, 0);
memset(used, 0, sizeof(used));
REP(i,50) edge[i].clear();
REP(i,n) {
state s1 = { B[i], i, 1 };
state s2 = { A[i], i, -1 };
edge[A[i]].push_back(s1);
edge[B[i]].push_back(s2);
}
REP(i,50) {
for(;;) {
bool ok = true;
ok &= dfs(i, 1);
ok &= dfs(i, -1);
if(!ok) break;
}
}
return res;
}
};
まとめ
難易度からいうとEasyはかなり簡単だったきがします。Mediumはなんとなく上のやり方でよさそうというところまでは思いついた人が結構いそうですが、どうしてこれで通るのかというところで実装まで踏み切れない感じがしました。
というわけで、今回の解説終わります。ありがとうございました。