AtCoder Beginner Contest 196 A~C問題

AtCoder Python

前書き

AtCoder Beginner Contest 196 A~C問題を解きました。

A問題

  • 難易度：灰
  • 時間：3分

atcoder.jp

a,b=map(int,input().split())
c,d=map(int,input().split())
print(b-c)

B問題

  • 難易度：灰
  • 時間：5分

atcoder.jp

_input = str(input())
if '.' in _input: 
  X1,X2 = map(str, _input.split('.'))
  print(X1)
else: print(_input)

C問題

  • 難易度：？
  • 時間：35分

atcoder.jp

1以上N以下の整数xにおいて、x（偶数桁）を前半と後半に区切ったとき、前半と後半の文字列が等しいxの個数を数える問題です。恐らくもっと簡略な回答があると思いますが、自分には以下のアルゴリズムしか思いつきませんでした。

まずNが奇数と偶数の場合で場合分けします。

ここでは偶数の場合の説明をします。N（偶数桁）を前半、後半に区切ったときの数字をLF、LBとします。LFの桁数をL'とします。

ここで大事なのはxを分割した時の桁数がL'となる時の処理※1です。

  • LF>LBの時→10**(L'-1)≤x'≤LF-1までのx'の個数（例えば・・・1311(13>11)、123111(123>111)）
  • LF<=LBの時→10**(L'-1)≤x'≤LFまでのx'の個数（例えば・・・1399(13<99)、123123(123=123)）

「133122」を例に出して解いてみましょう。

  • xの桁数が1桁→0
  • xの桁数が2桁→11〜99（LFが1~9の時=9）
  • xの桁数が3桁→0
  • xの桁数が4桁→1010~9999（LFが10~99の時=90）
  • xの桁数が5桁→0
  • xの桁数が6桁→100100~133122（LFが100~132の時(133>122より※1)=>133）

9+90+133=132（Ansewer）

このように規則を見つけていくとスムーズに解くことが可能です。

import sys,math
N,_sum=input(),0
Nlen=[i+1 for i in range(len(N))if (i+1)%2==0]

if len(N)==1: 
  print(0)
  sys.exit()
if len(N)%2!=0:
  for n in Nlen: _sum+=int('9'*int(n/2))-int(10**(int(n/2)-1))+1
  print(_sum)
  sys.exit()

for n in Nlen[:-1]: _sum+=int('9'*int(n/2))-int(10**(int(n/2)-1))+1

if int(N[:len(N)//2])<=int(N[len(N)//2:]):
  _sum+=int(N[:math.floor(len(N)/2)])-int(10**(int(Nlen[-1]/2)-1))+1
  print(_sum)
else:
  _sum+=(int(N[:math.floor(len(N)/2)])-1)-int(10**(int(Nlen[-1]/2)-1))+1
  print(_sum)

追記：

アホでした。普通に探索していけばもっとTLEなしで簡単なコードで解けますね・・・。
一度思いついたアルゴリズムが最短距離なのかを実装前に立ち止まって考える必要があるな・・・。

atcoder.jp

余談

情報技術者試験（午前の過去問：平成27年度秋）26/40問正解（60%）でした。