「2351～2360」の編集履歴（バックアップ）一覧はこちら
2351～2360 - (2012/03/21 (水) 18:22:16) の１つ前との変更点
追加された行は緑色になります。
削除された行は赤色になります。
*2360 Sharp 2SAT
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2360
一人でＷＡを出しまくって正答率を下げた問題。
基本的な考え方は考え始めて最初の50分で思いついたものの、実装が大変だった。
1 1
1 -1
のような場合を見落としていることに気づかず合計半日も悩んだりした。
基本的な考え方は論理式の連鎖が
(1,4)(4,2)(2,5)(5,1)というループか
(6,7)(7,8),,となる鎖かしかない。
鎖なら組み合わせ数をメモ化で求め。
ループならメモ化のスタート時がtrueだったかfalseだったかを覚えておきながら論理式のチェインでできる組み合わせ数を求め最後にTでおわるＦで終わるものだけを合計する。
というシンプルな発想です。
#include<stdio.h>
#include<string.h>
#include<map>
#include<math.h>
#include <stdlib.h>
std::map<int,int> perm[1003];//問題をグラフとして見て解く[今の番号}、<次の番号,種類>
std::map<int,int> conCount[1003];
int count[1003];
int TT=1,TF=2,FT=4,FF=8;
long long int mode=1000000007;
long long int calc(int deep,int s,int no,long long int ttCount,long long int tfCount,long long int ftCount,long long int ffCount){
std::map<int,int>::iterator it=perm[no].begin();
count[no]=0;
long long int tAns=(ttCount+tfCount+ftCount+ffCount)%mode;
long long int nextTT,nextTF,nextFT,nextFF;
while(it!=perm[no].end()){
int next=(*it).first;
int p =(*it).second;
if(deep==0){
nextTT=((p&TT)!=0);
nextTF=((p&TF)!=0);
nextFT=((p&FT)!=0);
nextFF=((p&FF)!=0);
if(conCount[no][next]==2){
count[next]=0;
return nextTT+nextTF+nextFT+nextFF;
}else{
return calc(deep+1,s,next,nextTT,nextTF,nextFT,nextFF);
}
}else if(s==next&&deep>1){
nextTT=(ttCount*((p&TT)!=0)+tfCount*((p&FT)!=0))%mode;
nextFF=(ftCount*((p&TF)!=0)+ffCount*((p&FF)!=0))%mode;
return nextTT+nextFF;
}else if(count[next]==0){
it++;
}else{
nextTT=(ttCount*((p&TT)!=0)+tfCount*((p&FT)!=0))%mode;
nextTF=(ttCount*((p&TF)!=0)+tfCount*((p&FF)!=0))%mode;
nextFT=(ftCount*((p&TT)!=0)+ffCount*((p&FT)!=0))%mode;
nextFF=(ftCount*((p&TF)!=0)+ffCount*((p&FF)!=0))%mode;
return calc(deep+1,s,next,nextTT,nextTF,nextFT,nextFF);
}
}
return tAns;
}
int main(){
int n,m,y1,y2,t1,t2;
long long int ans=1,temp;
memset(count,0,sizeof(count));
scanf("%d %d",&n,&m);
while(m--){
scanf("%d %d",&y1,&y2);
t1=abs(y1);
t2=abs(y2);
if(y1==y2){
//一通りしかないので何もしない
}else if(y1==-y2){
ans=(ans*2)%mode;
}else{
count[t1]++;
count[t2]++;
if(conCount[t1].find(t2)==conCount[t1].end()){
conCount[t1][t2]=1;
}else{
conCount[t1][t2]=2;
}
if(conCount[t2].find(t1)==conCount[t2].end()){
conCount[t2][t1]=1;
}else{
conCount[t2][t1]=2;
}
if(perm[t1].find(t2)==perm[t1].end()){
perm[t1][t2]=15;
}
if(perm[t2].find(t1)==perm[t2].end()){
perm[t2][t1]=15;
}
if(y1<0&&y2<0){
perm[t1][t2]&=(FF+FT+TF);
perm[t2][t1]&=(FF+FT+TF);
}else if(y1>0&&y2<0){
perm[t1][t2]&=(TT+TF+FF);
perm[t2][t1]&=(TT+FT+FF);
}else if(y1<0&&y2>0){
perm[t1][t2]&=(TT+FT+FF);
perm[t2][t1]&=(TT+TF+FF);
}else{
perm[t1][t2]&=(TT+FT+TF);
perm[t2][t1]&=(TT+FT+TF);
}
}
}
for(int i=1;i<=n;i++){
if(count[i]==1){
temp=calc(0,i,i,0,0,0,0);
ans=(ans*temp)%mode;
}
}
for(int i=1;i<=n;i++){
if(count[i]==2){
temp=calc(0,i,i,0,0,0,0);
ans=(ans*temp)%mode;
}
}
printf("%lld\n",ans);
}
*2360 Sharp 2SAT
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2360
論理式が与えられるのでそれを真にする真偽値の組み合わせを求める問題。
一人でＷＡを出しまくって問題全体の正答率を大幅に下げてしまった、反省。
基本的な考え方は考え始めて最初の50分で思いついたものの、実装が大変だった。
1 1
1 -1
のような場合を見落としていることに気づかず合計半日も悩んだりした。
基本的な考え方は論理式の連鎖が
(1,4)(4,2)(2,5)(5,1)というループか
(6,7)(7,8),,となる鎖かしかない。
鎖なら鎖を順にたどって組み合わせ数をメモ化で求めていきます。
ループならメモ化のスタート時がtrueだったかfalseだったかを覚えておきながら論理式のチェインでできる組み合わせ数を求め最後にTでおわるＦで終わるものだけを合計する。
というシンプルな発想です。
#include<stdio.h>
#include<string.h>
#include<map>
#include<math.h>
#include <stdlib.h>
std::map<int,int> perm[1003];//問題をグラフとして見て解く[今の番号}、<次の番号,種類>
std::map<int,int> conCount[1003];
int count[1003];
int TT=1,TF=2,FT=4,FF=8;
long long int mode=1000000007;
long long int calc(int deep,int s,int no,long long int ttCount,long long int tfCount,long long int ftCount,long long int ffCount){
std::map<int,int>::iterator it=perm[no].begin();
count[no]=0;
long long int tAns=(ttCount+tfCount+ftCount+ffCount)%mode;
long long int nextTT,nextTF,nextFT,nextFF;
while(it!=perm[no].end()){
int next=(*it).first;
int p =(*it).second;
if(deep==0){
nextTT=((p&TT)!=0);
nextTF=((p&TF)!=0);
nextFT=((p&FT)!=0);
nextFF=((p&FF)!=0);
if(conCount[no][next]==2){
count[next]=0;
return nextTT+nextTF+nextFT+nextFF;
}else{
return calc(deep+1,s,next,nextTT,nextTF,nextFT,nextFF);
}
}else if(s==next&&deep>1){
nextTT=(ttCount*((p&TT)!=0)+tfCount*((p&FT)!=0))%mode;
nextFF=(ftCount*((p&TF)!=0)+ffCount*((p&FF)!=0))%mode;
return nextTT+nextFF;
}else if(count[next]==0){
it++;
}else{
nextTT=(ttCount*((p&TT)!=0)+tfCount*((p&FT)!=0))%mode;
nextTF=(ttCount*((p&TF)!=0)+tfCount*((p&FF)!=0))%mode;
nextFT=(ftCount*((p&TT)!=0)+ffCount*((p&FT)!=0))%mode;
nextFF=(ftCount*((p&TF)!=0)+ffCount*((p&FF)!=0))%mode;
return calc(deep+1,s,next,nextTT,nextTF,nextFT,nextFF);
}
}
return tAns;
}
int main(){
int n,m,y1,y2,t1,t2;
long long int ans=1,temp;
memset(count,0,sizeof(count));
scanf("%d %d",&n,&m);
while(m--){
scanf("%d %d",&y1,&y2);
t1=abs(y1);
t2=abs(y2);
if(y1==y2){
//一通りしかないので何もしない
}else if(y1==-y2){
ans=(ans*2)%mode;
}else{
count[t1]++;
count[t2]++;
if(conCount[t1].find(t2)==conCount[t1].end()){
conCount[t1][t2]=1;
}else{
conCount[t1][t2]=2;
}
if(conCount[t2].find(t1)==conCount[t2].end()){
conCount[t2][t1]=1;
}else{
conCount[t2][t1]=2;
}
if(perm[t1].find(t2)==perm[t1].end()){
perm[t1][t2]=15;
}
if(perm[t2].find(t1)==perm[t2].end()){
perm[t2][t1]=15;
}
if(y1<0&&y2<0){
perm[t1][t2]&=(FF+FT+TF);
perm[t2][t1]&=(FF+FT+TF);
}else if(y1>0&&y2<0){
perm[t1][t2]&=(TT+TF+FF);
perm[t2][t1]&=(TT+FT+FF);
}else if(y1<0&&y2>0){
perm[t1][t2]&=(TT+FT+FF);
perm[t2][t1]&=(TT+TF+FF);
}else{
perm[t1][t2]&=(TT+FT+TF);
perm[t2][t1]&=(TT+FT+TF);
}
}
}
for(int i=1;i<=n;i++){
if(count[i]==1){
temp=calc(0,i,i,0,0,0,0);
ans=(ans*temp)%mode;
}
}
for(int i=1;i<=n;i++){
if(count[i]==2){
temp=calc(0,i,i,0,0,0,0);
ans=(ans*temp)%mode;
}
}
printf("%lld\n",ans);
}
