snuke

先手でも後手でもLISを(N+1)/2に出来ることを証明する
先手が回ってきたら2を言うと1をパスと同じにできるのでn-=2ができる
後手が回ってきて、先手が1ならN、それ以外なら1を言うとn-=2できる

snuke

1,6,72,350,1154,3758,14616,56342,206292,709544,2410382,

snuke

/* エセ Meldable Heap */
/* マージテクを使った簡易的な実装。ただし計算量はlog２つ。 */

// meldable heap (log^2)
struct heap {
  typedef int T;
  typedef priority_queue<T,vector<T>,greater<T>> TQ;
  TQ* q;
  heap():q(new TQ()) {}
  inline void push(T x) { q->push(x);}

snuke

modint calc(long long s) { // returns sum(S[0] ... S[pos(s)-1])
  modint res;
  while (n <= s) {
    res += sum(0, n);
    s -= n;
    s *= b;
  }
  res += sum(0, s);
  return res;
}

snuke

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

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

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

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

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

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