HIR180's diary

ICPC World Finals 2022 を集大成に

2013-05-18

■ JOI春合宿 埋めた分 No.1 19:18

Mall Lv.5

二次元累積和をとる

#include 
#include 
#define INF 1000000000LL
long long rui[1005][1005]={};
int m,n;
long long field[1005][1005];
int a,b;
long long ret=1e18;
int main()
{
    scanf("%d %d",&m,&n);
    scanf("%d %d",&a,&b);
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            scanf("%lld",&field[i][j]);
            if(field[i][j]==-1) field[i][j]=INF;
        }
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            rui[i][j]=rui[i-1][j]+rui[i][j-1]-rui[i-1][j-1]+field[i][j];
        }
    }
    for(int i=1;i<=n-b+1;i++)
    {
        for(int j=1;j<=m-a+1;j++)
        {
            ret=std::min(ret,rui[i+b-1][j+a-1]-rui[i+b-1][j-1]-rui[i-1][j+a-1]+rui[i-1][j-1]);
        }
    }
    printf("%lld%c",ret,10);
}

Building Lv.5

狭義最長増加部分列

include 
#include 
int main()
{
    int n;
    int height[1005];
    int dp[1005]={};
    int ret=0;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&height[i]);
    }
    for(int i=1;i<=n;i++)
    {
        dp[i]=1;
        for(int j=1;jif(height[i]>height[j]) dp[i]=std::max(dp[i],dp[j]+1);
        }
        ret=std::max(ret,dp[i]);
    }
    printf("%d%c",ret,10);
}

Fermat Lv.8

x^n+y^n≡z^n (mod p)

のとき、

a≡x^n, b≡y^n,c≡z^n (mod p)とすると

c=0の時を除くとき

1<=c<=p-1より pが素数であることから gcd(c,p)=1であるので

cd≡1(mod p)なる逆元dが存在し、

a+b≡c (mod p) より ad+bd≡cd (mod p)であるので、ad+bd≡1 (mod p).

つまり1<=z<=p-1の時、z^nがとりうる値それぞれについてmod p における逆元が存在し、

それを式全体にかけることによってc=1の場合に対応させることができるので

答えは(c=0である(x,y,z)の総数)+(c=1である(x,y,z)の総数)*(cのとりうる値の総数(1<=z<=p-1))で求められる。

#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
int mod[10005][15]={};
int cou[10005];
set<int>s;
int main(){
    int p,n;
    scanf("%d %d",&p,&n);
    for(int j=0;j0]=j%p;
        for(int i=1;i<=20;i++){
            mod[j][i]=(mod[j][i-1]*mod[j][i-1])%p;
        }
        int se=1;
        for(int i=0;i<=20;i++){
            if(((n>>i)&1)){
                se*=mod[j][i];
                se%=p;
            }
        }
        cou[se]++;
        s.insert(se);
    }
    int ans1=cou[0]*cou[0]*cou[0];
    int ans2=0;
    for(int i=0;i0]*cou[i]*cou[p-i];
    }
    ans2+=cou[1]*cou[1]*cou[0]*2;
    for(int i=0;i1]*cou[i]*cou[p+1-i];
    }
    printf("%d\n",ans1+ans2*(int)s.size()-ans2);
    return 0;
}

Anagram Lv.7

重複に気をつけてcombinationの積をとって足して+1する


