IOI2017 Day2 Books

solution.md

まず、本を持ちながら移動しなければいけない距離は Σ|i-p[i]| 以上なのは明らかで、逆にこれで十分なことも言える。
本を持たずに移動する距離を最小化したい。

本の台を頂点として、隣どうしの台を辺で繋いだグラフを考える。
i〜p[i]の間の辺に+1するってのを累積和とかでやっておく。（これをd[0~n-2]とする）

s = 0 の場合、i≠p[i]な i の最大値を mi として、「d[0]からd[mi-1]までの間にある 0 の個数」*2 が求めたいもの。
これで 50 点が来る。

s が真ん中だった場合なんでダメなのかは、2,1,0 とかを考えると分かるように、開始地点を跨いでるだけだと追加コストが生える。

以下の事実に気づくのが重要

• i → p[u]へ輸送する道中にある j について、j → p[j]を輸送するのに追加コストはかからない。

i から j に来て、一旦持ってたのを置いて j を運び、p[j] についたら p[j] を運び・・・というのを繰り返すといつか j に戻ってくるので、そこから i を運ぶのを再開すればいい、という感じ。
サブルーチン的なイメージ。
j を運んでる途中にもまたサブルーチン的なのが生えるかもしれない。

d[i]=0 の辺を切っていくつかの連結成分に分解してみる。
各連結成分は上の考察から、一番外側（両端）の頂点に到達できれば追加コストで全てを網羅できることが分かる。
求めたいものは（「s を含む連結成分の一番外側に到達するまでのコスト」＋「d[i]=0の辺の個数※」）*2 となる。
※：到達する必要のないものは除く。つまり、両端をi=p[i]である限り削った後に残るもの。

さて、後者は簡単に求まるので、前者をどう求めるか。

s から連結成分内で 0-1BFS (or dijkstra)をする。遷移は、

• 隣接へコスト 1 で移動
• i 〜 p[i] の間にある頂点の全てにコスト 0 で移動

で、両端の距離が"前者"の答え。
このままでは後者の遷移のせいで２乗かかるので、setを使ってすでに「コスト 0 で移動」をされた頂点を省くことで、各頂点につき高々１回しか注目されずにすみ、全体で O(N log N) で求まる。
setの代わりに隣接リストを使えば線形にもなりそう。（少なくともUF使えばンマーカッア）

source.cpp

#include "books.h"
#include <bits/stdc++.h>
#define fi first
#define se second
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define rrep(i,n) for(int i = 1; i <= (n); ++i)
#define drep(i,n) for(int i = (n)-1; i >= 0; --i)
#define each(it,c) for(__typeof((c).begin()) it=(c).begin();it!=(c).end();it++)
#define rng(a) a.begin(),a.end()
#define maxs(x,y) x = max(x,y)
#define mins(x,y) x = min(x,y)
#define pb push_back
#define sz(x) (int)(x).size()
#define pcnt __builtin_popcount
#define uni(x) x.erase(unique(rng(x)),x.end())
#define snuke srand((unsigned)clock()+(unsigned)time(NULL));
#define df(x) int x = in()
#define dame { puts("-1"); return 0;}
#define show(x) cout<<#x<<" = "<<x<<endl;
#define PQ(T) priority_queue<T,vector<T>,greater<T> >
#define bn(x) ((1<<x)-1)
#define newline puts("")
#define v(T) vector<T>
#define vv(T) vector<vector<T>>
using namespace std;
typedef long long int ll;
typedef unsigned uint;
typedef unsigned long long ull;
typedef pair<int,int> P;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vl;
typedef vector<P> vp;
inline int in() { int x; scanf("%d",&x); return x;}
inline void priv(vi a) { rep(i,sz(a)) printf("%d%c",a[i],i==sz(a)-1?'\n':' ');}
template<typename T>istream& operator>>(istream&i,vector<T>&v)
{rep(j,sz(v))i>>v[j];return i;}
template<typename T>string join(const vector<T>&v)
{stringstream s;rep(i,sz(v))s<<' '<<v[i];return s.str().substr(1);}
template<typename T>ostream& operator<<(ostream&o,const vector<T>&v)
{if(sz(v))o<<join(v);return o;}
template<typename T1,typename T2>istream& operator>>(istream&i,pair<T1,T2>&v)
{return i>>v.fi>>v.se;}
template<typename T1,typename T2>ostream& operator<<(ostream&o,const pair<T1,T2>&v)
{return o<<v.fi<<","<<v.se;}
const int MX = 100005, INF = 1001001001;
const ll LINF = 1e18;
const double eps = 1e-10;

ll minimum_walk(vi a, int si) {
  int n = sz(a);
  int li = si, ri = si;
  vi d(n+1);
  rep(i,n) {
    int l = i, r = a[i];
    if (l == r) continue;
    if (l > r) swap(l,r);
    d[l]++; d[r]--;
    mins(li,l);
    maxs(ri,r);
  }
  rep(i,n) d[i+1] += d[i];
  ll ans = 0;
  for (int i = li; i < ri; ++i) ans += max(2,d[i]);

  vi dist(n,INF);
  deque<P> q;
  dist[si] = 0; q.pb(P(0,si));
  set<int> s;
  rep(i,n) s.insert(i);
  while (sz(q)) {
    int nd = q[0].fi, v = q[0].se; q.pop_front();
    auto psh = [&](int u) {
      if (dist[u] <= nd+1) return;
      dist[u] = nd+1;
      q.pb(P(nd+1,u));
    };
    int l = min(v,a[v]);
    int r = max(v,a[v]);
    {
      for (auto it = s.lower_bound(l); it != s.end() && *it <= r;) {
        int u = *it;
        dist[u] = nd;
        q.push_front(P(nd,u));
        s.erase(it++);
      }
    }
    if (l && d[l-1]) psh(l-1);
    if (d[r]) psh(r+1);
  }
  int mx = 0;
  rep(i,n) if (dist[i] != INF) maxs(mx,dist[i]);
  ans += mx*2;
  return ans;
}