はじめに

AtCoderを始めました。かの有名なAtCoder過去問精選10問をPythonで解いたので、何番煎じかも分かりませんが、そのときのメモを残します。
- AtCoder に登録したら次にやること～これだけ解けば十分闘える！過去問精選10 問～
エレガントに短く書くより、多少冗長でも初心者にも追いやすそうにと意識して書きました。
ちなみに、入力部分は毎回下記を参考にさせていただいています。
- Pythonで使う競技プログラミング用チートシート

パターン	入力値	スクリプト	取得結果
文字列をstrで受け取る	abcde	s=input()	s='abcde'
文字列をstrのlistで受け取る	abcde	s_list=list(input())	s_list=['a', 'b', 'c', 'd', 'e']
数字をintで受け取る	1	n=int(input())	n=1
数字（複数/スペース区切り）を intでそれぞれ受け取る	1 2	n,q = map(int,input().split())	n=1,q=2
数字（複数/スペース区切り）を strのlistで受け取る	1 2 3	a_list = input().split()	a_list=['1','2','3']
数字（複数/スペース区切り）を intのlistで受け取る	1 2 3	a_list = list(map(int,input().split()))	a_list=[1,2,3]
文字列（複数/改行区切り/行数指定あり）を strのlistで受け取る	2 hoge foo	n=int(input()) s_list=[input() for _ in range(n)]	s_list=['hoge','foo']
数字（複数/改行区切り/行数指定あり）を intのlistで受け取る	2 0 3	n=int(input()) a_list=[int(input()) for _ in range(n)]	a_list=[0, 3]
数字（複数/改行区切り/行数指定あり）を intのlist（二次元)で受け取る	2 0 1 2 3 4 5	n=int(input()) a_list=[list(map(int,input().split())) for _ in range(n)]	a_list=[[0, 1, 2], [3, 4, 5]]

過去問精選10問

第 1 問: ABC 086 A - Product (100 点)

【問題概要】

二つの正整数 a, b が与えられます。 a と b の積が偶数か奇数か判定してください。

【制約】

1≤a,b≤100
a, b は整数

【数値例】

1)
　a=3
　b=4
　答え: Even

2)
　a=1
　b=2
　答え: Odd

【解法】

# -*- coding: utf-8 -*-
a, b = map(int, input().split())

result = a * b
if result % 2 == 0:
    print('Even')
else:
    print('0dd’)

【ポイント】

割り算
- 割り算（除算）: /
- 割り算の整数部（整数除算）: //
- 割り算の剰余（余り, mod）: %

第 2 問: ABC 081 A - Placing Marbles (100 点)

【問題概要】

0 と 1 のみから成る 3 桁の番号 s が与えられます。1 が何個含まれるかを求めてください。

【数値例】

1)
　s = "101"
　答え: 2

【解法】

# -*- coding: utf-8 -*-
s = input()
counter = 0

for i in range(len(s)):
    if s[i] == '1':
        counter += 1
print(counter)

【ポイント】

数字の各桁に注目するときは、string型でとらえる
stringもlist同様、インデックスで要素にアクセスできる

第 3 問: ABC 081 B - Shift Only (200 点)

【問題概要】

黒板に N 個の正の整数 A1,…,AN が書かれています。
すぬけ君は，黒板に書かれている整数がすべて偶数であるとき，次の操作を行うことができます。

黒板に書かれている整数すべてを，2 で割ったものに置き換える。
すぬけ君は最大で何回操作を行うことができるかを求めてください。

【制約】

1≤N≤200
1≤Ai≤10⁹

【数値例】

1)
　N=3
　A=(16,12,24)
　答え: 2

【解法】

# -*- coding: utf-8 -*-
n = int(input())
a_list = list(map(int,input().split()))

count = 10000000 # 十分に大きい値
for i in range(len(a_list)):
    a_i = a_list[i]
    count_i = 0
    while a_i % 2 == 0:
        a_i /= 2
        count_i += 1
    if count > count_i:
        count = count_i
print(count)

