Python で解く AtCoder ABC127

2019年5月25日に行われたAtCoder Beginner Contest 127 のPython3での実装例です。

A - Ferris Wheel

使用テクニック： if-elif-else

高橋君の年齢 A が13以上、6以上12以下、5以下で場合分け

B - Algae

使用テクニック： for-loop

for 文で10回 を更新して print

C - Prison

使用テクニック： 一次元いもす法

一次元いもす法で 番目のゲートを開くことができる IDカードの範囲を指定し、最後に累積和を取ることで、 個すべてのゲートを開くことができる IDカードの数を数えます。

想定解： min-max

公式の解説PDFによると、いもす法を用いた実装は想定解ではないようです。想定解は、leftの最大値とright の最小値の差で答えを求めています。差分が負になるコーナーケースに注意が必要です。

提出 #5664356 - AtCoder Beginner Contest 127

D - Integer Cards

解法 1

使用テクニック： Priority queue

書き換える数字が の時、手持ちのカードの最小値が よりも小さい時に数字を書き換えるとカードに書かれた整数の合計を最大化できます。

最小値を取り出すときには Priority queue (heapq) を使うと便利です。しかし、入力の順序そのままにカードの書き換えを行うと同じカードを何度も書き換えることになり、計算量が増え TLE になります。そこで、 の大きいものから書き換えを行うことで無駄を省くことができ、時間内に計算が終了します。

解法 2

使用テクニック： 条件を指定した sort

初めのカードセット と、 枚の からなる書き換え可能な数字のセットを混ぜたカード全体のセットを考えます。この全体セットから数字の大きい 枚を選択したものが最適なカードセットになります。

そのまま愚直に実装すると全体セット要素の数が非常に大きいため TLE になってしまいます。書き換える数字で必要な枚数は、 全てのカードを書き換える場合でも 枚あれば十分です。そこで、 書き換える数字を tuple として扱い、 の大きいものから 枚をはじめのカードセット に追加します。そして要素数が となった を sortして、上位 枚が求めるべきカードセットとなります。

E - Cell Distance

使用テクニック： 組合せ(Combination, )、フェルマーの小定理

行 列のマス目に 個の駒を置き、全ての配置パターンにおいて、全ての駒間のマンハッタン距離を求める問題です。

まず、2つのマスを選び、この2つのマスに駒が設置される配置パターンが何個あるかを考えます。
2つのマスに固定で駒が置かれているので残りの駒は 個です。また、2つのマスが常に使われているので、残りの空いたマス目は 個です。よって、選択した2つのマスに駒が置かれているパターン数は となります。以上より、この選択した2マスの答えへの寄与は、この2マスのマンハッタン距離の 倍となります。

あとは、全ての2マスの組合せにおいて同様の操作を行えば答えを求めることができますが、愚直に全ての組合せを列挙しようとすると TLE になります。そこで計算量を落とす工夫をします。

まず、マンハッタン距離を求める際には行方向と列方向を独立して扱うことができます。
例えば、列方向だけの1次元上で2点 を選んだとします。実際には2次元のマスであるため、1次元上で となる二次元上の点は の 個存在します。 点 も同様です。
さらに、 間の距離を とすると、距離 となる の組合せの数は 個存在します。

以上より、列方向の距離が となる駒の配置の総数は 個となります。あとは、 の全ての 距離 の寄与を積算します。行方向に対しても同じ計算を行えば答えとなります。

F - Absolute Minima

使用テクニック： Priority queue, 中央値