はじめに
久々にリアルタイムで参加しました。（ただし15分くらい遅刻した）
- 使用言語はC++
- REPマクロを使っています
#define REP(i, n) for(int i = 0; i < n; i++)
結果
- Ratingが2級->1級になった気がする（久々だったから忘れた）
A - 高橋くん
- 時計回りと反時計回りどちらが早いか調べる問題
- ベルトコンベアと高橋くんどちらが早いか意識しないと誤答するかもしれない
- coutだと桁数が足りないのでprintfを使う。誤差がある問題はprintfを意識すること
int main(int argc, const char * argv[]){ int l, x, y, s, d; cin >> l >> x >> y >> s >> d; // 時計回りに進む場合 double len1 = (d - s + l) % l; double time1 = len1 / (x + y); if(x < y) { // 反時計回りに進む場合 double len2 = (s - d + l) % l; double time2 = len2 / (y - x); time1 = min(time1, time2); } printf("%.8f\n", time1); }
B - ムーアの法則
- x軸に年、y軸に総時間をプロットすると下に凸のグラフになるので、範囲を3分割して最小値を求める手法を使う。（手法の名前忘れた）
- REPの中の数字が大きくなるほど誤差が小さくなるが、適当に手元で回してみて十分速い1000にした。本当はちゃんと誤差から逆算できるといい。
// p年かかる計算をx年目に始めたら合計何年かかるか
double calctime(double p, double x) {
return x + p / pow(2, x / 1.5);
}
int main(int argc, const char * argv[]){
long double p;
cin >> p;
long double pmin = 0.0, pmax = p;
REP(i, 1000) {
// pX 年目に計算を始めると vX 年目に計算が終わる
long double p0 = pmin;
long double p1 = (pmin * 2 + pmax * 1) / 3.0;
long double p2 = (pmin * 1 + pmax * 2) / 3.0;
long double p3 = pmax;
long double v0 = calctime(p, p0);
long double v1 = calctime(p, p1);
long double v2 = calctime(p, p2);
long double v3 = calctime(p, p3);
// 凸の部分がどこにあるかで探索の範囲を絞る
if(v1 < v2) {
pmax = p2;
} else {
pmin = p1;
}
}
printf("%.10f\n", calctime(p, (pmax + pmin) / 2));
}
復習はまたこんど
- B問題の手法の名前と解説
- C問題の回答
