ABC168に挑んだ回
今回はDまで突破出来てパフォーマンス890。
ついにRateも茶色に到達しました。やったね。
今回の問題のタイトルがなんだかおしゃれで素敵。
数式が書けるプラグイン入れて記事書いてる最中は数式で表示されるけど本番だと表示されなくて悲しんでる。
そのへんは心折れてしまったのでそのままです。
WordPressでKaTex記法(≒Latex記法)で入力して数式をレンダリングする 【WP Githuber MD】
C : (Colon)
愚直なので座標計算して長針・短針の間の距離を計算してました。
でも余弦定理で計算できたそうな。なるほど。
こういう計算式についてはすっぱり忘れてるので良くない。
余弦定理
$$(三角形の面積)=\frac{(底辺)\times(高さ)}{2}$$
1 |
<code>a^2 = b^2 + c^2 - 2 bc * cos \theta </code> |
時針・分針=bとc、θは2つのなす角度で求まる。
角度は時針が
。{(H/12)+(M/60/12)} *2π
、分針が
{M/60}*2π
時針-分針で求まる。
1 2 3 4 5 6 7 8 |
double dH = (h / 12.0 + m/60.0 / 12.0); double dM = m / 60.0; double radA = (dH - dM)*2*M_PI; double ans = pow(a, 2) + pow(b, 2) - 2 * a * b * cos(radA); ans = sqrt(ans); cout << fixed << setprecision(20) << ans; |
引っかかりポイント
- いつもの癖で浮動小数点の値を
12.f
とかFloat型にして死んだ(精度が下がる) - 普通にcoutすると出力桁数が足りなかったので
fixed << setprecision(20)
で出力調整が必要
愚か者の解法
本戦中は座標計算してた。まぁ間違っちゃいないよ。通ったんだもん。
座標回転の計算式
1 2 |
rotatedX = x * cos \theta - y * sin \theta \\\\ rotatedY = x * sin \theta + y * cos \theta |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 |
struct Vec2 { double x; double y; // 座標回転 void rotate(double rad) { double s = sin(rad); double c = cos(rad); double tmpX = this->x*c - this->y*s; double tmpY = this->x*s + this->y*c; this->x = tmpX; this->y = tmpY; } }; { // 長針の角度RadHと短針の角度RadM計算処理は省略 Vec2 posH = { 0,(double)a }; posH.rotate(radH); Vec2 posM = { 0,(double)b }; posM.rotate(radM); double ans = sqrt( pow(posH.x - posM.x, 2) + pow(posH.y - posM.y, 2) ); } |
D - .. (Double Dots)
BFS(幅優先探索)問題だそうな。
BFS (幅優先探索) 超入門! 〜 キューを鮮やかに使いこなす 〜
再帰で解いたけど、キューを使って解いたほうが頭良さそう。
再帰が619ms、キュー版(下)が331msだったので実行時間も優秀。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 |
// 部屋[a]につながる道リストvecを作成する unordered_map<ll, std::vector<ll>> routes; for (ll i = 0; i < m; ++i) { ll a, b; cin >> a >> b; routes[a].push_back(b); routes[b].push_back(a); } // 初期値は部屋+1→未設定値にしておく const ll ROUTE_INVALID_VALUE = n + 1; vector<ll> answers(n+1, ROUTE_INVALID_VALUE); // 探索リスト(部屋1から開始) queue<ll> queue; queue.push(1); // 探索リストの内容がある限り更新 while (!queue.empty()) { ll room = queue.front(); queue.pop(); // roomから移動可能な部屋をチェック for (ll i = 0; i < routes[room].size(); ++i) { ll nextRoom = routes[room][i]; // room につながる部屋nextRoomがINVALID→最短ルートを発見した if (answers[nextRoom] == ROUTE_INVALID_VALUE) { // 直前の部屋はroomになる answers[nextRoom] = room; queue.push(nextRoom); } } } // すべての部屋が1の部屋に戻れるか確認 bool isOK = true; // データが1始まり for (auto i = 1; i < answers.size(); ++i) { isOK &= answers[i] != ROUTE_INVALID_VALUE; } if (isOK) { cout << "Yes" << endl; // 始点はいらないので+1 for (auto i = 2; i < answers.size(); ++i) { cout << answers[i] << endl; } } else { cout << "No"; } |
引っかかりポイント
- 解答を入れてた配列が
unordered_map
で、実行環境とABC環境で出力順が違う原因に気づかず死にまくった。
E - ∙ (Bullet)
残り10分くらいだったので諦めた。
イワシの問題。解きたかったですね、閣下。
Ai+AjとBi+Bjが~なときは~みたいな問題は先にそのケースとか計算を列挙しとけ的な知見を得たけど、肝心のその問題、何だったっけなぁ…。
いつもお世話になってる解説を参考に後でお勉強する。
(ここまで書くのに1時間かかって疲れた
(Bullet) [AtCoder Beginner Contest 168 E]
コメントを残す