AtCoder Beginner Contest 183 備忘録

AtCoder Beginner Contest 183 の備忘録です。

問題はこちら↓

AtCoder Beginner Contest 183 - AtCoder

今回はABCD4完でした。

・A問題:ReLU

ReLU関数を次のように定義する。
・ReLU(x) = {x (x >= 0) , 0 (x < 0)
整数 x が与えられるので ReLU(x) を求める。
ReLU関数の定義から x が 0 以上であれば x 、0 未満であれば 0 となるので、max( x , 0 ) を出力すれば良い。

解答例(Python)
https://atcoder.jp/contests/abc183/submissions/18154515

・B問題:Billiards

2次元平面でビリヤードをしている。 x 軸は壁になっており、球をぶつけると入射角と反射角が等しくなるように球が跳ね返される。
今球が ( Sx,Sy ) にある。ある座標を狙って球を撞くと、球はその座標へ向かって直線的に転がる。x 軸でちょうど1回反射させたのち、( Gx,Gy ) を通過させるためには x 軸のどこを狙えば良いか求める。
狙う座標を ( Rx,0 ) とした時、三角形 ( Sx,Sy ),( Sx,0 ),(Rx,0) と ( Gx,Gy ),( Gx,0 ),( Rx,0 ) は合同な三角形となるので、Sy と Gy の長さの比を求めて Gx - Sx の長さから Sx から Rx の長さを求めて、Sx に加えた値が答えとなる。

解答例(Python)
https://atcoder.jp/contests/abc183/submissions/18154419

・C問題:Travel

N 個の都市があり、都市 i から都市 j に移動するのに Tij の時間がかかる。
都市1を出発し、全ての都市をちょうど1度ずつ訪れてから都市1に戻るような経路のうち、移動時間の合計がちょうど K になるようなものがいくつあるか求める。
N≦8 なので、順列を用いて全ての経路を試しても十分に間に合う(O(N!))。Pythonでは itertools.permutations を使う事で簡単に順列を列挙する事ができる。開始地点は1で固定なので2~8順列を全列挙し、1から順に移動時間をシミュレーションしていき、都市1へ戻った時の時間が K と同じなら答えに1加えて次の順列を同様に処理していく。最終的な ans を出力すればよい。

解答例(Python)
https://atcoder.jp/contests/abc183/submissions/18154049

・D問題:Water Heater

給湯器が1つあり、毎分 W リットルのお湯を供給できる。N 人の人がおり、i 番目の人は時刻 Si から Ti までの間(時刻 Ti ちょうどを除く)、この湯沸かし器で沸かしたお湯を毎分 Pi リットル使おうとしている。お湯は溜めておく事が出来ない。全ての人に計画通りにお湯を供給できるかを求める。
愚直にシミュレーションしようとすると N≦2*10^5 と 0≦Si<Ti≦2*10^5 の為、最大で O(10^10) 程度になる可能性もあり、間に合わない。そこでお湯を使い始めるタイミングと使い終わるタイミングだけに使うお湯の増減量を記録する配列を用意し、その配列を元に累積和と取ってやるとある時間 Ui で使用するお湯の量が分かるので、それが W を超えないかをチェックする事で求める事ができる。

解答例(Python)
https://atcoder.jp/contests/abc183/submissions/18153522