UVa/Volume5
Last-modified: 2008-05-23 (金) 11:16:00
Volume5
- 514:Rails
- Data Structure? - Stack?
- 生成される可能性のある列は、「駅にStackとして積む」か、「そのままB方向へ向かう」かのどちからの動作によってしか生まれないから、それをシミュレーションしていけばよい.
具体的には、出力の最初の番号の列車が出てくるまでは車両をStackに積み、列車が出てくる度に、Stackの残りの列車をチェックするようにする.
- 516:Prime Rand
- Mathematics? - Factorization Into Prime Factors?
- 素因数分解の問題．
入力は素因数とその指数で，入力値から1引いた値を素因数分解した結果を出力する．
- 530:Binomial Showdown
- Mathematics?
- 369と同じ.
多倍長だとTLE.
常に約分しながら計算していく.
約分は最大公約数をとって、分母と分子をそれで割る.
- 543:Goldbach's Conjecture
- Mathematics? - Primality Test?
- 素数の和の組み合わせを探す.
- 556:Amazing
- Backtracking?
- 迷路探索.入った部屋の数をカウントする.
- 562:Dividing coins
- Dynamic Programming?
- 各コインは一枚ずつしか使えないので、考えられる組み合わせには限りがある.
それらの可能性を挙げて、それぞれの場合の二人の差の最小値をとれば良い.
- 567:Risk
- Graph? - Floyd-Warshall?
- シンプルすぎるFloyd用テンプレートが出来た.
- 568:Just the Facts
- Mathematics?
- ゼロになった桁を破棄していく.
- 573:The Snail
- Simulation?
- シミュレーションの基本問題.
カタツムリが井戸に届くか地面に落ちるかをシミュレートする.
言われた通りにやればいいけど、successとfailureの定義に注意.
- 574:Sum It Up
- Backtracking?
- データの最大数が12なので明らかなバックトラック.
- 575:Skew Binary
- Mathematics? - Base Numbers?
- そのままやろう.
- 576:Haiku Review
- String?
- 連続するvowelはカウントしない.
- 579:ClockHands
- Simulation? + Mathematics?
- 長針と短針の関係を一般化.
- 583:Prime Factors
- Mathematics? - Prime Number?
- 単純に素因数分解すれば良い.
これも要ライブラリ化.
- 587:There's Treasure everywhere!
- Simulation? + Mathematics?
- 言われた通りやる.
- 591:Box of Bricks
- Simulation?
- 平均の高さから一番遠いのから潰していく.