解いた問題を振り返ります。

A.In Search of an Easy Problem

問題概要

Problem - A - Codeforces

0 または 1 である n 個の文字列が与えられる。 1 つでも 1 が存在する場合は "HARD" をそうでない場合は "EASY" を出力せよ。

考え方

問題概要の指定されたとおりに実装すればいいです。

Submission #43300583 - Codeforces

B.Vasya and Cornfield

問題概要

Problem - B - Codeforces

「http://codeforces.com/predownloaded/d4/77/d4774c8e0335ef834f224f203b990e3154fc535a.png」より引用

$2$ 数, $n, d$ をもとに $(0, d), (d, 0), (n, n - d), (n - d, n)$ なる $x-y$ 平面上の $4$ 点が与えられる。その後 $m$ つの点が与えられる。点 $(x_i, y_i)$ が $4$ 点に内包されるかどうか確認せよ。内包される場合は "YES" そうでない場合は "NO" を出力する。

考え方

座標上の内包判定は直線の方程式を求めて、内包されるか判定すればよい。与えられた点から 4 つの直線の方程式を求めることができる。

$y \geq -x + d$
$y \leq -x + 2n - d$
$y \geq x - d$
$y \leq x + d$

$m$ つの点それぞれについて、この条件を満たすかどうか判定すればいい。

Submission #43365208 - Codeforces

ポイント

図形を数式で表現する

類題

C.Vasya and Golden Ticket

問題概要

Problem - C - Codeforces

長さ n の数列 a が与えられる。a を 2 つ以上のいくつかに分割して、それぞれの分割された区間の和が等しくなるようにしたい。そのような分割が存在する場合は "YES" をそうでない場合は "NO" を出力せよ。

考え方

まず数列 a が全て 0 の場合は可能であるから "YES" である。制約が小さいため分割されたときの区間の和を全探索することができる。

数列 a の和を sum としておく。区間の和 t は [1, sum-1] を全探索する。

まず sum が t で割り切れない場合はそのような分割はできないため、"NO"である。

そうでない場合は数列を順に参照していき、[i, j] が t になったタイミングで t を 0 でリセットして次の要素から調べる。同様に [j+1,k] の和も t になったタイミングで 0 にリセットする。そのようにして数列の要素を最後まで調べることができれば t で分割することが可能であることがわかるから "YES"。そうでない場合は [1, sum-1] なるいずれの t でも分割することはできないため "NO" となる。

Submission #43365918 - Codeforces

ポイント

全探索
コーナーケース(すべてが 0 の場合)に注意

雑記

すべてが 0 の場合に気づかなくて、スコアを溶かしてしまいました・・・

D.Vasya and Triangle

問題概要

Problem - D - Codeforces

$n, m, k$ が与えられる。格子点上の 3 点 $(x_1, y_1), (x_2, y_2), (x_3, y_3)$ を選択して $3$ 点で内包される三角形の面積が $\displaystyle \frac{nm}{k}$ に等しくできる場合は "YES" を出力して、そのような $3$ 点を出力せよ。そうでない場合は "NO" を出力せよ。

考え方

$1$ 点を $(0, 0)$ にとり、他の $2$ 点を $x, y$ 軸上の $(0, x), (y, 0)$ にとることにする。このときの三角形の面積は $\displaystyle \frac{xy}{2}$ である。これが $\displaystyle \frac{nm}{k}$ と一致すれば良い。

格子点上の三角形 (多角形) の面積はピックの定理より $\displaystyle \frac{1}{2}$ の倍数になる。よってまず $2nm$ が $k$ で割り切れない場合は "NO" である。

$n, m$ について $k$ との最大公約数で割り、既約分数にする。 $2nm$ は $k$ で割り切れるため、 $nm$ を $k$ との最大公約数で割って既約分数にしたとき $k$ は $1$ ( $mn$ が $k$ で割り切れる場合)または $2$ ( $mn$ が $k$ で割り切れず $k$ が $2$ の倍数になっている時)となっている。

$k$ が $1$ となっている場合 $n, m$ と $k$ のいずれかの最大公約数が $2$ 以上になっているため、割れた数について、分子分母を $2$ 倍することで $\displaystyle \frac{xy}{2}$ と合わせることができる。そのときの $n, m$ が $x, y$ となる。