スポンサーサイト

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

CodeChef October Long Contest 2011

2011/01/01 18:30 ~ 10/11 18:30 (JST)
CodeChef October Long Contest 2011 の参加記

tie breaker problem が熱かった。

Tags : プログラミング CodeChef

結果

問題を、問題ページの上から順に A, B, .. と呼ぶことにする。
A. AC [1 pts]
B. AC [1 pts]
C. AC [0.999 pts] (21.956457)
D. AC [1 pts]
E. -
F. AC [1 pts]
Standing : 30/更新待ち
Rank (Long) : 111 → 更新待ち
Rating (Long) : 96.914 → 更新待ち


問題

問題セットの原文はここを参照。

A. The Baking Business
次の 2 種類のクエリを合計 S 個処理せよ。

・ クエリ I : 客の商品購入情報を登録する。
クエリは、
商品ID[.商品サイズ] 都道府県ID[.市ID[.町ID]] 性別 年齢 購入個数
というフォーマットで与えられる。[ ] で囲んだ部分は必ずしも入力に含まれない。

・ クエリ Q : 指定された商品の販売個数を答える。
クエリは、
商品ID[.商品サイズ] 都道府県ID[.市ID[.町ID]] 性別 年齢1[-年齢2]
というフォーマットで与えられる。[ ] で囲んだ部分は必ずしも入力に含まれない。
年齢 2 が含まれない場合は、年齢 2 = 年齢 1 とみなす。
年齢 1 以上年齢 2 以下の客について、クエリの条件をみたす商品の販売個数を答える。

S ≦ 105
商品 ID ≦ 10
商品サイズ ≦ 3
都道府県 ID ≦ 10
市 ID ≦ 20
町 ID ≦ 5
性別 = 'M' or 'F'
1 ≦ 年齢 ≦ 90

性別以外はすべて整数

B. Dish Distribution

n 枚の皿と m 人の料理人がいる。
i 番目の料理人には xi 枚以上 yi 枚以下の皿をわりあてる。
皿のわりあて方は何通りあるか? mod 1000000007 で求めよ。
なお、皿は区別できないものとする。

1 ≦ n, m ≦ 100

C. The Great Plain

M × N のグリッドを考える。
いくつかの点では、あらかじめ計測を行っていて高さがわかっている。
高さがわかっていないすべての点に、全体としてグリッドが平面に近づくように高さを割り当てよ。

隣接する任意の 2 マスを A, B として、2|h(A)-h(B)| の和が得点になる。 ( h(・) はその点での高さ )
得点が低いほど高評価。

1 ≦ M, N ≦ 100
高さの値は 1 以上 50 以下の整数

D. Lucky Palin

長さ 1000 以下のアルファベット小文字からなる文字列 S が与えられる。
「ある文字をある文字に置換する」 という操作を何回か繰り返して、S を "lucky" という部分文字列を含む回文にしたい。
必要な操作の最小回数と、得られる回文を求めよ。
答えが複数ある場合は辞書式最小のもの。

E. Sine Partition Function

f (M, N, X) := Σk1+...+kM=NΠi=1 to M sin (ki X)
とおく。ただし、各 ki は 0 以上の整数。

f (M, N, X) を求めよ。

1 ≦ M ≦ 30
1 ≦ N ≦ 109

F. Repeated String

長さ 105 以下のアルファベット小文字からなる文字列 S が与えられる。
長さ L 以上 H 以下の文字列で、S に部分文字列として含まれる回数が一番多いもの ( の長さ ) とその出現回数を求めよ。
複数ある場合は最長のもの。

解答

言語は C++。テンプレはここを参照。

A.
int rec[21][3][21][40][5][90][2];
// 第 0-1 成分 : 製品の id
// 第 2-4 成分 : 売られた地域の id
// 第 5 成分 : 年齢
// 第 6 成分 : 性別

// 第 0,2 成分 : 10+id なら全ての子, 20 なら兄弟も含め全てを指す
// 第 3 成分 : 20+id なら全ての子, 40 なら兄弟も含め全てを指す

