なんかばぐってた
Aランク(1,2を完答+4の10%=42)という通知を見て目を疑ってしまった。本当に嬉しい。合宿いけるのか。ギリギリだけどさ。
結果が来たのでブログを書きます。
2/11(金)
一足先に東京到着。id:peryaudoの家にお邪魔する。二回目。すごい御持て成しに大変恐縮した。着くやTopCoderに共に参加したりして遊ぶ。
システムテストに時間が掛かっているらしく暇なのでメシ食い+ゲーセンで音ゲーしにいく。jubeatおもしろかった。DDRはむずかしかった。帰ってきたらレートが微増してたりする。
2/12(土)
peryaudoのお母さんに車で送ってもらって、受付より30分くらい早めに会場到着。tozangezan君とmoneto君を見つける。挨拶する。
その後みんな来る。id:qnighy君とsemiexp君がじゃれあっていた。
会場では、プラクティスショーとコーディングしたり、名刺交換したりしてtwitter上で面識のある人たちとリアルに会う。japljさんにJ言語の良さを説いてもらったりした。
懇親会ではぱない席に座ってしまった。コーラとオレンジジュースを混ぜているターゲットが居た。qnighyが懇親会を痛い雰囲気にしようと企んでいた。peryaudoは多田野数人ファンだった。
メシが終わったら談話室でダラダラしたりした。Japljさんにjubeat plusさせてもらったりしたiPadいい感じ。他にも色々教えてもらったりもした。
勢いで200円する毒々しい色のジュースを5完してしまったのはさすがに後悔しています。
2/13(日)
asi1024さん,japljさんとホテルのバイキング的な何かである朝食会場に向かったりする。みんなもぐもぐしていた。
本選始まった⇒終わった。2問でほぼ時間を使い果たしてしまい、ブルーな気持ちに。自分より前方の人々の成績は異常に良さそうで、落ちたとしか思ってませんでした。
悲しい気持ちで昼飯をもぐもぐ。ラーメン食べた。関西弁なa_kawashiroさん,peryaudo,japljと同席。a_kawashiroさんが六甲おろしを歌うとばかり言っていた印象。
解説はとても分かりやすかったです。iwiwiさんがプログラミングコンテストチャレンジブックを宣伝していました。
帰りはperyaudo,a_kawashiroさんと一緒に。peryaudoとは原宿で別れ、a_kawashiroさんとは品川で別れたりした。
さてまともに解いた2問だけソース載せます。
1 惑星ほにゃらら
二次元累積和らしい。id:tozangezanがwriterのKTCで直前にやったことがあったけど、バグ取り含めて1時間くらい掛かって駄目だった。
#include <iostream> #include <cstdio> using namespace std; #define rep(i,n) for(int i=0;i<n;i++) int dp[1001][1001][3] = {0}; int main(){ int table[256]; table['J'] = 0; table['O'] = 1; table['I'] = 2; int w,h; //ato de scanf cin >> h >> w; int n; cin >> n; for(int i=0;i<h;i++){ rep(j,w){ char c; cin >> c; for(int x=0;x<3;x++){ if(table[c] != x){ dp[i+1][j+1][x] = dp[i+1][j][x]; } else dp[i+1][j+1][x] = dp[i+1][j][x] + 1; } } } rep(x,3){ rep(j,w+1){ rep(i,h+1){ dp[i+1][j][x] += dp[i][j][x]; } } } rep(i,n){ int x1,y1,x2,y2; scanf("%d %d %d %d\n",&y1,&x1,&y2,&x2); rep(x,3){ int sum = dp[y2][x2][x] - dp[y2][x1-1][x] - dp[y1-1][x2][x] + dp[y1-1][x1-1][x]; if(x)printf(" "); printf("%d",sum); } puts(""); } }
本屋ゃらら
よくわかんないけど難しいとおもいました。僕は。
#include <iostream> #include <vector> #include <algorithm> #include <climits> #include <map> #include <cstdio> using namespace std; #define rep(i,n) for(int i=0;i<n;i++) int r(int a){ return a*(a-1); } int main(){ int dp[11][2001] = {0}; int sum = 0 , k = 0 , n; int c[11]={0}; cin >> n >> k; vector< vector<int> > data(11); rep(i,n){ int a,b; cin >> a >> b; data[b-1].push_back(a); } rep(i,10)sort(data[i].begin(),data[i].end()); rep(i,10)data[i].push_back(0); rep(i,10)reverse(data[i].begin(),data[i].end()); rep(i,10){ rep(j,data[i].size()-1){ data[i][j+1] += data[i][j]; } } rep(i,10){ for(int j=1;j<data[i].size();j++){ data[i][j] += j*(j-1); } } reverse(data.begin(),data.end()); for(int x=1;x<=10;x++){ for(int i=0;i<2001;i++){ for(int j=0;j<data[x].size() && i+j < 2001;j++){ if(dp[x-1][i] + data[x][j] > dp[x][i+j]){ dp[x][i+j] = dp[x-1][i] + data[x][j]; } } } } cout << dp[10][k] << endl; }
3 なんか最短経路
ただのdijkstraするだけだったらしいのですが、
ABを結ぶ辺上に存在するある点Cから一番遠い点 = (AC+AB+BC)/2.0の立式すら出来ずに死んだ。
dijkstra組めるだけに勿体無いと思いました。
4 よくわからない
マンハッタン距離。出現するx,y毎に中央値とればいいらしい。ぱない。
↑でいう3に相当するジャンルの問題なのかな?
5
セグメントツリーなどたくさん最適化をしないと満点とれない問題らしい。ぱない。
問3は落としちゃいけなかったなあ・・・。それはそうと、id:semiexpさん満点おめでとうございます。
