Facebook Hacker Cup 2020 Qualification Roundメモ

2019のQualと違って全完できました。Round 1もがんばります。

A

• 愚直に実装できる

B

• 隣接するAとBを消すという操作に帰着できる
• AとBが1つ以上ある場合、どこかでAとBは必ず隣接しているので必ず消せる
• したがって、AとBの個数を数えて差が1ならOK

C

• 考察すると、右に倒した木を複数つなげる + 左に倒した木を複数つなげる が最善であることが読める
• {倒した木の先端の座標, 倒した木の長さの最大値} を左に倒した場合と右に倒した場合でそれぞれmapで管理して、あとで合わせる

D1

• しばらく考えたあと、D2で役に立たないんだろうなーと思いながらrange chminのセグ木で殴った

D2

• ここでは解説のようなセグ木ではなく、0の重みの逆辺をあらかじめ貼ってダイクストラするやつをした
• AからBへのshortest path以外の点についても、考察すると実はshortest path内で辺を貼ることに帰着できる
• 具体的にはAからx離れていてAB間のshortest pathからy離れている点の場合、Aからx離れた点からx+m-2y離れた点にコストcの辺が貼れる (Aからx離れた点は全て同一視して、Bに向けてどれだけ進めるかだけ考える感じ)
• shortest pathから離れた点からスタートしてそこからさらに離れていく操作は無意味なこともしばらく考えるとわかるので、これで充分

手元実行について

• -O2付け忘れてC問題の本番データの実行に10秒以上かかった
• D2問題を本番データで実行したらSEGVして焦った。-fsanitize=address,undefined 付けて実行したら配列サイズが足りないことがわかったので修正して事なきを得た