TTPC
ラテ君とチームでTTPC(東京工業大学プログラミングコンテスト)に参加しました。
チーム名は「こくりつくるめどうぶつえん」でした。(先輩方が「こくりつくるめようちえん」だったので)
僕は最近全然競プロやってなかったのでラテ君に頼った感じでした。
A~D問題
まずラテ君がA問題からプロの速度でやるだけ埋めをやってくれました。
僕はやるだけライン見極めのためにとりあえずD問題を見ました。
D問題は制約見てビビったけどよく考えたら全列挙いけそうなのでラテ君に投げて僕はE,Fへ行きました。
D問題のコード(らてくん)
int N; bool prime(long long x){ if(x==1)return false; for(long long i=2;i*i<=x;i++){ if(x%i==0)return false; } return true; } int main(){ string s; cin>>s; N=s.size(); set<char>S; for(int i=0;i<N;i++)S.insert(s[i]); if(S.size()>5){ cout<<-1<<endl; return 0; } vector<char>v; for(int i=0;i<N;i++)v.push_back(s[i]); sort(v.begin(),v.end()); v.erase(unique(v.begin(),v.end()),v.end()); vector<int>a(N); for(int i=0;i<N;i++){ a[i]=find(v.begin(),v.end(),s[i])-v.begin(); } vector<int>p; for(int i=0;i<5;i++)p.push_back(i*2+1); do{ vector<int>b=a; for(int i=0;i<b.size();i++)b[i]=p[b[i]]; long long x=0; for(int i=0;i<b.size();i++)x=x*10+b[i]; if(prime(x)){ for(int i=0;i<b.size();i++)cout<<b[i]; cout<<endl; return 0; } }while(next_permutation(p.begin(),p.end())); cout<<-1<<endl; return 0; }
ラテ君が思った以上にすごいスピードでやるだけ埋めをしていたので、僕はEのアルゴリズムをラテ君に伝えて実装してもらうことにしてFを考えていました。
E問題
まず2次元の累積和のやつで、ある長方形に含まれる赤色・青色のマスの数はO(1)で出ます。
変更される場所はたかだか10個なので、その10個が含まれる行・列を辺にした長方形を全列挙することを考えました。
辺を4つ決めれば長方形が決まるので長方形の数は最悪10*10*10*10です。
しかし、長方形の辺の長さが1ずれると赤色・青色のマスの数が変わることがある(ただし2ずれると戻る)と気付きました。
そこで、変更された場所が含まれる行・列以外にその1つ隣の行・列もてきとうに含めて、30*30*30*30個の長方形を全列挙するのを思いつきました。
そしてラテ君に実装を投げました。
コード(らてくん)
int N,K; int fld[2001][2001]; int y[10],x[10]; int main(){ scanf("%d%d",&N,&K); for(int i=1;i<=N;i++){ for(int j=1;j<=N;j++){ fld[i][j]=(i+j)&1; } } for(int i=0;i<K;i++){ scanf("%d%d",&y[i],&x[i]); y[i];x[i]; fld[y[i]][x[i]]=1-fld[y[i]][x[i]]; } vector<int>ys,xs; for(int i=0;i<K;i++){ if(y[i]>1)ys.push_back(y[i]-1); ys.push_back(y[i]); if(y[i]<N)ys.push_back(y[i]+1); } for(int i=0;i<K;i++){ if(x[i]>1)xs.push_back(x[i]-1); xs.push_back(x[i]); if(x[i]<N)xs.push_back(x[i]+1); } sort(xs.begin(),xs.end()); sort(ys.begin(),ys.end()); xs.erase(unique(xs.begin(),xs.end()),xs.end()); ys.erase(unique(ys.begin(),ys.end()),ys.end()); for(int i=0;i<N;i++){ for(int j=0;j<N;j++){ fld[i+1][j+1]+=fld[i][j+1]+fld[i+1][j]-fld[i][j]; } } int ans=0; for(int i=0;i<ys.size();i++){ for(int j=0;j<xs.size();j++){ for(int k=i;k<ys.size();k++){ for(int l=j;l<xs.size();l++){ int y1=ys[i],y2=ys[k]; int x1=xs[j],x2=xs[l]; int sum=fld[y2][x2]-fld[y2][x1-1]-fld[y1-1][x2]+fld[y1-1][x1-1]; //cout<<"("<<y1<<","<<x1<<") ("<<y2<<","<<x2<<")"<<" "<<sum<<endl; ans=max(ans,abs((y2-y1+1)*(x2-x1+1)-sum-sum)); } } } } printf("%d\n",ans); return 0; }
F問題
まず引き算はなんか怖いので、お釣りX-A円を決めてA円に足すことにしました。
そして筆算的にお釣りの各桁を順番に決めながら足していく感じの桁DPをしようと思いました。
AにX-Aを足してXにしたとき、その3つの整数の同じ桁の数字が揃うのは、「前の桁から繰り上がりをもらってきた状態で9に9を足した」か「繰り上がりがない状態で0に0を足した」ときだけです。
また足し算の筆算をするとき、今見ている桁に繰り上がりがあるかどうかだけ分かればそれより前の桁は全く関係ありません。
しかも、繰り上がりを作るときは9を足せばよいし繰り上がりを作らないときは0を足せばよいので、1~8の数字はお釣りに現れなくてもよいことになります。
そこで
dp[i][j] = お釣りのi-1桁目までを決めていて、i桁目への繰り上がりがj(jは0か1)であるとき、いくつ揃ったかの最大値
としてDPをやりました。
コード(ぼく)
const int latte[2] = {0, 9}; int dp[101][2]; int main(){ string A; cin >> A; reverse(A.begin(), A.end()); for(int i = 0; i < A.size(); i++) A[i] -= '0'; fill_n((int*)dp, 101*2, -1); for(int i = 0; i < A.size(); i++) { for(int j = 0; j < 2; j++) { if(i == 0 && j == 0) dp[i][j] = 0; if(dp[i][j] == -1) continue; for(int k = 0; k < 2; k++) { int nj = 0, next = dp[i][j], res = A[i] + latte[k] + j; if(res >= 10) nj = 1; if(A[i] == latte[k] && res % 10 == A[i]) next++; dp[i+1][nj] = max(dp[i+1][nj], next); } } } printf("%d\n", max(dp[A.size()][0], dp[A.size()][1])); return 0; }
名付けとかがひどい。
E問題がACした直後にF問題も通って、この時だけ順位がかなり良かったです(しみじみ)
G問題
問題の問題です。
しばらくG問題を2人で考えていました。
文字列をひっくり返して、まだ選んでいない文字のなかからなるべく左側の文字を使って貪欲的に"hcetit"をつくる、という貪欲法を最初にやってWAしました。
"ttitechitech"みたいな文字列だとやばいと気付いて、(ひっくり返したとき)なるべく右側にある"h"から始めて、そこからなるべく左側にある文字を使って"hcetit"をつくる、というふうに改良したのですが全く同じケースをWAしました。
この後諦めてJ問題へ行き、結局最後まで解けませんでした。
教えて下さいつよいかた。
J問題
Gを諦めてJを解きに行きました。Hは知りません。
とりあえずDPっぽいと思いました。
僕は逆元を知らないので(学ばなければ!)困ってたら、ラテプロが解いてくれました。
ラテ君の解法を全部聞いたわけじゃないので以下は解法の予測です。
まずこの問題はK人以下にグループ分けする感じで考えられます。
それはDPで頑張れば解けそうと思いました。
ただ問題は同じ人数のグループが複数できたとき(例えば2人グループが3つできたとき)で、このときそれらのグループは人数が同じなので状態が重複してしまい、その重複分を省かなければいけません。
僕はここで詰まりましたが、逆元なる魔法を使うとmodをとられた数の割り算ができるみたいです。
dp[i][j] = K人からi人までのグループを既に分けていて、残りがj人である、という状態に至るまでの組み合わせ数
多分こんな感じ?
高度なコード(らてくん)
const int mod=1e9+7; int mod_pow(int n,int m){ int ret=1; while(m){ if(m&1)ret=ret*n%mod; m>>=1; n=n*n%mod; } return ret; } int N,K; int dp[2][1001]; int fact[2000]; int rev[2000]; int table[1001][1001]; int comb[1001][1001]; signed main(){ cin>>N>>K; if(K==1){ cout<<0<<endl; return 0; } for(int i=0;i<=N;i++){ comb[i][0]=comb[i][i]=1; for(int j=1;j<i;j++){ comb[i][j]=(comb[i-1][j-1]+comb[i-1][j])%mod; } } fact[0]=1; for(int i=1;i<=1000;i++)fact[i]=fact[i-1]*i%mod; for(int i=0;i<=1000;i++)rev[i]=mod_pow(fact[i],mod-2); for(int i=2;i<=K;i++){ int a=1; table[i][0]=1; for(int j=1;j*i<=N;j++){ a=a*comb[i*j][i]%mod; table[i][j]=a*rev[j]%mod*mod_pow(fact[i-1],j)%mod; } } for(int i=1;i*K<=N;i++){ dp[(K-1)&1][i*K]=table[K][i]*comb[N][i*K]%mod; } for(int i=K-1;i>2;i--){ for(int j=0;j<=N;j++){ if(dp[i&1][j]==0)continue; for(int k=0;j+k*i<=N;k++){ dp[(i+1)&1][j+k*i]=(dp[(i+1)&1][j+k*i]+dp[i&1][j]*table[i][k]%mod*comb[N-j][i*k])%mod; } dp[i&1][j]=0; } } if(K!=2){ for(int i=0;i<=N;i++)if((N-i)%2==0){ dp[1][N]=(dp[1][N]+dp[0][i]*table[2][(N-i)/2])%mod; } } cout<<dp[1][N]<<endl; return 0; }
ラテ君がJを解いてる間に(既にあまり時間がなかった)、僕はGが思いつかなくてぷよぷよをやりながら、「Gフローで解けそうじゃない?w」とか言ってました。
Jを解き終えた戦士らてが「実はフローのライブラリあるゾ」と言って時間ギリギリにアタックしましたが、何かしらバグったのか駄目だったみたいです。
ちゃんとフロー手伝えば良かった感あります。(完全に集中力がなくなっていたので申し訳ない)
結果はA,B,C,D,E,F,Jを解いて47位でした。
ちなみに今久留米高専は特別教育機関(という名の秋休み)なので、この期間に数学をお勉強しようと思ってます。
あと多分数オリに初参加しますが、数学弱者なので数学を勉強するのが目的な感じです。
JOIもあるので競プロもこれから精進していきます。