読者です 読者をやめる 読者になる 読者になる

競技プログラミングをするんだよ

ICPC国内予選突破を目標に一日一問題以上解いていきます。

yukicoder 「No265 数学のテスト」

作問 yukicoder 作問

http://yukicoder.me/problems/605

ICPC構文解析対策用に作ってみたもの.
先に注意点を述べておきます.

  • 文字列の長さが5*10^4以下なのでO(|S|)以下でなければ許されない.(制約が甘くてO(|S|^2)でも通るらしい)
  • 出力する整数は32bitで収まらない可能性がある.
  • ある項において定数が一番最初に来るとは限らない.(x*2*xなど)

これらに注意して落ち着いて実装すれば解けるはずです.

色々解法があると思うのでWriter解法だけ挙げておきます.

  1. 文字列の先頭から順に見ていく.
  2. "d{"を引いたときdepthを+1,同様に}を引いたときdepthを-1とする.このdepthが項に対して微分を行う回数である.
  3. "x"を引くと現在の項の次数を+1,"定数"を引くと現在の項の係数をその定数にする.
  4. +を引いたときが項の終了の合図なので微分後の次数と係数を計算."}+"の処理に注意必要

一度ずつしか各文字を見ないのでO(N)

※d{x^n}=nx^{n-1}