int main(){
int Q; scanf("%d",&Q);
while(Q--){
char type,sex;
vector<int> id1,id2,age;
scanf(" %c",&type);
do{ int a; scanf("%d",&a); id1.push_back(a); }while(getchar()=='.');
do{ int a; scanf("%d",&a); id2.push_back(a); }while(getchar()=='.');
scanf(" %c",&sex); sex=(sex=='M'?0:1);
do{ int a; scanf("%d",&a); age.push_back(a-1); }while(getchar()=='-');

if(type=='I'){
vector<int> p11,p12;
switch(id1.size()){
case 2:
p11.push_back(id1[0]);
p12.push_back(id1[1]);
case 1:
p11.push_back(10+id1[0]);
p12.push_back(0);
default:
p11.push_back(20);
p12.push_back(0);
}

vector<int> p21,p22,p23;
switch(id2.size()){
case 3:
p21.push_back(id2[0]);
p22.push_back(id2[1]);
p23.push_back(id2[2]);
case 2:
p21.push_back(id2[0]);
p22.push_back(20+id2[1]);
p23.push_back(0);
case 1:
p21.push_back(10+id2[0]);
p22.push_back(0);
p23.push_back(0);
default:
p21.push_back(20);
p22.push_back(0);
p23.push_back(0);
}

int sold; scanf("%d",&sold);
rep(i,p11.size()) rep(j,p21.size()) {
rec[p11[i]][p12[i]][p21[j]][p22[j]][p23[j]][age[0]][sex]+=sold;
}
}
else{ // type=='Q'
int p11,p12;
if (id1[0]==-1) p11=20, p12=0;
else if(id1.size()==1) p11=10+id1[0], p12=0;
else p11=id1[0], p12=id1[1];

int p21,p22,p23;
if (id2[0]==-1) p21=20, p22=0, p23=0;
else if(id2.size()==1) p21=10+id2[0], p22=0, p23=0;
else if(id2.size()==2) p21=id2[0], p22=20+id2[1], p23=0;
else p21=id2[0], p22=id2[1], p23=id2[2];

if(age.size()==1) age.push_back(age[0]);

int ans=0;
for(int i=age[0];i<=age[1];i++) ans+=rec[p11][p12][p21][p22][p23][i][sex];
printf("%d\n",ans);
}
}

return 0;
}

全て配列に記録した。
高級なデータ構造などは一切使っていない。

B.
const int M=1000000007;

int m,lb[100],ub[100],dp[100][101];

int dfs(int i,int n){
int res=0;
for(int j=lb[i];j<=ub[i];j++){
if(j>n) break;

if (i+1==m) res+=(n==j?1:0);
else if(~dp[i+1][n-j]) res+=dp[i+1][n-j];
else res+=dfs(i+1,n-j);
if(res>=M) res-=M;
}
return dp[i][n]=res;
}

int main(){
int T; scanf("%d",&T);
while(T--){
int n; scanf("%d%d",&n,&m);
rep(i,m){
rep(j,n+1) dp[i][j]=-1;
scanf("%d%d",lb+i,ub+i);
}
printf("%d\n",dfs(0,n));
}

return 0;
}

メモ化再帰。
dp[i][j] := i 番目の料理人まで見ていて、残りの皿が j 枚であるときの分配方法の総数
とした。

TLE したので、再帰の終了条件を関数呼び出しの前に組み込んでやったら間に合うようになった。
そのせいで、少し読みにくいコードになってしまった。

C.
#include<cstdio>
#include<cstdlib>
#include<sys/time.h>

#define rep(i,n) for(int i=0;i<(n);i++)

using namespace std;

typedef long long ll;

const int dx[]={1,0,-1,0},dy[]={0,-1,0,1};

bool q[100][100];
int m,n,h[100][100],ans[100][100];

inline int MIN(int a,int b){ return a<b?a:b; }
inline int MAX(int a,int b){ return a<b?b:a; }

ll gettime(){
static timeval tv;
gettimeofday(&tv,NULL);
return tv.tv_sec*1000000LL+tv.tv_usec;
}

ll score(){
ll sc=0;
rep(i,m) rep(j,n) rep(k,4) {
int y=i+dy[k],x=j+dx[k];
if(0<=y && y<m && 0<=x && x<n) sc+=1LL<<abs(h[i][j]-h[y][x]);
}
return sc/2;
}

