Menu

UVa/VolumeC

Last-modified: 2008-05-23 (金) 11:17:22

VolumeC

  • 10000:Longest Paths
    • Graph? - Floyd-Warshall?
    • フロイドのアルゴリズムで、最長経路を探すように変更する.
      隣接リスト表現でDFSを行うとTLE.
  • 10003:Cutting Sticks
    • Dynamic Programming? - Matrix-chain Multiplication Problem?
    • 問題なのは、どの順番で切ればいいかである.
      これは連鎖行列積問題と良く似ている.
      つまり、長さLの棒を位置a,b,c(昇順)で切るとしたとき、
      区切る位置をk(a<=k<=c)として、最も最適なkを見つければ良い.
      例えば最適解がk=aだとすれば、それは最小コストが、「L」と「aからcまでの長さの棒の最小コスト」の和であることを意味する.
      aからcまでの最小コストは、
      この場合だと切る位置がbしかないため、c-aとなり、全体の解が得られる.
      aからcまでの間に複数の切る位置があった場合は、上記の手順を再帰的に用いる事により解が得られる.
  • 10004:Bicoloring
    • Graph?
    • 与えられたグラフを、
      隣接するノードを互いに違う色になるように、
      二色を使って塗り分けられるかという問題.
      再帰のDFSで全探索すればおｋ.
  • 10006:Carmichael Numbers
    • Mathematics?
    • Carmichael Number?の定義通りに。
  • 10008:What's Cryptanalysis?
    • String?
    • 文字数をカウント.
  • 10013:Super long sums
    • Mathematics? - Big Integer?
    • タイトル通りに多倍長の和を求める問題.
  • 10018:Reverse and Add
    • String?
    • ひっくり返して足していく.
  • 10019:Funny Encryption Method
    • Mathematics?
    • 定義通りにやれば良い.
  • 10034:Freckles
    • Graph? - Minimum Spanning Tree?
    • 最小木問題.Prim's Algorithm?のアルゴリズムで解いた.
  • 10035:Primary Airthmetic
    • Mathematics? -- Big Integer?
    • 桁上がりの回数を数える.
  • 10038:Jolly Jumpers
    • Mathematics?
    • 定義通りに.
  • 10041:Vito's family
    • AdHoc?
    • 力ずくで調べれば見つかる.
  • 10048:Audiophobia
    • Graph? - Floyd-Warshall?
    • フロイドのアルゴリズムをMinimax法に応用.
  • 10050:Hartals
    • AdHoc?
    • 単純な問題.
      普通にストライキの日を計算で求めて日にちを表すbool配列をtrueに.
      最後にtrueの数を求める.
  • 10055:Hashmat the brave warrior
    • Mathematics?
    • 差を求めるだけ.
  • 10062:Tell me the frequencies!
    • String?
    • 文字の出現頻度を数える.
  • 10066:The Twin Towers
    • Dynamic Programming? - Longest Common Subsequence?
    • シンプルにLCSを適用.
  • 10069:Distinct Subsequence
    • Dynamic Programming?
    • 与えられた文字列の中に、指定された単語が何通りの方法で見つかるかって問題.
      練習問題に最適.
  • 10071:Back to High School Physics
    • Mathematics?
    • ハジキの公式.
  • 10074:Take the Lane
    • Backtracking?
    • 最大長方形問題?.
  • 10079:Pizza Cutting
    • Mathematics?
    • 和の公式を発展させて、n(n+1)/2 + 1の式で求める事ができる.
  • 10082:WERTYU
    • String?
    • めんどいだけ.
  • 10098:Generating Fast, Sorted Permutation
    • String?
    • next_permutation.