beet's soil

競プロのことなど

codeFlyer 本戦 E - 数式とクエリ

AtCoder

ぱじぇ見てるか〜w

問題

E - 数式とクエリ

方針

SをN変数一次関数 f(a1,a2,...aN) として見ると、 ∂f∂ai を各iについて求めておくことでクエリに O(1) で答えられることがわかる。
具体的には、 ansi=f(a1,a2,...,aN)+∂f∂abi⋅(xi−abi) となる。

まずは構文解析をしてf(a1,a2,...aN)を求める。

構文解析の基本はこれが参考になる。
構文解析 Howto · GitHub
上の記事ではStateという型を定義していたが、僕はstring&とint&に分ける方が好みなのでそうしている。

リクエストがあったので今回の場合についてもう少し詳しく説明する。

まず与えられたBNFを見るとexprとtermとvalueが必要なことがわかる。
また、今回の演算は全て二項演算であり、LL1（現在の状態から1文字見ると次の状態がわかるタイプ）であることも確認できる。
構文解析では複数の関数を相互に呼び出す必要があるので、まずはプロトタイプ宣言をする。

int expr(string &s,int &p);
int term(string &s,int &p);
int value(string &s,int &p);

続いて各関数の実装を行う。
とは言っても、今回のようにBNFが陽に与えられている場合はやるだけである。
その関数として定義されているtokenとみなせる間処理続ければよい。オーダーは O(|S|)となる。 

int expr(string &s,int &p){
  int res=term(s,p);
  while(p<(int)s.size()){
    if(s[p]=='+'){
      p++;
      int tmp=term(s,p);
      res+=tmp;
      res%=MOD;
      continue;
    }
    if(s[p]=='-'){
      p++;
      int tmp=term(s,p);
      res+=MOD-tmp;
      res%=MOD;
      continue;
    }
    break;
  }
  return res;
}

int term(string &s,int &p){
  int res=value(s,p);
  while(p<(int)s.size()){
    if(s[p]=='*'){
      p++;
      int tmp=value(s,p);
      res*=tmp;
      res%=MOD;
      continue;
    }
    break;
  }
  return res;
}

int value(string &s,int &p){
  static Int x=0;
  if(s[p]=='a'){
    return a[x++];
  }
  assert(s[p]=='(');
  p++;
  int res=expr(s,p);
  assert(s[p]==')');
  p++;
  return res;
}

value内のかっこの処理では閉じかっこをスキップする必要があることに気をつける。

さて、これでf(a1,a2,...aN) を求めることはできた。
次に、偏微分を行うための下準備として構文木を作る。
構文木とは与式からオペランドとオペレーターをノードとして作ったグラフである。
例えばサンプル1は以下のような木として考えられる。

f:id:beet_aizu:20180722153226j:plain

今回は全ての演算が二項演算であったので、適当な操作により二分木にすることができる。
構文木上をpost-orderで走査することで実際に式が評価できることを確認してほしい。

実際に木を作るために、ノードに載せる情報を考える。
今回は左右の子、評価の結果、（オペレータの場合）演算の種類、（オペランドの場合）aの番号が必要である。
したがってノードは以下のように定義できる。

struct T{
  T *l,*r; // 左右の子のポインタ
  char c; // 演算の種類
  Int idx,val; // aの番号、評価の結果
  T(char c):c(c){} 
  void set(T *a,T *b,Int i,Int v){
    l=a;r=b;idx=i;val=v;
  }
};

返り値の型を変えたので、当然先ほどの関数も書き換える必要がある。詳細は省略する。
これは競プロなのでnewした後にdeleteする必要はない。（たまにMLEで破滅するんですけどね）

T* expr(string &s,Int &p){
  T *l=term(s,p);
  while(p<(Int)s.size()){
    if(s[p]=='+'){
      T *t=new T(s[p++]);
      T *r=term(s,p);
      t->set(l,r,-1,((l->val)+(r->val))%MOD);
      l=t;
      continue;
    }
    if(s[p]=='-'){
      T *t=new T(s[p++]);
      T *r=term(s,p);
      t->set(l,r,-1,((l->val)+MOD-(r->val))%MOD);
      l=t;
      continue;
    }
    break;
  }
  return l;
}

T* term(string &s,Int &p){
  T *l=value(s,p);
  while(p<(Int)s.size()){
    if(s[p]=='*'){
      T *t=new T(s[p++]);
      T *r=value(s,p);
      t->set(l,r,-1,(l->val)*(r->val)%MOD);
      l=t;
      continue;
    }
    break;
  }
  return l;
}

T* value(string &s,Int &p){
  static Int x=0;
  if(s[p]=='a'){
    p++;
    T *t=new T('a');
    t->set(nullptr,nullptr,x,a[x]);
    x++;
    return t;
  }
  assert(s[p]=='(');
  p++;
  T* res=expr(s,p);
  assert(s[p]==')');
  p++;
  return res;
}

最後に、 ∂f∂ai を求めることを考える。
これは先ほど構築した二分木に対し偏微分を行えばよい。

偏微分は以下のように計算できる。
z=x+y のとき ∂z∂x=1,∂z∂y=1
z=x−y のとき ∂z∂x=1,∂z∂y=−1
z=x∗y のとき ∂z∂x=y,∂z∂y=x

また、偏微分の結合律から、二分木の根からDFSを行うことで各aに対して偏微分を求められることがわかる。
例えば z=(s−t)∗u,w=s−t のとき、 ∂z∂t=∂z∂w⋅∂w∂t=u⋅(−1)=−u である。

下図のようにイメージするとわかりやすいかもしれない。
f:id:beet_aizu:20180722155155j:plain
f:id:beet_aizu:20180722155159j:plain

具体的な実装は以下のようになる。

void dfs(T *t,Int dl){
  if(~(t->idx)){
    c[t->idx]=dl;
    return;
  }
  if(t->c=='*'){
    dfs(t->l,dl*(t->r->val)%MOD);
    dfs(t->r,dl*(t->l->val)%MOD);
    return;
  }
  dfs(t->l,dl);
  if(t->c=='-') dfs(t->r,(MOD-dl)%MOD);
  else dfs(t->r,dl);
}

これで偏微分が求めることができたので、あとはクエリを処理するだけとなる。

実装例

Submission #2761626 - codeFlyer （bitFlyer Programming Contest）本選

おわりに

機械学習の誤差逆伝搬っぽくておもしろいなあと思った。
本番解けなくてくやしい。