UVa/Volume6

Volume6

• 601:The PATH
  • Graph? - Depth First Search?
  • 基本的にDFS．バックトラック部分の処理が若干面倒．

• 603:Parking Lot
  • Simulation?
  • 単なるシミュレーション

• 612:DNA Sorting
  • AdHoc?
  • brute forceでがんがん．

• 621:Secret Research
  • String?
  • 定義通りにやれば良い.

• 622:Grammer Evaluation
  • Parsing?
  • トップダウンの構文解析．入力には空白があり得る．

• 623:500!
  • Mathematics? - Big Integer?
  • 入力最大値が999であることに注意.

• 624:CD
  • Dynamic Programming?
  • 長さNのテープに一番長く曲を入れる方法を求める.DPの典型的な問題.

• 628:Passwords
  • String?
  • 正規化された入力から、あり得るパスワードを生成.

• 630:Anagrams (II)
  • String?
  • アナグラムを入力された辞書データの中から見つける.
    next_permutationとだと、たぶんTLEなので、あらかじめ辞書データをソートしておいて、入力文字列のソートしたものと比べる.
    出力順は入力順で良いので、順序比較の必要も無し.

• 637:Booklet Printing
  • AdHoc?
  • 本のページがどうなるかを求める.色々法則があるので、それを探す.

• 639:Don't Get Rooked
  • Backtracking?
  • 8 Queen?的.

• 640:Self Numbers
  • Mathematics?
  • 十分な大きさののbool配列を用意して、self-numberでない数にfalseを突っ込んでいく.

• 673:Parentheses Balance
  • Data Structure? - Stack?
  • かっこの組み合わせ問題.Stack使ってそのまま.

• 674:Coin Change
  • Dynamic Programming? - Couting Chane?
  • 良い練習問題.

• 681:Convex Hull Finding
  • Computer Geometry? - Convex Hull?
  • やっとこさ凸法ライブラリ完成．疲れた・・・

• 686:Goldbach's Conjecture (II)
  • Mathematics?
  • 定義通りに.

• 694:The Collatz Sequence
  • Mathematics?
  • 定義通りにやるだけ.