この記事は 『AtCoder ABC226～250 ARC129～139 灰・茶・緑問題 超詳細解説』 のサンプルです。
値段：300円(Kindle Unlimited対象)
【kindle】
https://www.amazon.co.jp/dp/B0B7G13QMS
【booth(pdf)】
https://sano192.booth.pm/items/4025713
ARC129～139の部分のみ抜粋した廉価版 もあります。
値段：200円(Kindle Unlimited対象)
【kindle】
https://www.amazon.co.jp/dp/B0B7G337YF
【booth(pdf)】
https://sano192.booth.pm/items/4025737
【サンプル一覧】
ABC228 A：https://qiita.com/sano192/private/f8f09ea769f2414a5733
ABC249 B：https://qiita.com/sano192/private/daf74d7c31bc698d33ce
ABC226 C：https://qiita.com/sano192/private/3aa26373ca6cfcb3ef0f
ABC246 D：https://qiita.com/sano192/private/a22aadde99945bfb01a8
「ものすごく丁寧でわかりやすいABC解説」シリーズをベースに【キーワード】【どう考える？】【別解】を追加し、【解説】と【実装のコツ】を分けることでよりわかりやすく、具体例や図もより豊富に全ての問題の解説を書き直しました！
さらにQiitaでは公開していないARC129～139の灰・茶・緑問題も解説しています！
緑を目指す灰・茶コーダーの方へおすすめ！
【キーワード】
二分探索
【どう考える？】
変数が複数出てきた場合はいくつかを固定して考えるのがセオリー。今回はa,bどちらを固定してもよい。
bを固定した場合はX=f(a)として、f(a)がN以上となるもののうちで最小のXを探すという問題になる。ここで重要なのはX=f(a)がaに関して単調増加であるということ。「〇〇以上(以下)のうちで最小(最大)」といえば二分探索。Xは二分探索を使うことで高速に求められる。
bについては3乗があるからNが最大の10^18であっても10^6までの値で計算すればよいということがわかる。(b=10^7や10^8ならXが10^18を超える)
・変数が複数ならいくつかを固定
・単調増加(減少)で「〇〇以上(以下)のうちで最小(最大)」なら二分探索
この2つは他の問題でもよく使うテクニックなので覚えておこう。
【解説】
bを固定し、X=f(a)=a^3+a^2b+ab^2+b^3と置く。
この時f(a)はaに関して単調増加であるから、二分探索でNを超えるXの最小値を探すことができる。
「二分探索」
二分探索は区間の中央の値が条件を満たすか確認し、徐々に区間を狭めて目的の値を得るアルゴリズム。
(1)左=区間の最小、右=区間の最大 とする
(2)中央=(左+右)//2が条件を満たすか確認
(3)(2)の結果より左または右を更新する
(4)1**<(右-左)となっている間(2)~(4)を繰り返す
例としてN=100でb=3と固定されている場合を考えよう。b=3を代入してX=f(a)=a^3+3a^2+9a+27となる。
(1)左=区間の最小、右=区間の最大 とする
aは非負整数だから区間の最小(=左)はa=0、最大(=右)は10^6とする。(Nの最大値である10^18の3乗根10^6、実装では少し大きめにしている)
しかし、説明を簡単にするため右=10とする。
左：0
右：10
(2)中央=(左+右)//2が条件を満たすか確認
中央=(左+右)//2
中央=(0+10)//2=5
f(5)=5^3+35^2+95+27=272
(3)(2)の結果より左または右を更新する
N≤272である。この場合は右を更新する。
(4)1**<(右-左)となっている間(2)~(4)を繰り返す
左：0
右：5
1**<(5-0)だから(2)へ戻る。
(2)中央=(左+右)//2が条件を満たすか確認
中央=(左+右)//2
中央=(0+5)//2=2
f(2)=2^3+32^2+92+27=65
(3)(2)の結果より左または右を更新する
65**<Nである。この場合は左を更新する。
(4)1**<(右-左)となっている間(2)~(4)を繰り返す
左：2
右：5
1**<(5-2)だから(2)へ戻る。
(2)中央=(左+右)//2が条件を満たすか確認
中央=(左+右)//2
中央=(2+5)//2=3
f(3)=3^3+33^2+93+27=108
(3)(2)の結果より左または右を更新する
N≤108である。この場合は右を更新する。
(4)1**<(右-左)となっている間(2)~(4)を繰り返す
左：2
右：3
(3-2)**<1だから終了。
f(2)=65**<N
N≤f(3)=108
であるからb=3のとき、a=3の場合のXがN以上で最小。
同様にb=0~10^6についてaを確認し、N以上で最も小さいXを探す。
(実装では10^6より少し大きめにしている)
【実装のコツ】
<二分探索>
二分探索は[左,右]の区間を取って中央が条件を満たすか？を判定し、区間を狭めていく方法。
本文の場合実装は以下のように行う。
# (1)左=区間の最小、右=区間の最大 とする
# 左
l=0
# 右
r=10**6+100
# 1**\<(右-左)の間
while 1**\<r-l:
# (2)中央=(左+右)//2が条件を満たすか確認
c=(r+l)//2
# (3)(2)の結果より左または右を更新する
# 計算結果がN未満なら
if f(c,b)**\<N:
# 左=中央と更新
l=c
# 計算結果がN以上なら
else:
# 右=中央と更新
r=c
他の問題でも二分探索はほとんど同じ書き方が使える。
(1)左=区間の最小、右=区間の最大 とする
本問の場合、以下のように初期値を取っている。
左：1
右：10^9より大きい数(実装では大きめの数(=10^15)を入れている)
(2)中央=(左+右)//2が条件を満たすか確認
(3)(2)の結果より左または右を更新する
・中央が条件を満たす：右(または左)=中央と更新
・中央が条件を満たさない：左(または右)=中央と更新
(4)1**<(右-左)となっている間(2)~(4)を繰り返す
本問は二分探索問題としてはかなり難しい。
二分探索を練習する場合は以下が比較的簡単な問題なので二分探索を書いたことがない人は本問の前に以下の問題で練習するとよい。
ABC231 C Dif：194：https://atcoder.jp/contests/abc231/tasks/abc231_c
ABC146 C Dif：741：https://atcoder.jp/contests/abc146/tasks/abc146_c
<範囲を少し大きめに取る>
この問題は本来a,bともに10^6までを探索すれば十分なのだが、ギリギリの値で提出するとなにか勘違いがあったときにWAになってしまう。TLEしない程度に少し大きめにするという保険をかけておくと良い。
<pypyで提出>
計算量が大きく、pythonでは間に合わないので、提出の際言語に「pypy3」を選んで提出する。
「pypy」はプログラミング言語の一つで、pythonで書いたコードを高速で実行することができる。
(pythonは2sec以内にだいたい10^6回、pypyは2sec以内にだいたい10^8回計算が可能)
【提出】
# pypyで提出
# 入力の受け取り
N=int(input())
# 関数にする
def f(a,b):
return a**3+a**2*b+a*b**2+b**3
# 答え
ans=10**20
# b=0,1,2,...10^6
# (10^6より少し大きめにしている)
for b in range(10**6+100):
# (1)左=区間の最小、右=区間の最大 とする
# 左
l=0
# 右
r=10**6+100
# 1**\<(右-左)の間
while 1**\<r-l:
# (2)中央=(左+右)//2が条件を満たすか確認
c=(r+l)//2
# (3)(2)の結果より左または右を更新する
# 計算結果がN未満なら
if f(c,b)**\<N:
# 左=中央と更新
l=c
# 計算結果がN以上なら
else:
# 右=中央と更新
r=c
# N≤f(l,b)ならば
if N**\<=f(l,b):
# f(l,b)がansより小さければ更新
ans=min(ans,f(l,b))
# そうでなければ(f(l,b)**\<N⇔f(r,b)≤N)
else:
# f(r,b)がansより小さければ更新
ans=min(ans,f(r,b))
# 答えの出力
print(ans)