GigaCode 2019に参加しました

gigacode.connpass.com ヤフー社員枠で参加 + LT + 設営撤収のお手伝いをしました。

LT

Virtual contestの開き方 #GigaCode2019 from Yahoo!デベロッパーネットワーク

会社の名前が出るので、会社の同好会でやっていることの紹介を簡単にしました。また、デモではVirtual Contestをする際にCodeforces APIからユーザ情報をスクレイピングして、まだ1問も解いたこともないコンテストを出力するツールを紹介しました。

数十行のスクリプトでいろいろできるのでおすすめです。

個人的にはバルーンアートのLTが1番好きで、設計図がグラフそのものになっていたのが面白かったです(よく考えるとそれはそうなんですが)。

Dは二次元累積和をして上下を固定して尺取りで $O(H^{2}W)$ を思いついたが尺取りを書きたくないので上下左を固定して二分探索 $O(H^{2}W \log{W})$ を書いた。解説によると二分探索すら必要なくて、 $O(H^{2}W^{2})$ が間に合う。
Eは最初 $N \leq 100000$ と誤読していて何かしらのデータ構造を疑っていたけど、よく読んだら $N \leq 2019$ なので普通にDPできました。タイムロス。 $N = 100000$ でもLi Chao Treeで解けるらしい(ライブラリ持ってない)。
Fは満点狙いをしていたけどいい感じのプログラムが書けずじまい。。。最大長方形を知っている前提だと、端を固定して数え上げて重複を消すという部分が本質な気がする(これに全然気づかず、真に条件を満たす長方形を最初から数えあげようとしていた)。例えば下を固定して数え上げた場合、上左右が同じ長方形で下の座標が1ずれている長方形が2つある場合、小さい方の長方形は不要。
Fに時間を割きすぎて、GとHもあまり部分点が稼げず。