はじめに

n = int(input())
dat = [[0] * 10 for _ in range(10)]
for i in range(1, n+1):
    dat[int(str(i)[0])][int(str(i)[-1])] += 1
res = sum([dat[a][b] * dat[b][a] for a in range(10) for b in range(10)])
print(res)

だけで良い問題だったのだが、まったく見通しが立たなかったので、ある程度列挙してみて法則性を見つけた + 力わざの併用で無理やり解い話。

賢さ的にもオーダー的にも全く優れていないけど、一応ACできた。（こういう解き方ばっかりしているのでレーティングが上がらないんだろうなと思いつつ！）

問題文

問題文は非常にシンプル。

N 以下の正の整数の組 (a,b)に対してaの末尾がbの先頭に等しく、bの末尾がaに等しい

制約 $ N < 2 \times 10^{5}$ から総当たりは無理そう。

あたりをつける

そもそもどういう数字かは簡単に列挙できそうなので、コードを書いて試す。

n=100
count=0
for x in range(1, n+1):
    for y in range(1, n+1):
        if str(x)[0] == str(y)[-1] and str(y)[0] == str(x)[-1]:
            print("({0},{1})".format(x,y))
            count += 1
print("total:{0}".format(count))

(1,1), (1,11), (2,2) ... (98,89), (99,9), (99,99)
total:108

のように列挙できた。このコードをベースにnをインクリメントして傾向を探る。

(k:count)
(1:1),(2:2),(3:3),(4:4),(5:5),(6:6),(7:7),(8:8),(9:9),(10:9)
(11:12),(12:12),(13:12),(14:12),(15:12),(16:12),(17:12),(18:12),(19:12),(20:12)
(21:14),(22:17),(23:17),(24:17),(25:17),(26:17),(27:17),(28:17),(29:17),(30:17)
(201:430),(202:435),(203:437),(204:439),(205:441)
(206:443),(207:445),(208:447),(209:449),(210:449),
(211:471),(212:478),(213:480),(214:482),(215:484)
(216:486),(217:488),(218:490),(219:492),(220:492),

一見すると法則性がないように見えるが、例えば、9->0ではカウントが増えないなど何らか法則性はありそうだ。
0-9の数字であるので、10ごとに何らかの法則がありそうなので、nを10ずつインクリメントして、差分を取ってみる。

(10:9),(20:12),(30:17),(40:24),(50:33),(60:44),(70:57),(80:72),(90:89),(100:108)
(110:129),(120:152),(130:177),(140:204),(150:233),(160:264),(170:297),(180:332),(190:369),(200:408)
(210:449),(220:492),(230:537),(240:584),(250:633),(260:684),(270:737),(280:792),(290:849),
-> これらのcountだけを取り出すと、
x = [9, 12, 17, 24, 33, 44, 57, 72, 89, 108, 129, 152, 177, 204, 233, 264, 297, 332, 369, 408, 449, 492, 537, 584, 633, 684, 737, 792, 849]
-> それぞれの隣接する項の差を取ると
[x[i] - x[i-1] for i in range(1,len(x))]
> [3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27, 29, 31, 33, 35, 37, 39, 41, 43, 45, 47, 49, 51, 53, 55, 57]

この結果から、nが10の倍数のとき、n = 10 x iとすれば、求めたい数 anは

a_{i}はある数列の初項9で、項差をb_{i}とする数列である。\\

ただし、b_{i}は初項3、項差2とした等差数列であり、\\
b_{i} = 3 + 2(n-1) = 2n + 1 \\
で表される。このため、a_{i}は以下のように示せる。 \\
 a_{i}  = 9 + \sum_{k = 1}^{i - 1} b_{n} 
 = 9 + \sum_{k = 1}^{i - 1} (2k + 1)  \\
 = 9 + 2 \sum_{k = 1}^{i - 1} k + \sum_{k = 1}^{i - 1} 1  \\
 = 9 + 2 \cdot \frac{(n-1)n}{2} + (n - 1) \\
 = n^{2} + 8

表されそうである。試しに、in/outサンプルの$2020 = 202 \times 10$で試すと、$202^{2} = 40812$となり、一致する。このため、10の倍数についてはこのまま行けそうだと思って進める。

10の倍数の法則が分かった次は？

ここまでで、Nが10の倍数の時はいけそうなことが分かったが、例えば、$N=1234$の時の$15274$という答えはどう求めるか？

まず、$N=1230$なら$ 123^{2} + 8 = 15137 $ となる。
これで、(1～1230, 1～1230)の区間は計算されているのだから、
(1231～1234, 1～1234)と(1～1234, 1231～1234)の区間について実際にシミュレーションし、数を加えればよい。ただし、この際に、この例では(1231, 1231)という値が2度カウントされるので、ダブルカウントしないようにしなければならない。

ループの回数は高々10回以内に押さえられるため、$N=2 \times 10^{5}$の制約下ではO(10N)のため間に合う。

尚、1から9の数値に関しては上記が適応できない(そもそも、上記の数式$a_{n}$は10以上なので)ため、数え上げる(といいつつ、$n<10$では答えが$n$なのでそのまま反射しているだけ。)

n = int(input())
# else以下は10以上の時のみ適応できるので10未満は埋め込み
if n < 10:
    print(n)
else:
    # 説明中のiを求めるため10でわる(切り捨て)
    x = n // 10
    # 公式による計算。x^2+8
    basenum = x * x + 8
    addnum = 0
    # ここ以下で(10*i から n, 1 から n)と(1 から n, 10*i から n)の数え上げを行うが、
    # 重複した数え上げがないか確認するフラグ
    hassame = False
    # 数え上げ(ここでは、(10*i から n, 1 から n)だけ数え上げ、倍にすることで(1 から n, 10*i から n)分も数え上げる)
    for i in range(x * 10 + 1, n + 1):
        for j in range(1, n + 1):
            if str(i)[0] == str(j)[-1] and str(i)[-1] == str(j)[0]:
                addnum += 1
                if i == j:
                    hassame = True
    res = basenum + addnum * 2 # 10の倍数の公式分と　力わざで数え上げた加算
    res -= 1 if hassame else 0 # ダブルカウントがあれば1減らす
    print(res)