HackerRank Ad Infinitum - Math Programming Contest May'14 5問目 - Cyclic Quadruples

Source

HackerRank Ad Infinitum - Math Programming Contest May'14 5問目
problem statement(コンテストページ)
problem statement

問題概要

$L_k, R_k, \;\; k=1,2,3,4$ が与えられた時,以下の条件1~2.を満たす整数の $4$ つ組 $(X_1,X_2,X_3,X_4)$ が何個存在するかを ${\rm mod}\ 1000000007\ (10^9+7)$ で求める問題.

  1. $L_k \leq X_k \leq R_k, \;\; k=1,2,3,4$
  2. $X_k \neq X_{(k\ {\rm mod}\ 4) + 1}$,つまり,$X_1 \neq X_2, X_2 \neq X_3, X_3 \neq X_4, X_4 \neq X_1$

解法

条件2が無ければ掛け算するだけで簡単に計算できる.
また,条件1を満たし,かつ,$X_1 = X_2$の時なども,同様に簡単に計算できる.
なので,包除原理を用いる.

C++によるスパゲッティなソースコード

#include<bits/stdc++.h>
using namespace std;

#define REP(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)

#define mygc(c) (c)=getchar_unlocked()
#define mypc(c) putchar_unlocked(c)

#define ll long long
#define M 1000000007

void reader(int *x){int k,m=0;*x=0;for(;;){mygc(k);if(k=='-'){m=1;break;}if('0'<=k&&k<='9'){*x=k-'0';break;}}for(;;){mygc(k);if(k<'0'||k>'9')break;*x=(*x)*10+k-'0';}if(m)(*x)=-(*x);}
void reader(int *x, int *y){reader(x);reader(y);}
void writer(int x, char c){int i,sz=0,m=0;char buf[10];if(x<0)m=1,x=-x;while(x)buf[sz++]=x%10,x/=10;if(!sz)buf[sz++]=0;if(m)mypc('-');while(sz--)mypc(buf[sz]+'0');mypc(c);}

int L[4], R[4];
int num[4];

ll solve(){
  int i, j, k;
  int l[4], r[4], ok[4] = {};
  ll res = 1;

  rep(i,4) l[i] = L[i], r[i] = R[i];
  rep(k,4) rep(i,4) rep(j,4) if(num[i]==num[j]){
    l[i] = l[j] = max(l[i],l[j]);
    r[i] = r[j] = min(r[i],r[j]);
  }

  rep(i,4) if(l[i] > r[i]) return 0;
  rep(i,4) if(!ok[num[i]]){
    res = (res * (r[i]-l[i]+1)) % M;
    ok[num[i]] = 1;
  }
  return res;
}

int main(){
  int T;
  int i, j, k, mask;
  ll res, tmp;

  reader(&T);
  while(T--){
    rep(i,4) reader(L+i,R+i);
    res = 0;

    rep(mask,1<<4){
      rep(i,4) num[i] = i;
      k = 1;
      rep(i,4) if(mask & 1<<i) k *= -1;

      rep(j,4) rep(i,4) if(mask & 1<<i){
        num[i] = num[(i+1)%4] = min(num[i], num[(i+1)%4]);
      }

      res += k * solve();
    }

    res %= M;
    if(res < 0) res += M;
    writer((int)res, '\n');
  }

  return 0;
}

Current time: 2017年07月24日15時49分03秒
Last modified: 2014年09月23日00時02分57秒 (by laycrs)
Tags: Competitive_Programming HackerRank HackerRank_infinitum-may14
トップページに戻る

Logged in as: unknown user (not login)

ログイン: