SRM 583

出てました。
oo- +50 (664.45) 10位！！嬉しい。
1804 -> 1981 (+177)
500の解法思いつくのが早かったらしい？
終了間際に950を出してた人がいたので何も考えずにsample投げたら落ちてくれた。(+50)

500

概要：
木の辺に電灯の現在の状態(on/off)と点いていなければならないかどうかが決まっているので、その条件を満たすために必要なパス上の電灯のon/offを切り替える回数を最小値は？
解法：(多分ちょっと日本語が貧相)
根付き木にしてDFS。
パスというのは根付き木(有向)上のパス２つをある頂点で繋げたものなので、各頂点に繋がっている切り替えをしなければならないパスの個数を求める。これをxとすると、answer+=x/2で、xが奇数の場合は保留して親の頂点に委ねる。
サンプルではわざわざ変な切り替え方をしてるけど、各辺について切り替える必要があるのは高々１回。

vector<int> to[MX];
bool a[MX], b[MX];
int ans, m, n;

class TurnOnLamps {
  public:
  int dfs(int v, int p){
    int cnt = 0, u, res;
    rep(i,to[v].size()){
      u = to[v][i];
      if(u == p) continue;
      res = dfs(u,v);
      if(!a[u] && b[u]) cnt++;
      if(!b[u]) cnt += res;
      if(b[u] && a[u]) ans += res;
    }
    ans += cnt/2;
    return (cnt&1);
  }
  
  int minimize(vector <int> e, string s, string t) {
    m = e.size(); n = m+1;
    rep(i,m){
      a[i+1] = (s[i] == '1');
      b[i+1] = (t[i] == '1');
    }
    rep(i,n) to[i].clear();
    rep(i,m){
      to[e[i]].pb(i+1);
      to[i+1].pb(e[i]);
    }
    
    ans = 0;
    ans += dfs(0,-1);
    
    return ans;
  }
}

roads[i] <= i を見逃しててちょっとだけ実装量増えた。まーしゃーないかぁ。デバッグしないように気をつけないと・・・

250

概要：やるだけ
解法：やるだけ

bool used[MX];

class TravelOnMars {
  public:
  int minTimes(vector <int> r, int s, int t) {
    int n = r.size(), v, d;
    queue<P> q;
    q.push(P(s,0));
    rep(i,n) used[i] = false;
    while(!q.empty()){
      P p = q.front(); q.pop();
      v = p.fi; d = p.se;
      if(used[v]) continue;
      used[v] = true;
      if(v == t) return d;
      rrep(i,r[v]){
        q.push(P((v+i)%n,d+1));
        q.push(P((v-i+n*100)%n,d+1));
      }
    }
    return -1;
  }
}

((v-i+n)%n)みたいなことすると危ない。けどこのBFSだと配列外参照が起きる前にreturnされるから多分大丈夫。
こういうのはWFの方が頭良いということを知った。
classの外に変数作ってるの、普通だったらあから様にひどいよねw