ma24mag0のブログ

朝起きれん

暑くなってきたので扇風機つけてます。

2024/4/13
- 競プロ典型90問
  - 018 - Statue of Chokudai（★3）
- AtCoder Beginner Contest 349
  - E - Weighted Tic-Tac-Toe
2024/4/14
- ランニング

2024/4/13

競プロ典型90問

今日も競プロ典型90問を解いた。

018 - Statue of Chokudai（★3）

問題

平面 $x=0$ 上に高さ $L$ の $T$ 分で一周する円形の観覧車がある。以下のように一定の速さで動く。

$0$ 分後に座標 $(0,0,0)$ にある
$\frac{T}{4}$ 分後に座標 $(0,-\frac{L}{2},\frac{L}{2})$ にある
$\frac{T}{2}$ 分後に座標 $(0,0,L)$ にある
$\frac{3T}{4}$ 分後に座標 $(0,\frac{L}{2},\frac{L}{2})$ にある

像は座標 $(X,Y,0)$ にある。以下のような $Q$ 個の質問が与えられる。

$E_i$ 分後の像への俯角を求めよ。

制約

$1\le Q\le 1000$
$90$ 度までの度数法で出力
相対誤差または絶対誤差が $10^{-7}$ 以下となる

方針

三角関数を使って座標や角度を求める。

double t, l, x, y; cin >> t >> l >> x >> y;
double pi = acos(-1);
int q; cin >> q;
while (q--){
  double e; cin >> e;
  double a = 2 * pi * (e / t);
  double Y = -l / 2 * sin(a), Z = l / 2 *(1 - cos(a));
  cout << fixed << setprecision(10) << atan2(Z, hypot(x, y - Y)) / pi * 180 << endl;
}

ポイント

C++ではatan2という関数があり、2辺の長さ $x,y$ を引数としてラジアン単位の角度 $\theta$ を求めることができる。

cpprefjp.github.io

また、hypotという関数では平方和の平方根を求めることができる。hypotはhypotenuse((直角三角形)の斜辺)の略らしい。

cpprefjp.github.io

三角関数を使う問題をほとんど解いたことがなく、幾何が得意でないので難しかった。解説やほかの人の提出コードを見てなんとか分かった。

AtCoder Beginner Contest 349

E - Weighted Tic-Tac-Toe

問題

$3×3$ の白いマス目があり、マス $(i,j)$ は $A_{i,j}$ である。先攻、後攻が以下の操作を交互に行う。

プレイヤーは白マス $(i,j)$ を選び得点 $A_{i,j}$ を得る。先攻はマス $(i,j)$ を赤に後攻は青に塗る。

各操作後判定を行う。

赤（青）マスが縦・横・斜めのいずれかの方向に3連続するなら先攻（後攻）が勝利する。
白マスがなければ得点の合計が高い方が勝利する。

両者が勝利のために最適に行動するときどちらが勝つか判定せよ。

制約

$|A_{i,j}|\le 10^{9}$
$\sum_{i=1}^{3}\sum_{j=1}^{3}A_{i,j}$ は奇数

方針

DFS。メモ化。

ポイント

特にない。問題の理解はすぐにできたが、実装が重くて解けなかった。

2024/4/14

ランニング

10:42開始。西武池袋線沿いを通り練馬駅を経由して新江古田駅で折り返し。久々に運動して疲れた。大通りを通って行ったので信号で止まることが多かった。いい感じのルートを探しておきたい。

距離: $11.74km$
時間: $1:17:56$
ペース: $6m38s/km$
平均心拍: $162bpm$