やるだけPython競プロ日誌

競プロの解説をPythonでやっていきます。できるだけ初心者に分かりやすいように『やるだけ』とかは言わないようにします。コメントについては必ず読んでいます。どんなに細かいことでもいいのでコメントくださればうれしいです。

AtCoder に登録したら解くべき精選過去問 10 問 をPythonで解いてみた

全く違うサイトにはなりますが、 drken 氏がQiitaで投稿された
AtCoder に登録したら次にやること ~ これだけ解けば十分闘える!過去問精選 10 問 ~ - Qiita

Pythonで解いてみました。

ある程度難しい問題があるので、説明を端折ることもあると思いますが、できるだけわかりやすく説明します。

0問目 PracticeA - はじめてのあっとこーだー(Welcome to AtCoder

A: はじめてのあっとこーだー(Welcome to AtCoder) - Language Test | AtCoder

問題文
高橋君はデータの加工が行いたいです。
整数 a,b,cと、文字列 s が与えられます。
整数 a+b+c と、文字列 s を並べて表示しなさい。

入力
入力は以下の形式で与えられる。

a
b c
s
1 行目は、整数 a (1≦a≦1,000) が与えられる。
2 行目は、整数 b,c (1≦b,c≦1,000) が与えられる。
3 行目は、文字列 s が与えられる。この文字列の長さは 1 文字以上 100 文字以下である。
出力
a+b+c と s を空白区切りで 1 行に出力せよ。

また、出力の末尾には改行を入れること。

要は、与えられる文字列と数字を出力しろということですね。

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

1問目 ABC086A - Product

A: Product - AtCoder Beginner Contest 086 | AtCoder

問題文
シカのAtCoDeerくんは二つの正整数 a,b を見つけました。 a と b の積が偶数か奇数か判定してください。

制約
1 ≤ a,b ≤ 10000
a,b は整数
入力
入力は以下の形式で標準入力から与えられる。

a b
出力
積が奇数なら Odd と、 偶数なら Even と出力せよ。

非常に簡単な問題ですね

a, b = map(int, input().split())
if (a*b) % 2:
    print("Odd")
else:
    print("Even")

かけ合わせたものを純粋に割った方が早いです

2問目 ABC081A - Placing Marbles

A: Placing Marbles - AtCoder Beginner Contest 081 | AtCoder

問題文
すぬけ君は 1,2,3 の番号がついた 3 つのマスからなるマス目を持っています。 各マスには 0 か 1 が書かれており、マス i には si が書かれています。

すぬけ君は 1 が書かれたマスにビー玉を置きます。 ビー玉が置かれるマスがいくつあるか求めてください。

制約
s1,s2,s3 は 1 あるいは 0
入力
入力は以下の形式で標準入力から与えられる。

s1s2s3
出力
答えを出力せよ。

つまり、1の個数を数えればいいわけですね。

print(input().count("1"))

与えられるのは文字列ですので、そのままcountでよいと思います

3問目 ABC081B - Shift only

B: Shift only - AtCoder Beginner Contest 081 | AtCoder

問題文
黒板に N 個の正の整数 A1,…,AN が書かれています.

すぬけ君は,黒板に書かれている整数がすべて偶数であるとき,次の操作を行うことができます.

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

制約
1≤N≤200
1≤Ai≤109
入力
入力は以下の形式で標準入力から与えられる。

N
A1 A2 ... AN
出力
すぬけ君は最大で何回操作を行うことができるかを出力せよ.

つまり、与えられた数字を一気に2で割るとしたとき、何回まで整数のままで割れますか。ということです。

import math
n = input()
a = list(map(int, input().split()))
ans = float("inf")
for i in a:
    ans = min(ans, len(bin(i)) - bin(i).rfind("1") - 1)
print(round(ans))

binに変換すると、右に続く0の数が、何回2で割れるか、というものになっています。ですから、わざわざrfindとかを使います。
なんかいもfor分を回すのはめんどくさいですからね。
Pythonは面白い言語で、"無限"を表現しようとすると、float("inf") としなければいけません。

4問目 ABC087B - Coins

B: Coins - AtCoder Beginner Contest 087 | AtCoder

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

同じ種類の硬貨どうしは区別できません。2 通りの硬貨の選び方は、ある種類の硬貨についてその硬貨を選ぶ枚数が異なるとき区別されます。

制約
0≤A,B,C≤50
A+B+C≥1
50≤X≤20,000
A,B,C は整数である
X は 50 の倍数である
入力
入力は以下の形式で標準入力から与えられる。

A
B
C
X
出力
硬貨を選ぶ方法の個数を出力せよ。

制約が大きいとforの回し方を工夫する必要がありますが、今回は小さいので、普通に回しましょう。

a, b, c, x = map(int, [input() for i in range(4)])
ans = 0
for i in range(a+1):
    for j in range(b+1):
        for k in range(c+1):
            if i * 500 + j * 100 + k * 50 == x:
                ans += 1
print(ans)

rangeの引数には+1を忘れないで入れておきましょう。

5問目 ABC083B - Some Sums

B: Some Sums - AtCoder Beginner Contest 083 | AtCoder

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

制約
1≤N≤104
1≤A≤B≤36
入力はすべて整数である
入力
入力は以下の形式で標準入力から与えられる。

N A B
出力
1 以上 N 以下の整数のうち、10 進法での各桁の和が A 以上 B 以下であるものの総和を出力せよ。

文字列変換→リストでsumとすればよいでしょう。制約も小さいので。

n, a, b = map(int, input().split())
ans = 0
for i in range(n+1):
    if a <= sum(list(map(int, list(str(i))))) <= b:
        ans += i
print(ans)

美しいですね。

6問目 ABC088B - Card Game for Two

B: Card Game for Two - AtCoder Beginner Contest 088 | AtCoder

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

制約
N は 1 以上 100 以下の整数
ai (1≤i≤N) は 1 以上 100 以下の整数
入力
入力は以下の形式で標準入力から与えられる.

N
a1 a2 a3 … aN
出力
両者が最適な戦略を取った時, Alice は Bob より何点多く取るかを出力してください.

パット見ても、sliceを使いそうですよね。

n = int(input())
a = sorted(list(map(int, input().split())), reverse=True)
print(sum(a[::2]) - sum(a[1::2]))

これでよいと思います。sliceでは2つ区切りで取り出して、sumを求めるということをしています。rangeも同じような使い方ができますよね。

7問目 ABC085B - Kagami Mochi

B: Kagami Mochi - AtCoder Beginner Contest 085 | AtCoder

問題文
X 段重ねの鏡餅 (X≥1) とは、X 枚の円形の餅を縦に積み重ねたものであって、どの餅もその真下の餅より直径が小さい(一番下の餅を除く)もののことです。例えば、直径 10、8、6 センチメートルの餅をこの順に下から積み重ねると 3 段重ねの鏡餅になり、餅を一枚だけ置くと 1 段重ねの鏡餅になります。

ダックスフンドのルンルンは N 枚の円形の餅を持っていて、そのうち i 枚目の餅の直径は di センチメートルです。これらの餅のうち一部または全部を使って鏡餅を作るとき、最大で何段重ねの鏡餅を作ることができるでしょうか。

制約
1≤N≤100
1≤di≤100
入力値はすべて整数である。
入力
入力は以下の形式で標準入力から与えられる。

N
d1
:
dN
出力
作ることのできる鏡餅の最大の段数を出力せよ。

何やら難しそうなことを言ってますが、要は、ユニークな要素はいくつありますか。ということです。ですので、setがうまく使えそうですね。

n = int(input())
print(len(set(map(int, [input() for i in range(n)]))))

非常に簡単ですね。

8問目 ABC085C - Otoshidama

C: Otoshidama - AtCoder Beginner Contest 085 | AtCoder

問題文
日本でよく使われる紙幣は、10000 円札、5000 円札、1000 円札です。以下、「お札」とはこれらのみを指します。

青橋くんが言うには、彼が祖父から受け取ったお年玉袋にはお札が N 枚入っていて、合計で Y 円だったそうですが、嘘かもしれません。このような状況がありうるか判定し、ありうる場合はお年玉袋の中身の候補を一つ見つけてください。なお、彼の祖父は十分裕福であり、お年玉袋は十分大きかったものとします。

制約
1≤N≤2000
1000≤Y≤2×107
N は整数である。
Y は 1000 の倍数である。
入力
入力は以下の形式で標準入力から与えられる。

N Y
出力
N 枚のお札の合計金額が Y 円となることがありえない場合は、-1 -1 -1 と出力せよ。

N 枚のお札の合計金額が Y 円となることがありうる場合は、そのような N 枚のお札の組み合わせの一例を「10000 円札 x 枚、5000 円札 y 枚、1000 円札 z 枚」として、x、y、z を空白で区切って出力せよ。複数の可能性が考えられるときは、そのうちどれを出力してもよい。


これに関しては、よーくfor文の条件を考えないとTLE(時間オーバー)してしまいます

n, y = map(int, input().split())
for i in range(n + 1):
    for j in range(n - i + 1):
        if i * 10000 + j * 5000 + (n - i - j) * 1000 == y:
            print(i, j, n - i - j)
            exit()
print("-1 -1 -1")

はい。じつは、for文二回でいけるんですね。それも当然で、2種類の枚数が定まれば、自然ともう一種類も定まるからですね。
競プロは、時間がきちきちになることはありますが、必ず解けます
あと、exit()を忘れないように…(僕は一回忘れました)

9問目 ABC049C - 白昼夢 / Daydream

C: 白昼夢 / Daydream - AtCoder Beginner Contest 049 | AtCoder

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

T の末尾に dream dreamer erase eraser のいずれかを追加する。
制約
1≦|S|≦105
S は英小文字からなる。
入力
入力は以下の形式で標準入力から与えられる。

S
出力
S=T とすることができる場合 YES を、そうでない場合 NO を出力せよ。

つまり、与えられる文字列は、すべて、["eraser", "erase", "dream", "dreamer"]でなっていますか。という問題です。

s=input().replace("eraser","").replace("erase","").replace("dreamer","").replace("dream","")
if s:
    print("NO")
else:
    print("YES")

考えてみると分かるのですが、dreamerは、後ろのerを削っても大丈夫です。ですが、eraseとeraserが削られると致命的ですよね。

ですから、先にeraseとeraserを消しておいて、あとからdream, dreamerを消します。
残った文字列が空ならばOKです。でなければ、何か混ざっています。

10問目 ABC086C - Traveling

C: Traveling - AtCoder Beginner Contest 086 | AtCoder

問題文
シカのAtCoDeerくんは二次元平面上で旅行をしようとしています。 AtCoDeerくんの旅行プランでは、時刻 0 に 点 (0,0) を出発し、 1 以上 N 以下の各 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 ≤ 105
0 ≤ xi ≤ 105
0 ≤ yi ≤ 105
1 ≤ ti ≤ 105
ti < ti+1 (1 ≤ i ≤ N−1)
入力は全て整数
入力
入力は以下の形式で標準入力から与えられる。

N
t1 x1 y1
t2 x2 y2
:
tN xN yN
出力
旅行プランが実行可能ならYesを、不可能ならNoを出力してください。

これも考えてみると実に簡単です。

n = int(input())
for i in range(n):
    t, x, y = map(int, input().split())
    if x + y < t or (x + y + t) % 2:
        print("No")
        exit()
print("Yes")

それぞれの t, x, y について
x + y が t より大きければダメ。
x + y と t の偶奇が違っていればダメ
この二つのコードを書けば終わりです。

終わりに

未だPythonは日本ではあまり主流とまではいっていません。それが競技プログラミングともなれば、ほとんどがC++などといった高速な言語ばかりです。
我々Pythonistaは、それによる速度の遅さのせいでしばしばPythonistaにしかわからない苦悩を味わうときさえあります。
しかし、少なくとも私はPythonに対する愛で乗り越えてきましたし、これからもそうでしょう。
特にfunctools, itertools, bisect, 等といった標準ライブラリには感服せざるを得ません。
豊富なライブラリに幾度となく助けられてきました。それは競技プログラミングでも同じです。
あなたも、この素晴らしい言語に対する愛が深まるように応援しています。

いい話

Pythonパーカーを作っています。ちなみに、私のデザインですが、一切私に利益は来ないようにするので、お安いです。
買いたいという人が多ければ多いほど安くなるので、DMなりコメントなりリプライなりよろしくお願いします。