Hatena::Grouptopcoder

hotpepsiの練習帳

2017-02-11

Facebook Hacker Cup 2017 Round 2

01:40

https://www.facebook.com/hackercup/round/742957399195355/

A. Subtle Sabotage (12pt)

問題

  • N×M個のマス目がある
  • 上下左右にだけ移動可能
  • 左上から右下に、最短距離で移動する
  • K×Kのお邪魔ブロックを置くことにより、最短距離をN+M-1以上にしたい
  • ただし到達可能であること
  • お邪魔ブロックの最小数を求める

方針

  • サンプルが割と親切
  • ただしKの大きさについての考察は必要
    • NとMの小さいほうをA,大きいほうをBとする
    • AがK以下だと完全にふさがれるので不可能
    • 始点と途中で曲がるところと終点の3つの経路が必要なので、Bが(K×2+3)より小さいと不可能
    • 最初に1つ並べてそれをよけさせて、下から縦にずらっと並べるパターン(サンプル2)
    • ベランダのようなでっぱりを作るパターン(サンプル3)
  • Passed System Test
  • https://github.com/firewood/topcoder/blob/master/fhc_2017/R2_A.cpp

-

結果

o--- 12pt 823th/1587

Tシャツ獲得ならず。


editorial:

https://www.facebook.com/notes/facebook-hacker-cup/hacker-cup-2017-round-2-solutions/1607098535972708


https://togetter.com/li/1073027

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