天下一プログラマーコンテスト 2012 本戦
9月15日に KLab オフィスで行われた天下一プログラマーコンテスト 2012に参加しました。
まとめ
3位でした。やったー。
詳細
A
A問題なのでやるだけに違いない。そこそこの早さでAC。
B
B問題なので簡単に違いない、と思っていたらむずかった。
点の座標が不自然に小さいので自然に直線を全列挙した。直線に沿って累積和をとっていくとヨサゲだった。
ちょっと時間使ったが特にハマることなくAC。
C
B問題が結構頭使ったのでC問題は難しいに違いない、と思っていたら簡単だった。
単なるBFSで、連続する B の個数は 100 まで考えればいいという考察はいるけれどもわりと自明だった。
多少バグらせたりはしたが特にハマらずAC。
D
C問題が簡単だったのでD問題これもう(どんな問題が出るか)わかんねえな、と思っていたらほんとに見たことない問題が出た。おもしろかった。
どうみてもマラソン勢の wata さんとか瞬殺しそうだなあという感じで、逆にマラソンガチ苦手勢のぼくとかはどうしようもなさそうな感じだった。
しかし E が満点は激ムズそうで、部分点も頑張って実装したらボーナス点あげますぐらいの感じだったのでせっかくだから面白い問題を楽しんだほうがよいと思って E は無視して D に全力を尽くすことにした。
まず最初に N <= 18 の DP を書いて送ってみたりした。ここでバグらせて WA を積んだりしていて悲しかった。
DPで得られた厳密解を観察していると、(左下隅の点, 右下隅の点, 上真ん中の点) みたいな三角形がたくさん作られていたので、そういう三角形をたくさん作ることにした。四隅の点を O(N) で探してきて、 左下と右下を決め打ったときに三角形を最大にする3個目の点を普通に O(N) で求めるのを N/3 回繰り返すとちょうど O(N^2) でよさそうだったので書いた。
さすがにサンプル(格子状に並んでいるだけ)ではそこそこの解が得られるが、あんまり点がたくさんあるときにいい解が出せる自信がなかった(外側の点を無限に消費していくので最後のほうは小さい三角形ばっかりになりそう)。しかし送ってみたら通った。
E
読んで、実装を確実にやって確実に点を拾うならこっちで、100点を狙うなら D だなあと思った。
全体
- A よい
- B もっと早く解けてもよかった
- C そこそこ
- D 運
- E さて
各問題だけ見るともう少し改善できそうだが、全体で見るとわりと良かった。WAはそこそこ出してしまったがそもそも最後に点が更新されたときの時間がペナルティなのであまり影響はなく、ドハマリして時間を無駄に消費することもあまりなかった。順番もA->B->C->Dと順調に解いていくことができ、しかもDを通したのが終了4分前ぐらいだったので全体を通して充実感があってチョー楽しかった。
戦略的には D, E が残った際に E を忘れて D に全力を傾けようという決断がよかった。どんなコンテストでも問題間を右往左往して解けるものが解けなくなってしまうとかありがちなので、うまい選択が出来たのは強かった。もちろんこれで選択する方を間違えてしまうと悲惨だが、しかしぶっちゃけ選択を間違えるのと右往左往するのとか大して変わんない気がするし、どの問題を解くべきか判断する力はとても重要だと思うので積極的に選択していくほうがよさそう。
ソース
A
はい
#include<cstdio> typedef long long Int; int main() { Int X; scanf("%lld", &X); Int F[60]; F[0] = 0; F[1] = 1; for(int i=2; i<60; ++i) F[i] = F[i-1] + F[i-2]; int res = 0; while(X > 0) { int x = 0; while(F[x] <= X) x++; X -= F[x-1]; res++; } printf("%d\n", res); return 0; }
B
ちょっと実装頭わるい感じでよくない。実際のコンテスト中でも思いついたら即書き始めてアホなことするより、実装をある程度練ってから書いたほうが全体のコストは小さくできると思うので気をつけたい。
#include<cstdio> #include<set> using namespace std; typedef long long Int; int P[100][100]; const Int MO = 1000000007; int gcd(int m, int n) { return n ? gcd(n, m%n) : m; } int main() { int N; scanf("%d", &N); for(int i=0; i<N; ++i) { int x, y; scanf("%d%d", &x, &y); P[y][x]++; } Int sub = 0; for(int dx=1; dx<=99; ++dx) { for(int dy=-99; dy<=99; ++dy) { if(dy == 0) continue; if(gcd(dx, dy<0 ? -dy : dy) == 1) { Int C[100][100] = {}, R[100][100] = {}; for(int y=dy>0 ? 99 : 0; ; ) { if(dy > 0 && y < 0) break; if(dy < 0 && y >= 100) break; for(int x=0; x<100; ++x) { C[y][x] = P[y][x]; int ny = y+dy, nx = x+dx; if(0<=nx && nx<=99 && 0<=ny && ny<=99) { C[y][x] += C[ny][nx]; R[ny][nx] = 1; } } if(dy > 0) y--; if(dy < 0) y++; } for(int y=0; y<100; ++y) { for(int x=0; x<100; ++x) { if(!R[y][x] && C[y][x] >= 3) { sub += C[y][x]*(C[y][x]-1)*(C[y][x]-2)/6LL*(N-C[y][x]) % MO; if(sub >= MO) sub -= MO; sub += C[y][x]*(C[y][x]-1)*(C[y][x]-2)*(C[y][x]-3)/24 % MO; if(sub >= MO) sub -= MO; } } } } } } for(int y=0; y<100; ++y) { Int s = 0; for(int x=0; x<100; ++x) s += P[y][x]; if(s >= 3) { sub += s*(s-1)*(s-2)/6LL*(N-s) % MO; if(sub >= MO) sub -= MO; sub += s*(s-1)*(s-2)*(s-3)/24LL % MO; if(sub >= MO) sub -= MO; } } for(int x=0; x<100; ++x) { Int s = 0; for(int y=0; y<100; ++y) s += P[y][x]; if(s >= 3) { sub += s*(s-1)*(s-2)/6LL*(N-s) % MO; if(sub >= MO) sub -= MO; sub += s*(s-1)*(s-2)*(s-3)/24LL % MO; if(sub >= MO) sub -= MO; } } Int all = (Int)N*(N-1)*(N-2)*(N-3)/24 % MO; all -= sub; if(all < 0) all += MO; printf("%lld\n", all); return 0; }
C
WA はあったものの細かい条件のミスとかがなかったのは良かった
#include<cstdio> #include<algorithm> #include<queue> using namespace std; int N, A[32], B[32], C[32]; int dp[31][101][101][101]; struct st { int id, ehp, shp, cb; st(int a, int b, int c, int d) : id(a), ehp(b), shp(c), cb(d) { if(cb > 100) cb = 100; } }; const int INF = 1001001001; inline void checkmin(int& a, int b) { if(a>b) a=b; } inline void check(queue<st>& q, st x, int f) { if(dp[x.id][x.ehp][x.shp][x.cb] > f) { dp[x.id][x.ehp][x.shp][x.cb] = f; q.push(x); } } int main() { scanf("%d", &N); for(int i=0; i<N; ++i) scanf("%d%d%d", &A[i], &B[i], &C[i]); A[N] = 0; for(int i=0; i<=N; ++i) for(int j=0; j<=100; ++j) for(int k=0; k<=100; ++k) for(int x=0; x<=100; ++x) dp[i][j][k][x] = INF; dp[0][A[0]][100][0] = 0; queue<st> q; q.push(st(0, A[0], 100, 0)); while(!q.empty()) { st s = q.front(); q.pop(); if(s.id == N) { printf("%d\n", dp[s.id][s.ehp][s.shp][s.cb]); return 0; } int damaged = s.shp - B[s.id]; if(damaged <= 0) continue; int f = dp[s.id][s.ehp][s.shp][s.cb] + 1; if(s.ehp <= 5) { check(q, st(s.id + 1, A[s.id + 1], damaged, 0), f); } else { check(q, st(s.id, min(A[s.id], s.ehp - 5 + C[s.id]), damaged, 0), f); } check(q, st(s.id, min(A[s.id], s.ehp + C[s.id]), min(100, damaged+50), 0), f); int k = s.cb + 1; if(s.ehp <= k) { check(q, st(s.id + 1, A[s.id + 1], damaged, s.cb + 1), f); } else { check(q, st(s.id, min(A[s.id], s.ehp - k + C[s.id]), damaged, s.cb + 1), f); } } puts("-1"); return 0; }
D
終了5分前ぐらいに超焦って書いてたのでひどい。
#include<cstdio> #include<algorithm> #include<cstdlib> using namespace std; typedef long long Int; int x[3030], y[3030], oid[3030]; Int dp[1<<18]; int prev[1<<18], used[3030]; int N; int search_left(int a, int b, Int& M) { Int mx = -1; int mxc = -1; if(a == b) { M = -1; return -1; } for(int i=0; i<N; ++i) { if(a==i || b==i || used[i]) continue; Int x1 = x[a]-x[i], y1 = y[a]-y[i]; Int x2 = x[b]-x[i], y2 = y[b]-y[i]; Int A = x1*y2 - x2*y1; if(A < 0) A *= -1; if(mx < A) { mx = A; mxc = i; } } M = mx; return mxc; } int main() { scanf("%d", &N); for(int i=0; i<N; ++i) scanf("%d%d", &x[i], &y[i]); if(N <= 18) { dp[0] = 0; Int area[18][18][18]; for(int i=0; i<N; ++i) { for(int j=i+1; j<N; ++j) { for(int k=j+1; k<N; ++k) { Int x1 = x[j]-x[i], x2 = x[k]-x[i]; Int y1 = y[j]-y[i], y2 = y[k]-y[i]; area[i][j][k] = x1*y2 - x2*y1; if(area[i][j][k] < 0) area[i][j][k] *= -1; } } } for(int i=1; i<(1<<N); ++i) { int pc = 0; for(int j=0; j<N; ++j) if(i & (1<<j)) pc++; if(pc % 3 == 0) { int ps[18], k = 0; dp[i] = -1; for(int j=0; j<N; ++j) if(i & (1<<j)) ps[k++] = j; for(int p=0; p<k; ++p) { for(int q=p+1; q<k; ++q) { for(int r=q+1; r<k; ++r) { int sel = (1<<ps[p])|(1<<ps[q])|(1<<ps[r]); Int A = area[ps[p]][ps[q]][ps[r]] + dp[i ^ sel]; if(dp[i] < A) { dp[i] = A; prev[i] = sel; } } } } } } for(int i=(1<<N)-1, t=0; t<N/3; t++, i^=prev[i]) { for(int j=0, k=0; j<N; ++j) if(prev[i] & (1<<j)) printf("%d%c", j, ++k == 3 ? '\n' : ' '); } } else { for(int i=0; i<N/3; ++i) { int tl, tr, bl, br; for(int j=0; j<N; ++j) { if(!used[j]) { tl = tr = bl = br = j; break; } } for(int j=0; j<N; ++j) { if(!used[j]) { if(y[tl] - x[tl] < y[j] - x[j]) tl = j; if(y[tr] + x[tr] < y[j] + x[j]) tr = j; if(-y[bl] - x[bl] < -y[j] - x[j]) bl = j; if(-y[br] + x[br] < -y[j] + x[j]) br = j; } } Int M[4] = {0}; int C[4]; C[0] = search_left(tl, tr, M[0]); C[1] = search_left(tr, br, M[1]); C[2] = search_left(br, bl, M[2]); C[3] = search_left(bl, tl, M[3]); Int mx = -1; int mxc = -1; for(int j=0; j<4; ++j) { if(mx < M[j]) { mx = M[j]; mxc = j; } } if(mx >= 0) { if(mxc == 0) printf("%d %d %d\n", tl, tr, C[0]), used[tl] = used[tr] = used[C[0]] = 1; if(mxc == 1) printf("%d %d %d\n", br, tr, C[1]), used[br] = used[tr] = used[C[1]] = 1; if(mxc == 2) printf("%d %d %d\n", br, bl, C[2]), used[br] = used[bl] = used[C[2]] = 1; if(mxc == 3) printf("%d %d %d\n", tl, bl, C[3]), used[tl] = used[bl] = used[C[3]] = 1; } else { int found = 0; for(int j=0; j<N; ++j) { if(!used[j]) { printf("%d%c", j, found==2 ? '\n' : ' '); found++; used[j] = 1; } } } } } return 0; }
JOI 2011-2012 予選第二問も解いた
Shakespeare で。
第一問は 5 個の整数が入力だったので微妙だと思って、N 個の入力が必要になるような問題を解いた。問題は こんなやつ。
第一問に比べて詰めて書いたはずなのに長さが3倍ぐらいになってしまった。
solve joi 2011-2012 yo-t2.
Achilles, the number of teams.
Banquo, counts the number.
Claudio, first team.
Dionyza, second team.
Emilia, score of first team.
Fenton, score of second team.
Gertrude, stores points.
Hecate, stores points reversed.
Isabella, the number of matches.
John of Gaunt, points the first team will earn.
John of Lancaster, points the second team will earn.
Lady Macbeth, modified point.
Malcolm, counts the number.
Octavia, with the last result.
Pantino, remembers the point.
Shallow, have the rank.
The Abbot of Westminster, copy.
Romeo, talks with others.
Juliet, a Romeo's lover.
Desdemona, feeds lines to others.
Helen, returns with a carriage.
Act I: First Process.
Scene I: The Introductions.
[Enter Romeo and Desdemona]
Romeo:
Thou art as fine as the sum of a pretty flower and a lovely
smooth rich plum.
[Exit Desdemona]
[Enter Helen]
Romeo:
Thou art as fine as the sum of Desdemona and the sum of a red
rose and a flower.
[Exit Helen]
[Enter Achilles]
Romeo:
Listen to your heart.
[Exit Achilles]
[Enter Isabella]
Romeo:
Thou art as gentle as the quotient between the product of
Achilles and the difference between Achilles and a father and
a amazing brother.
[Exit Isabella]
[Enter Banquo]
Romeo:
Thou art as embroidered as Achilles.
Scene II: The Initializations.
[Exeunt]
[Enter Juliet and Gertrude]
Gertrude:
Thou art nothing!
Juliet:
Remember me.
[Exit Gertrude]
[Enter Banquo]
Juliet:
Thou art as honest as the difference between thyself and a
moon. Are thou worse than a lamp?
Banquo:
If not, let us return to scene II.
Scene III: The Termination of Act I.
[Exeunt]
[Enter Romeo and Banquo]
Romeo:
Thou art as mighty as Isabella.
Act II: Process Matches.
Scene I: Input a Match and Process.
[Exeunt]
[Enter Romeo and Malcolm]
Romeo:
Thou art as reddest as Achilles.
[Exit Malcolm]
[Enter Claudio]
Romeo:
Listen to your heart.
[Exit Claudio]
[Enter Emilia]
Romeo:
Listen to your heart.
[Exit Emilia]
[Enter Dionyza]
Romeo:
Listen to your heart.
[Exit Dionyza]
[Enter Fenton]
Romeo:
Listen to your heart.
[Exit Romeo]
[Enter Dionyza]
Dionyza:
Am I better than you?
Fenton:
If so, let us proceed to scene II.
Am I better than you?
Dionyza:
If so, let us proceed to scene III.
[Exeunt]
[Enter John of Gaunt and John of Lancaster]
John of Gaunt:
Thou art as noble as a sky!
John of Lancaster:
Thou art as peaceful as the town!
We must proceed to scene IV.
Scene II: Dionyza beats Fenton.
[Exeunt]
[Enter John of Gaunt and John of Lancaster]
John of Gaunt:
Thou art as good as zero.
John of Lancaster:
Thou art as honest as the sum of a mistletoe and a proud town.
We must proceed to scene IV.
Scene III: Fenton beats Dionyza.
[Exeunt]
[Enter John of Gaunt and John of Lancaster]
John of Gaunt:
Thou art as trustworthy as the sum of a warm summer's day and
a stone wall.
John of Lancaster:
Thou art nothing.
Scene IV: Update Points.
[Exeunt]
[Enter Gertrude and Lady Macbeth]
Lady Macbeth:
Recall your imminent death!
Gertrude:
Thou art as disgusting as me.
[Exit Gertrude]
[Enter Malcolm]
Lady Macbeth:
Are you as pretty as Claudio?
Malcolm:
If so, let us proceed to scene V.
Lady Macbeth:
Are you as smooth as Emilia?
Malcolm:
If so, let us proceed to scene VI.
We must proceed to scene VII.
Scene V: Claudio Get Points.
[Exeunt]
[Enter Lady Macbeth and John of Gaunt]
John of Gaunt:
Thou art as healthy as the sum of thyself and me. We must
proceed to scene VII.
Scene VI: Emilia Get Points.
[Exeunt]
[Enter Lady Macbeth and John of Lancaster]
John of Lancaster:
Thou art as lovely as the sum of thyself and me.
Scene VII: Hecate Get Modified Points.
[Exeunt]
[Enter Lady Macbeth and Hecate]
Lady Macbeth:
Remember me.
[Exit Lady Macbeth]
[Enter Malcolm]
Hecate:
Thou art as cursed as the difference between thyself and a
thing. Are thou worse than a wind?
Malcolm:
If not, let us return to scene IV.
Hecate:
Thou art as noble as Achilles.
Scene VIII: Reverse Hecate.
[Exeunt]
[Enter Hecate and Lady Macbeth]
Lady Macbeth:
Recall what you said.
Hecate:
Thou art as mighty as me!
[Exit Hecate]
[Enter Gertrude]
Lady Macbeth:
Remember me.
[Exit Lady Macbeth]
[Enter Malcolm]
Gertrude:
Thou art as handsome as the difference between thyself and an
uncle. Are thou worse than a son?
Malcolm:
If not, let us return to scene VIII.
[Exit Gertrude]
[Enter Banquo]
Malcolm:
Thou art as foul as the difference between thyself and a
niece. Are thou worse than a sister?
Banquo:
If not, let us return to scene I.
Act III: Calculate Ranks.
Scene I: Prepares.
[Exeunt]
[Enter Romeo and Banquo]
Romeo:
Thou art as loving as Achilles.
Scene II: Push Points to Hecate.
[Exeunt]
[Enter Gertrude and Hecate]
Hecate:
Recall the point!
Gertrude:
Remember me.
[Exit Hecate]
[Enter Banquo]
Gertrude:
Thou art as mighty as the difference between thyself and a
nose. Are thou worse than a nephew?
Banquo:
If not, let us return to scene II.
Gertrude:
Thou art as loving as Achilles.
Scene III: Copy The Points.
[Exeunt]
[Enter Gertrude and Hecate]
Gertrude:
Recall what I said!
Hecate:
Remember me.
[Exit Gertrude]
[Enter The Abbot of Westminster]
Hecate:
Remember me.
[Exit Hecate]
[Enter Banquo]
The Abbot of Westminster:
Thou art as amazing as the difference between thyself and a
mother. Are thou worse than a niece?
Banquo:
If not, let us return to scene III.
The Abbot of Westminster:
Thou art as blossoming as Achilles.
Scene IV: Actual Computation.
[Exeunt]
[Enter Gertrude and Shallow]
Gertrude:
Thou art as rich as a squirrel.
Shallow:
Recall the point you have.
[Exit Shallow]
[Enter Pantino]
Gertrude:
Thou art as proud as me.
[Exit Pantino]
[Enter Malcolm]
Gertrude:
Thou art as reddest as Achilles.
Scene V: Calculation.
[Exeunt]
[Enter Shallow and The Abbot of Westminster]
Shallow:
Recall the point I will fight.
The Abbot of Westminster:
Am I better than Pantino?
Shallow:
If not, let us proceed to Scene VI.
The Abbot of Westminster:
Thou art as embroidered as the sum of thyself and a purse.
Scene VI: Next Team.
[Exeunt]
[Enter The Abbot of Westminster and Hecate]
The Abbot of Westminster:
Remember me.
[Exit Hecate]
[Enter Malcolm]
The Abbot of Westminster:
Thou art as clearest as the difference between thyself and a
lantern. Are thou worse than a horse?
Malcolm:
If not, let us return to scene V.
The Abbot of Westminster:
Thou art as bold as Achilles.
Scene VII: Restore.
[Exeunt]
[Enter Hecate and The Abbot of Westminster]
The Abbot of Westminster:
Recall what I gave you.
Hecate:
Remember me.
[Exit The Abbot of Westminster]
[Enter Malcolm]
Hecate:
Thou art as cunning as the difference between thyself and a
hamster. Are thou worse than a moon?
Malcolm:
If not, let us return to scene VII.
Scene VIII: Store The Rank.
[Exeunt]
[Enter Shallow and Octavia]
Shallow:
Remember me.
[Exit Shallow]
[Enter Banquo]
Octavia:
Thou art as cute as the difference between thyself and a
morning. Are thou worse than a hair?
Banquo:
If not, let us return to scene IV.
Act IV: Output The Result.
Scene I: Prepare for Output.
[Exeunt]
[Enter Octavia and Banquo]
Octavia:
Thou art as fair as Achilles.
Scene II: Actual Output.
[Exeunt]
[Enter Octavia and Romeo]
Romeo:
Recall the rank! Open your heart!
[Exit Octavia]
[Enter Helen]
Romeo:
Speak your mind!
[Exit Helen]
[Enter Desdemona]
Romeo:
Speak your mind!
[Exit Desdemona]
[Enter Banquo]
Romeo:
Thou art as fine as the difference between thyself and a
fellow. Are thou worse than a door?
Banquo:
If not, let us return to scene II.
JOI 2011-2012 予選第一問を解いた
Shakespeare で。
solve JOI 2011-2012 yo-t1.
Paris, just counts the number.
Benvolio, reads first three lines.
Romeo, with the most inexpensive pasta.
Capulet, reads last two lines.
Juliet, with the most inexpensive juice.
Montague, stores total price of the set.
Desdemona, feeds lines to others.
Helen, returns with a carriage.
Act I: A menu is presented.
Scene I: The introductions.
[Enter Romeo and Desdemona]
Romeo:
Thou art as fine as the sum of a pretty flower and a lovely
smooth rich plum.
[Exit Desdemona]
[Enter Helen]
Romeo:
Thou art as fine as the sum of Desdemona and the sum of a red
rose and a flower.
[Exit Helen]
[Enter Juliet]
Juliet:
Thou art as fine as the cube of a lovely beautiful charming
rich summer's day.
Romeo:
Thou art as charming as the cube of a lovely pretty smooth
white flower.
[Exit Juliet]
[Enter Paris]
Romeo:
Thou art as good as the sum of a lovely rose and a flower.
Scene II: The three pastas.
[Exeunt]
[Enter Romeo and Benvolio]
Romeo:
Listen to your heart.
Benvolio:
Am I worse than you?
If so, you are as fine as I.
[Exit Benvolio]
[Enter Paris]
Romeo:
Thou art as good as the difference between thyself and a
brother. Are you worse than a cat?
Paris:
If not, let us return to scene II.
Scene III: Preparing for the juice.
[Exeunt]
[Enter Juliet and Paris]
Juliet:
Thou art as fine as a white flower.
Scene IV: The juice.
[Exeunt]
[Enter Juliet and Capulet]
Juliet:
Listen to your heart.
Capulet:
Am I worse than you?
If so, you are as charming as I.
[Exit Capulet]
[Enter Paris]
Juliet:
Thou art as fine as the difference between thyself and a
rose. Are you worse than a tree?
Paris:
If not, let us return to scene IV.
Act II: Order the set.
Scene I: Calculating the price.
[Exeunt]
[Enter Romeo and Paris]
Romeo:
Thou art as good as a little tiny furry white animal.
Thou art as fine as the sum of thyself and a delicious
flower. Thou art as fine as the sum of a lovely smooth
rich furry red plum and thyself.
[Exit Paris]
[Enter Montague]
Romeo:
Thou art as good as I.
[Exit Romeo]
[Enter Juliet]
Juliet:
Thou art as fine as the sum of I and thyself.
[Exeunt]
Scene II: Print the price.
[Enter Paris and Montague]
Paris:
Thou art as foul as the difference between thyself and I.
Open your heart!
[Exit Montague]
[Enter Helen]
Paris:
Speak your mind!
[Exit Helen]
[Enter Desdemona]
Paris:
Speak your mind!
[Exeunt]
8月まとめ
前(～20日)
ろ～ど～
中(21日)
二の腕をできるかぎりぷるぷるさせるのがコツ
手の形は両隣の人の頭を撫でるイメージで
二人で。思いの限り頭を上下に動かそう
後(～31日)
情報オリンピックの夏季セミナーでちゅーたーをやったよ
選手時代に夏季セミナーに参加したことはないよ
遺伝的プログラミングの本を担当していたよ