bool smooth_h(){
bool first;
for(first=true;;first=false){
bool changed=false;

rep(i,m) rep(j,n-1) if(q[i][j] && q[i][j+1]) {
ll sc1=0,sc2=0,sc3=0,sc4=0,sc5=0,sc6=0,sc7=0;
// sc1 : そのまま
// sc2 : 左 +1
// sc3 : 左 -1
// sc4 : 右 +1
// sc5 : 右 -1
// sc6 : 左右 +1
// sc7 : 左右 -1
if(i>0){
sc1+=1LL<<abs(h[i][j ]-h[i-1][j ]);
sc1+=1LL<<abs(h[i][j+1]-h[i-1][j+1]);
sc2+=1LL<<abs(h[i][j ]-h[i-1][j ]+1);
sc2+=1LL<<abs(h[i][j+1]-h[i-1][j+1]);
sc3+=1LL<<abs(h[i][j ]-h[i-1][j ]-1);
sc3+=1LL<<abs(h[i][j+1]-h[i-1][j+1]);
sc4+=1LL<<abs(h[i][j ]-h[i-1][j ]);
sc4+=1LL<<abs(h[i][j+1]-h[i-1][j+1]+1);
sc5+=1LL<<abs(h[i][j ]-h[i-1][j ]);
sc5+=1LL<<abs(h[i][j+1]-h[i-1][j+1]-1);
sc6+=1LL<<abs(h[i][j ]-h[i-1][j ]+1);
sc6+=1LL<<abs(h[i][j+1]-h[i-1][j+1]+1);
sc7+=1LL<<abs(h[i][j ]-h[i-1][j ]-1);
sc7+=1LL<<abs(h[i][j+1]-h[i-1][j+1]-1);
}
if(i<m-1){
sc1+=1LL<<abs(h[i][j ]-h[i+1][j ]);
sc1+=1LL<<abs(h[i][j+1]-h[i+1][j+1]);
sc2+=1LL<<abs(h[i][j ]-h[i+1][j ]+1);
sc2+=1LL<<abs(h[i][j+1]-h[i+1][j+1]);
sc3+=1LL<<abs(h[i][j ]-h[i+1][j ]-1);
sc3+=1LL<<abs(h[i][j+1]-h[i+1][j+1]);
sc4+=1LL<<abs(h[i][j ]-h[i+1][j ]);
sc4+=1LL<<abs(h[i][j+1]-h[i+1][j+1]+1);
sc5+=1LL<<abs(h[i][j ]-h[i+1][j ]);
sc5+=1LL<<abs(h[i][j+1]-h[i+1][j+1]-1);
sc6+=1LL<<abs(h[i][j ]-h[i+1][j ]+1);
sc6+=1LL<<abs(h[i][j+1]-h[i+1][j+1]+1);
sc7+=1LL<<abs(h[i][j ]-h[i+1][j ]-1);
sc7+=1LL<<abs(h[i][j+1]-h[i+1][j+1]-1);
}
if(j>0){
sc1+=1LL<<abs(h[i][j]-h[i][j-1]);
sc2+=1LL<<abs(h[i][j]-h[i][j-1]+1);
sc3+=1LL<<abs(h[i][j]-h[i][j-1]-1);
sc4+=1LL<<abs(h[i][j]-h[i][j-1]);
sc5+=1LL<<abs(h[i][j]-h[i][j-1]);
sc6+=1LL<<abs(h[i][j]-h[i][j-1]+1);
sc7+=1LL<<abs(h[i][j]-h[i][j-1]-1);
}
if(j<n-2){
sc1+=1LL<<abs(h[i][j+1]-h[i][j+2]);
sc2+=1LL<<abs(h[i][j+1]-h[i][j+2]);
sc3+=1LL<<abs(h[i][j+1]-h[i][j+2]);
sc4+=1LL<<abs(h[i][j+1]-h[i][j+2]+1);
sc5+=1LL<<abs(h[i][j+1]-h[i][j+2]-1);
sc6+=1LL<<abs(h[i][j+1]-h[i][j+2]+1);
sc7+=1LL<<abs(h[i][j+1]-h[i][j+2]-1);
}
sc1+=1LL<<abs(h[i][j]-h[i][j+1]);
sc2+=1LL<<abs(h[i][j]-h[i][j+1]+1);
sc3+=1LL<<abs(h[i][j]-h[i][j+1]-1);
sc4+=1LL<<abs(h[i][j]-h[i][j+1]-1);
sc5+=1LL<<abs(h[i][j]-h[i][j+1]+1);
sc6+=1LL<<abs(h[i][j]-h[i][j+1]);
sc7+=1LL<<abs(h[i][j]-h[i][j+1]);

// update
int dl=0,dr=0;
if(h[i][j ]<50 && sc2<sc1) dl=+1, dr= 0, changed=true, sc1=sc2;
if(h[i][j ]> 1 && sc3<sc1) dl=-1, dr= 0, changed=true, sc1=sc3;
if(h[i][j+1]<50 && sc4<sc1) dl= 0, dr=+1, changed=true, sc1=sc4;
if(h[i][j+1]> 1 && sc5<sc1) dl= 0, dr=-1, changed=true, sc1=sc5;
if(h[i][j ]<50 && h[i][j+1]<50 && sc6<sc1) dl=+1, dr=+1, changed=true, sc1=sc6;
if(h[i][j ]> 1 && h[i][j+1]> 1 && sc7<sc1) dl=-1, dr=-1, changed=true, sc1=sc7;

h[i][j ]+=dl;
h[i][j+1]+=dr;
}

if(!changed) break;
}

return !first;
}

