やるだけPython競プロ日誌

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

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

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

Pythonで解いてみました。

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

2022/5/22
記事執筆時は未熟だったもので、十分にPythonicであるといえない解答も多く解説も不十分でしたので、改訂いたしました。

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

https://language-test-201603.contest.atcoder.jp/tasks/practice_1

問題文
高橋君はデータの加工が行いたいです。
整数 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

問題文
シカの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")

この問題はa, bともに10000未満と制約が緩いので問題ありませんが、C++などの整数を扱える型に最大値の制限がある言語では、a, bともに奇数であるかどうかを判定したり、文字列として受け取ったのちに1の位のみを判定したりする必要があります。

しかしPython多倍長整数を使えるので、かけ合わせたものを純粋に割った方が早いです。

2問目 ABC081A - Placing Marbles

A - Placing Marbles

問題文
すぬけ君は 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

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

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

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

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

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

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

n = input()
a = list(map(int, input().split()))

ans = float("inf")
for v in a:
    ans = min(ans, list(reversed(bin(v))).index('1'))
    
print(ans)

binを用いて2進数に変換すると、右に続く0の数=何回2で割れるか、というものになっています。そして、その最小の値をとるという流れです。
1つでも奇数のものがあれば無条件に0になります。
愚直にやった場合、計算量的には O(200 * log2109 ≒6000 ) と普通に通ってしまうのですが、スマートではないので2進数にしています。何回もfor分を回すのはめんどくさいですしね。
Pythonは面白い言語で、"無限"を表現しようとすると、float("inf") としなければいけません。

4問目 ABC087B - Coins

B - Coins

問題文
あなたは、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 _ 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

問題文
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(map(int, str(i))) <= b:
        ans += i
print(ans)

そのままですね。

6問目 ABC088B - Card Game for Two

B - Card Game for Two

問題文
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(map(int, input().split()), reverse=True)
print(sum(a[::2]) - sum(a[1::2]))

これでよいと思います。sliceでは2つ区切りで取り出して、sumを求めるということをしています。

7問目 ABC085B - Kagami Mochi

B - Kagami Mochi

問題文
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

問題文
日本でよく使われる紙幣は、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()を忘れないように…(1敗)

9問目 ABC049C - 白昼夢 / Daydream

C - Daydream

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

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

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

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

s = input()

while s:
    for query in ("erase", "eraser", "dream", "dreamer"):
        if s.endswith(query):
            s = s[:-len(query)]
            break
    else:  # breakされなかったとき、つまり、合致する文字列がなかった場合
        print('NO')
        exit()

print('YES')

この問題の面倒なところは、頭から順番に見ていくと"dreamer..."という文字列が"dream"+"eraser?"なのか、"dreamer"なのか分からないという部分です。

この問題の簡単な解法がぱっと思いつくだけで2通りあります。
1つが、「先頭が"dreamera" の時は"dreamer"ではなく"dream"を削除する」というものです。"a"から始まるクエリは存在しないので、"dream"というクエリが与えられていると確定します。
2つ目が、先頭から見ていくのではなく最後尾から見ていくというものです。頭のerで困っているのなら、後ろから削ってしまえば問題ありません。この方法では、"dream"と"dreamer"の優先順位など気にしなくてもよいので、とても楽です。
今回は後者を採用しました。

10問目 ABC086C - Traveling

C - Traveling

問題文
シカの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())

plans = []
for _ in range(n):
    plans.append(map(int, input().split()))

st = sx = sy = 0
for t, x, y in plans:
    dt, dx, dy = t - st, abs(x - sx), abs(y - sy)
    if t % 2 != (x + y) % 2 or dx + dy > dt:
        print('No')
        exit()
    st, sx, sy = t, x, y
print('Yes')

それぞれの t, x, y について
x + y と t の偶奇が違っていればダメ
x + y が t より大きければダメ。
この二つのコードを書けば終わりです。
その場にとどまることはできないので、tが1増えるとx+yの偶奇が入れ替わります。つまり、tの偶奇とx+yの偶奇は必ず同じになります。
また、前回からの移動距離であるabs(dx)+abs(dy)はdt以下でなければなりません。絶対値を取らなければ、例えば

0 0 0
1 -100 100

といった値が通ってしまうので注意が必要です。

終わりに

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

2022/5/22 追記

近年機械学習や深層学習の流れを受け、主にアカデミーの分野からPythonの波が来ています。
Web系においても十分選択肢として挙げられるものとなり、喜びを隠せません