AtCoder Beginner Contest 183をPythonで解く

こんにちは, Shinoryoです.

今回はAtCoder Beginner Contest 183を, Pythonで解いてみた結果を書き連ねていこうと思います.

A - ReLU

if文で条件分岐をすれば問題ないと思います.

B - Billiards

2点$(S_x, S_y)$, $(G_x, - G_y)$を通る直線と$x$軸の交点を求めることになります. 2点$(S_x, S_y)$, $(G_x, - G_y)$を通る直線の式は

です. これに$y = 0$を代入すればよく, 計算すると

となります. これを出力します.

C - Travel

Pythonで順番を並び替えたもののリストを作成するには, itertools.permutations(リスト)を利用します.

下で「index[(i+1)%n]」としている理由は, $i = n-1$のときにindex[0](つまり都市$1$のデータ)を参照できるようにするためです.

D - Water Heater

各時刻で使われているお湯の量を直接求めようとすると$O(N)$かかるため, 時刻の最大値$2 \times 10^5$を$T$として時間計算量$O(NT)$となり, TLE. そのようなコードを参考までに以下に示しておきます.

そこで, いもす法と呼ばれる方法を用います(いもす法に関しては, 下の参考にしたものを参照). 各時刻で使われているお湯の量を直接求めるのではなく, 開始時刻と終了時刻でのお湯の使用量の増減を記録し, 後にそのデータを基にシミュレーションします. 開始時刻と終了時刻の記録に$O(N)$, シミュレーションに$O(T)$なので, 計算量は$O(N+T)$となります.

E以降

E以降は私の能力不足故に省略いたします.

参考にしたもの

• 「解説 - AtCoder Beginner Contest 183」
  Editorial - AtCoder Beginner Contest 183

  AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.

• junkls様による「itertoolsによる順列, 組み合わせ, 直積のお勉強」
  itertoolsによる順列, 組み合わせ, 直積のお勉強 - Qiita

  itertoolsを使うと順列や組み合わせをスッキリ書くことができます. >>> import itertools (a, b, c, d, e)の並べ方を考えてみます. >>> seq =...

• nkmk様による「Pythonでリストの最大値・最小値から順にn個の要素を取得」
  Pythonでリストの最大値・最小値から順にn個の要素を取得 | note.nkmk.me

  Pythonでリスト（配列）の最大値・最小値から順にn個の要素を取得したい場合, n=1であれば, 組み込み関数max(), min(), n>1であれば, リストをソート（並び替え）する方法と標準ライブラリのheapqモジュールを使う方法がある. 最大値・最小値を取得: max(), min() 最大値・最小値から順にn個の要素を取得: ソート 最大値・...

• Kentaro Imajo様による「いもす法」
  いもす法