23 pypy Dif:565 ABC189 C：「AtCoder 凡人が『緑』になるための精選50問詳細解説」サンプル

この記事は拙著「AtCoder　凡人が『緑』になるための精選50問詳細解説」のサンプルです
価格：100円
kindle：https://www.amazon.co.jp/dp/B09C3TPQYV
booth(pdf)：https://sano192.booth.pm/items/3179185

前：https://qiita.com/sano192/items/780e1c4751b60cb0c8ed
次：https://qiita.com/sano192/items/abd5108d9c4f74e3efba

【目標】
・制約を見てpypyなら間に合うか？を判断できるようになる

【概要】
問題の解法自体は難しくないがやたらDifが高くなってしまった問題。原因は制約の大きさ。実際pythonだと想定解法ではTLE(実行時間制限超過)するがC++などの高速な言語ならO(N^2)でも余裕で間に合う。しかしpythonユーザーでも裏技としてpypyを使うことができる。本問ではpypyで間に合うか？を判断し、コードテストで確認するというテクニックを学ぶ。

【方針】
すぐに思いつく解法は
まずlを固定し、rを1つずつ増やしながらl番目～r番目までの最小値を確認
→(最小値)*(l-r+1)を計算して一番大きいものが答え
という方法。

しかしNの制約が1<=N<=10^4のため、Nが最大の場合にN^2=10^8回計算が発生して間に合わない・・・かと思いきや公式の想定解法がそれだった。

pythonでは実行制限時間1.5sec以内に10^8回計算するのは当然無理だが裏技としてpypyで提出するという方法が使える。

pypyはプログラミング言語の一種で、pythonとまったく同じ文法ながらC++並に高速で動作する。つまりpythonの文法でコードを書き、提出時の言語選択でpypyを選べばこの問題は解ける。

pypyで提出するときは2つの注意事項がある。
(1)pythonで使えるライブラリの一部はpypyで使えない
pythonではバージョンが上がるごとに標準ライブラリが追加されているが、その全てがpypyにも実装されているわけではないので注意が必要。ただし競技プログラミングで使用するほとんどのライブラリについてはpypyでも使用できるのであまり気にしなくて良い。

(2)pythonよりpypyのほうが遅くなってしまう処理がいくつかある
例えば文字列を反転させるなどの処理は若干pythonのほうが速い。ほかに「Decimal」という十進数の計算を誤差なく正確に行うための標準ライブラリについてはpypyで使うと10倍以上の時間がかかる。

pypyで提出するときはpypyの実行環境を自分のPCに作り、書いたコードがpypyできちんと動くのか確かめるのがベストだがそこまでするのも面倒くさい。
コードを書いたら提出する前にAtCoderの「コードテスト」をしてみよう。
「コードテスト」は問題ページの上部にあるタブから開ける。

このページで書いたコードを「ソースコード」にコピペして言語「pypy」を選択。
「標準入力」に制約が最大のケースを入力して「実行」してみよう。
これでエラーが起きないかの確認+実行時間を計測することができる。上図では216msと余裕で終わっているのがわかるだろう。

「標準入力」にコピペするための入力内容についてはpythonで作ると手っ取り早い。上図の入力内容は以下のコードで1が10000個並んだ数列を作っている。

# テストケース作成
path="C:\\test.txt"
s="1"
for i in range(10**4-1):
    s+=" 1"
with open(path, mode='w') as f:
    f.write(s)

上記コードを実行するとCドライブ直下に1が10000個並んだテキストファイルが作成される。

【実装】
入力を受け取る。

N=int(input())
A=list(map(int, input().split()))

答えを格納する変数ansを作る。
初期値としてとてつもなく小さい数を入れておく。

ans=-10**15

まずlを固定し、r=l、l+1、...、N-1まで増やしていく。
l～rの最小値を更新しながら(最小値)*(l-r+1)を確認し、ansより小さければansを更新する。

for l in range(N):
    A_min=A[l]
    for r in range(l,N):
        A_min=min(A_min,A[r])
        ans=max(ans,A_min*(r-l+1))

最後に答えを出力して終わり。

print(ans)

コンテスト中に思いついた解法がTLE(実行時間制限超過)しそうとなった場合、とりあえずその問題は飛ばそう。
TLE(実行時間制限超過)する可能性が高い解法のコードを書いている時間はほとんどの場合無駄になる。一旦その問題は飛ばして次の問題を見れば、むしろ次の問題のほうが簡単だったり、自分が知っている典型問題であるということは多い。他の解けそうな問題に取り組んでからその問題に戻ろう。

コードを書いた後、時間に余裕があれば【方針】で書いたように自分で最大ケースのサンプルを作り、提出前にコードテストに投げてみるのが一番良い。しかし時間がなければpypyを選択し、ダメ元で提出してみよう。

一番ダメなのは他の問題を見ずにとりあえずTLE(実行時間制限超過)しそうなコードを書いてダメ元で投げてみること。これは失敗した時ペナルティをくらううえ余計な時間を使い、他の問題を解く時間が短くなってしまう。

【コード全文】

N=int(input())
A=list(map(int, input().split()))

ans=-10**15
for l in range(N):
    A_min=A[l]
    for r in range(l,N):
        A_min=min(A_min,A[r])
        ans=max(ans,A_min*(r-l+1))

print(ans)

この記事は拙著「AtCoder　凡人が『緑』になるための精選50問詳細解説」のサンプルです
価格：100円
kindle：https://www.amazon.co.jp/dp/B09C3TPQYV
booth(pdf)：https://sano192.booth.pm/items/3179185

前：https://qiita.com/sano192/items/780e1c4751b60cb0c8ed
次：https://qiita.com/sano192/items/abd5108d9c4f74e3efba