【ポイント】

条件を満たす間ずっと処理を繰り返したいなら、while文を使う
変数を用意して、記録していく

第 4 問: ABC 087 B - Coins (200 点)

【問題概要】

500 円玉を A 枚、100 円玉を B 枚、50 円玉を C 枚持っています。
これらの硬貨の中から何枚かを選び、合計金額をちょうど X 円にする方法は何通りあるでしょうか？

【制約】

0≤A,B,C≤50
A+B+C≥1
50≤X≤20000
A,B,C は整数である
X は 50 の倍数である

【数値例】

1)
　A=2
　B=2
　C=2
　X=100
　答え: 2

【解法】

# -*- coding: utf-8 -*-
a = int(input())
b = int(input())
c = int(input())
x = int(input())

count = 0
for a_i in range(a+1):
    for b_i in range(b+1):
        for c_i in range(c+1):
            total = 500*a_i + 100*b_i + 50*c_i
            if total == x:
                count += 1
print(count)

【ポイント】

200点問題とかなら（制約がそんなに大きくなければ）、とりあえずfor 文で全探索してみる

第 5 問: ABC 083 B - Some Sums (200 点)

【問題概要】

1 以上 N 以下の整数のうち、10 進法で各桁の和が A 以上 B 以下であるものについて、総和を求めてください。

【制約】

1≤N≤10⁴
1≤A≤B≤36
入力はすべて整数

【数値例】

1)
　N=20
　A=2
　B=5
　答え: 84

【解法】

# -*- coding: utf-8 -*-
n,a,b=map(int,input().split())
 
def sum_digits(n):
    n_str = str(n)
    sum = 0
    for i in range(len(n_str)):
        sum += int(n_str[i])
    return sum
 
total = 0
for i in range(1, n+1):
    sum_of_digits_i = sum_digits(i)
    if a <= sum_of_digits_i and sum_of_digits_i <= b:
        total += i
 
print(total)

【ポイント】

数字の各桁に注目するときは、string型でとらえる
- 特に各桁の和は（たぶん）あるあるなのですぐ書けるように

第 6 問: ABC 088 B - Card Game for Two (200 点)

【問題概要】

N 枚のカードがあり、i 枚目のカードには ai という数が書かれています。 Alice と Bob はこれらのカードを使ってゲームを行います。ゲームでは 2 人が交互に 1 枚ずつカードを取っていきます。Alice が先にカードを取ります。 2 人がすべてのカードを取ったときゲームは終了し、取ったカードの数の合計がその人の得点になります。2 人とも自分の得点を最大化するように最適戦略をとったとき、Alice は Bob より何点多くの得点を獲得できるかを求めてください。

【制約】

N は 1 以上 100 以下の整数
ai は 1 以上 100 以下の整数

【数値例】

1)
　N=3
　a=(2,7,4)
　答え: 5

【解法】

# -*- coding: utf-8 -*-
n=int(input())
x_list=list(map(int,input().split()))

x_list.sort(reverse=True)

a = 0
b = 0
for number_turns_i in range(n):
    if number_turns_i % 2 == 0:
        a += x_list[number_turns_i]
    elif number_turns_i % 2 == 1:
        b += x_list[number_turns_i]
print(a-b)

【ポイント】

リストのソート
交互、偶数奇数は、%2==0で表現

第 7 問: ABC 085 B - Kagami Mochi (200 点)

【問題概要】

N 個の整数 d[0],d[1],…,d[N−1] が与えられます。この中に何種類の異なる値があるでしょうか？
(原問題文をかなり意訳していますが、題意はこういうことです)

【制約】

1≤N≤100
1≤d[i]≤100
入力値はすべて整数

【数値例】

1)
　N=2
　Q=3
　d=(8,10,8,6)
　答え: 3

【解法】

# -*- coding: utf-8 -*-
n=int(input())
d_list=[input() for i in range(n)]

d_list_int = [int(n) for n in d_list]
d_set_int = set(d_list_int)
print(len(d_set_int))

【ポイント】

