【AtCoder】PythonでABC235のB問題を丁寧に読み解く

実際の問題はこちらからご覧ください。

この問題のポイント

この問題を解く鍵となるアルゴリズムの仕組みは、線形探索を応用した効率的な探索手法にあります。

具体的には、問題文から「高橋君は現在立っている台から右隣の台が高ければ移動し、そうでなければ停止する」というルールが与えられています。この挙動を実現するために、現在の台の高さと右隣の台の高さを比較し、右隣の台の方が高い場合にのみインデックスを一つ進めて次の台へと移動します。

このプロセスを現在の台が右端に達するか、右隣の台が現在の台よりも高くなくなるまで繰り返します。このアプローチでは、配列を一度だけ前から後ろへと順に走査するため、アルゴリズムの計算量は配列の長さに直接比例するO(N)となります。

シンプルながらも効率的なこの手法は、条件に基づいて特定の要素を検索する際に非常に有効であり、問題を解く上で核となるアルゴリズムの仕組みを形成しています。

n = int(input()): 台の総数nを標準入力
h = list(map(int, input().split())): 各台の高さを表す整数のリストhを標準入力
ans = 0: ansを移動の回数（または、最終的に高橋君が立つ台のインデックス）で初期化
while(ans+1 < n and h[ans] < h[ans+1]):: ans+1 < nは高橋君がまだリストの最後に達していないことを、h[ans] < h[ans+1]は右隣の台が現在の台より高いことを確認する、これらの条件が共に真である間、ループを続ける
ans += 1: 条件が真である場合、ansをインクリメントして高橋君を右隣の台に移動
print(h[ans]): ループを抜けた後（高橋君がこれ以上右に移動できない時）、最終的に高橋君が立つ台の高さを出力

n = int(input())
h = list(map(int, input().split()))
ans = 0
while(ans+1 < n and h[ans] < h[ans+1]):
    ans += 1
print(h[ans])