AtCoder Beginner Contest 246をPythonで解く

こんにちは, Shinoryoです.

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

A - Four Points

解法パターンA

$x$座標のリスト, $y$座標のリストを用意し, それぞれのリストで登場回数が$1$回の座標の組み合わせが求める座標になります. リストにおける登場回数を調べるには, collectionsのCounterを用いるとよいです.

解法パターンB(こちらの方が標準的っぽい)

上記の「登場回数が$1$回の座標の組み合わせ」というのを, 別の方法で求めます. 入力する$x$座標を$x_1, x_2, x_3$, 求めるべき$x$座標を$x_{\mathrm{ans}}$とします.

• $x_1 = x_2$ならば, $x_{\mathrm{ans}} = x_3$
• $x_1 = x_3$ならば, $x_{\mathrm{ans}} = x_2$
• $x_2 = x_3$ならば, $x_{\mathrm{ans}} = x_1$

以上のようにして, $x_{\mathrm{ans}}$を求めることができます. 問題文にある「制約」から, この3つのどれか1つにかならず当てはまります.

$y$座標についても同様になります.

B - Get Closer

求めるのは,

になります.

C - Coupon

クーポンによる値下げには, 以下の2つのタイプがあります. クーポン使用前の値段を$a$円とします.

• タイプ1：$a \geq X$のときは, $a$から$X$円ぴったりが引かれる.
• タイプ2：$a < X$のときは, $a$から$a$円のみが引かれる.

全商品を買うための合計費用を最小化するためには, より効率的にクーポンを使用していく, つまりタイプ1の値下げをできる限り行った後に, タイプ2の値下げを行えばよいわけです.

タイプ1の値下げに関して考えます. $i$番目の商品に関して$A_i$から$X$をできる限り引くことを考えるわけですが, 可能な回数は

となります(ただし, $\lfloor x \rfloor$はGauss記号であり, $x$を超えない最大の整数). クーポンは$K$枚しかありませんので, タイプ1の値下げに使えるクーポンの枚数は

となります.

タイプ2の値下げに関して考えます. タイプ1のような値下げを全て仕切ってなお, クーポンが余っている場合を考えますので, $A_i$は全て$X$で割った余りに変換してしまいます. その上で, $A_i$を大きい順にソートして, クーポンがある限り順番にタイプ2の値下げを行っていきます.

以上により, 全商品を買うための最小合計費用を求めることができます.

D - 2-variable Function

ある整数$X$が条件に当てはまるかを考えるのは非常に難しいので, さまざまな$a, b$に対して$f(a, b) = a^3 + a^2 b + a b^2 + b^3$の値を格納したリストを用意して, そのリストの中から$N$以上の最小の整数を持ってきて$X$にすることが考えられます. さらに具体的に手法を詰めていくと, 固定された$a$に対して$f(a, b)$が$b$に関して単調増加であることを利用して, 以下のように求められます.

1. 答えの初期値として, $\mathrm{ans}$を無限大で用意する.
2. $a$の値を定める($0$から$10^6$までループ).
   1. $b = 0$として$f(a, b)$の値を求める.
   2. $f(a, b) < N$の場合は, $b += 1$として上に戻る.
   3. $f(a, b) \geq N$の場合は, $\mathrm{ans} = \min (\mathrm{ans}, f(a, b))$のように更新して, $b$に関するループを終了する.
3. 結果として得られる$\mathrm{ans}$が答え.

なお, $N = 10^{18}$であり, $a = 10^6$, $b = 0$とすると$f(a, b) = 10^{18}$であるので, $a$, $b$の調べる範囲は$0$から$10^6$まででいいことが分かることを利用しています. しかし, それらの全範囲を探索しているだけではとても時間が足りません.

そこで, $a$に関するループはそのままに, 固定された$a$に対して$f(a, b)$が$b$に関して単調増加であることをさらに利用して, 二分探索(binary search)を用いることを考えます.

• ある$\mathrm{low}$(適切な$b$がある範囲の下限)とある$\mathrm{high}$(適切な$b$がある範囲の上限)の値を用意する.
• $\mathrm{low}$と$\mathrm{high}$の真ん中の値として, $\mathrm{mid} = \left( \mathrm{low} + \mathrm{high} \right) / 2$を用意する.
• $f(a, \mathrm{mid})$を求める.
• $f(a, \mathrm{mid})$の値によって, 以下のように分類する.
  • $f(a, \mathrm{mid}) < N$の場合は, $b$としては$\mathrm{mid}$より大きい値を取ることになるので, $\mathrm{low} = \mathrm{mid}$とする.
  • $f(a, \mathrm{mid}) \geq N$の場合は, $b$としては$\mathrm{mid}$以下の値を取ることになるので, $\mathrm{high} = \mathrm{mid}$とする.
• $\mathrm{low}$と$\mathrm{high}$の差が$1$になるまで, これを繰り返す.

このようにしていくことで, 最終的に$\mathrm{high}$が, 固定された$a$に対して適切な$b$になります. 答えの初期値として, $\mathrm{ans}$を無限大で用意して, 各$a$に対してループしていく過程で$f(a, \mathrm{high})$によって$\mathrm{ans}$を更新していけば, 最終的な$\mathrm{ans}$が求める答えとなります.

二分探索については「SOMPO HD プログラミングコンテスト2021(AtCoder Beginner Contest 192)をPythonで解く」でも取り上げていますので, ぜひご覧ください.

E以降

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

参考にしたサイト等

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

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

• nkmk様による「PythonのCounterでリストの各要素の出現個数をカウント」
  PythonのCounterでリストの各要素の出現個数をカウント | note.nkmk.me

  Pythonでリストやタプルの全要素の個数は組み込み関数len(), 各要素の個数（要素ごとの出現回数）はcount()メソッドで取得できる. さらに, Python標準ライブラリcollectionsのCounterクラスを使うと, 出現回数が多い順に要素を取得できたりする. ここでは, 全要素数をカウント: len() 各要素の個数（要素ごとの出現回数）を...