Hatena::Grouptopcoder

hotpepsiの練習帳

2013-01-30

Facebook Hacker Cup 2013 QR

02:07

A. Beautiful strings (20)

問題

  • 文字列の美しさを評価する
  • アルファベットに1~26の価値を設定する
  • 文字列の最大の価値を求める

方針

  • 文字毎の価値を自由に決めていいということらしい
  • 文字の出現数を配列にカウント
  • 昇順にソートして(index+1)をかける
  • accepted

B. Balanced Smileys

問題

  • 文字列がbalancedかどうかの判定条件ある
  • 顔文字や括弧を含む文字列が与えられる
  • balancedかどうかを求める

方針

  • 少なくとも1通り、balancedとして解釈可能かどうかを判定すればよい
  • DFS
  • [start,end)の範囲がbalancedかどうか判定する関数を用意
  • [start,start)はbalanced
  • [start,end)が顔文字に一致していればbalanced
  • [start,x)と[x,end)がbalancedなら全体がbalanced
  • startとend-1が()ならば、[start+1,end-1)がbalancedかどうかに従う
  • accepted

C. Find the Min

問題

  • 配列はハッカーの愉しみである(知らなかった...)
  • n個の数値からなる配列の最後の要素を求める
  • 最初のk個は、生成するパラメータが与えられる
  • 最初のk個以降の要素は、それよりk個前の要素に含まれない0以上の整数

方針

  • 直前のk個をsetに突っ込んで生成
  • TLE
  • (終了後)
  • 最初のk個には同じ数も含まれている
  • 乗算のオーバーフローを考慮
  • k個のうちに含まれているかどうかは、0からkまでの範囲を知っていればOK
  • 配列で持っておき、いちいち調べても制限時間には十分間に合う

結果

oox 55pt (通過)

一発提出なのに適当すぎて反省。

トラックバック - http://topcoder.g.hatena.ne.jp/firewood/20130130