AGC15のC問題ほんのちょっとメモ
今更感半端なくてすみません。２完でした。
agc015.contest.atcoder.jp
これです。Cが分かりませんでした。
実装は（面倒くさいので（一番駄目な奴））していないのですが、やり方だけメモります。
一番初めの説明について
ぬすけ君は、N×M のグリッドを持っています。行には上から順に 1 から N、列には左から順に 1 から M の番号がついています。 グリッドの各マスは白か青かに塗られており、Si,j が 1 のとき i 行 j 列のマスは青マス、0 のとき白マスです。 青く塗られた任意の二つのマス a,b について、a からはじめて、現在いるマスから辺を共有する青いマスに進むことを繰り返して b に至るような経路のうち、同じマスを 2 度以上通らないようなものは、高々 1 通りです。
ここの意味さっぱりだったのですが、解説動画みて、要するに
って感じです。一周しないってこと
その次
二次元累積和で青いマスの和をメモリましょう
最重要ポイント
この場合、一周しないということは、木なんですよ。
いや、たくさんあるから森なんですよ。（雑
木の特徴はね、頂点数が辺より一本少ないってことなんですよ
なので、頂点引く辺の数ってやればおけ
その次
辺の数を二次元累積和で求めましょう。
雑とか言わない
