SPOJ埋め日記
最近これといって特にコードをあまり書かないで過ごしていたのですが，気づいたらアジア地区予選まで3週間とかになっていて
何か目標を持って練習した方がいいような気がしてきたのでSPOJの3ページ目(USERソート順)を埋めることにしました．
現状だと↓みたいなかんじで，BrainFuckの問題を除けばあと14問です．解いた問題の記録とか書いていきたいな．
TODOリスト
以下個人的なメモ．
☆https://www.spoj.pl/problems/GSS1
- BinaryIndexedTreeを拡張したような構造を使うと解けるらしい．
☆https://www.spoj.pl/problems/WORDCNT
- あほみたいなもんだいだけどなぜかWrongAnswerくらって放置してる．
☆https://www.spoj.pl/problems/BRCKTS
- SegmentTreeを使えば解ける…らしいけど方針がついていませんorz
☆https://www.spoj.pl/problems/POTHOLE
- 最大流問題だけどなぜかWrongAnswerで放置してる．
☆https://www.spoj.pl/problems/TRICENTR
- めんどうな幾何問題．幾何ライブラリで解く予定．
☆https://www.spoj.pl/problems/PICAD
- なぜかWrongAnswerで放置(ry
☆https://www.spoj.pl/problems/EQBOX
- 幾何問題．
- 3角関数の式立てて解くらしい．
☆https://www.spoj.pl/problems/JRIDE
- 簡単そうだけどなぜかWrongAnswerで放置
☆https://www.spoj.pl/problems/ROADS
- 拡張ダイクストラらしい．
☆https://www.spoj.pl/problems/TRIP
- よくわからない
- 前考えたアルゴリズムではTLEを食らっていた
☆https://www.spoj.pl/problems/THREECOL
- よくわからない
- 何らかの規則で点を置いてシミュレート?
☆https://www.spoj.pl/problems/POSTERS
- IntervalTreeでも使うのかな．
☆https://www.spoj.pl/problems/TWENDS
- ゲームの問題
- DPっぽく最適解出すのかし．
☆https://www.spoj.pl/problems/FPOLICE
- グラフの問題ということしか覚えてない．
ついでに4ページ以降でも見当の付くものリスト：
☆https://www.spoj.pl/problems/ORDERS
- IntervalTreeを使うとか誰か言ってた．
- 問題文は読んですらいない．
☆https://www.spoj.pl/problems/QUEST4
- 2部グラフの最大マッチング，すなわち最大流問題に帰結される．
☆https://www.spoj.pl/problems/CMEXPR
- 文字式の括弧をはずしていく
- 構文木作って括弧はずせるならはずすとかやればいいだけなんじゃ…と思うけどAC率がやけに低くていやな感じ．
☆https://www.spoj.pl/problems/MUL
- 掛け算をする
- 高速フーリエ変換?
☆https://www.spoj.pl/problems/TRANK
- 小さいインプット．
- 安心のAC率．
☆https://www.spoj.pl/problems/WATER
- よくわからない．
☆https://www.spoj.pl/problems/FRACTION
- i番目に小さい分数式を求める問題．
- オイラーのφ関数とかなんかやれば出来そう(適当)
☆https://www.spoj.pl/problems/GEOPROB
- 多倍長専用とか死ねば良いのに…
☆https://www.spoj.pl/problems/TREE
- ある探査木を構成するような列の個数を求める．
- 再帰っぽくできそう．(適当)
☆https://www.spoj.pl/problems/PB
- 問題名短い.
- よくわからない．
☆https://www.spoj.pl/problems/DISTANCE
- マンハッタン距離→L∞距離の変換で解決する．
☆https://www.spoj.pl/problems/SUBSUMS
- 分割＋ソート＋2分探索
☆https://www.spoj.pl/problems/SHORTCUT
- 適当なデータ構造を組むとできそう．
