SRM 463 DIV2
145.73/ 250pt ○
357.07/ 500pt ○
0/1000pt ×
Score : 502.8
レートは上がったけど、数値は書きません(え
言い訳をさせていただきますと、前回と前々回が酷かった。
英語的な意味で、ほんとだよ><
250pt
問題概要
X座標に兎がいます。兎の位置は vector
bunnies[i]地点の兎は
2*bunnies[i-1]-bunnies[i] or 2*bunnies[i+1]-bunnies[i] の位置に移動することができます。
ただし、移動地点に既に兎がいる場合or移動する際に2匹以上兎を飛び越えた場合は移動できません。
求めるのは移動可能なパターン数です。
bunnies[i]が移動し、その状態が次に反映されるということはありません。
vector
-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
求めるのは、そのパターンの総数を1000000007で割った余りです。パターンが存在しない場合は0です。
vector
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; } };
解法:
ソートとして順列計算するだけ。
マイナスになるケースを忘れずに処理する。