SRM505 Div1

とぷこだ 参加ログ

なにこの難易度。
体調崩してたから参加するか迷ってたけど、結果的に参加してよかった。

300 RectangleArea

解けた。


読む。自由度がどのくらいあるかを求めればよさそうな問題。自由度？なんの？
サンプルを読む。親切なサンプル。
W*H=(R0+...+RN)*(C0+...+CM)だったら、すべてのR,Cをどちらかの1種類のみで表現できればいけそう。
1種類のみで表現可能な条件は、、、knownがYの場所はそのR,Cのペアがそのどちらかで表現できる。同様に、knownがYとなってるR,Cでグループを作るとそのグループ内のR,Cはグループ内の1種類で表現できる！だから、グループの数を求めて-1したのが知らないといけない質問数なはず！
グループは、、、Union-Find！
書く。。。セグる。。あれ、セグるようなコードじゃないのに、、、
どこだああああ、、、、、、NとM間違ってる！！orz直して提出。
、、、本当にあってる？？ちゃんと証明しよう、、、、大丈夫、、なはず、、、
コーディングフェーズ終了。

500, 1000

開いてすらいない。

撃墜

Summary全体が大惨事。
とりあえず、解読できないコード見つけたので、読む。が、やっぱりよくわからないまま終了。(そのコードはSystemTest通ってた)

反省

なんとか生き残れて、1完、順位210位。レートは1322->1433。今回の300はDiv2Hardだったみたいだから、解けただけでよかった。Div1Mediumに手を付けられるようにしたい。