hotpepsiの練習帳

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 (通過)

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