AtCoder Beginner Contest 152 D – Handstand 2 をPython3で解く

AtCoder上にある問題のうち、AtCoder Problemsでdiff 800以上と判定されているものを順番に解いていく企画。
基本的な考え方は全てコード中のコメントに入れてあるので、参照のこと。

出典：
AtCoder Beginner Contest 152 D – Handstand 2

桁DPなどでもう少し効率をあげることもできると思われるが、制約が緩いのでここでは単純な全探索を用いている。

# AtCoder Beginner Contest 152 D - Handstand 2
# https://atcoder.jp/contests/abc152/tasks/abc152_d
# tag: 整数 順列・組み合わせ 数え上げ

# 先頭が top、末尾が bottom の数が、N 以下に
# いくつあるのかを数えられればいい。

# 1 <= N <= 200000 なので、これを全探索しつつ
# 数え上げておく。

# あとは (top, bottom) の数と (bottom, top) の数を
# 掛けたものを、全ての top, bottom に対して足したものが
# 組み合わせ数になる。

def main():
    N = int(input())

    # カウンタ初期化
    cnt = dict()
    for top in range(10):
        for bottom in range(10):
            cnt[(top, bottom)] = 0

    # 全ての cnt[(top, bottom)] の数を数えておく
    for i in range(1, N+1):
        top = int(str(i)[0])
        bottom = int(str(i)[-1])
        cnt[(top, bottom)] += 1

    result = 0

    # 全ての (top, bottom) に対して、
    # cnt[(top, bottom)] * cnt[(bottom, top)] を
    # 足し合わせる
    for top in range(10):
        for bottom in range(10):
            result += cnt[(top, bottom)] * cnt[(bottom, top)]

    print(result)

main()

abc152_d.py view raw

関連

コメントを残すコメントをキャンセル