DDCC2016 参加記
この記事はTSG Advent Calendar 2016 - Adventar10日目の記事として書かれました。
前に引き続き参加記です。知見がなくてすいません。
コンテスト開始まで
青いDDCCのTシャツを得る。割と好きなデザインでよかった。隣にガチプロの方々がいて早速委縮したりする。
コンテスト
A問題を開く。サイズが小さいので全部数えればいい。第一象限の数だけ数えて4倍すると実装が楽。通す(2分）。
#include <bits/stdc++.h> #define rep(i,n) for(int i = 0; i < n; i++) using namespace std; typedef long long ll; typedef pair<ll,ll> P; typedef pair<ll,P> PP; const long long int MOD = 1000000007; const int INF = 1000000000; int r, c; int ans = 0; int main(){ cin >> r >> c; for(int i = c;; i+=c){ if(i > r) break; for(int j = c;;j+=c){ if(j > r) break; if(r*r >= i*i+j*j) ans++; } } cout << ans*4 << endl; }
B問題を開く。あ、見たことある感じのやつだと思う。とりあえず分割したときの辺の長さを求める関数を書く。意外と細々したところが面倒くさくて時間を食う。解法としては真ん中から貪欲に削っていくという方法をとった。証明してないけど正しそうだったので投げたら通った（周りの通した人も未証明の人ばっかりだった）。ここまで43分。
#include <bits/stdc++.h> #define rep(i,n) for(int i = 0; i < n; i++) #define PI 3.1415926535897932384626433832795028841971 #define INF 100000000 #define EPS 1e-10 #define MOD 1000000007 using namespace std; typedef long long ll; int r, n, m; bool c[1000]; double cut(int rr, int id){ double rrr = rr; id--; int N = n-1; if(N%2 == 0){ if(N/2 > id) id = N/2-1-id; else id = id-n/2; double y = 2*((double)id+0.5)*rrr/(double)n; return 2*sqrt(rrr*rrr-y*y); } else{ if(N/2 >= id) id = N/2-id; else id -= N/2; double y = 2*(double)id*rrr/(double)n; return 2*sqrt(rrr*rrr-y*y); } } int main(){ cin >> r >> n >> m; int nx; double va; double ans = 0.0; for(int i = 1; i < n; i++){ va = -1; for(int j = 1; j < n; j++){ if(c[j]) continue; if(va < cut(r,j)){ va = cut(r,j); nx= j; } } if(va < 0) break; ans += va; c[nx] = true; double add = -1; int ad; for(int j = nx+m; j < n; j++){ if(c[j]) continue; if(add < cut(r,j)){ add = cut(r,j); ad = j; } } for(int j = nx-m; j > 0; j--){ if(c[j]) continue; if(add < cut(r,j)){ add = cut(r,j); ad = j; } } if(add > 0){ c[ad] = true; } } printf("%.9f\n",ans); }
C問題を開く。どうやればいいのかわからずしばらくお絵かきタイム。0の連続した部分列と1の連続した部分列のペアから左右にガーっといい感じにやるとO()で解けて、左右にガーの部分は前処理できるので解けることに気が付く。しかし、無限にバグらせる。±1のずれがあったりtypoがあったりで散々なデバッグだったがギリギリ通した。114分。
#include <bits/stdc++.h> #define rep(i,n) for(int i = 0; i < n; i++) #define PI 3.1415926535897932384626433832795028841971 #define INF 5000000000000000000 #define EPS 1e-10 #define MOD 1000000007 using namespace std; typedef long long ll; typedef pair<ll,int> P; ll a, b, c; string s; ll si; ll ch[200000]; vector<P> p; int main(){ cin >> a >> b >> c; cin >> s; si = s.size(); for(int i = 1; i < s.size(); i++){ ch[i] = ch[i-1]; if(s[i-1] != s[i]){ ch[i]++; } } int st = 0; char now = '_'; rep(i,s.size()){ if(i == 0){ now = s[i]; continue; } if(now == s[i]) continue; else{ p.push_back(P(st,i-1)); st = i; now = s[i]; } } p.push_back(P(st,s.size()-1)); ll ans = INF; if(p.size() == 1){ if(s[0] == '0'){ ans = min(ans,a*si); ans = min(ans,b*si+c); } else{ ans = min(ans,b*si); ans = min(ans,a*si+c); } cout << ans << endl; return 0; } for(int i = 1; i < p.size(); i++){ ll cnt = INF; bool one = false; P x = p[i-1]; P y = p[i]; bool check = false; if(x.first == 5) check = true; ll xsi = x.second-x.first+1, ysi = y.second-y.first+1; cnt = min(cnt,a*xsi+b*ysi); cnt = min(cnt,a*(xsi+ysi)+c); cnt = min(cnt,b*(xsi+ysi)+c); if(s[x.first] == '1') one = true; if(p.size() == 2){ if(one) cnt += c; cout << cnt << endl; return 0; } cnt += c; cnt += (max(ch[x.first],ch[si-1]-ch[y.first])-1)*c; if(one == false && (max(ch[x.first],ch[si-1]-ch[y.first])-1)%2 == 0){ cnt += c; } if(one == true && (max(ch[x.first],ch[si-1]-ch[y.first])-1)%2 == 1){ cnt += c; } cnt += a*x.first+b*(si-1-y.second); if(cnt < ans) ans = cnt; } cout << ans << endl; }
一応D問題を開いて目を通す。
終わり。
コンテスト後
ビュッフェはいつもの通り寿司、肉、スパゲティなどがあった。珍しいものとしてチョコレートタワーがあり、美味しかった。reew氏はそればっか食べてた。LayCurseさんにDの解法を聞くなどした。また、E*氏、latte氏の顔を知った。
厚切りジェイソンの講演。基本的には真面目な話だったが所々ネタも入れていてトークスキルの高さを感じた。とても面白かった。
latte氏を誘ってDISCO社内見学。プールとかジムとかあってすげーなーとなっていたが、あまり技術的なものには興味を持てなかった。
表彰式。JOI界隈、流石に偉い人が話してる時ぐらいは静かにしませんか...。その後は適当にケーキやサンドイッチと食べながらペチャクチャしていた。
楽しかったけどやっぱりもっと実力をつけなきゃ話にならないなぁと思った（最近こんなのばっかり）。
