D - Handstand 2

https://atcoder.jp/contests/abc152/tasks/abc152_d

場合分けがしんどかった。

解法

1〜Nを以下実装のフローで全探索する。

実装

入力値の先頭の桁の数、末尾の桁の数、その間の数を返す関数を作る

def bunkai(n:int):
    ls=list(str(n))
    top,bottom=int(ls[0]),int(ls[-1])
    if n<=99:
        middle=0
    else:
        middle=int("".join(ls[1:-1]))
    return top, middle, bottom

Nを分解して保持しておく

N=int(input())
Nt,Nm,Nb = bunkai(N) # N=47856 => (Nt, Nm, Nb)=(4, 785, 6)

探索中の数字iも分解して(t,m,b)で保持しておく。 b==0のときは飛ばして次の探索に行く（∵先頭の桁が0の数字はない） t==bのときは(A,B) = (i, t)という組が取れるのでcount+=1

count=0
for i in range(1,N+1):
    t,m,b = bunkai(i)
    if b==0:continue
    if t==b:count+=1

N<=99のときは、(t,b)をひっくり返した2桁の数字がN以下ならcount+=1

    if N<=99:
        if int(str(b)+str(t))<=N:count+=1
    else:

N>=100のときは場合分けが必要。
まず、Nの数値によらず、「Nの桁数-1」の桁までは確定で候補に入れることができるのでこちらを先に考える。 (N,i)=(47856, 24)ののケースを試しに考える。

2桁：42 の1個
3桁：4X2 の10個 (X=0,1,2,3,...,8,9)
4桁：4XX2の100個 (X=0,1,2,3,...,98,99)
つまりそれぞれの桁で、10の(桁数-2)乗だけcountに追加できる

        keta = len(str(N))
        for x in range(keta-2):
            count+=10**x

4XXX2、つまりNと同じ桁数を考える時、場合分けが必要。
Ntがbより大きい時は、遠慮なくXXX=000〜999の10³個をcountに追加できる。 Ntがbより小さい時は、この桁数では条件をみたすXXXが存在しないので、count追加なし。

        x+=1
        if Nt>b:
            count+=10**x
        elif Nt<b:
            count+=0

今回のケースのように、Ntがbと同じ場合はさらに場合分けが必要

N=47856, i = 24
iがひっくり返って5桁になった4XXX2がNの範囲でどれだけとれるか考える

1. Nの最後の桁の数字Nbが、iの先頭の桁の数字tよりも大きい場合（今回のケースに該当）
40002, 40012, 40022, ... , 47842, 47852, の786個がとれる。これはNm+1個。
2. Nの最後の桁の数字Nbが、iの先頭の桁の数字tよりも小さい場合（たとえばN=47851のとき)
40002, 40012, 40022, ... , 47842, 47852<=こいつがとれない！ので785個がとれる。これはNm個。

        elif Nt==b:
            if Nb>=t:
                count+=Nm+1
            else:
                count+=Nm
print(count)

以下コード全体

def bunkai(n:int):
    ls=list(str(n))
    top,bottom=int(ls[0]),int(ls[-1])
    if n<=99:
        middle=0
    else:
        middle=int("".join(ls[1:-1]))
    return top, middle, bottom

N=int(input())
Nt,Nm,Nb = bunkai(N)

count=0
for i in range(1,N+1):
    t,m,b = bunkai(i)
    if b==0:continue
    if t==b:count+=1
    if N<=99:
        if int(str(b)+str(t))<=N:count+=1
    else:
        keta = len(str(N))
        for x in range(keta-2):
            count+=10**x
        x+=1
        if Nt>b:
            count+=10**x
        elif Nt<b:
            count+=0
        elif Nt==b:
            if Nb>=t:
                count+=Nm+1
            else:
                count+=Nm
print(count)