snuke

まず、本を持ちながら移動しなければいけない距離は Σ|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 とかを考えると分かるように、開始地点を跨いでるだけだと追加コストが生える。

snuke

B勝ちの頂点を求めていく。

まず、以下の条件を満たす最小のNG集合をBFSで求める。（次数記録しながらやるやつ）（NGというネーミングに特に意味はないです）

• 充電頂点は全部NG
• Aの頂点で、NG頂点に辺が生えてるものはNG
• Bの頂点で、NG頂点にしか辺が生えていないものはNG

NG集合に含まれない頂点はB勝ちとなる。
というのも、NG集合に含まれない頂点集合内では、

snuke

score : 96.31

full data: https://drive.google.com/open?id=0B7FRO5ydKzReWENzWFJPOVhUcGs

leaves for each case:
73
1272
1069
21464
16747

snuke

// 高速アダマール変換
typedef long long Int;
void ada(vector<Int>& d) {
  int n = d.size();
  for (int i = n; i >= 1; i >>= 1) {
    for (int j = 0; j < n; ++j)  if (j&i) {
      int x = d[j^i], y = d[j];
      d[j^i] = x+y;
      d[j] = x-y;
    }

snuke

xの山とyの山のgrundy数を(x,y)に書いた表を考える。

1*1の表：
|0|
0-indexedなので、両方0の山です。

2*2の表：
|01|
|10|
このパターンが基本になってきます。

snuke

Hello, I am Kento Nikaido (aka. snuke) from the team Running.
I'd like to set you a puzzle.
I think of some English words and I tell you the FORMAT of the words.
Can you guess these words?

Example:
Q. ABCCDCE -> A. running
(Some words may be in the past tense or the -ing form.)

Problem:

snuke

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <vector>
#include <map>
#include <ctime>
#include <cstdlib>
#define fi first
#define se second
#define rep(i,n) for(int i = 0; i < n; i++)

snuke

// HL-decomposition
struct hl {
	int n;
	vector<vi> to, d;
	vi vd, vk, pv, dep;
	vector<bit> t; // bit
	int root;
	hl() {}
	hl(int mx):n(mx),to(mx),vd(mx),vk(mx),dep(mx) {}
	void add(int a, int b) {

snuke

#include <cstdio>
#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <algorithm>
#define rep(i,n) for (int i = 0; i < n; ++i)
#define df(x) int x = in()
#define fi first

snuke

// 乱数依存＋map使用の軽実装バージョン
#include <cstdio>
#include <vector>
#include <map>
#include <cstdlib>
#define rep(i,n) for (int i = 0; i < n; ++i)
using namespace std;
typedef long long ll;

class ToursDecomposition {