UVaに寝返り5

試験期間中でもUVaを解くッ!(簡単な問題に限る)

136 - Ugly Numbers

• 2^i*3^j*5^kとかける数をUglyNumberと呼ぶ．1500番目のUglyNumberを求めよ．
• 入力無し．
• SUP=1000000000くらいまでのUglyNumberを全部列挙してソートして出してやればよろしい．

160 - Factors and Factorials

• 階乗の素因数分解
• 幅3での出力はprintf("%3d",N)みたいにする

147 - Dollars

• 両替の場合の数
• DP
  • O(NK), N:=価格の上限, K:=硬貨の枚数
• 入力をdoubleとして受け取ってintに変換する場合，

scanf("%lf",&dollar);
int N=(int)(dollar*100.0+EPS);

• のように+EPSを付けないと小数誤差で値がずれることがあるので注意．

195 - Anagram

• 与えられた文字列の順列を全列挙してアルファベット順に出力．
• 重複する要素は除外する必要があるため除外する必要がある．
• 入力の上限は明記されていない．(aaaaaaaaaaaaaaaのような長い文字列が来る場合がある)
• ソート順がABCDE...abcde...ではなく，AaBbCcDdEe...になっているので注意．
• 普通にnext_permutation使うのがよろしいかと…

以下自分の取った方法．荒業の参考(??)として．
最初，残念なことにnext_permutaionの仕様を勘違いしてたため，以下のような方法にしていた．

• setにどんどん順列を追加していく．
  • 最初は空文字列""の1要素からなるsetからスタートして，文字列の最後まで順列を作っていく．
• 最後まで順列ができたらそれを自作関数でソートして出力．

ただこれだとsetで順列を作る処理がとても重いのと，自作関数での比較がNlogN回されて結構重くなることが原因でTLEになっていた．
そこで，自作関数で比較するのをやめて，次のような方針でACを取った．

• まず，文字AaBcCcDdEe... を abcde... に， abcde... を AaBbCcDdEe..に変換するような関数をそれぞれ作る．(string→stringの関数)
  • 前者をt1,後者をt2とする．
• 元の文字列をt1で変換，↑の順列作成アルゴリズムを適応する．
• setを.begin()から.end()までループさせ，t2で変換して出力．
  • setの中身はすでにソートされているので正しく動く．

こうするとソートするコストが省ける(標準のソート関数で済む)ので高速化が測れる．