AtCoder Beginner Contest 181 備忘録

AtCoder Beginner Contest 181 の備忘録です。

問題はこちら↓

AtCoder Beginner Contest 181 - AtCoder

今回はABCD4完でした。

A問題:Heavy Rotation

白い服を着た次の日は黒い服を、黒い服を着た次の日は白い服を着る。
今白い服を着ている時、N 日後には何色の服を着ているか求める。
白い服と黒い服を交互に着るので、1日後は黒、2日後は白となり、これは N ％ 2 が0ならば白、1ならば黒を着るということになる。

解答例(Python)
https://atcoder.jp/contests/abc181/submissions/17820382

B問題:Trapezoid Sum

何も書かれていない黒板に N 回の操作を行い黒板に整数を書いていく。
i 回目の操作では、Ai から Bi までの整数 Bi - Ai + 1 個の整数を書く。
N 回の操作を終えた時に黒板に書かれている整数の合計を求める。
制約から愚直に全てを列挙して足し合わせていては間に合わない為、一度の操作で黒板に書かれる整数を素早く求める必要がある。Ai から Bi までの全ての整数を書くので、その合計は (Ai + Bi)*(Bi - Ai + 1)/2 で求めることができる。これにより一度の操作で書かれる整数の合計を O(1) で求めることが出来るので、これを全て足すことで求めることができる。

解答例(Python)
https://atcoder.jp/contests/abc181/submissions/17820644

C問題:Collinearity

無限に広い2次元平面状に N 個の点があり、i 番目の点は ( xi , yi ) にある。これらの点のうち異なる3点で同一直線上にあるものが存在するか求める。
異なる2点間を結ぶ直線の傾きと切片を調べ、もう一つの点がその直線上にあるか調べばよい。
傾きを求めるには xi < xj として、

傾き : ( yj - yi) / ( xj - xj )
切片 : ( xj * yi - xi * yj ) / ( xj - xi )

で求めることが出来るので、 i , j と j , k の2直線が同じ傾きと切片を持つか調べれば良い。ただし、この時に xi == xj など2点間の x 座標同士、y 座標同士が同じ点があると0除算エラーが出るので弾く必要がある。また xi==xj==xk など3点間の x 座標同士、y  座標同士が同じ時は直線上にあることが明確なので、傾き等調べることなく分かる。

解答例(Python)
https://atcoder.jp/contests/abc181/submissions/17822860

D問題:Hachi

'1'~'9'の数字のみからなる数字列 S が与えられる。この数字列 S を並べ替えて 8 の倍数を作ることができるか求める。
制約から S の長さが 2*10^5 なので全てを試すことはできないので、数字列を並べ替えるのではなく8の倍数を列挙していくことにする。こちらも全て列挙してしまうと間に合わないので、特定の範囲だけを列挙することにすると、0~1000まで列挙することで下3桁が1周することが分かる。これよりも上の桁の値が幾つであっても下3桁が一致すれば8の倍数であると言えるので、数字列 S からこの3桁を作ることが出来るかを調べることで答えを求めることができる。

解答例(Python)
https://atcoder.jp/contests/abc181/submissions/17823583