HIR180's diary

ICPC World Finals 2022 を集大成に

2013-08-05

■ SRM514(練習) 13:59

これから番号500~550あたりのセット(Div1)をこなしていこうかなあと思っています

正誤表記:

AC:時間内に解けた

o:時間内に解けなかったが独力で解けた

△:解説をみて通した

x:まだできてない

というわけで今日はSRM514を解いてみました

結果:

AC,o,x / 210.43, (192,76), 0.0

210.43pts (当時)127位相当

Easy:

まず

(0,0)->(1,n)->(2,0)という動き方と

(0,0)->(1,n)->(n+1,n-1)->(1,n-2)という動き方ができるので

n%2==0なら(1,n-2)->...(1,0)より

偶数のものが１つあればできる。

奇数の時でも

(even,even),(odd,odd)は作れることがわかる。

で、nがoddだとn≡1なのでx座標,y座標の偶奇は一致する。

よって偶奇が一致しないとだめ。

以上のことをまとめればいい。こういう超弱実装の思考ゲーたのしい。

//E? Nandatte?
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
typedef pair<int,int> P;
typedef pair<int,P> P1;
typedef pair P2;
#define pu push
#define pb push_back
#define mp make_pair
#define eps 1e-7
#define INF 2000000000
class MagicalGirlLevelOneDivOne{
public:
string isReachable(vector <int> jumpTypes, int x, int y)
{
	bool ok=false;
	for(int i=0;iif(jumpTypes[i]%2==0) ok=true;
	if(ok) return "YES";
	if(abs(x-y)%2==1) return "NO";
	return "YES";
}
};


Medium:

600点問題。

要約:長方形に含まれるどの縦の1*n,横の1*mに含まれている数字の和がoddになる数字の埋め方は？

少し考えると,mod 2で考えたとき

n*mの長方形を繰り返し貼付けたようなものではないといけないと分かる。

よって、n*mの長方形において、0,1を埋めて各々のマスに対して処理をすればいい。

まず0,1の埋め方を考える。

ぱっと見2^100通りの探索が必要に思えるが

あくまでmod2で考えればいいので

dp[i][a]=(1列目からi列目まで埋めて、各列を数字ととらえそのxorをaとする埋め方)とすると

O(10*2^20)で計算でき、求める解はdp[n][(1<

余りは確定したので後は実際に値を埋めていけばよいが、

実は1なら5通り0なら4通りなのでその累乗を適当にかければいい。

本番で40人くらいしか通してない問題なので解けて嬉しい。

あとwriterがwrongさんでした。

//E? Nandatte?
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
typedef pair<int,int> P;
typedef pair<int,P> P1;
typedef pair P2;
#define pu push
#define pb push_back
#define mp make_pair
#define eps 1e-7
#define INF 2000000000
#define mod 1000000007
int val[12][12];
int am[12][12]={};
class MagicalGirlLevelTwoDivOne{
public:
int theCount(vector  palette, int n, int m)
{
	if(abs(n-m)%2==1) return 0;
	int h=palette.size();
	int w=palette[0].size();
	vectorvec=palette;
	for(int i=0;i<12;i++) for(int j=0;j<12;j++) val[i][j]=-1;
	for(int i=0;ifor(int j=0;jif(vec[i][j]=='.')
			{
				am[i%n][j%m]++;
				continue;
			}
			
			if(val[i%n][j%m]==-1) val[i%n][j%m]=(vec[i][j]-'0')%2;
			else if(val[i%n][j%m]!=(vec[i][j]-'0')%2) return 0;
		}
	}
	long long va=1;
	for(int i=0;ifor(int j=0;jif(val[i][j]!=-1)
			{
				if(val[i][j]==0)
				{
					for(int k=0;k4LL)%mod;
				}
				else
				{
					for(int k=0;k5LL)%mod;
				}
			}
		}
	}
	
	long long int dp[12][1025]={};
	
		for(int j=0;j<(1<int root[12];
			int f=j;
			long long v=1;
			int sum1=0;
			for(int k=0;k2;
				sum1+=root[k];
				if(val[0][k]!=-1 && val[0][k]!=root[k]) goto fail;
				f/=2;
			}
			if(sum1%2==0) goto fail;
			for(int k=0;kif(root[k] && val[0][k]==-1) for(int f=0;f0][k];f++) v=(v*5LL)%mod;
				else if(val[0][k]==-1) for(int f=0;f0][k];f++) v=(v*4LL)%mod;
			}
			dp[0][j]=v;
			//cout << v;
			fail:;
		}
	for(int i=1;ifor(int k=0;k<(1<int root[12];
				int f=k;
				long long v=1;
				int sum2=0;
				for(int qk=0;qk2;
					sum2+=root[qk];
					if(val[i][qk]!=-1 && val[i][qk]!=root[qk]) goto fail2;
					f/=2;
				}
				if(sum2%2==0) goto fail2;
				for(int qk=0;qkif(root[qk] && val[i][qk]==-1) for(int s=0;s5LL)%mod;
					else if(val[i][qk]==-1) for(int s=0;s4LL)%mod;
				}
				//cout << v << endl;
				for(int j=0;j<(1<//if(!dp[i-1][j]) continue;
					int root2[12];
					int ff=j;
					int nest=0;
					int sum3=0;
					for(int qk=0;qk2;
						ff/=2;
					}		
					
					for(int a=0;aif((root[a]+root2[a])%2==1) nest+=(1<<(a));
					}
					
					dp[i][nest]=(dp[i][nest]+(dp[i-1][j]*v)%mod)%mod;
					cout << dp[i][nest] << " " << i << " " << nest << endl;
					fail3:;
				}
				fail2:;
			}
	}
	return (va*dp[n-1][(1<1])%mod;
	}
};