問題作った「パスカルの三角形クエリ」
解答書きました: http://d.hatena.ne.jp/anta1/20130201/1359651597
※一瞬このブログに別の問題文を載せてましたが、問題変えました
※少しの発想で作っただけで、よく考えたりしていないので、質は良いとはいえないです。
問題
サイズN(≦10^3)の、段yの幅はy+1の三角形グリッドがある。各点は数値を持っており最初は0。
Q(≦10^4)個のクエリを処理した後の状態を出力せよ。
クエリx,y,k(k≦10^3,x≦y,y≦N-k):パスカルの三角形の最初のk段を(x,y)から下にmod10^9+7で足す
問題文だけじゃわからないところもある思うので、ナイーブにやるコード
#include <cstdio> int main() { static const long long MOD = 1000000007; int N, Q; static long long a[1111][1111]; static long long C[1111][1111]; for(int i = 0; i <= 1000; i ++) { C[i][0] = 1; for(int j = 1; j <= i; j ++) { if((C[i][j] = C[i-1][j-1] + C[i-1][j]) >= MOD) C[i][j] -= MOD; } } scanf("%d", &N); scanf("%d", &Q); for(int ii = 0; ii < Q; ii ++) { int x, y, k; scanf("%d%d%d", &x, &y, &k); for(int i = 0; i < k; i ++) { for(int j = 0; j <= i; j ++) { if((a[y + i][x + j] += C[i][j]) >= MOD) a[y + i][x + j] -= MOD; } } } for(int i = 0; i < N; i ++) { for(int j = 0; j <= i; j ++) { printf("%I64d%c", a[i][j], j == i ? '\n' : ' '); } } return 0; }
その他
時間制限はTopCoderサーバーくらいで2秒程度。
