ferinの競プロ帳

競プロについてのメモ

2017-12-17から1日間の記事一覧

AOJ 2152 Restrictive Filesystem

問題ページ Restrictive Filesystem | Aizu Online Judge 考えたこと 10^9の配列確保して1つずつ記録していくのはメモリ的にも計算量的にも不可能なので座圧は必須そう dp[i] = (j, k) (位置iからjまでkが記録されている)としてunordered_mapを使ってメモリ…

AtCoder Regular Contest 087 E - Prefix-free Game

問題ページ E - Prefix-free Game 考えたこと ゲームと言われたのでサンプルについてWin-Loseの探索木を書いてみるがよくわからない 01文字列なのでtrie木を書いてみると葉を通らないような位置に頂点を追加する問題に言い換えられることがわかった 木上のゲ…