naoya_t@topcoder

Google Code Jam 2010 Round 1B

11:52 |

5/23 1am〜

夢の満点通過ktkr！

A. File Fix-it

ディレクトリリストが与えられ、これを全部作るのに mkdir を何回使う必要があるか。既存のディレクトリのリストも与えられている。

• xhlさんのようにシェルスクリプトで実際にディレクトリを掘って解くのが正解w
• 残念ながらC++で書きました
• 最初はディレクトリツリーを表現する構造を書こうと思ったけど
• めんどくさいので、既存のサブディレクトリをすべて持った set<string> で良しとすることに
  • なにげに deja とか書いてるね。仏語で"already"ですはい
    • 変数 nu は仏語ではありません。念のため。（そこの君わざわざ辞書ひかない）
• 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++でメモ化再帰。
  • modつきの組み合わせ数演算の部分は4月のSRMでcafelier先生が書いてたやつをまるっと参考にしつつ

#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位で無事通過。まさかの満点通過。