hotpepsiの練習帳

Facebook Hacker Cup 2016 Qualification Round

22:53

A. Boomerang Constellations

問題

• 同じ点から延びる同じ長さの二つの線分が何ペアあるかを数える

方針

• 全ての点のペア(i,j)を列挙して、i,jそれぞれ、長さ別に保持しておく
• ある点aについて、長さbのものがc個あるとき、対象の線分は(c×(c-1))÷2ペアある
• Passed System Test
• https://github.com/firewood/topcoder/blob/master/fhc_2016/QR_A.cpp

B. High Security

問題

• 2行N列のマス目状の施設がある
• それぞれの場所は何もないか障害物である
• 何人かの守衛を配置する
• 守衛は障害物にさえぎられない見通しの上下左右を監視できる
• 施設内で守衛が監視できていない場所をなくすために必要な守衛の人数の最小値を求める

方針

• 左から右に1列ずつ見ていき、上下2マスが空いている場所があったら、そこは必ず埋める必要があるので、左下が空いていれば下に、そうでなければ上に配置する
• 右端まで見たら、もう一度左から右に1列ずつ見ていき、空いているマスを埋める
• Passed System Test
• https://github.com/firewood/topcoder/blob/master/fhc_2016/QR_B.cpp

C. The Price is Correct

問題

• N個の数がある
• 連続するK個の数を取り出し、P以下になる場合の数を求める

方針

• 典型的なしゃくとり法
• N個の数を一つずつ読み込んでいく
• K個の合計がPを越えたら、左端の数を合計から引いて、位置leftを進める
• 今の位置rightまでを取り出す個数は(right-left+1)通り
• Passed System Test
• https://github.com/firewood/topcoder/blob/master/fhc_2016/QR_C.cpp

D. Text Editor

問題

• 末尾に1文字追加、末尾の1文字を削除、現在の単語を印刷、の3つの操作が可能な装置がある
• 与えられたN個のうち、K個の単語を印刷し、最後に現在の単語を空にするとき、総操作回数の最小値を求める

方針

• ソートしておく
• DP[どの単語で終わったか][印刷した個数]=コスト
• 単語aで終わっていて単語bを入力するときは、aとbの共通部分の長さを求めて、その位置まで削除してからbの残りを入力する、というのが追加コストになる。
• Passed System Test
• https://github.com/firewood/topcoder/blob/master/fhc_2016/QR_D.cpp

結果

全問正解

Bの解き方は確証がない。Dが比較的シンプルに書けたのが良かった。

http://togetter.com/li/923210