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

score : 96.31

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

leaves for each case:
73
1272
1069
21464
16747

snuke

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

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

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

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

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

9
9 -9 8 -7 2 -5 3 -4 9
-5 3 -1 6 -5 5 -2 6 -8
5 -4 3 -6 4 -9 1 -4 7
-9 1 -1 4 -8 7 -7 5 -1
4 -7 2 0 20 0 4 -2 3
-4 5 -5 7 -9 6 -3 6 -5
8 -6 3 -6 1 -8 5 -1 3
-3 1 -8 9 -6 4 -5 6 -4
2 -1 4 -3 6 -7 2 -2 4　　　　　　　　　　　　　　　　　　

snuke

rを根、LCA(h[a],h[b])=cとして、cを寝とする部分木をt、cの子を根とする部分木をt_i(1≦i≦子の数)とする。
以下の新たな変数を置く。
・Ta_i: h[a]が部分木t_iのどこかにある (単にTaならtのどこか)
・Tb_i: h[b]が部分木t_iのどこかにある（単にTbならtのどこか）
・Av: h[a]を頂点vに割り当てる
・Bv: h[b]を頂点vに割り当てる
条件節は以下の通り。＊はbについても同様の条件節を作る。
＊ Ta = true
・ ~Ta_i ∨ ~Tb_i
＊ ~Ta ∨ Ta_i

snuke

    x x x . x    
   . . . . . .   
  . . . . . . .  
 . . . . . . . . 
. . . . . . . . .
 . . . . . . . . 
  . . . . . . .  
   . . . . . .   
    . . . . x    

snuke

import java.util.*;

static final int h = 50, w = 50;

static final int MA = 10;
static final int S = 20;
static final int TH = h*S+MA;
static final int TW = w*S+MA;
static final int MH = TH+1+MA;
static final int MW = TW+1+MA;

snuke

#! /usr/bin/python
import re, sys, os

re_num = '(0|-?[1-9]\d*)'

def check(fname, f):
  lines = re.split(r'\r*\n',f.read())
  global li; li = 0
  def get():
    global li

snuke

/* Custom CSS for GCJ new platform by snuke
** - 問題文のブロックを枠で囲って視認性up
** - 問題文のブロックの上の無駄な余白を無くした
** - 順位表のチェックマークを緑にして視認性up
** - 順位表を等幅フォントにしたりちょっと文字を小さくしたりして調整
** - テーマカラーを赤から青に変えた。青には集中効果があるので。
**
** 注意点：画面幅が狭い時のレイアウトには対応してないので、ある程度広げて使ってください。
*/
table.scoreboard {