CSA #76

(→) D:面倒高さ順に降順ソートして,左右の勾配だけを見ると,どの高さでも各勾配の相対位置は変わらないので左右の勾配それぞれのsetを持つ.山が重なるところは包除原理で足し引き E:やるだけ頂点内にコストa[i][j],頂点間にコストINFを張る最小カット問題に帰着出来るのでDinicを信じる

2018-04-13 02:05:54

E、素人目に見ても最小カットな気がしたけどフロー力が足りなくてお風呂だった

2018-04-13 02:05:56

とーらす🌸📦🌕✨🍀 @torus711

やったこと A: 書いてある通りに実装すればおｋ B: 有効な i, j について B[ i + X ][ j + Y ] -= B[i][j] してからリサイズ

2018-04-13 02:06:11

とーらす🌸📦🌕✨🍀 @torus711

やったこと C: 貰った飴はストックしておいて，足りなくなってから「過去にそこに入れておいた」ことにする．ほぼ蟻本のガソスタのやつ．

2018-04-13 02:06:20

さすがに黄色いったやろ…

2018-04-13 02:06:20

考察時間，A<E<B=C<D

2018-04-13 02:07:08

D ソートして左から見ていって丸ついた山だけ残して後で足せばなんとかなりそう？？ pic.twitter.com/GazEg9gsBw

2018-04-13 02:07:43

拡大

蟻本Dinicで1108 msとかで通ったぞい

2018-04-13 02:08:09

D、実装量の割にすんなり通ったので気持ちよかった

2018-04-13 02:08:25

やっぱりちょっと重そうなら一つ一つ確認しながら落ち着いて実装するの大事だ

2018-04-13 02:09:12

C はなんか蟻本のガソリンスタンドの問題思い出した（足りなくなったら補充みたいなやつ）

2018-04-13 02:09:15

CSA(div2only)で13位は今の所最高かな？

2018-04-13 02:10:17

Dで無駄に1時間くらいかけた後にE15分で通してるのウケるな

2018-04-13 02:10:56

頭の回転おせ～　つれ～

2018-04-13 02:11:03

Dはx軸でソートして端から舐めていくと他の三角に飲まれる点が洗い出せるので、それらを排除した後隣り合う点で重複する部分を計算しながら順に見ていった

2018-04-13 02:12:59

このセットで全完15人なのか (D面倒だからかな)

2018-04-13 02:13:16

実装系の問題の解法が終了 15 分前とかに降ってきて死ぬの渋い

2018-04-13 02:15:20

今日のアルゴリズム勉強会は解いてる様子を眺める側に回ってて若干飢えてたのでちょうどCSAあってて良かった

2018-04-13 02:15:46

くりんぺっと @climpet

今日のアルゴリズム

2018-04-13 02:16:19

ツカモ @tsukammo

アルゴへの飢餓感、欲しい。

2018-04-13 02:16:22

解法降ってきただけマシになったと思おう

2018-04-13 02:18:21

analysisで kmjp さんのコードの綺麗さが褒められている

2018-04-13 02:19:18