PKU演習問メモ(8/12)
| No. | 問題名 | 問題の種類および解法 | 難易度 |
|---|---|---|---|
| 2287 | Tian Ji -- The Horse Racing | 貪欲法(or DP) | ★★★★☆ |
| 3046 | Ant Counting | 動的計画法 | ★★☆☆☆ |
| 2475 | Any fool can do it | 構文解析・メモ化再帰 | ★★☆☆☆ |
| 2411 | Mondriaan's Dream | 動的計画法（ビットDP） | ★★★☆☆ |
2287 Tian Ji -- The Horse Racing
問題概要
王がn匹の馬を持っていて、それぞれの強さが与えられる。
自分もn匹の馬を持っていて、それぞれの強さが与えられる。
それぞれが馬を一匹ずつ出場させるレースをn回行い、勝てば+200、負けると-200、引き分けなら0の収入が得られる。
王の馬のレースに出場する順序が与えられたとき、得られる収入の最大値を求めよ。
n≦1000を満たす。
解法
wikipediaで調べたところ、このエピソードは実際のもので、問題文中のQiは（古代中国の国家）斉の威王、Tian Jiは斉の将軍田忌、Sun Binは孫ピン（兵法書を残した人物で、孫氏の子孫とされる）であるらしい。
斉の威王にまつわるエピソードは他にも「鳴かず飛ばず」の故事成語となったものも存在している。
微妙に解法を理解できていない部分があるので参考までに。
動的計画法または貪欲法の二種類の解法があるらしい。
とりあえずは貪欲法の解法を。DP版は理解できたら後で書く。
- 残りの馬のうち、王のもので最も速い馬と、自分の最も速い馬を比較し、
- 自分の馬が勝つなら自分の馬を出してよい
- 自分の馬が負けるならば、代わりに最も遅い馬を出せばよい
- 引き分けのときは、最も遅い馬同士を比較して、
- 自分の遅い馬が勝てるなら、王の遅い馬に遅い馬をぶつけ、
- 負けるなら王の最も早い馬に遅い馬をぶつける
A＜Bのときに、
王の最も速い馬(Aと呼称)に自分の最も速い馬(Bと呼称）をぶつけてよい証明:
AとBがぶつからない最適解があったとする。
Bがぶつかる王の馬をC,Aがぶつかる自分の馬をDとする。
- 二敗のとき、は仮定よりありえない
- Bが負けてDが勝つとき、なんてこともありえない
- Bが勝ってDが負けるとき 仮定よりBはAに勝てる
- 二勝のとき、DでAに勝てるのだから、入れ替えても二勝できる
で、遅い馬についての証明も同様。
（遅い-遅い同士で自分が勝てるとき、別のペアの最適解があったとすると、入れ替えてもそれと同等以上の勝利ができる）
遅い馬同士が引き分けのときに王の速い馬に自分の遅い馬をぶつけて良いのも同様にペアを考えればよいのかな。ここ自信ない。
(王遅い)-(自分遅い)が引き分けの条件下で、
(王遅い)-(自分の何か)
(王何か)-(自分遅い)の最適解があったとする。
戦績としてありえるのは一敗一分けor一勝一敗。一敗一分けは入れ替えてもおｋ。
一勝一敗の場合は……どうなるんだろう。
引き分ける馬がいるのでそいつと入れ替えるのだろうか。それでいいのかよくわからない。
ソースコード
int n,a1[1000],a2[1000]; int main() { while(scanf("%d",&n),n) { rep(i,n)scanf("%d",a1+i); sort(a1,a1+n,greater<int>()); rep(i,n)scanf("%d",a2+i); sort(a2,a2+n,greater<int>()); int t1=n-1,t2=n-1,h1=0,ans=0; for(int i=0;i<=t2;i++) { if(a1[h1]>a2[i]) { ans++,h1++; continue; } else if(a1[h1]<a2[i]) { ans--,t1--; continue; } for(int j=t1,k=t2;j>=h1;j--,k--) { if(a1[j]>a2[k]) { ans++; continue; } if(a1[j]<a2[i])ans--; t1=j-1; t2=k; break; } } printf("%d\n",ans*200); } return 0; }
3046 Ant Counting
解法
典型的な動的計画法。ただしメモリは節約する必要がある。
dp[i][j]に数字をiまで使った要素数jの集合の場合の数を入れて、表を更新していく。
計算量が怪しい気がするが通った。
（最悪1000*100000くらいでびみょーなはず）
ソースコード
const int MOD=1000000; int t,a,s,b; int cnt[1000]; int dp[2][100001]; int main() { scanf("%d%d%d%d",&t,&a,&s,&b); rep(i,a) { int x; scanf("%d",&x); cnt[x-1]++; } sort(cnt,cnt+t); rep(i,a+1)dp[0][i]=i<=cnt[0]; int sum=cnt[0],cur=0,next=1; for(int i=1;i<t;i++) { rep(j,a+1)dp[next][j]=0; rep(j,cnt[i]+1)rep(k,sum+1) { dp[next][j+k]+=dp[cur][k]; if(dp[next][j+k]>=MOD)dp[next][j+k]-=MOD; } sum+=cnt[i]; swap(cur,next); } int ans=0; for(int i=s;i<=b;i++) { ans+=dp[cur][i]; if(ans>=MOD)ans-=MOD; } printf("%d\n",ans); return 0; }
2475 Any fool can do it
問題概要
200文字以下の文字列が、与えられる。これが、以下のBNF記法におけるsetであるかを判定せよ。
Set ::= "{" Elementlist "}"
Elementlist ::= <empty> | List
List ::= Element | Element "," List
Element ::= Atom | Set
Atom ::= "{" | "}" | ","
ソースコード
bool isse(int,int); bool isli(int,int); bool isel(int,int); int n; char in[201]; int li[201][201],se[201][201],el[201][201]; bool isel(int s,int t) { if(s<0||t>n||s>=t)return 0; if(el[s][t]!=-1)return el[s][t]; if(s+1==t)return el[s][t]=in[s]=='{'||in[s]=='}'||in[s]==','; return el[s][t]=isse(s,t); } bool isli(int s,int t) { if(s<0||t>n||s>=t)return 0; if(li[s][t]!=-1)return li[s][t]; if(isel(s,t))return li[s][t]=1; for(int p=s;p<t;p++)if(in[p]==',') if(isel(s,p)&&isli(p+1,t))return li[s][t]=1; return li[s][t]=0; } bool isse(int s,int t) { if(s<0||t>n||s>=t-1)return 0; if(se[s][t]!=-1)return se[s][t]; if(in[s]!='{'||in[t-1]!='}')return se[s][t]=0; return se[s][t]=s==t-2||isli(s+1,t-1); } int main() { int CS; scanf("%d",&CS); rep(cs,CS) { scanf("%s",in); n=strlen(in); rep(i,n+1)rep(j,n+1)li[i][j]=se[i][j]=el[i][j]=-1; printf("Word #%d: %sSet\n",cs+1,isse(0,n)?"":"No "); } return 0; }
2411 Mondriaan's Dream
問題概要
wxhの長方形の部屋に、1x2の長方形のタイルを敷き詰める場合の数を求めよ。
w,h≦11を満たす。
解法
辺は11なので、一行についてビットで状態が持てる。
なので、dp[i][j]=i行を、最後の行を状態jで埋める場合の数として、
一行ずつDP表を更新していけばよい。
ソースコード
int w,h; ll dp[12][1<<11]; void gen(ll *a,int &sz,int bit,int c) { if(c>=w) { a[sz++]=bit; return; } if(c<w-1&&!(bit&1<<c)&&!(bit&1<<c+1)) gen(a,sz,bit|1<<c|1<<c+1,c+2); gen(a,sz,bit,c+1); } int main() { while(scanf("%d%d",&w,&h),w) { if(w>h)swap(w,h); rep(i,h+1)rep(j,1<<w)dp[i][j]=0; dp[0][0]=1; rep(i,h)rep(j,1<<w)if(dp[i][j]) { ll tmp[1<<w]; int sz=0; gen(tmp,sz,j,0); rep(k,sz)dp[i+1][tmp[k]^(1<<w)-1]+=dp[i][j]; } cout<<dp[h][0]<<endl; } return 0; }
