AtCoderをPythonで取り組んだ振り返り(ABC406 A~B,Cも更新)

どうもこんにちは！

今週のコンテストはA,Bを完答。CはTLEを解消できず。

# 問題

問題は以下のリンクから。完答できたBとCのできたところまでを振り返ります。

https://atcoder.jp/contests/abc406/tasks

https://atcoder.jp/contests/abc406/editorial

## A - Not Acceptable -
入力として4つの数字A,B,C,Dが与えられ、C時D分がA時B分より前の時間かを判定する問題。内容としてはA時B分がレポート提出期限で、C時D分に提出したら期限内かどうか、というもの。時間は24時間制で与えられ、同じ時間が与えられることはないです。
シンプルに時間を比較するんですが、比較条件が以下のどちらかを満たせばよいことに注意ですね。
- C < A (この場合、分は無条件で成立する)
- C = A かつ D < B
~~~Python
a,b,c,d = map(int,input().split())
if a > c or (a == c and b >= d):
  print("Yes")
else:
  print("No")
~~~

## B - Product Calculator -
N個の整数と正整数Kが与えられます。最初の値を1として、N個の整数を順番にかけ算しますが、計算結果の桁数がK桁以下なら計算結果をそのまま、K+1桁となった場合は計算結果を1におきかえるとして、最終結果を出力するという問題。
計算結果の桁数判定は計算結果をstr型にしたものをlen関数で求めて判定しました。
~~~Python
n,k = map(int,input().split())
s = [int(x) for x in input().split()]

ans = 1
for i in s:
  ans *= i
  if len(str(ans)) > k:
    ans = 1

print(ans)
~~~

## C - ~ -
与えられた長さnの整数列Pに対して、Pの連続部分列でありかつ下記4つの条件をすべて満たす数列($A_1,A_2,･･･,A_n$)の個数を出力する問題。整数列Pは1,2,3,4,･･･,nを並び替えたもので、同じ値が複数個存在することはないです。
- 数列の長さが4以上
- $A_1 < A_2$
- 数列内で$A_{i-1} < A_i > A_{i+1}$を満たすのは1箇所のみ (例えば 2 4 3という並び)
- 数列内で$A_{i-1} > A_i < A_{i+1}$を満たすのは1箇所のみ (例えば 4 2 3という並び)

例えば数列が(1, 3, 6, 4, 2, 5)のときは(1, 3, 6, 4, 2, 5)と(3, 6, 4, 2, 5)を満たすこととなり、回答は2となります。なお与えられる数列の長さは最大$3 × 10^5$で計算量を意識する必要があります。

さて、計算量を考えなければ、for文の2重ループで条件を満たすかを順番に比較すればよいです。3個目と4個目の条件は1個しか含まないように判定する点に注意です。
判定だけなら以下の実装でできるはずです。(なおTLEで完答にはなりません)
~~~Python:計算量過多
n = int(input())
s = [int(x) for x in input().split()]

ans = 0
for i in range(1,n-2):
    if s[i-1] >= s[i]:
        continue
    n1,n2 = False,False
    for j in range(i+1,n-1):
        if s[j-1] < s[j] and s[j] > s[j+1]:
            if n1 == False:
                n1 = True
            else:
                break
        if s[j-1] > s[j] and s[j] < s[j+1]:
            if n2 == False:
                n2 = True
            else:
                break
        if n1 == True and n2 == True:
~~~
解説によると、前後の数字を比較して不等号の配列を作って、この配列にランレングス圧縮をかけると探索すべき場所がわかって答えが出る…らしいんですが、現状理解できていません。。ある程度わかってコード書けたら追記するかもしれません。

--- 2025/5/19追記、2025/5/22一部整理 ---
C問題について、自分なりに解釈できたので整理がてら。
$A_1 < A_2$かつ極大値と極小値を1個ずつ持つという条件から、対象の数列には以下の順に現れます。
1\. $A_1 < A_2$
2\. 極大値($a < b > c$の$b$のような隣接する2つの値より大きい値)
3\. 極小値($a > b < c$の$b$のような隣接する2つの値より小さい値)

数列では扱いにくいので、先に数列の不等号だけを並べた文字列を作りましょう。こうすると対象の数列は<で始まり1個以上の連続する>を挟んで<で終わる文字列を数えればよいことになります。また、最初や最後の<が複数個連続するときは<の数だけ対象の数列があることになります。例えば、<<><<なら4個です。(<<><<, <<><, <><<, <><)
さらに、前後の連続する<<の数を明確にすべく不等号を並べた文字列をランレングス圧縮で変換します。例えば<<><<なら<2>1<2と変換され、2×2で4が答えとなります。
(ランレングス圧縮は連続する文字を文字+個数に変換することでデータサイズを圧縮する方法です。連続する文字が多いほど圧縮でき、例えばaaaaaabccならa6b1c2となり9文字を6文字に圧縮します。余談ですが実装方法は幅があるようで、aaaaaabccをa5bc1にする書き方もあるようです)

以上を踏まえて下記を作成してACとできました。コンテスト中の正答数を増やすにはこれを最初から思いついて実装する必要があるわけですが、道のりは長そうです。
~~~Python
n = int(input())
s = [int(x) for x in input().split()]

# 前後の数字の比較結果を<と>で並べ、ランレングス圧縮も使ってまとめる
sign = []  
for i in range(n-1):
    if s[i] < s[i+1]:
        if (len(sign) == 0 or sign[-1][0] == '>'):
            sign.append(['<',1])
        else:
            sign[-1][1] += 1
    else:
        if (len(sign) == 0 or sign[-1][0] == '<'):
            sign.append(['>',1])
        else:
            sign[-1][1] += 1

# 対象文字列の算出
# 対象文字列は<><となっている部分なので、>の前後の<の数をかけた数が対象文字列の数
ans = 0
for i in range(1,len(sign)-1):
    if sign[i][0] == '>':
        ans += sign[i-1][1] * sign[i+1][1]

print(ans)
~~~

--- 追記ここまで ---

ではでは。