naoya_t@hatenablog

いわゆるチラシノウラであります

SRM583

あんまりratingが落ちる心配とかせずに出れるだけ出たほうがいいかも、と思い、引き続きSRMに出てみた。

Easy ("TravelOnMars", 250)

解けた。
速解き系なのに提出のんびりしすぎ。ダイクストラのライブラリをコピーしてきて試すのに時間かけすぎ

Medium ("TurnOnLamps", 500)

開いた。
最初の方針で続けて書いたら良かったのに別方針にしてしまってgdgd

Challenge Phase 〜 System Test

割とMedium通す人が多い&チャレンジ大会。特に何もせず。

o--
青1452→青1448 (-4)

あとで書けたら書く

Easy通過コード

#include <iostream>
#include <sstream>
#include <cstdio>
#include <cmath>
#include <cctype>
#include <algorithm>
#include <string>
#include <vector>
#include <deque>
#include <stack>
#include <queue>
#include <list>
#include <map>
#include <set>

using namespace std;
typedef long long ll;
typedef vector<int> vi;
#define sz(a)  int((a).size())
#define pb  push_back
#define FOR(var,from,to) for(int var=(from);var<=(to);var++)
#define rep(var,n)  for(int var=0;var<(n);var++)
#define all(c)  (c).begin(),(c).end()
#define tr(c,i)  for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); i++)
#define found(s,e)  ((s).find(e)!=(s).end())

const int DIJKSTRA_1 = 1;
const int DIJKSTRA   = 2;
//const int PRIM       = 4;
const int infty = 999999; //INT_MAX;

template <typename T> T infsum(T a, T b){
  return (a == infty || b == infty)? infty : (a + b);
}

list<int> follow_predecessor(const vector<int>& predecessor, int start_v, int goal_v)
{
  list<int> ans;
  for(int v=goal_v; v!=start_v; v=predecessor[v]) ans.push_back(v);
  ans.push_back(start_v);
  reverse(ans.begin(), ans.end());
  return ans;
}

template <typename T> pair<vector<T>,vector<int> >
dijkstra_core(int algo, vector<vector<T> > arclength, int start_v, int goal_v=-1)
{
  int N = arclength.size();

  set<int> S;
  vector<T> distance(N, infty);
  vector<int> predecessor(N, -1);

  S.insert(start_v);
  distance[start_v] = 0;

  rep(v,N){
    if (v == start_v) continue;
    if (arclength[start_v][v] == infty) continue;
    
    distance[v] = arclength[start_v][v];
    predecessor[v] = start_v;
  }
  
  while (((algo & 1) && !found(S, goal_v)) // 指定されたゴールへ
         || ((algo & 6) && S.size() < N)) { // 各点へ
    // while (!found(S, goal_v)) {
    // find v* from V¥S with distance(v*) = min{distance(v):v from V¥S}
    int v_ = -1;
    T d_ = infty;
    rep(v,N){
      if (found(S,v)) continue;
      if (distance[v] < d_) { d_ = distance[v]; v_ = v; }
    }
    if (v_ == -1) break;
    S.insert(v_);

    rep(v,N){ // FOR ALL v from V¥S DO
      if (found(S,v)) continue;
      T d_;
      switch (algo) {
        case DIJKSTRA: case DIJKSTRA_1:
          d_ = infsum(distance[v_], arclength[v_][v]); break;
          //case PRIM:
          //d_ = arclength[v_][v]; break;
      }
      if (d_ < distance[v]) {
        distance[v] = d_;
        predecessor[v] = v_;
      }
    }
  }

  return make_pair(distance, predecessor);
}

template <typename T> pair<list<int>,T>
dijkstra1(vector<vector<T> > arclength, int start_v, int goal_v)
{
  pair<vector<T>,vector<int> > res = dijkstra_core(1, arclength, start_v, goal_v);

  list<int> lis = follow_predecessor(res.second, start_v, goal_v);
  return make_pair(lis, res.first[goal_v]);
}

class TravelOnMars {
 public:
  int minTimes(vector<int> range, int startCity, int endCity) {
    int N=sz(range);
    vector<vector<int> > a(N,vector<int>(N, infty));
    rep(i,N) {
      int r = range[i];
      set<int> s;
      for (int j=i-r; j<=i+r; ++j) {
        int j_ = (j+N*r)%N;
        if (found(s,j_)) continue;
        if (j_ == i) continue;
        a[i][j_] = 1;
      }
    }
    pair<list<int>,int> res = dijkstra1(a, startCity, endCity);
    return res.second;
  }
};

