読者です 読者をやめる 読者になる 読者になる

ichirin2501's diary

いっちりーん。

SRM 463 DIV2

145.73/ 250pt ○
357.07/ 500pt ○
0/1000pt ×

Score : 502.8
レートは上がったけど、数値は書きません(え
言い訳をさせていただきますと、前回と前々回が酷かった。
英語的な意味で、ほんとだよ><


250pt

問題概要
X座標に兎がいます。兎の位置は vector bunnies で与えられます(昇順にソート済み)。
bunnies[i]地点の兎は
2*bunnies[i-1]-bunnies[i] or 2*bunnies[i+1]-bunnies[i] の位置に移動することができます。
ただし、移動地点に既に兎がいる場合or移動する際に2匹以上兎を飛び越えた場合は移動できません。
求めるのは移動可能なパターン数です。
bunnies[i]が移動し、その状態が次に反映されるということはありません。
vector bunnies は2以上50以下の個数。
-10^6 <= bunnies[i] <= 10^6 の範囲。


Sample0
input : {5, 8}
output : 2


Sample1
input : {-1, 0, 1}
output : 2


Sample2
input : {0, 1, 3}
output : 3


Sample3
input : {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}
output : 2


class BunnyPuzzle
{
public:
   int theCount(vector <int> bunnies)
   {
      int ret = 0;
      for(int i=0; i<bunnies.size(); i++){
         int d1,d2;
         int flag = 0;
         int cnt = 0;
         
         if( i>0 ){
            d1 = 2*bunnies[i-1]-bunnies[i];
            for(int j=0; j<i; j++){
               if( bunnies[j]==d1 )flag=1;
               if( bunnies[j]>d1 )cnt++;
            }
            if( !flag && cnt<2 ){
               ret++;
            }
         }
         
         flag = cnt = 0;
         if( i<bunnies.size()-1 ){
            d2 = 2*bunnies[i+1]-bunnies[i];
            for(int j=i+1; j<bunnies.size(); j++){
               if( bunnies[j]==d2 )flag=1;
               if( bunnies[j]<d2 )cnt++;
            }
            if( !flag && cnt<2 ){
               ret++;
            }
         }
      }
      return ret;
   }
};

解法:
素直に実装するだけ。上のコードはあまりに醜い。


500pt

問題概要
各々の位置に指定された範囲の任意の数字を割り当てたい。
ただし、同じ数字が出現してはならない(重複なし)
各々の位置に対して指定される数字の範囲は vector maxNumber で与えられる。
求めるのは、そのパターンの総数を1000000007で割った余りです。パターンが存在しない場合は0です。
vector maxNumber の個数は最大50個
1 <= maxNumber[i] <= 1000 の範囲。



Sample0
input : { 4, 4, 4, 4 }
output : 24


Sample1
input : { 2, 1, 2 }
output : 0


Sample2
input : { 5, 8 }
output : 35


Sample3
input : {420, 380, 38, 839, 626}
output : 652805463


#define all(x) x.begin(),x.end()
class RabbitNumbering
{
public:
   int theCount(vector <int> maxNumber)
   {
      sort(all(maxNumber));
      long long ret = 1LL;
      long long MOD = 1000000007LL;
      for(int i=0; i<maxNumber.size(); i++){
         ret *= (maxNumber[i]-i);
         if( ret<0 )ret=0;
         ret %= MOD;
      }
      return ret;
   }
};

解法:
ソートとして順列計算するだけ。
マイナスになるケースを忘れずに処理する。