AtCoder-ABC196 C - Doubled【Python解答例】
AtCoder Beginner Contest196のC - DoubledについてPythonの解答例を記事にしていきます。
AtCoder Beginner Contest 196 - AtCoder
AtCoder Beginner Contest196 C - Doubled
問題文
整数 N が与えられます。以下の条件を満たす 1 以上 N 以下の整数 x は何個あるでしょうか?
・x の十進表記 (先頭に 0 を付けない) は偶数桁であり、その前半と後半は文字列として等しい。
制約
・N は整数
・1≤N<10^12
解答例
N = input() n = int(N) digit = pow(10,len(N)//2) # 入力Nの半分の桁 ans = 0 for i in range(1,digit): tmp = str(i) # tmpを前半部分とする target = int(tmp + tmp) # 偶数桁で前半と後半文字列が等しい数target if target <= n: ans += 1 print(ans)
解説
1以上N以下の数字において、偶数桁で前半と後半の文字列が等しい数の個数を答える問題です。
Nの制約が10^12までなので全探索では間に合いません。
したがって、前半部分(後半でもいいですが)にしぼって考えていきます。
入力Nの半分の桁をdigit変数に代入し、1からdigitまでのループを回します。
ループ値のがiのとき、まずiをstring型にしてtmpとします。
調べる値targetはtmp+tmpを再度int型にした値です。
これでtargetは偶数桁で前半と後半が等しい条件を満たす値になります。
targetがN以下ならans変数に1を足していきます。
ループを抜けてansを出力すればOKでした。
D問題はコンテスト中に解けませんでしたが、復習して記事にしたいと思います。
ABC196の関連記事はこちら
ebisuke33.hatenablog.com
ebisuke33.hatenablog.com