Google Code Jam 2014 Round 1A
こんにちはtatsyです。
GCJ2014のRound1Aの解説します。今回は普通にAとBをSmallとLarge両方通して800位台でした。去年もRound1は突破できてたし、実力は格段に伸びてるはずなので、通過できてよかったです。
一応全て解説しますが、自力で出来たのはA、Bだけなのでコードはその2問分だけのせます。Cについてはやり方のみ説明しますので、詳しくは他の方のコードを公式から見ていただけると良いかと思います。
A. Charging Chaos (Small: 8pt, Large: 17pt)
問題
ショウタはN個の異なるデバイス(スマホ、PC、タブレット等)を持っているがそれぞれは使用可能な電気の流れが固有のビットパターンになっている。
今、ショウタの家にはN個の異なるビットパターンを持ったコンセントがある。デバイス、コンセントのビットパターンはいずれも長さがLであり、家にL個あるスイッチiを押すと、コンセントのi番目のビットが全て反転する。今、ミサキはショウタに頼まれて、全てのデバイスが使えるようにスイッチを押したい。
これを実現するために押さなければならない最小のスイッチの数を答えよ。もし、どうやっても全て使えない場合には”NOT POSSIBLE”と表示せよ。
解法
SmallはL=10なので、2^10通りの全ての反転パターンを調べればOKなのですが、Largeを解こうと思うと、L=40なので全探索は無理です。
注目すべきことは、あるデバイスが使えるということは、それが使えるようにいずれかのコンセントのビットパターンを変更する必要がある、ということです。
なので、デバイスを1つ選んで、それが0番目のコンセントで使えるように押すスイッチを決めます。あとは、これに合わせて、他のコンセントのビットパターンを変更して、全てのデバイスが使用可能になるかどうかを調べます。
このやり方だと、どのデバイスを0番目のコンセントに割り当てるかでO(N)、それにより決定されたビットバターンで全てのデバイスが使えるかを調べるのにO(LN^2)の計算量がかかるので、合計の計算量はO(LN^3)になり、最大のテストケースの場合でも10^8くらいのオーダーになるので大丈夫です。特にGCJはLargeだと8分あるので、この計算量なら十分すぎるくらいです。
#include <sstream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <ctime>
#include <cstring>
#include <climits>
#include <algorithm>
#include <functional>
#include <numeric>
#include <map>
#include <set>
#include <stack>
#include <vector>
#include <queue>
#include <bitset>
#include <string>
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 PB(a) push_back(a)
#define MP(i,s) make_pair(i,s)
#define SZ(a) (int)(a).size()
#define ALL(a) (a).begin(), (a).end()
#define PRT(a) cerr << #a << " = " << (a) << endl
#define PRT2(a,b) cerr << #a << " = " << (a) << ", " << #b << " = " << (b) << endl
#define PRT3(a,b,c) cerr << (a) << ", " << (b) << ", " << (c) << endl
typedef long long lint;
typedef pair<lint,lint> pll;
int N, L;
string pat[155];
string goal[155];
bool vis[155];
const int INF = 1<<20;
int check(string flip) {
memset(vis, 0, sizeof(vis));
vector<string> pp;
REP(i,N) {
pp.push_back(pat[i]);
REP(j,L) {
if(flip[j] == '1') {
pp[i][j] = (pp[i][j] == '1') ? '0' : '1';
}
}
}
int suc = 0;
REP(i,N) {
REP(j,N) {
if(!vis[j] && pp[i] == goal[j]) {
vis[j] = true;
suc++;
break;
}
}
}
if(suc != N) return -1;
int ret = 0;
REP(i,L) {
if(flip[i] == '1') ret++;
}
return ret;
}
void solve() {
int ans = INF;
REP(i,N) {
string s = pat[i];
string g = goal[0];
string flip = "";
REP(k,L) {
if(s[k] == g[k]) flip += "0";
else flip += "1";
}
int res = check(flip);
if(res != -1) {
ans = min(ans, res);
}
}
if(ans == INF) {
printf("NOT POSSIBLEn");
} else {
printf("%dn", ans);
}
}
void coding() {
int T;
while(cin>>T) {
REPP(t,1,T) {
cin>>N>>L;
REP(i,N) cin>>pat[i];
REP(i,N) cin>>goal[i];
printf("Case #%d: ", t);
solve();
}
}
}
// #define _LOCAL_TEST
int main() {
#ifdef _LOCAL_TEST
clock_t startTime = clock();
freopen("a.in", "r", stdin);
#endif
coding();
#ifdef _LOCAL_TEST
clock_t elapsedTime = clock() - startTime;
cout << endl;
cout << (elapsedTime / 1000.0) << " sec elapsed." << endl;
cout << "This is local test" << endl;
cout << "Do not forget to comment out _LOCAL_TEST" << endl << endl;
#endif
}
B. Full Binary Tree (Small: 9pt, Large: 21pt)
問題
1からNまでに番号付けされたN個のノードが木構造を作るようにN-1本のエッジにより結ばれている。この木構造からノードを削って、単一の二分木になるようにしたい。削らなければ成らないノードの最小数を答えよ。
解法
これもSmallの場合にはN=10なので、深さ優先探索で全ての場合を試せばよいと思います。Largeの場合には、もう少し工夫が必要です。
あるノードからスタートして、それ以下の階層にあるノードだけを二分木の構造にするための最小コストがいくつになるかを考えます。
これはノードに接続されている葉ノードの数で場合分けされます。
(i) 葉ノードが1つもないとき
これは何もしなくても二分木なので、コストは0です。
(ii) 葉ノードが1つのとき
これはその1つの葉ノードを削らなくては成らないので、葉ノード以下に接続されたノードの数の合計がコストになります。
(iii) 葉ノードの数が2つ以上のとき
この場合は少し複雑です。今、葉ノードがm個あって、i番目の葉ノードを除去するコストがremove[i], i番目の葉ノードを残すことにして、それ以下を二分木にするコストがremain[i]だと仮定します。
残されるべき葉ノードの数は2つなのですが、このときremain[i] – remove[i]が小さいものを優先的に残したほうが合計のコストは小さくなります。なので、葉ノード全てについて、remain[i] – remove[i]を計算して、ソートし、先頭から2つだけを残すようにコストを計算します。
以上の方針が固まったので、あとは全てのノードについて、それがrootになる場合のコストを求め、その最小値を答えとして返せばOKです。
僕の書いたコードは若干汚いですが、やっていることは
- あるノードの下に接続されたノードの合計数を求める
- 求めた合計数を利用して、前述の方針により除去すべきノード、残すべきノードを決定する
というものです。
あと一応補足なのですが、(iii)の場合で、2個を残すのではなく、そもそも全部のノードを除去するという選択肢もあると思います。ですが、この場合はどうがんばっても2つ残す場合よりもコストが増大します。なんでかというと、2つ残した葉ノード以下を二分木にするコストはそれ以下に接続されたノード数よりは確実に小さくなるからです。なので、上の方針でちゃんと最適になります。
#include <sstream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <ctime>
#include <cstring>
#include <climits>
#include <algorithm>
#include <functional>
#include <numeric>
#include <tuple>
#include <map>
#include <set>
#include <stack>
#include <vector>
#include <queue>
#include <bitset>
#include <string>
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 PB(a) push_back(a)
#define MP(i,s) make_pair(i,s)
#define SZ(a) (int)(a).size()
#define ALL(a) (a).begin(), (a).end()
#define PRT(a) cerr << #a << " = " << (a) << endl
#define PRT2(a,b) cerr << #a << " = " << (a) << ", " << #b << " = " << (b) << endl
#define PRT3(a,b,c) cerr << (a) << ", " << (b) << ", " << (c) << endl
typedef long long lint;
typedef pair<lint,lint> pll;
typedef tuple<int,int,int> node;
int N;
int cnt[1011];
vector<int> G[1011];
const int INF = 1 << 20;
int dfs(int cur, int pre) {
if(pre >= 0 && G[cur].size() == 1) return 0;
int tot = 0;
REP(i,G[cur].size()) {
int to = G[cur][i];
if(to != pre) {
tot += dfs(to, cur) + 1;
}
}
cnt[cur] = tot;
return tot;
}
int dfs2(int cur, int pre) {
if(pre >= 0 && G[cur].size() == 1) return 0;
vector<node> num;
REP(i,G[cur].size()) {
int to = G[cur][i];
if(to != pre) {
int en = dfs2(to, cur);
num.push_back(make_tuple(en - (cnt[to]+1), en, to));
}
}
sort(ALL(num));
int tot = INF;
if(num.size() == 1) {
tot = cnt[get<2>(num[0])] + 1;
} else {
tot = 0;
REP(i,2) {
tot += get<1>(num[i]);
}
REPP(i,2,num.size()-1) {
tot += cnt[get<2>(num[i])] + 1;
}
}
return tot;
}
int remove_count(int rt) {
memset(cnt, 0, sizeof(cnt));
dfs(rt, -1);
return dfs2(rt, -1);
}
void solve() {
int ans = INF;
REP(i,N) {
int res = remove_count(i);
ans = min(ans, res);
}
printf("%dn", ans);
}
void clear_graph() {
REP(i,1011) G[i].clear();
}
void coding() {
int T, x, y;
cin>>T;
REPP(t,1,T) {
clear_graph();
cin>>N;
REP(i,N-1) {
cin >> x >> y;
x--; y--;
G[x].push_back(y);
G[y].push_back(x);
}
printf("Case #%d: ", t);
solve();
}
}
// #define _LOCAL_TEST
int main() {
#ifdef _LOCAL_TEST
clock_t startTime = clock();
freopen("b.in", "r", stdin);
#endif
coding();
#ifdef _LOCAL_TEST
clock_t elapsedTime = clock() - startTime;
cout << endl;
cout << (elapsedTime / 1000.0) << " sec elapsed." << endl;
cout << "This is local test" << endl;
cout << "Do not forget to comment out _LOCAL_TEST" << endl << endl;
#endif
}
C. Proper Shuffle (Small: 45pt, Large: なし)
問題
0からN-1までのN個の数字が昇順に並んだ列がある。これをシャッフルして任意のならびを均等な確率で得る方法はいくつか知られている。ところが悪いシャッフルの仕方をすると混ざりかたにばらつきが出る。ばらつきがでるようなやり方の一例を挙げる。
iを0からN-1まで動かす。各iについて、0からN-1までの数字をランダムに選び、それをjとする。iとjの位置にある数字を入れ替える。
このようなやり方をするとばらつきが出るのだが、今適当な長さ1000の数列が与えられた時に、それが上記の間違ったやり方で生成されたものか、それとも正しいやりかたで生成されたものかを答えよ。ただし、確率的な問題になるので、120個の数列のうち109個があえば正解とする。
解法
とりあえず小さめのNで実験をしてみると、確かにばらつきが出る。なのでばらついた結果、間違ったやり方で高確率に出現するようなものであれば”BAD”と答えることにします。
ところが、全ての場合をシミュレーションすることはN=1000という制約から難しいので、1000回のシャッフルを行ったあとで、数字iがj番目に来る確率を動的計画法で求めます。
やり方は、2つのDP表、buf[step][p]とbad[num][p]を更新していく作業に置き換えらます。
ここでbuf[step][p]はstep回の移動の後に数字iがpに来ている確率を記憶するもの。これを各iについて作成します。作成し終わったら、buf[N][p]をbad[i][p]にコピーすると、数字iがpに行く確率の表が求まります。
ここまできたら数字を読んで、その数字が間違ったやり方で生成される確率を求める。つまり与えられた数字がi番目にnum[i]を持つとすればbad[num[i]][i]をどんどん掛け算していけばいいです。といいたいところなんですが、当然確率はとても小さくなるのでdoubleでは計算できません。そこで、各数のlogとかlog10とかをとって確率の対数を求めます。
あとは閾値処理をしてGOODかBADかを決めればよいのですが、閾値を決めるときにも少し考える必要があります。長さ1000の数列の並び替え方は1000!通りあるので、確率はその逆数になることが分かります。そこで試しに1000!が10の何乗になるのかを調べてみると、10の2567乗になります。なのでこれを閾値にしたくなるんですが、今回はこれではまずいです。
というのも、上記のDPで求められるのは「2つ以上の桁に同じものが来てもいいときに」与えられた数字が出る確率だからです。なので、確率としては1000の1000乗、すなわち10の3000を閾値にする必要があります。
実際にテストケースとして得られるデータを上のやり方で処理すると、大体10の-3000前後の値がでます。なので、これを閾値にしてGOODかBADかを判定すればいいです。
まとめ
今回の2問はいずれもSmallは全探索すればOKで、Largeは少し工夫が必要というものでした。
解けている人の人数を見るとAのLargeもBのLargeも同じくらいというのが個人的には結構驚きです。明らかにBの方が実装大変だと思うので…。
Round 1Aで通ってしまうと、あと2ラウンド分待つ時間が長いという贅沢な悩みが生じてきますが、今年こそはTシャツをゲットしたいと思います。
というわけで、今回も最後までお読みいただきありがとうございました。