2010-05-23
Google Code Jam 2010 Round 1C
| 
5/23 6pm〜
1Bで通ったので観戦モード（と言いつつ問題を解く）。
外出先から戻って18:25からのスタート。
時間内に3問とも解けた。終了後、practiceのデータを通したらC-large以外は全部通った。76点相当。実行時間＋submitの手間を考慮しても141〜142位あたりで通過。
ていうか何でC-large通らなかったんだ？（後述）
A. Rope Intranet 18:32 (0:07)
- こういうの最近見た気がします
- あれだ。一昨日のSRM470 Div1 Medium
- バブルソートの回数でおｋ
#include <iostream>
#include <sstream>
#include <algorithm>
#include <string>
#include <vector>
#include <deque>
#include <stack>
#include <queue>
#include <list>
#include <map>
#include <set>
#include <cstdio>
#include <cmath>
#include <cctype>
using namespace std;
#define sz(a) int((a).size())
#define pb push_back
#define rep(var,n) for(int var=0,lim=(n);var<lim;var++)
#define REP(var,ar) for(int var=0,lim=(ar).size();var<lim;var++)
#define FOR(var,from,to) for(int var=(from),till=(to);var<=till;var++)
#define all(c) (c).begin(),(c).end()
#define rall(c) (c).rbegin(),(c).rend()
#define found(s,e) ((s).find(e)!=(s).end())
typedef pair<int,int> ii;
int main(){
int T; cin >> T;
rep(t,T){ // 15
int N; cin >> N;
vector<ii> wire(N);
rep(n,N){
int a, b; cin >> a >> b;
wire[n] = ii(a,b);
}
sort(all(wire));
int s=0;
rep(n,N){
rep(i,n) {
if(wire[n].second<wire[i].second)s++;
}
}
printf("Case #%d: %d\n", 1+t, s);
}
return 0;
}
B. Load Testing 18:48 (0:23)
皆さん題意がつかめずに苦労されていたようですが…
負荷テストを何度かやって、サーバがどこまでの負荷に耐えられるか知りたい。（求める負荷は厳密な数字ではなく）a≦x≦a*C みたいな範囲でわかればいい。あと何回負荷テストをしたら、要求する狭さで範囲が求まるか。
- 対数空間で二分探索する感じ。logの底がC、みたいな。
- たぶん答えは ceiling( log_2( log_C( P/L ) ) ) みたいな値
int main(){
int T; cin >> T;
rep(t,T){
int l,p,c; cin >> l >> p >> c; // 1<=L<P<=1e9, C:2..10
double x = log((double)p/l)/log((double)c);
int ans = max(0, (int)ceil(log(x)/log(2.0)));
printf("Case #%d: %d\n", 1+t, ans);
}
return 0;
}
- これで答えがあうよ
- でもチキンなので整数演算で書きました
// #include,#defineの内容はA,B,C共通なので省略
typedef pair<int,int> ii;
typedef long long ll;
int main(){
int T; cin >> T;
rep(t,T){
int l,p,c; cin >> l >> p >> c; // 1<=L<P<=1e9, C:2..10
ll L=l, P=p, C=c;
int ans;
if (P <= L*C) {
ans = 0;
} else {
ans=1;
for(ll j=L,m=C*C; j*m<P; m*=m)
ans++;
}
printf("Case #%d: %d\n", 1+t, ans);
}
return 0;
}
C. Making Chess Boards 19:40 (1:15)
与えられた白黒パターンの木版からチェス盤（というか市松模様）を切り出す問題。
大きい順、上から、左から、と明確に優先順位があるので一意に求まる。計算量だけの問題か。
- ある升目（行r,列c）から右にどれだけ市松模様が続いているか、をO(1)で分かるようにしておいて
- (r,c)を左上、(r+w-1,c+w-1)を右下とする幅w高さwの正方形を切り出したら市松模様になっているかの判定は、正方形の左端各行(r+i,c)からw以上市松模様が続いていることと、左端各行の色が交互に白黒白黒…となっていること
- 切り出した場所については、市松模様が続いていないのがわかる数字を設定しておけばよい（※ここでバグった）
// #include,#defineの内容はA,B,C共通なので省略
typedef pair<int,int> ii;
inline int unhex(char c){
if (c<='9') return c-'0';
else return c-'A'+10;
}
int main(){
int T; cin >> T;
rep(t,T){
int M,N; cin >> M >> N; // それぞれ４の倍数; 1-512/512
vector<vector<int> > bt(M,vector<int>(N,0));
vector<vector<int> > pt(M,vector<int>(N,0));
rep(m,M) {
string s; cin >> s;
rep(i,N/4){
int c=unhex(s[i]);
for(int j=0,mk=8;j<4;j++,mk>>=1){
//if (i*4+j >= N) cout << "err" << endl;
bt[m][i*4+j] = (c & mk)?1:0;
}
}
int cont=0, last=bt[m][N-1];
for(int i=N-1; i>=0; i--){
if (bt[m][i]==last) {
pt[m][i] = cont = 1;
} else {
pt[m][i] = ++cont;
}
last = bt[m][i];
}
}
int maxw=min(M,N), rest=M*N;
vector<int> ks(maxw+1,0);
for(int w=maxw; w>1; w--){
for(int sy=0; sy<=M-w; sy++) {
for(int sx=0; sx<=N-w; sx++) {
if (pt[sy][sx] < w) continue;
bool ok=true;
for(int r=1,po=bt[sy][sx]; r<w; r++){
int y=sy+r;
if (pt[y][sx] < w || bt[y][sx]==po) { ok=false; break; }
po = 1 - po;
}
if (ok) { // take it
ks[w]++; rest -= w*w;
rep(r,w) {
int y=sy+r;
rep(c,w){
pt[y][sx+c] = 0;
}
if (sx==0) continue;
int b=pt[y][sx-1];
for (int x=sx-1; x>=0; x--){
if (pt[y][x]==1) break; ///OOPS
pt[y][x]-=b-1; //printf(" (%d,%d)-%d=%d¥n", x,y,b, pt[y][x]);
}
}
}
}
}
}
ks[1] = rest;
vector<ii> res;
for(int w=1; w<=maxw; w++) {
if (ks[w] > 0) res.pb(ii(w,ks[w]));
}
reverse(all(res));
int K=sz(res);
printf("Case #%d: %d¥n", t+1, K);
rep(k,K) {
printf("%d %d¥n", res[k].first, res[k].second);
}
}
return 0;
}
C-large (practice) を通しても1秒で終わる。しかしincorrectだ…オーバーフローは無いはずだし何でだろうと思ってソースを見返したら
if (pt[y][x]==1) break;
がおかしい。既にチェス盤を切り出した所であれば0になっているはずだしそれならbreakしてほしい。
if (pt[y][x]<=1) break;
が正しい。これでC-largeも通った。（C-smallが通ったのは偶然だろう）
というわけで皆さんお疲れ様でした。次はRound 2でお会いしましょう。
Google Code Jam 2010 Round 1B
| 
5/23 1am〜
夢の満点通過ktkr！
A. File Fix-it
ディレクトリリストが与えられ、これを全部作るのに mkdir を何回使う必要があるか。既存のディレクトリのリストも与えられている。
- xhlさんのようにシェルスクリプトで実際にディレクトリを掘って解くのが正解w
- 残念ながらC++で書きました
- 最初はディレクトリツリーを表現する構造を書こうと思ったけど
- めんどくさいので、既存のサブディレクトリをすべて持った set<string> で良しとすることに
- なにげに deja とか書いてるね。仏語で"already"ですはい
- 変数 nu は仏語ではありません。念のため。（そこの君わざわざ辞書ひかない）
- なにげに deja とか書いてるね。仏語で"already"ですはい
- split()のコードはこのブログのどこかにあるのでコピペ割愛
#include <iostream>
#include <sstream>
#include <algorithm>
#include <string>
#include <vector>
#include <deque>
#include <stack>
#include <queue>
#include <list>
#include <map>
#include <set>
#include <cstdio>
#include <cmath>
#include <cctype>
using namespace std;
#define sz(a) int((a).size())
#define pb push_back
#define rep(var,n) for(int var=0,lim=(n);var<lim;var++)
#define REP(var,ar) for(int var=0,lim=(ar).size();var<lim;var++)
#define FOR(var,from,to) for(int var=(from),till=(to);var<=till;var++)
#define all(c) (c).begin(),(c).end()
#define rall(c) (c).rbegin(),(c).rend()
#define found(s,e) ((s).find(e)!=(s).end())
//#include "cout.h"
int main(){
int T; cin >> T;
rep(t,T){
int N, M; cin >> N >> M;
set<string> deja;
rep(n,N){
string name; cin >> name;
vector<string> ns = split(name,'/');
int nu=sz(ns)-1;
for(int i=nu;i>=1;i--){
string s="";
rep(j,i){
s += "/" + ns[1+j];
deja.insert(s);
}
}
}
int ans = 0;
rep(m,M){
string name; cin >> name;
vector<string> ns = split(name,'/');
int nu=sz(ns)-1;
for(int i=nu;i>=1;i--){
string s="";
rep(j,i){
s += "/" + ns[1+j];
if (found(deja,s)) {
;
} else {
ans++; deja.insert(s);
}
}
}
}
printf("Case #%d: %d\n", t+1, ans);
}
return 0;
}
デバッグに使ってるローカルのcout.hをincludeしたままA-smallのコードをsubmitしてしまったことにA-largeで気づき、A-largeではコメントアウトして提出。しかしsmallは一度acceptされてしまうとコードも再投稿できないのでどうしたものかと運営にメールしたら、手動でrejectしてくれたので再投稿。順位落ちるけどこれですっきり。中の人は去年のRound 1Aでも同じ事をやってメール送って対応してもらった時と同じ人だった。
B. Picking Up Chicks
chickがN匹いて、それぞれの位置（すべて非負）と速度（すべて正）が整数で与えられている。chickは自力では前を走るのろい奴を追い抜けず、クレーンでのろい奴を上から持ち上げて後続のchickをくぐらせる必要がある。位置Bに時刻Tまでに少なくともK匹到着するには何回クレーンswapを発動させなければならないか。
- （鉄道の）ダイヤグラム的なものをノートに書いて考えてた。
- すべてのchickの動きは直線 y = Vi*x + Xi で表せるお
- Xi≧0, Vi≧1なのですべて右上がり
- 追いつくポイント = ２直線の交点
- 前のchickが（swapでベストを尽くした場合）時刻Tまでに到着できるやつなら無理に追い抜かなくて良いとして、要は頑張ればTni間に合うchickが、どんなに頑張ってもTに間に合わない雑魚chickを何匹抜かす必要があるか（＝何回直線が交差するか）を数えといて
- 抜かす回数の少ない順にK匹選んでΣを返せばよさげ
- というわけでまたC++ですが
int main(){
int C; cin >> C; // 100
rep(c,C){
cout << "Case #" << (c+1) << ": ";
int N,K,B,T; cin >> N >> K >> B >> T;
// N:1-10/50 K:0-3/N B:1-1e9 T:1-1000
vector<int> x(N), v(N);
rep(i,N) cin >> x[i];
rep(i,N) cin >> v[i];
vector<double> ar(N); int cn=0;
rep(i,N){
ar[i] = ((double)(B - x[i]))/v[i];
if (ar[i]<=T) cn++;
}
if (cn < K) {
cout << "IMPOSSIBLE" << endl;
continue;
}
vector<int> swa(N,987654321);
rep(i,N) {
if (ar[i]>T) continue;
int sw=0;
rep(j,N){
if (i==j) continue;
if(ar[j]<=T) continue;
double mx = (double)(x[j]-x[i])/(v[i]-v[j]);
if (0 <= mx && mx <= T) sw++;
}
swa[i] = sw;
}
sort(all(swa));
int S=0; rep(i,K) S+=swa[i];
cout << S << endl;
}
return 0;
}
クレーンで前の遅いやつを持ち上げて後ろから来た速いやつに先に行かせるテクニックは問題Cでも使われた（別の意味で）。
C. Your Rank is Pure
127って素数だよね。単に素数ってだけじゃなく、31番目の素数だよね。しかもその31ってのがまた素数でさ。
うん。その31も5番目の素数で、その5がまた素数で、5も3番目の素数で、3も2番目の素数で、2は1番目の素数だよね。
ここでは素数だが、別に素数以外の集合でもこれと同じことが出来る。ここでの127をnとして、nでこんな事ができる集合は何通りあるか。答えがでかくなるのでmod 100003で返してくれればいいよ
- 例えばn=500として
- 500が集合Sで小さい方から何番目かというのは1〜499の可能性がある。まあforループで全部見るとしよう
- 例えば100番目だとする。だとしたら"100"もSに含まれているべきで、
- その100も小さい方から何番目かといえば1〜99番目までの可能性があるからループしよう。とりあえず10番目だとすると、"10"もSに含まれているべきで、それと同時に、101から499まで（両端included）の間に11番目から99番目がいることになって、そいつらの内容はどうでも良いので組み合わせの数を計算（この場合 399C89 通り）して mod 100003 したやつを掛けたものになりそう
- 10も小さい方から1〜9番目までの可能性がある。例えばSの中で一番小さいとすると、1はSに含まれないのでそれより下はパターン数が増えず 1、それに11から99までの間に2番目から9番目がいるので 1 x 89C8 通り、これをさっきの100の時の話に戻して 399C89 を掛けて…
- ってDPですねこれは
- 書いたコードはC++でメモ化再帰。
#define rep(var,n) for(int var=0,lim=(n);var<lim;var++)
#define found(s,e) ((s).find(e)!=(s).end())
typedef long long ll;
typedef pair<int,int> ii;
map<ii,ll> mm;
static const ll MODVAL = 100003ll;
ll add(ll x, ll y) { return (x + y) % MODVAL; }
ll sub(ll x, ll y) { return (x - y) % MODVAL; }
ll mul(ll x, ll y) { return (x * y) % MODVAL; }
ll pow(ll x, ll y) {
ll v = 1;
for(;y;x=mul(x,x),y>>=1)
if(y&1) v = mul(v, x);
return v;
}
ll divi(ll x, ll y) { return mul(x, pow(y, MODVAL-2)); }
ll C(ll n, ll k) { // nCk
ll v = 1;
for(ll i=1; i<=k; ++i)
v = divi(mul(v, n-i+1), i);
return v;
}
ll sub(int n,int last){
if (n == 1) return 1LL;
//nがk番目(k=1..n-1)
ii key=ii(n,last);
if (found(mm,key)) return mm[key];
ll skm=last-n-1;
ll a = 0LL;
if (last > 10000) {
for(int k=1; k<=n-1; k++){
a += sub(k,n);
}
} else {
for(int k=1; k<=n-1; k++){
///当然kが入ってる
int kos=n-k-1;
a += mul(C(skm,kos),sub(k,n));
}
}
mm[key] = a % MODVAL;
return mm[key];
}
int main(){
int T; cin >> T; //100
mm.clear();
rep(t,T){
int n; cin >> n; // 2-500
int ans = (int)sub(n,987654321);
printf("Case #%d: %d¥n", t+1, ans);
}
return 0;
}
同じコードでC-largeを通そうとしたらCase #2あたりまで吐いたところで死んでる。n=500は無理か・・・あきらめムード
あ。組み合わせ数を計算している C(n,k) をメモ化することでスピードアップできるよね… コード改竄。コンパイル。C-large食わせた。まだCase #2あたりで止まっている前のコードをクレーンで持ち上げて追い抜いて瞬殺。投稿。T=8分に間に合った。
以下修正部分：
typedef pair<ll,ll> ll2;
map<ll2,ll> cmm;
ll C(ll n, ll k) { // nCk
ll2 p(n,k);
if (found(cmm,p)) return cmm[p];
ll v = 1;
for(ll i=1; i<=k; ++i)
v = divi(mul(v, n-i+1), i);
return cmm[p]=v;
}
ここまでで1時間34分。時間が随分余ったのでA-smallの再投稿のこととか運営にメールしてみた。→手動でリジェクトしてくれたので再投稿できた。
３問ともsmall/large全問submitして、A-smallの再投稿で若干順位を落としたけれど終了前402位、終了後291位で無事通過。まさかの満点通過。
コメント
トラックバック - https://topcoder-g-hatena-ne-jp.jag-icpc.org/n4_t/20100523