bool smooth_v(){
bool first;
for(first=true;;first=false){
bool changed=false;

rep(i,m-1) rep(j,n) if(q[i][j] && q[i+1][j]) {
ll sc1=0,sc2=0,sc3=0,sc4=0,sc5=0,sc6=0,sc7=0;
// sc1 : そのまま
// sc2 : 上 +1
// sc3 : 上 -1
// sc4 : 下 +1
// sc5 : 下 -1
// sc6 : 上下 +1
// sc7 : 上下 -1
if(j>0){
sc1+=1LL<<abs(h[i ][j]-h[i ][j-1]);
sc1+=1LL<<abs(h[i+1][j]-h[i+1][j-1]);
sc2+=1LL<<abs(h[i ][j]-h[i ][j-1]+1);
sc2+=1LL<<abs(h[i+1][j]-h[i+1][j-1]);
sc3+=1LL<<abs(h[i ][j]-h[i ][j-1]-1);
sc3+=1LL<<abs(h[i+1][j]-h[i+1][j-1]);
sc4+=1LL<<abs(h[i ][j]-h[i ][j-1]);
sc4+=1LL<<abs(h[i+1][j]-h[i+1][j-1]+1);
sc5+=1LL<<abs(h[i ][j]-h[i ][j-1]);
sc5+=1LL<<abs(h[i+1][j]-h[i+1][j-1]-1);
sc6+=1LL<<abs(h[i ][j]-h[i ][j-1]+1);
sc6+=1LL<<abs(h[i+1][j]-h[i+1][j-1]+1);
sc7+=1LL<<abs(h[i ][j]-h[i ][j-1]-1);
sc7+=1LL<<abs(h[i+1][j]-h[i+1][j-1]-1);
}
if(j<n-1){
sc1+=1LL<<abs(h[i ][j]-h[i ][j+1]);
sc1+=1LL<<abs(h[i+1][j]-h[i+1][j+1]);
sc2+=1LL<<abs(h[i ][j]-h[i ][j+1]+1);
sc2+=1LL<<abs(h[i+1][j]-h[i+1][j+1]);
sc3+=1LL<<abs(h[i ][j]-h[i ][j+1]-1);
sc3+=1LL<<abs(h[i+1][j]-h[i+1][j+1]);
sc4+=1LL<<abs(h[i ][j]-h[i ][j+1]);
sc4+=1LL<<abs(h[i+1][j]-h[i+1][j+1]+1);
sc5+=1LL<<abs(h[i ][j]-h[i ][j+1]);
sc5+=1LL<<abs(h[i+1][j]-h[i+1][j+1]-1);
sc6+=1LL<<abs(h[i ][j]-h[i ][j+1]+1);
sc6+=1LL<<abs(h[i+1][j]-h[i+1][j+1]+1);
sc7+=1LL<<abs(h[i ][j]-h[i ][j+1]-1);
sc7+=1LL<<abs(h[i+1][j]-h[i+1][j+1]-1);
}
if(i>0){
sc1+=1LL<<abs(h[i][j]-h[i-1][j]);
sc2+=1LL<<abs(h[i][j]-h[i-1][j]+1);
sc3+=1LL<<abs(h[i][j]-h[i-1][j]-1);
sc4+=1LL<<abs(h[i][j]-h[i-1][j]);
sc5+=1LL<<abs(h[i][j]-h[i-1][j]);
sc6+=1LL<<abs(h[i][j]-h[i-1][j]+1);
sc7+=1LL<<abs(h[i][j]-h[i-1][j]-1);
}
if(i<m-2){
sc1+=1LL<<abs(h[i+1][j]-h[i+2][j]);
sc2+=1LL<<abs(h[i+1][j]-h[i+2][j]);
sc3+=1LL<<abs(h[i+1][j]-h[i+2][j]);
sc4+=1LL<<abs(h[i+1][j]-h[i+2][j]+1);
sc5+=1LL<<abs(h[i+1][j]-h[i+2][j]-1);
sc6+=1LL<<abs(h[i+1][j]-h[i+2][j]+1);
sc7+=1LL<<abs(h[i+1][j]-h[i+2][j]-1);
}
sc1+=1LL<<abs(h[i][j]-h[i+1][j]);
sc2+=1LL<<abs(h[i][j]-h[i+1][j]+1);
sc3+=1LL<<abs(h[i][j]-h[i+1][j]-1);
sc4+=1LL<<abs(h[i][j]-h[i+1][j]-1);
sc5+=1LL<<abs(h[i][j]-h[i+1][j]+1);
sc6+=1LL<<abs(h[i][j]-h[i+1][j]);
sc7+=1LL<<abs(h[i][j]-h[i+1][j]);

// update
int dt=0,db=0;
if(h[i ][j]<50 && sc2<sc1) dt=+1, db= 0, changed=true, sc1=sc2;
if(h[i ][j]> 1 && sc3<sc1) dt=-1, db= 0, changed=true, sc1=sc3;
if(h[i+1][j]<50 && sc4<sc1) dt= 0, db=+1, changed=true, sc1=sc4;
if(h[i+1][j]> 1 && sc5<sc1) dt= 0, db=-1, changed=true, sc1=sc5;
if(h[i ][j]<50 && h[i][j+1]<50 && sc6<sc1) dt=+1, db=+1, changed=true, sc1=sc6;
if(h[i ][j]> 1 && h[i][j+1]> 1 && sc7<sc1) dt=-1, db=-1, changed=true, sc1=sc7;

h[i ][j]+=dt;
h[i+1][j]+=db;
}

if(!changed) break;
}

return !first;
}

