UVa/Volume1
Last-modified: 2008-05-23 (金) 11:14:33
Volume1
- 100:The 3n + 1 problem
- AdHoc?
- 最初の問題だけどやらしい.入力の大小に注意.
- 101:The Blocks Problem
- Data Structure? - Stack?
- Stackを使う.
- 102:Ecological Bin Packing
- 103:Stacking Boxes
- Dynamic Programming? - Longest Inc/Dec-reasing Subsequence?
- 箱をソートして、小さい箱から順に何個入るか調べていく.
個数は以前の結果を使って更新していく.DPの基礎的な問題.
- 104:Arbitrage
- Graph? - Floyd-Warshall?
- この問題は、よくある最短経路系(この場合は最も利益が大きくなるような取引の順番)を求めるものではなく、利益が101%を超えるような最も少ない取引の仕方を求める.
そのため、頂点の重みと共に、何箇所辿ったかも重要になる.そこで、3次元配列を使う.value[a][b][k]で、aからbへと間にk個の取引を含む場合の最大の利益を表すものとす
る.
kの値を1から増やしていき、利益が1.01を超えたらそこで出力して終了とする.
3次元配列を使うタイプのグラフ問題はDPにも近い.
ソースは要保存&完璧に理解しておくこと.
- 105:The Skyline Problem
- AdHoc?
- 配列にデータを格納していく.
以前より高い建物が来たらデータを更新.
- 106:Fermat vs. Pythagoras
- Mathematics?
- x^2+y^2=z^2となるようなx, y, zに関する問題.
最初の出力は、x, y, zが互いに素であるような組み合わせの数.
2番目の出力は、互いに素かどうかに関わらず、全てのx, y, zの組み合わせに「一度も現れない」自然数の数.
d*(a^2-b^2)^2+d*(2*a*b)^2=d*(a^2+b^2)^2という式を用いるとピタゴラス数?を簡単に求めることが出来る.
ただし、互いに素なピタゴラス数?を生成するためには、aとbに以下のような条件が付く.
aとbは互いに素
aが偶数の場合、bは奇数(逆も可)
この2つの条件を満たすようなa, bが、上記の式から生成するピタゴラス数?は3つの数が互いに素となる.
- 107:The Cat in the Hat
- Mathematics?
- 実数の扱いが難しいが、処理自体は簡単.
入力をa, bすると、bをi(2<=i)で割っていき、v=1であるvにi+1をかけたものを計算していく.
bが1より小さくなったとき、 vがhとほぼ同じであればその時のiがNとなるほぼ同じかどうかを調べるには、EPSILON?を定義して二つの値の差がEPSILON?より小さいか調べれば良い.
- 108:Maximum Sum
- Dynamic Programming?
- 6重ループだとTLE.
- 109:SCUD Busters
- Computational Geometry? - Convex Hull?
- 凸包の問題.
まず、入力の点から凸包でできる多角形を求め、
次にミサイルが多角形内に落ちていない多角形の合計面積を求める.
凸包に関してはセジウィックに載ってるままのアルゴリズムでは危険なので注意.
- 110:Meta-Loopess Sorts
- Backtracking?
- 数列をソートするPascalのプログラムを作る問題.
普通にバックトラックをやれば良いが、比較で出力する二つのアルファベットを決めるのがめんどい.
さらにelse ifを使う時がめんどい.
インデントさせるのがめんどい.
とにかくめんどい.
そしてソースの可読性悪し.
でもAcceptだから(・ε・)ｷﾆｼﾅｲ!!
- 111:History Granding
- Dynamic Programming? - Longest Inc/Dec-reasing Subsuquence?
- ただし、入力データはそのまま使えないので注意.
- 112:Tree Summing
- Data Structure?
- 入力がめんどくさそうだが、再帰関数を使えば楽.
あとは普通の木の探索.
- 113:Power of Cryptography
- Mathematics?
- ほんとはBig Integer?の問題だと思うけど、doubleを使うと入っちゃうらしい.
整数へのキャストだけ気をつければおｋ.
- 114:Simulation Wizardry
- Simulation?
- 問題自体は簡単.
しかしこの問題により、uvaのジャッジシステムでは前置デクリメントが危険なことが判明！--aではなく、(--(a))と書かなくてはならないぽい.
- 115:Climbing Trees
- Graph?
- ``p is child of q''のときに、a[p][q]=1, a[q][p]=2として親子の関係を有向グラフで表現する.
出力が、child, parent, no relationの場合は、Floyd-Warshall?で判定出来る. siblingとcousinはFloyd-Warshall?だけでは出力出来ないので、Depth First Search?を使う.
- 116:Unidirectional TSP
- Dynamic Programming?
- 考え方がモロDP.
- 117:The Postal Worker Rings Once
- Graph?
- 各辺を少なくとも一度ずつ通るようなコストが最小のパスを探す.
問題の定義として、各点には必ず辺があるので、Euler Path?とFloyd-Warshall?の組み合わせで解ける.
まず、Euler Path?で行けるところまで行き、仕方なく前に通った道を再度通る時は、Floyd-Warshall?で求めておいた最小距離を加える.
- 118:Mutant Flatworld Explorers
- Simulation?
- もしもし亀よー亀さんよー.
- 120:Stack of Flapjacks
- Sorting?
- ソートの問題だけど、ほんのちょっと頭を捻る.
もとの数列に戻したいんだから、最大値を後ろから順番にならべていけるように、逆からシミュレートする.
- 121:Pipe Filters
- Computational Geometry?
- 紙に絵を書いてみると、一つの円が加わったときに増える長さが分かる.
それをもとに何個入るか調べるだけ.精度に注意.
- 122:Trees on the level
- Data Structure?
- そのまま木の問題.
- 123:Searching Quickly
- String?
- 各タイトルを単語ごとに区切って保存しておく.
順番も入力通りに保存.
あとはキーワードを辞書順に検索していって出力するだけ.
同じタイトルに同じキーワードが複数ある場合に注意.
- 124:Following Orders
- String?
- 文字の順位付けが与えられて、その順位付けを満たすような文字列を辞書順に出力.next_permutationで順列を作成し、それが順位付けを満たしているか調べる.
- 125:Numbering Paths
- Graph? - Floyd-Warshall?
- あるノードから別のノードへ行く方法が何通りあるか調べる.
Floyd-Warshall?を使う.
無限にあるかどうかを調べる必要があるが、どうすれば良いか.
まず、i->jかつj->iとなるようなi,jを見つける.
すると、i,jをパスに含むような経路全てがinfiniteとなる.
i,jで始まる、もしくは終わる経路を見つけるのは簡単だが、
パスの間に含む場合はどうすれば良いか.
infiniteとなるノードをiとして、a->iとi->bという点があったとき、a->bはinfiniteである.
これをループで調べればよい.
Depth First Search?を使う必要も、パスを保存しておく必要もなし.
というか最初それをやっていて出来なかった.
- 待てよ、これはサイクル判定でないのか？
- 126:The Errant Physicist
- Mathematics? + String?
- まず入力がめんどい.
そして出力がめんどい.
それ以外は楽勝.
- 127:"Accordian" Patience
- Simulation?
- 簡単だけど、出力の順番間違ってWrong Answer連発・・・.
出力は降順じゃなくて、左からそのまま表示.
- 128:Software CRC
- Mathematics?
- よう分からん.
定義を良く見て言われた通りやったけど上手くいかず、適当にいじくってたらaccept.
なんじゃそりゃ.
- 129:Krypton Factor
- String?
- Brute Force?でいける。繰り返す文字列の文字数を増やしながら順番に調べていく.使ってもいい文字列の中で一番小さい(辞書順的に前にある)文字を使う.
ただし、使える文字がまったくない場合は、ひとつ前に戻らなくてはならないので注意.
- 130:Roman Roulette
- Simulation?
- 殺す人と、埋葬する人を選ぶ.
Josephsっぽい.埋葬する人は場所が変わることに注意.
- 131:The Psychic Poker Player
- Backtracking?
- 現在の手札と、積まれたカードが与えられ、
積まれたカードからカードを引いた場合も考慮して、
どのような手が一番強いかを出力する.
積まれた山から引くカードの枚数=現在の手札から捨てたカードでなくてはならない.
また、積まれた山からは、上から順番にしか引けない.
再帰関数で考えられる全ての組み合わせを求め、
バックトラックを使って最強の役を求めていく.
- 132:Bumpy Objects
- Geometry?
- 多角形が与えられて，それを回転させて安定なポジションを求めて云々ってな問題．
幾何では簡単な問題．
- 133:The Dole Queue
- Simulation?
- Josephsっぽいけどもっと簡単な問題.
同じところを選んだらコンマを打つ.
- 135:No Rectangles
- Ad-Hoc?
- 数学の問題っぽいけど．
いくつかのnについて答えを出して，法則を見つけた．
- 136:Ugly Numbers
- Mathematics?
- この手の問題は、
ある数の因数が2,3,5だけかを調べるのではなくて、
2,3,5の因数を持つ数を作っていくことで解けるものが多い.
Sieve of Eratosthenes?的な考え方.
ただし、どこまでかけるかを考えないと、メモリ領域が確保出来ないかも.
- 138:Street Numbers
- AdHoc?
- 一度Brute Force?で出力を出して、漸化式を求めればaccept.
Brute Force?のままだと、もちろんTLE.
- 140:Bandwidth
- Graph?
- 最大でも8!なので，bruteforce．
- 142:Mouse Clicks
- Computational Geometry?
- 定義通りに処理.Computational Geometry?の基礎問題.
- 144:Student Grants
- Simulation?
- 各生徒に対してコインを分配するって問題.
マシンの中に金が余ったときの処理だけ気を付ければ良い.
- 146:ID Codes
- String?
- next_permutation.
- 147:Dollars
- Dynamic Programming? - Counting Change?
- 与えられたコインの種類のうち、
使用するコイン枚数を増やしながら最適解を求める.要テンプレ.
- 151:Power Crises
- Simulation?
- これも円形に並べて考える.
- 154:Recycling
- AdHoc?
- 五つのビンをリサイクルする.
一番一般的な方法を求める.
- 155:All Squares
- Backtracking?
- 問題の定義によるサイズkの正方形の集合のうち，入力の座標の点を含むものがいくつあるか調べる．
総当り．
- 156:Ananagrams
- String?
- アナグラムを消去して、残った文字をソートして出力.
- 160:Factors and Factorials
- Mathematics?
- 与えられた数の階乗の、素因数の指数を出力.
- 161:Traffic Lights
- Simulation?
- イベント駆動型シミュレーション．ごりごり．
- 167:The Sultan's Successors
- Backtracking?
- 8 Queen?のちょっと違うやつ.
- 177:Paper Folding
- Simulation?
- 紙を半分ずつ折っていくとどうなるかって問題.
実際に折ってみると規則性が分かる.
再帰関数でaccept(1<=N<=13だし).
奥村事典?によると、Dragon Curve?と言うらしい.
- 186:Trip Routing
- Graph? - Floyd-Warshall?
- Dijkstra's Algorithm?だと、たぶんTLE.
- 190:Circle Through Three Points
- Computational Geometry?
- ただ計算するだけだけど、x=aの直線が出てきたらとか考えるとめんどい.
そこでax+by+c=0の直線方程式を使う.
要テンプレ.
- 191:Intersection
- Computational Geometry?
- 線分と長方形の各辺の間で交差判定をする.
場合分けをちゃんとやれば解ける.
- 195:Anagram
- String?
- next_permutationで一発.