#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
long long mem[25][25]={};
string str;
map<char,int>ma;
long long conb(int n,int m)
{
	if(mem[n][m]) return mem[n][m];
	if(m==0 || n==m) return 1;
	if(n0) return 0;
	return mem[n][m]=conb(n-1,m)+conb(n-1,m-1);
}
int main(){
	cin >> str;
	for(int i=0;ilong long ret=0;
	for(int i=0;ichar>candidate;
		for(int j=i+1;jif(str[i]>str[j])
			{
				candidate.pb(str[j]);
			}
		}
		sort(candidate.begin(),candidate.end());
		candidate.erase(unique(candidate.begin(),candidate.end()),candidate.end());
		for(int j=0;jint am=str.size()-i-1;
			map<char,int>::iterator it;
			long long res=1;
			for(it=ma.begin();it!=ma.end();++it)
			{
				res*=conb(am,it->second);
				am-=it->second;
			}
			ma[candidate[j]]++;
			ret+=res;
		}
		ma[str[i]]--;
	}
	printf("%lld\n",ret+1LL);
}

Route Lv.8

二個前の頂点, 一個前の頂点 を状態にもってdijkstraすればいい。

bug partyしたのでまた今度書きます。

Fiber Lv.5

UFするなりBFSするなりどうとでも。

#include 
#include 
#include 
#include 
using namespace std;
vector<int>edge[10005];
bool used[10005]={};
int main()
{
    int n,m;
    scanf("%d %d",&n,&m);
    for(int i=0;iint a,b;
        scanf("%d %d",&a,&b);
        edge[a].push_back(b);
        edge[b].push_back(a);
    }
    int cnt=0;
    for(int i=1;i<=n;i++)
    {
        if(used[i]) continue;
        used[i]=true;
        queue<int>que;
        que.push(i);
        while(!que.empty())
        {
            int ii=que.front();
            que.pop();
            for(int j=0;jif(!used[edge[ii][j]])
                {
                    used[edge[ii][j]]=true;
                    que.push(edge[ii][j]);
                }
            }
        }
        cnt++;
    }
    printf("%d%c",cnt-1,10);
    return 0;
}

Committee Lv.7

木上の再帰か... と思ったけど

dp[i] = i番目の人を含み、その人以下の人とのやる気の合計の最大値

とすると簡単。

#include 
#include 
#include 
using namespace std;
int dp[100005]={};
int up[100005];
vector<int> down[100005];
int power[100005];
int n;
int main()
{
    scanf("%d",&n);
    int flag=-10000;
    for(int i=1;i<=n;i++)
    {
        int a,b;
        scanf("%d %d",&a,&b);
        up[i]=a;
        down[a].push_back(i);
        power[i]=b;
        flag=std::max(flag,b);
    }
    if(flag<=0)
    {
        printf("%d%c",flag,10);
        return 0;
    }
    int ret=0;
    for(int i=n;i>=1;i--)
    {
        int sum=0;
        for(int j=0;jif(dp[down[i][j]]>0) sum+=dp[down[i][j]];
        dp[i]=power[i]+sum;
        ret=max(ret,dp[i]);
    }
    printf("%d%c",ret,10);
}

Sheet Lv.8

AのマスがBの存在する領域にある時B->Aの辺を結んでトポロジカルソートすればいい

けどまだ書いてないです

Flu Lv.9

点を列挙してBFSする。

なんでLv.9なんだろう

#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
vector<int>go[100005];
bool used[100005]={};
int ex[1005][1005]={};
vector<int>za[1005];
int x[100005],y[100005];
int n,m,d,K;
int main()
{
    scanf("%d %d %d %d",&n,&m,&d,&K);
    for(int i=1;i<=n;i++)
    {
        int a,b;
        scanf("%d %d",&a,&b);
        x[i]=a;
        y[i]=b;
        ex[a][b]=i;
        za[a].push_back(b);
    }
    for(int i=0;i<1005;i++)
    {
        if(za[i].size()) sort(za[i].begin(),za[i].end());
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=max(0,x[i]-25);j<=min(1000,x[i]+25);j++)
        {
            int p=lower_bound(za[j].begin(),za[j].end(),y[i])-za[j].begin();
            for(int k=p;kif(abs(x[i]-j)*abs(x[i]-j)+abs(za[j][k]-y[i])*abs(za[j][k]-y[i])<=d*d)
                {
                    go[i].push_back(ex[j][za[j][k]]);
                }
                else break;
            }
            for(int k=p-1;k>=0;k--)
            {
                if(abs(x[i]-j)*abs(x[i]-j)+abs(za[j][k]-y[i])*abs(za[j][k]-y[i])<=d*d)
                {
                    go[i].push_back(ex[j][za[j][k]]);
                }
                else break;
            }
        }
    }
    queue<int>que;
    que.push(1);
    int ret=0;
    used[1]=true;
    for(int i=1;i<=K;i++)
    {
        int e=(int)que.size();
        if(K-m+1<=i-1) ret+=e;
        for(int j=0;jint fr=que.front();
            que.pop();
            for(int k=0;kif(!used[go[fr][k]])
                {
                    used[go[fr][k]]=true;
                    que.push(go[fr][k]);
                }
            }
        }
    }
    printf("%d%c",ret+(int)que.size(),10);
}

Nile.com Lv.6

DP.

ちょっとした工夫がいる。明らかにLv.6より難しいとおもった

#include 
#include 
using namespace std;
long long dp[3005][4][366];
int n,d;
int main()
{
    scanf("%d %d",&n,&d);
    long long zan=1e10;
    for(int i=0;i<3005;i++)for(int j=0;j<4;j++)for(int k=0;k<366;k++)dp[i][j][k]=1e10;
    for(int i=1;i<=n;i++)
    {
        long long int p; scanf("%lld",&p);
        dp[i][1][1]=p;
        zan=min(zan,p);
    }
    for(int i=2;i<=d;i++)
    {
        long long prev=1e10;
        for(int j=1;j<=n;j++)
        {
            long long int p; scanf("%lld",&p);
            dp[j][1][i]=zan+p;
            dp[j][2][i]=dp[j][1][i-1]+p/10*9;
            dp[j][3][i]=min(dp[j][2][i-1],dp[j][3][i-1])+p/10*7;
            for(int k=1;k<=3;k++) dp[j][k][i]=min(dp[j][k][i],10000000000ll);
            prev=min(min(prev,dp[j][1][i]),min(dp[j][2][i],dp[j][3][i]));
        }
        zan=prev;
    }
    printf("%lld%c",zan,10);
}

いじょーです〜