AtCoder過去問: Python～第一回アルゴリズム実技検定（随時更新）

AtCoderの過去問解いていきます。
競技プログラミングの練習というよりは、Pythonのコーディング学習の一環として。
できる限り無駄のないコーディングになるよう、一問ずつ試行錯誤しながら、
随時更新していきます。

第一回 アルゴリズム実技検定 過去問

A - 2倍チェック

問題リンク

S = input()
if S.isdecimal():
    print(int(S)*2)
else:
    print("error")

Sが数字か、小文字かという可能性のみなのでこれでよいかなと。
3桁以外が来るなら len() でチェックが必要になりますが。
0始まりもこれで問題なし。

B - 増減管理

問題リンク

解法1

実行時間：197 ms
メモリ：13836 KB

N = int(input())
A_list = [int(input()) for _ in range(N)]
prev_a = A_list[0]
for a in A_list[1:]:
    if a == prev_a:
        print("stay")
    elif a < prev_a:
        print("down %d" % (prev_a - a))
    else:
        print("up %d" % (a - prev_a))
    prev_a = a

解法2

実行時間：233 ms
メモリ：12900 KB

N = int(input())
A_list = [int(input()) for _ in range(N)]
for i in range(len(A_list)-1):
    if A_list[i] == A_list[i+1]:
        print("stay")
    elif A_list[i] > A_list[i+1]:
        print("down %d" % (A_list[i] - A_list[i+1]))
    else:
        print("up %d" % (A_list[i+1] - A_list[i]))

わずかに解法1の方が速かった。
わかりやすさでも解法1のほうが個人的にはいいのかなとは思ってます。

C - ３番目

問題リンク

l = list(map(int, input().split(' ')))
l.sort()
print(l[-3])

mapという関数を初めて知りました。便利。

D - 重複検査

問題リンク

問題文、制約からわかるのは
・元の整数列は　1, 2, 3, ... , N　のように連続した整数列
・1～Nの範囲のうち、書き換えられた整数に存在しない値が x
・書き換えられた整数列のうち、重複した（複数存在する）値が y

このように整理したうえで下記。

N = int(input())
A_list = [int(input()) for _ in range(N)]

x = 0
y = 0
for i in range(1, N+1):
    if not i in A_list:
        x = i
    if A_list.count(i) > 1:
        y = i
    if x != 0 and y != 0:
        break

if x == 0 and y == 0:
    print('Correct')
else:
    print("%d %d" % (y, x))

ところがこれで提出したら実行時間制限超過してしまった。。
現在改善調査中です。

N = int(input())
A_list = [int(input()) for _ in range(N)]

A_list_union = set(A_list)
if len(A_list_union) == N:
	print("Correct")
	exit()

A_dict = {}
for i in range(N):
    if A_list[i] in A_dict:
        A_dict[A_list[i]] += 1
    else:
    	A_dict[A_list[i]] = 1

x = 0
y = 0

for i in range(1, N+1):
    if not i in A_list_union:
    	x = i
    	continue
    if A_dict[i] > 1:
    	y = i
    if x != 0 and y != 0:
    	break

print("%d %d" % (y, x))

上記のようにしたところ実行時間クリアしました。
countがかなり時間かかるみたいです。