AGC15のC問題ほんのちょっとメモ
今更感半端なくてすみません。2完でした。
agc015.contest.atcoder.jp
これです。Cが分かりませんでした。
実装は(面倒くさいので(一番駄目な奴))していないのですが、やり方だけメモります。
一番初めの説明について
ぬすけ君は、N×M のグリッドを持っています。行には上から順に 1 から N、列には左から順に 1 から M の番号がついています。 グリッドの各マスは白か青かに塗られており、Si,j が 1 のとき i 行 j 列のマスは青マス、0 のとき白マスです。 青く塗られた任意の二つのマス a,b について、a からはじめて、現在いるマスから辺を共有する青いマスに進むことを繰り返して b に至るような経路のうち、同じマスを 2 度以上通らないようなものは、高々 1 通りです。
ここの意味さっぱりだったのですが、解説動画みて、要するに
って感じです。一周しないってこと
その次
二次元累積和で青いマスの和をメモリましょう
最重要ポイント
この場合、一周しないということは、木なんですよ。
いや、たくさんあるから森なんですよ。(雑
木の特徴はね、頂点数が辺より一本少ないってことなんですよ
なので、頂点引く辺の数ってやればおけ
その次
辺の数を二次元累積和で求めましょう。
雑とか言わない
深さ優先探索のテンプレ
AOJの深さ優先探索の入門的な問題を解いて、いちいち書くのが面倒と思ったのでテンプレ作ります(ほぼ使えないかもしれないが)
説明は下手です、すみません()
ちなみに、AOJの方のコードはこちら
AIZU ONLINE JUDGE: Code Review
#include<iostream> #include<vector> #include<string> #include<stack> #include<cstdio> #include<algorithm> #define WHITE 0 #define GRAY 1 #define BLACK 2 using namespace std; #define FOR(i,a,b) for(int i=(a);i<(b);++i) #define REP(i,n) FOR(i,0,n) int n, m[100][100] = { 0 }, nt[100] = { 0 };//ntはその頂点から他の頂点を探索するときに重ならないようにするための物 int color[100] = { WHITE }; int next(int u) { FOR(i, nt[u], n) { nt[u] = i + 1; if (m[u][i]==1){ return i;//もし何かつながる頂点があれば返す } } return -1;//なければ-1を返す } int dfs(int r) { stack<int>S; S.push(r); color[r] = GRAY; while (!S.empty()) { int u=S.top(); int v = next(u); if (v != -1) { if (color[v]==WHITE) { S.push(v); color[v] = GRAY; } } else { S.pop(); color[v] = BLACK; } } return 0; } int main() { cin >> n; REP(i, n) { int u, k; cin >>u >> k;// u--;// REP(j, k) { int muki; cin >> muki;// muki--; m[u][muki] = 1; } } REP(i, n) { if (color[i] == WHITE) { dfs(i); } } return 0; }
ちなみにGRAYとBLACKは分ける必要ないです
boolにした方が軽くなると思います
隣接リストを行列に直してやりましたが、遅いらしいのでこれはあまり使えないかもしれません()