UVa/Volume2

Volume2

• 200:Rare Order
  • AdHoc? + String?
  • 各文字列のi番目(0<=i<=一番長い文字列の最後)について、与えられた順番通りに配列に入れていくだけ.
    同じ文字が来たらムシ.
    iは当然0から始める.
    何故それで上手くいくかは色々試すと分かる.
    文字列のインデックスに注意.

• 201:Square
  • Ad-hoc?
  • 全探索

• 202:Repeating Decimals
  • Mathematics?
  • 循環小数の問題．50桁以内に循環しなくても，繰り返し幅の出力のとこは99で固定じゃないんだねorz．

• 208:FIretruck
  • Graph?
  • DFS+Floyd．DFSで遅いとき＆目的地が定まっているときは，Floydと組み合わせるのは常套手段か．

• 209:Triangular Vertices
  • Grid?
  • めんどくさい．でも，こういう入力の便利な方法を発見！

• 211:Domino Effect
  • Graph?
  • DFS．またまた凡ミス．こういう入力の終了判定には気をつけないと．

• 213:Message Decoding
  • String?
  • 定義がややこしいので注意.それ以外は簡単.

• 216:Getting in Line
  • Graph? - Minimum Spanning Tree?
  • 最小木問題.
    MSTの練習には丁度良い.桁落ちに注意.

• 220:Othello
  • Ad-hoc?
  • 言われたとおりに．

• 227:Puzzle
  • Sumilation?
  • 問題の定義そのまま.命令セットの入力に注意.

• 231:Testing the CATCHER
  • Dynamic Programming? - Longest Inc/Dec-reasing Subsequence?
  • 向かってるミサイルに対して、どのミサイルを妨害すれば一番多く妨害出来るか.
    ミサイルは来る順番通りに並んでるので、ソートしたらダメ.
    前のミサイルよりも低い位置のミサイルが来れば妨害出来るから、降順になるような最適解を求めていく.つまりLDSの問題.

• 232:Crossword Answers
  • String?
  • 入力の行列から出来る文字列を出力.インデックスの順序付けに注意.

• 256:Quirksome Squares
  • String? + Mathematics?
  • 定義通りに調べる.

• 259:Software Allocation
  • Graph? - Maximum Matching?
  • 最大マッチングの典型．

• 264:Count on Cantor
  • Grid?
  • 両軸の座標を一般化する.

• 271:Simply Syntax
  • String?
  • 再帰的な定義があるので注意.

• 272:TeX Quotes
  • String?
  • bool値を使う.uvaで一番簡単な問題かも.

• 280:Vertex
  • Graph? - Graph Representation?
  • これを隣接行列表現(O(V^2))でやると、TLE(実際やりました).
    O(V+E)の隣接リスト表現を使う.

• 291:The House Of Santa Claus
  • Graph? - Euler Path?
  • オイラーの一筆書きそのものの問題.

• 294:Divisors
  • Mathematics?
    LからUまでとにかく調べる.
    たぶんポイントはsqrt(N(L<=N<=U))まで調べるところだと思う.

• 299:Train Swapping
  • Sorting?
  • 何回入れ替えれば良いか.