void smooth(){ while(smooth_h() || smooth_v()); }

void init_dom(){
int k=0,x[1000],y[1000];
rep(i,m) rep(j,n) if(!q[i][j]) {
x[k]=j;
y[k]=i;
k++;
}

rep(i,m) rep(j,n) if(q[i][j]) {
int tmp=200,l_min;
rep(l,k) if(abs(i-y[l])+abs(j-x[l])<tmp) {
tmp=abs(i-y[l])+abs(j-x[l]);
l_min=l;
}
h[i][j]=h[y[l_min]][x[l_min]];
}
}

void init_rnd(){
rep(i,m) rep(j,n) if(q[i][j]) h[i][j]=rand()%50+1;
rep(_,12){
rep(i,m) rep(j,n) if(q[i][j]) {
int mn=50,mx=1;
rep(k,4){
int y=i+dy[k],x=j+dx[k];
if(0<=y && y<m && 0<=x && x<n){
mn=MIN(mn,h[y][x]);
mx=MAX(mx,h[y][x]);
}
}
h[i][j]=(mn+mx)/2;
}
}
}

void init_flat(int k){
rep(i,m) rep(j,n) if(q[i][j]) h[i][j]=k;
}

void solve(ll tlim){
const ll t_ini=gettime();

int mean=0,cnt=0;
rep(i,m) rep(j,n) {
if(h[i][j]){
mean+=h[i][j];
cnt++;
}
q[i][j]=!h[i][j];
}
mean=(int)((double)mean/cnt+0.5);

ll sc=(1LL<<63)-1;

// type 0 : domination
{
init_dom();
smooth();

ll tmp=score();
if(tmp<sc){
sc=tmp;
rep(i,m) rep(j,n) ans[i][j]=h[i][j];
}
}

// type 1 : flat
int np=1,p[3]={mean};
if(mean+1<=50) p[np++]=mean+1;
if(mean-1>= 1) p[np++]=mean-1;

rep(k,np){
if(gettime()-t_ini>tlim) return;

init_flat(p[k]);
smooth();

ll tmp=score();
if(tmp<sc){
sc=tmp;
rep(i,m) rep(j,n) ans[i][j]=h[i][j];
}
}

// type 2 : random
for(int t=1;;t++){
if(gettime()-t_ini>tlim) return;

init_rnd();
smooth();

ll tmp=score();
if(tmp<sc){
sc=tmp;
rep(i,m) rep(j,n) ans[i][j]=h[i][j];
}
}
}

