Codeforces Round #352 Div2
http://codeforces.com/contest/672
またしてもsystestでやられました……。
A : Summer Camp
1234567891011121141516171811920..........のn桁目を答えろ、と言う問題。面倒なのでint_to_string(自作、信頼性低)を貼りました。
string int_to_string(int k){ string res = ""; if(k == 0) res += '0'; while(k > 0){ char a = '0' + (k % 10); res = a + res; k /= 10; } return res; } string a; void pre(){ a = ""; for(int i = 1; ;i++){ a += int_to_string(i); if(a.size() > 1000) return; } } int main(){ int n; cin >> n; pre(); cout << a[n - 1] << endl; return 0; }
B : Different is Good
部分文字列が一致しないように書き換えるときの最小手数。実は全部違う文字にすればいいだけ。uniqueを使うと簡単です。
int main(){ cin.tie(0); ios::sync_with_stdio(false); int n; cin >> n; string s; cin >> s; if(n > 26){ cout << "-1" << endl; return 0; } sort(s.begin(), s.end()); cout << s.end() - unique(s.begin(), s.end()) << endl; return 0; }
C : Recycling Bottles
アリスとボブ、ゴミ捨て場、ゴミ(たくさん)の座標が与えられる。効率のいい回り方を求めよ、という問題。
この大きさで巡回セールスマン問題!? と思ったらゴミを拾ったらゴミ捨て場にいちいち捨てに行くというルールがあるのでした。なるべく(ゴミ捨て場までの距離 ― アリス/ボブからの距離)が大きいのを選んで合計×2から引きます。アリスとボブの片方が動かないケースを見落としていてSystest落ちしました……。毎度思うのですけど、深夜眠い状態でコーナーケースに思いを馳せるの、結構難しいです。
const double DINF = -1000000000000000000.0; double ax, ay, bx, by, tx, ty; double dist(double px, double py, double qx, double qy){ return sqrt((px - qx) * (px - qx) + (py - qy) * (py - qy)); } int main(){ scanf("%lf%lf%lf%lf%lf%lf", &ax, &ay, &bx, &by, &tx, &ty); int n; scanf("%d", &n); double sum = 0.0; double ma = DINF, mb = DINF; double ma2 = DINF, mb2 = DINF; bool same = false; rep(i, n){ double cx, cy; scanf("%lf%lf", &cx, &cy); double dis = dist(cx, cy, tx, ty); double disa = dist(cx, cy, ax, ay); double disb = dist(cx, cy, bx, by); sum += dis * 2.0; if(dis - disa > ma && dis - disb > mb){ same = true; }else if(dis - disa > ma || dis - disb > mb){ same = false; } if(dis - disa > ma){ ma2 = ma; ma = dis - disa; }else if(dis - disa > ma2){ ma2 = dis - disa; } if(dis - disb > mb){ mb2 = mb; mb = dis - disb; }else if(dis - disb > mb2){ mb2 = dis - disb; } } if(same){ double temp1, temp2; temp1 = sum - ma - max(0.0, mb2); temp2 = sum - mb - max(0.0, ma2); sum = min(temp1, temp2); }else{ if(ma < 0.0 && mb < 0.0){ sum -= max(ma, mb); }else{ sum -= max(0.0, ma); sum -= max(0.0, mb); } } printf("%.10f\n", sum); return 0; }
わりと汚くなってしまいました。
D : Robbin Hood
数列が与えられます。最大値--, 最小値++をk行ったときの最大最小の差を答えろ、という問題。ソートした棒グラフを平らにするようなイメージで、少ない方の区間については(最終的な最小値 ー 最初の値 = 増加値)の合計がkになります。大きい方も同様。最終的な最大/最小値について二分探索をそれぞれ行うと求められます。
諦めて布団に入ってから二分探索を思いついて書いたら時間が足りず。
ソートはしてもしなくてもよい(psum += max(0, mid - c[i]) のように書く)のですが、ソートしたほうが20msくらい速かったのでそちらを載せます。
int c[500000]; int main(){ int n, k; scanf("%d%d", &n, &k); ll sum = 0LL; rep(i, n){ scanf("%d", c + i); sum += (ll)c[i]; } sort(c, c + n); ll lb = (sum + n - 1) / n - 1, ub = 1LL << 32; while(ub - lb > 1){ ll mid = (ub + lb) / 2; ll psum = 0LL; for(int i = n - 1; i >= 0; --i){ psum += c[i] - mid; if(psum > k) break; } if(psum > k) lb = mid; else ub = mid; } ll memo = ub; lb = 0LL, ub = sum / n + 1; while(ub - lb > 1){ ll mid = (ub + lb) / 2; ll psum = 0LL; rep(i, n){ psum += mid - (ll)c[i]; if(psum > k) break; } if(psum > k) ub = mid; else lb = mid; } cout << memo - lb << endl; return 0; }
CodeforcesのDiv2、僕に実力でも4完くらいはできそうなのですが、眠かったり不注意だったりでなかなかうまくいきません。実力相応の問題は普通に通せるようにしたいですね。