AtCoder Beginner Contest 467 コンテストまとめ

2026-07-19

コンテスト情報

コンテスト時間: 2026-07-18(土) 21:00 ~ 2026-07-18(土) 22:40 (100分)

\mathrm{BMI} = \frac{\text{体重}[\mathrm{kg}]}{\text{身長}[\mathrm{m}] \times \text{身長}[\mathrm{m}]}

で計算される $\mathrm{BMI}[\mathrm{kg}/\mathrm{m}^2]$ が $25$ 以上の人は日本では肥満とされる。身長 $H[\mathrm{cm}]$ 、体重 $W[\mathrm{kg}]$ の人が肥満であるかどうかを判定せよ。

$H$ は $\mathrm{cm}$ 単位で与えられるので、 $\mathrm{m}$ 単位に変換する必要がある。
したがって、以下を判定すればよい。
- $\frac{W}{\left( \tfrac{H}{100} \right)^2} \geq 25 \iff 10000 W \geq 25 H^2$

高橋君は $N$ 軒の店で買い物をした。

はじめ、高橋君は $10000$ 円持っており、 $i$ 軒目の店では $A_i$ 円の商品を買って $B_i$ 円支払った。そして、 $S_i =$ keepの時、高橋君はお釣りを受け取らず、 $S_i =$ takeの場合、お釣りを受け取った。

高橋君が全ての店でお釣りを受け取っていた場合に比べて損した金額を求めよ。

$0$ 以上 $M-1$ 以下の整数からなる整数列 $A=(A_1,A_2,\dots,A_N), \, B=(B_1,B_2,\dots,B_{N-1})$ が与えられる。

$A$ に対して以下の操作を好きな回数行う。

以下の条件を満たすようにするために必要な操作回数の最小値を求めよ。

$M = 2$ なので、 $A_i$ は $0$ か $1$ のいずれかであり、これはビット列とみなしてよい。
操作後のビット列を $x_i$ $x_{i}$ として、条件を満たすためには、 $x_{i+1} = x_i \oplus B_i$ $x_{i + 1} = x_{i} \oplus B_{i}$ が成り立てばよい。
- つまり、最初のビット $x_1$ を決めると、残りの $N-1$ 個のビットは一意に決まる。
元の $A_i$ $A_{i}$ が取り得る値は $0$ $0$ か $1$ $1$ なので、 $i$ $i$ 番目の要素に対する操作回数は、
- $A_i \neq x_i$ の場合は $1$ 回
- $A_i = x_i$ の場合は $0$ 回
$2$ 回以上余分に加えると偶奇は同じまま操作回数だけ増えるので、各要素への操作は高々 $1$ 回としてよく、最初のビット $x_1$ を $0$ とした場合と $1$ とした場合の両方を試して、操作回数の合計が少ない方を選べばよい。

$xy$ 平面上に以下の条件を全て満たす $2$ 個の円 $C_1, C_2$ は存在するか判定せよ。ただし、 $C_1, C_2$ は同一である可能性があります。

まず、平面上の2点を通る円の中心は、その2点を結ぶ線分の垂直二等分線上にあるから、線分 $\mathrm{PQ}$ の垂直二等分線と線分 $\mathrm{RS}$ の垂直二等分線が交点を持つならば、その交点を中心とする円 $C_1, C_2$ が存在する。
また、両者の垂直二等分線が交点を持たない場合でも、2つの垂直二等分線が一致するならば、条件を満たす円が存在する。
実装では、線分 $\mathrm{PQ}$ $PQ$ の方向ベクトルを $\bm{a}$ $a$ 、線分 $\mathrm{RS}$ $RS$ の方向ベクトルを $\bm{b}$ $b$ 、線分 $\mathrm{PQ}$ $PQ$ と線分 $\mathrm{RS}$ $RS$ の中点を結ぶ線分の方向ベクトルを $\bm{d}$ $d$ とすると、
- $\bm{a} \times \bm{b} \neq 0$ ならばYes
- $\bm{a} \times \bm{b} = 0 \land \bm{a} \cdot \bm{d} = 0$ ならばYes
- それ以外なら、No