リストの全ての要素に処理を加えたい時は、リストの内包表記
重複削除はsetで

第 8 問: ABC 085 C - Otoshidama (300 点)

【問題概要】

10000 円札と、5000 円札と、1000 円札が合計で N 枚あって、合計金額が Y 円であったという。このような条件を満たす各金額の札の枚数の組を 1 つ求めなさい。
そのような状況が存在し得ない場合には -1 -1 -1 と出力しなさい。

【制約】

1≤N≤2000
1000≤Y≤2∗10⁷
N は整数
Y は 1000 の倍数

【数値例】

1)
　N=9
　Y=45000
　答え: (4,0,5) など

【解法】

n,y = map(int,input().split())

import sys
for a in range(n+1):
    for b in range(n-a+1):
        c=n-a-b
        if 10000*a+5000*b+1000*c==y:
            print(a, b, c)
            sys.exit()
print("-1 -1 -1")

【ポイント】

二重三重の for 文を使いたくなったときは、工夫で回避できないか考える
条件を満たした場合に、処理を途中で切り上げる

第 9 問: ABC 049 C - Daydream (300 点)

【問題概要】

英小文字からなる文字列 S が与えられます。
T が空文字列である状態から始めて、以下の操作を好きな回数繰り返すことで S=T とすることができるか判定してください。

T の末尾に "dream", "dreamer", "erase", "eraser" のいずれかを追加する。

【制約】

1≤|S|≤10⁵
S は英小文字からなる

【数値例】

1)
　S = "dreameraser"
　答え: "YES"

【解法】

# -*- coding: utf-8 -*-
s = input()
 
dp = [0] * 100007 # sの最大値+t_element_listの要素の最大値以上
 
t_element_list = ["dream", "dreamer", "erase", "eraser"]
 
dp[0] = 1
for i in range(len(s)):
    if dp[i] == 1:
        for j in range(len(t_element_list)):
            if s[i:i+len(t_element_list[j])] == t_element_list[j]:
                dp[i + len(t_element_list[j])] = 1
 
if dp[len(s)] == 1:
    print('YES')
else:
    print('NO')

【ポイント】

動的計画法（？）
- 状態を記録する箱を用意する

第 10 問: ABC 086 C - Traveling (300 点)

【問題概要】

シカの AtCoDeer くんは二次元平面上で旅行をしようとしています。
AtCoDeer くんの旅行プランでは、時刻 0 に点 (0,0) を出発し、1 以上 NN 以下の各 i に対し、時刻 ti に点 (xi,yi) を訪れる予定です。
AtCoDeer くんが時刻 t に点 (x,y) にいる時、時刻 t+1 には点 (x+1,y),(x−1,y),(x,y+1),(x,y−1) のうちいずれかに存在することができます。
その場にとどまることは出来ないことに注意してください。AtCoDeer くんの旅行プランが実行可能かどうか判定してください。

【制約】

1≤N≤10⁵
0≤xi,yi≤10⁵
1≤ti≤ti+1≤10⁵
入力はすべて整数

【数値例】

1)
　N=2
　(t,x,y)=(3,1,2),(6,1,1)
　答え: "Yes"

【解法】

# -*- coding: utf-8 -*-
n=int(input())
input_list=[list(map(int,input().split())) for i in range(n)]
 
can_exec = True
for i in range(len(input_list)):
    t_i = input_list[i][0]
    x_i = input_list[i][1]
    y_i = input_list[i][2]
    if (x_i + y_i) > t_i or (t_i + x_i + y_i) % 2 ==1:
        can_exec = False
        print('No')
        break
if can_exec == True:
    print('Yes')

【ポイント】

偶数奇数判定
- 分岐させるのではなく、まとめて2で割った余りをみる
フラグ管理変数とif文のbreakでフロー制御

おわりに

次は、過去問のD問題を解き漁ろうかと思います。
関連
- AtcorderABC-Dより先へ行くために代表的なアルゴリズムを勉強した-その1-（DP、累積和、UnionFind木、bit関係、二分探索）