Medium通らないコード

#include <iostream>
#include <sstream>
#include <cstdio>
#include <cmath>
#include <cctype>
#include <algorithm>
#include <string>
#include <vector>
#include <deque>
#include <stack>
#include <queue>
#include <list>
#include <map>
#include <set>

using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<vector<int> > vvi;
typedef vector<string> vs;
typedef vector<long long> vll;
#define sz(a)  int((a).size())
#define pb  push_back
#define FOR(var,from,to) for(int var=(from);var<=(to);var++)
#define rep(var,n)  for(int var=0;var<(n);var++)
#define all(c)  (c).begin(),(c).end()
#define tr(c,i)  for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); i++)
#define found(s,e)  ((s).find(e)!=(s).end())

#define cons(x,y) make_pair((x),(y))

class TurnOnLamps {
 public:
  int minimize(vector<int> roads, string initState, string isImportant) {
    int M = sz(roads), N = M+1;

    map<int,vector<int> > children;
    map<int,int> parent;

    vector<int> sum(N, 0); //, arb(N, 0);

    vector<int> isi(N, 0);
    rep(r, M) {
      bool init = (initState[r] == '1');
      bool isin = (isImportant[r] == '1');
      if (isin) {
        isi[r] = init ? 0 : 1;
      } else {
        isi[r] = 2;
      }
    }
    // printf("%llx -> %llx\n", from, to);

    vector<ll> rma(N, 0);
    rep(r, M){
      int p = roads[r], c = r+1;
      parent[c] = p;
      children[p].pb(c);
      //rma[c] = rma[p] | (1LL << r);
    }

    int ans = 0;

    for (int r=M-1; r>=0; --r) {
      int p = roads[r], c = r+1, u = 0;
      if (sum[c] > 0) {
        ans += (sum[c] / 2);
        sum[c] %= 2;
        if (sum[c]) u=1;
        // if (u && arb[c]) {ans++; u=0;}
      }
      // if (arb[c]) v=1;

      switch (isi[r]) {
        case 0:
          if (u) sum[p]++;//ans++;
          break;
        case 1:
          sum[p]++;
          break;
        case 2: // arb
          if (u) sum[p]++;
          break;
      }
    }
    ans += (sum[0] + 1)/2;

    return ans;
  }
};

→こんな感じ

Test Case #0...PASSED (0.079 msec)
Test Case #1...PASSED (0.034 msec)
Test Case #2...PASSED (0.036 msec)
Test Case #3...PASSED (0.038 msec)
Test Case #4...PASSED (0.057 msec)
Test Case #5...FAILED (0.228 msec)
	Expected: "14"
	Received: "13"

当初の方針で書きなおしたら

class TurnOnLamps {
 public:
  int minimize(vector<int> roads, string initState, string isImportant) {
    int M = sz(roads), N = M+1;

    vector<ll> ms(N, 0);

    ll initStateF = 0LL, isImportantF = 0LL;
    ll roadmask = 1;
    rep(r, M) {
      //ll roadmask = 1LL << r;

      if (initState[r] == '1') initStateF |= roadmask;
      if (isImportant[r] == '1') isImportantF |= roadmask;

      int c=r+1, p=roads[r];
      ms[c] = ms[p] | roadmask;

      roadmask <<= 1LL;
    }

    ll moveF = isImportantF ^ initStateF;
    int cnt = 0;

    for (int r=M-1; r>=0; --r) {
      roadmask >>= 1LL;
      // ll roadmask = 1LL << r;
      if (!(isImportantF & roadmask)) continue;
      if (!(moveF & roadmask)) continue;

      int c=r+1, p=roads[r];
      moveF ^= ms[c]; cnt++;
    }

    return (cnt + 1)/2;
  }
};

Test Case #0...PASSED (0.032 msec)
Test Case #1...PASSED (0.009 msec)
Test Case #2...PASSED (0.008 msec)
Test Case #3...PASSED (0.008 msec)
Test Case #4...PASSED (0.008 msec)
Test Case #5...PASSED (0.017 msec)

→Practice Room通った