/*************************************************/

int _m[10],_n[10],_h[10][100][100];

int main(){
srand(77777);

int T0; scanf("%d",&T0);
rep(T,T0){
scanf("%d%d",_m+T,_n+T);
rep(i,_m[T]) rep(j,_n[T]) scanf("%d",_h[T][i]+j);
}

rep(T,T0){
m=_m[T];
n=_n[T];
rep(i,m) rep(j,n) h[i][j]=_h[T][i][j];

solve(4000000/T0);

rep(i,m) rep(j,n) printf("%2d%c",ans[i][j],j<n-1?' ':'\n');
}

return 0;
}

色々やったけど、最終的には次の戦略に落ちついた。

最初から高さがわかっている点を 計測点 と呼ぶことにする。

1. ( 計測点でない ) 各点を良さそうな値で初期化
2. 局所改善
3. 時間が許す限り 1. に戻る

1. について
次の 3 種類の戦略が有望だった。( どの 1 つを除いてもスコアが下がる )
・ 点 A の高さ = 計測点のうち、マンハッタン距離で測って A に一番近いものの高さ
・ 点 A の高さ = 計測点の高さの平均値 ( ± 1 )
・ 点 A の高さ = [1, 50] からランダムに割り振ったあと、4 近傍との差が小さくなるようになめした値。
( A は計測点でない点 )

2. について
連続する縦 2 マスについて、その高さを変えたらスコアがよくなる場合は高さを変える。
連続する横 2 マスについても同様。
スコアの改善がなくなるまで繰り返した。
コードがひどいことになっているのは、主にここの処理が原因。

3. について
制限時間 5 秒をテストケース数で割って、各テストケースごとに均等に時間を配分した。
グリッドサイズが大きいケースに多く時間を割いたり、その逆も試したりしたけど、スコアは伸びなかった。



Editorials で言われていたように、連結している同じ高さの点を一気に更新するようにすればもっとスコアが伸びたかもしれない。
あと、焼きなましやその他のヒューリスティクスはやっぱり強いと思った。

ちなみに、サンプル 1 の最適解は 57 点。

D.
int main(){
const char *L="lucky";

int T; scanf("%d",&T);
while(T--){
char s[1001]; scanf("%s",s);
int n=strlen(s);

if(n<9){ puts("unlucky"); continue; }

int ans=7777777;
char s_ans[1001];
rep(i,n-4){
if(i<n/2 && (n-1)/2<i+4) continue;

char s2[1001];
rep(j,(n+1)/2) s2[j]=s2[n-j-1]=min(s[j],s[n-j-1]);
rep(j,5) s2[i+j]=s2[n-(i+j)-1]=L[j];
s2[n]='\0';

int tmp=0;
rep(i,n) if(s[i]!=s2[i]) tmp++;

if(tmp<ans || (tmp==ans && strcmp(s2,s_ans)<0)){
ans=tmp;
strcpy(s_ans,s2);
}
}

printf("%s %d\n",s_ans,ans);
}

return 0;
}

