メタアルゴリズム問題
AOJ
AOJ-ICPC
ICPCアジア
AOJ-ICPC450点
構文解析
カッコ列
stack
データ構造
メタアルゴリズム問題
BNF
連想配列(setやmap)
構文解析:再帰下降パーサ
入れ子構造
操作をstackを用いて高速化する
アドホックに構文解析した。カッコ列の問題とみなして、stack で処理した。 問題へのリンク 問題概要 次のような「配列を宣言したり配列に値を代入したりする処理を表すプログラム」が与えられる。 a[2147483647] a[0]=1 B[2] B[a[0]]=2 a[B[a[0]]]=3 a[2147…
AtCoder
ABC-Ex
橙色diff
多項式・FPS(形式的冪級数)
DP
順列を題材とした問題
順列の数え上げ
順列テク:巡回群の直積と見る
FFT
DP高速化
DP高速化:FFT
分割統治FFT
分割統治法
二項係数
包除原理:対称性
包除原理
数え上げ問題
解空間:O(N!)通りの選択肢
指数型FPS
メタアルゴリズム問題
なもりグラフ
入力が定数個
数珠
AtCoder650点
オンライン処理を実現する分割統治法
コンテスト終了から 8 秒後の AC で泣いた。でも、分割統治 FFT が自力で書けてよかった。想定解法は FPS だった。 問題へのリンク 問題概要 次の問題がある。 の順列 と が与えられる。 これらをもとに次のように、頂点数 、辺数 の有向グラフを作る。 頂点…
LCA ライブラリを持っていれば書くだけ！ 問題へのリンク editorial 問題概要 頂点の根付き木が与えられる (根は頂点 0)。この木上で幅優先探索を行う (隣接する頂点のうち、頂点番号が小さい順にキューに push する)。 このとき、探索順序が であったとした…
こういうの超苦手。。。解き方はわかるけど実装を工夫する感じの。 問題へのリンク 問題概要 N 頂点のツリー (頂点番号は 1, 2, ..., N) と、(1, 2, ...., N) の順列 a が与えられる。 このツリーを頂点 1 から出発して BFS したとして、その頂点訪問順序が …
