ABC-041-D

abc041.contest.atcoder.jp

概要

N匹のウサギがいて、それを矛盾せずに並び替える方法はなんとおり？
頂点（ウサギ）には特徴がある場合とない場合があるぞい。

よかったところ

解説をちらってみてしまったが、大体のところは自分でくみたてられた。

反省点

解くのに時間をかけすぎてしまった。解法を変えることも大事って一番いわれていること（適当）
bit &ってやるとき、powで累乗してしまっていた。シフトした方がいいので、次からはシフトを使ってみる。
構造を理解したつもりであまり理解してないのでだめ

やりかた

bitDPというものでやります。私は、dp[vコメの頂点][どの頂点に行ったのかを表したbit]
という風にやりました。

その後、条件があるところは、たとえばxがyより先にあるとしたら、次の頂点がxのとき、すでにyが含まれていたら、return というようにやります。

ここが一番引っ掛かった部分なのですが、私は次の頂点がyのとき、もしxが逆に含まれていないときはreturnというようにやりました。

これはなぜダメなのかが分かりませんが、確かにこの方法は正解法を逆向きで同じようにやったときと同じなんですね・・・

多分、1つずらしたらなんとかなるとか？そんな感じだと思います。この度、あきらめるという方法を思いついたのでそこについてはゆっくり考えさせていただきます。

ソース

#include<iostream>
#include<algorithm>
#include<functional>
#include <string>
#include<cstdio>
#include<math.h>
#include<stack>
#include<queue>
#include<cstring>
#include<vector>
#define FOR(i,a,b) for(ll i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)
#define EREP(i,n) for(int i=(n-1);i>=0;--i)
#define D(n,retu) REP(i,n){cin>>retu[i];}
#define mod 1000000007
#define MIN -93193111451418101
#define INF 931931114518101
using namespace std;
typedef long long int ll;
template<typename T>
void fill_all(T& arr, const T& v) {
	arr = v;
}
template<typename T, typename ARR>
void fill_all(ARR& arr, const T& v) {
	for (auto& i : arr) { fill_all(i, v); }
}
 
//------------------変数-----------------------//
ll n, m;
typedef pair<ll, ll> P;
 
ll dp[20][100000] = {};//vコメの頂点のとき、どの頂点に行ったか
vector<vector<ll>> G(50001);
ll maxa = 0, moto = 0;
queue <ll>q;
ll bitmax = 0;
//-------------------関数----------------------//
 
ll DP(ll vertex, ll bit) {
	ll cnt = 0;
	if (bitmax == bit) {//もしすべての頂点に行ったなら
   		return 1;
	}
	if (dp[vertex][bit] >= 0) { return dp[vertex][bit]; }//return dp
	REP(i, n) {
		ll hoge = pow(2, i);
		if (!(hoge&bit)) {//行ったことが無かったら
			bool flag = true;
			REP(j, G[i].size()) {//その前に行かなければならない頂点はいくつあったか
				ll piyo = pow(2, G[i][j]);//そこに行ったことがあるかどうかを確かめるため
				if ((piyo&bit)) {//ここ、もし行ったことがあるなら逆に条件通るだろ
					flag = false; break;
				}
			}
			if (flag) {
				cnt += DP(i, bit + hoge);
			}
		}
	}
	//cout << vertex << endl;
	return dp[vertex][bit] = cnt;
}
 
int main() {
	memset(dp, -1, sizeof(dp));
	cin >> n >> m;
	bitmax = pow(2, n) - 1;
	REP(i, m) {
		ll x, y; cin >> x >> y;//yのほうが　速くつくって言いたいの？
		x--; y--;
		G[x].push_back(y);//yコメの頂点はxより後じゃないとだめ！
	}
	ll cnt = 0;
	REP(i, n) {
		ll hoge = pow(2, i);
		cnt += DP(i, hoge);
	}
	cout << cnt << endl;
	return 0;
}

これなんですが、G[x].pushback(y)のxとyを逆にしても、同じことが起きます。なぜならもらうDPと同じようになるからです。私が考えていたことは、結果的にもらうDPになっていました。。。
精進します。

最後に

最後まで教えて下さったSatanicプロ、本当に有難うございます！おかげさまでACしました！