"lucky" がどの位置に入るかを全部試す。
"lucky" が入らなかった場所は、辞書式最小の回文になるように、必要であれば文字を置換する。

O(|S|2) で間に合う。

E. (時間外)
int main(){
int T; scanf("%d",&T);
while(T--){
int m,n;
double x; scanf("%d%d%lf",&m,&n,&x);

double A[60][60]={};
rep(i,m){
A[i][m+i]=1;
A[i+m][i]=-1;
A[i+m][i+m]=2*cos(x);
if(i>0) A[i+m][i+m-1]=sin(x);
}

double v[60]={};
v[m]=sin(x);

rep(l,30){
if(n&(1<<l)){
double v2[60]={};
rep(i,2*m) rep(j,2*m) v2[i]+=A[i][j]*v[j];
rep(i,2*m) v[i]=v2[i];
}

double A2[60][60]={};
rep(i,2*m) rep(j,2*m) rep(k,2*m) A2[i][j]+=A[i][k]*A[k][j];
rep(i,2*m) rep(j,2*m) A[i][j]=A2[i][j];
}

printf("%f\n",v[m-1]);
}

return 0;
}

解説を見ながら解いた。
解法は解説とほぼ同じなので、省略気味に書く。

sin mx = 2 cos x sin (m-1)x - sin (m-2)x
という漸化式が重要で、これに気付かないと ( 想定解法では ) 解けない。

この式を使えば、
f (M, N, X) = sin X f (M-1, N, X) + 2 cos X f (M, N-1, X) - f (M, N-2, X)
という漸化式を作ることができる。

これは N に関する 3 項間漸化式なので、行列べき乗を繰り返し二乗法で計算することで、大きい N に対する f (M, N, X) を求めることができる。
O(M3 log N).

F.
const ll M=1000000007;

int len;
char s[100001];

ll p=1009,pinv=222993064;

int solve(int n){
int m=0;
static ll sub[100000];

ll hash=0,d=1;
rep(i,n){
hash=(hash+s[i]*d)%M;
d=(d*p)%M;
}
for(int i=n;i<=len;i++){
sub[m++]=hash;
if(i<len){
hash=(hash-s[i-n]+s[i]*d+M)%M;
hash=(hash*pinv)%M;
}
}
sub[m]=-1;

int res=0;
sort(sub,sub+m);
for(int i=1,c=1;i<=m;i++){
if(sub[i-1]==sub[i]) c++;
else{
res=max(res,c);
c=1;
}
}
return res;
}

int main(){
for(int lo,hi;scanf("%d%d%s",&lo,&hi,s),lo;){
len=strlen(s);
int ans=solve(lo);
while(lo<hi){
int mi=(lo+hi+1)/2;
if(ans==solve(mi)) lo=mi; else hi=mi-1;
}
printf("%d %d\n",ans,lo);
}

return 0;
}

問題文が読めなくて、多分こういう意味なんじゃないかと推測して解いたら通った。

C(K) := max { T が S に含まれる回数 | T は長さ K (L ≦ K ≦ H) の S の部分文字列 }
とすれば、
K1 ≦ K2 ⇒ C(K1) ≧ C(K2).
すなわち、解には単調性があるので、二分探索が使える。

調べる部分文字列の長さを固定してしまえば、C(K) の計算は rolling hash を使うことで O(|S| log |S|) でできる。
( ソートしているから log がつく。 )

hash の衝突検出をしていないので 100% 正解が求まるわけじゃないけど、1 つの基数を試すだけで通った。
逆に、安全性を高めようとして基数を増やすと TLE した。

Suffix Tree とか知らない。
スポンサーサイト

コメントの投稿

非公開コメント

プロフィール

fura2

Author : fura2
数学・コンピュータを中心に、考えたこと・やったことを書いていきます。

誤植等を含め、間違いはご指摘いただければ幸いです。

FC2カウンター
検索フォーム
最新記事
最新コメント
最新トラックバック
月別アーカイブ
リンク
RSSリンクの表示
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。