始めに
競技プログラミングサイトAtCoder にて
AtCoder Beginner Contest (以下ABC) 最新回 (2019年2月23日現在) の
第118回から さかのぼって第1回まで、Bの問題を全て解いてみました。
Bの問題では、Aの問題ではほとんど無かった
要素数を指定した入力 (要素数が動的に変わる入力) ならびに
繰り返し処理が出てきます。
Aの問題をまとめて解いた後、Bの問題をまとめて解くと分かるのですが
Bの問題の方が、難しく、間違いも増えました。
これまでに解いた問題を振り返り
しっかり確認しておきたいと思い書きました。
予告無く、内容は削除、修正することがあります。
ご了承下さい。
ABC 118 B Foods Loved by Everyone
N, M = map(int, input().split())
l = []
for i in range(N):
A = [int(x) for x in input().split()]
for j in range(1, A[0] + 1):
l.append(A[j])
ans = 0
for i in range(M + 1):
if l.count(i) == N:
ans += 1
print(ans)
要素数を指定した入力 (要素数が動的に変わる入力)
空の 「リスト」 を作成して、要素を追加 (append) する。
後で要素ごとの 出現回数 を数える為に
「リスト」 に 「リスト」 をそのまま追加せずに
「リスト」 の要素ごとに 「リスト」 に追加することにした。
空の 「リスト」 を作成する
l = [] とすると、空の 「リスト」 l を作成できる。
「リスト」 の 追加 は append
l.append(要素) で 要素 を 追加する。
追加した順番 で 保持 され、インデックス での アクセス が 可能 となる。
重複 の 要素 も そのまま 保持 される。
ABC 116 B Collatz Problem
def f(s):
cnt = 0
st = set()
cnt += 1
st.add(s)
while True:
cnt += 1
if s % 2 == 0:
tmp = s / 2
else:
tmp = 3 * s + 1
if tmp in st:
break
st.add(tmp)
s = tmp
return cnt
s = int(input())
ans = f(s)
print(ans)
関数 (function) を定義する
def を用いて関数 (function) を定義することができる。
ここでは s という引数を受け取り、cnt を戻り値として返す。
s は 初項
s が 偶数 なら s / 2
s が 奇数 なら 3 * s + 1
計算した値が初項を含め既に存在するか確認し
存在しない場合は集合に値を格納する。
存在する場合は初項を含めた現在の要素数を戻り値として返す。
空の 「集合」 を 作成 する
st = set() とすると、空の 「集合」 st を作成できる。
「集合」 の 追加 は add
st.add(要素) で 要素 を 追加する。
「集合」 では 要素 は 一意 となり、重複 の 要素 は 無視される。
重複 の 要素 を 追加 しようとしても エラー にはならない。
追加した順番 など 並び順 は 保証 されず、バラバラになる。
in 「集合」
in で 「集合」 に 値 があるかどうかをテストする。
ABC 114 B 754
S = input()
num = 753
ans = 999
for i in range(len(S) - 2):
cur = int(S[i:i + 3])
if (abs(num - cur) < ans):
ans = abs(num - cur)
print(ans)
「文字列」 の 切り出し
「文字列」[開始インデックス:終了インデックス] で 「文字列」 の切り出しができる。
「文字列」 の 先頭 の インデックス は 「0」。
「文字列」 の 末尾 の インデックス は 「-1」、len(「文字列」) - 1 でもよい。
終了インデックス に 該当する 文字 は 含まれない為、注意が必要。
「文字列」[開始インデックス:] で 開始インデックス の 文字 から 末尾 まで となる。
「文字列」[:終了インデックス] で 先頭 から 終了インデックス の 一つ前の文字 まで となる。
ABC 112 B Time Limit Exceeded
N, T = map(int, input().split())
ct = []
for i in range(N):
ct.append([int(i) for i in input().split()])
ct.sort(key=lambda x: x[0])
ans = 1001
for i in range(N):
if ct[i][1] <= T:
ans = ct[i][0]
break
print("TLE" if ans == 1001 else ans)
決まった要素数で「リスト」に「リスト」を追加する (splitする場合)
ct = []
for i in range(N):
ct.append([int(i) for i in input().split()])
この 3行
for の i と リストの中で使っている i で
意図せず 変数名 が被っている
予想外の動作をする場合があると考えられるので良くない。
リストの中で使っている i を j として 1行でできる。
ct = [[int(j) for j in input().split()] for i in range(N)]
「リスト」 に 格納された 「リスト」 の 第1項目 で 昇順ソート
「リスト」.sort(key=lambda x:x[0])。
x は 「リスト」 に 格納された 「リスト」
0-indexed なので 第1項目 は x[0]となる。
ABC 108 B Ruined Square
x1, y1, x2, y2 = map(int, input().split())
dx = x2 - x1
dy = y2 - y1
nx = x2
ny = y2
l = []
for i in range(2):
dx, dy = -dy, dx
nx = nx + dx
ny = ny + dy
l.append(nx)
l.append(ny)
print(l[0], l[1], l[2], l[3])
正方形、90度、反時計回り
xy 平面、4つの頂点の座標、反時計回り に 順番 に
(x1, y1), (x2, y2), (x3, y3), (x4, y4)。
(x1, y1), (x2, y2) が与えられるので
(x3, y3), (x4, y4)を出力する。
ある頂点から次の頂点への x軸の変化量、y軸の変化量を
それぞれ dx と dy とした時、さらに次の頂点への x軸の変化量、y軸の変化量は
それぞれ dx = -dy、dy = dx となる。
Python3 では スワップ が できるので、値の退避は必要ない。
dx, dy = -dy, dx とできる。
ABC 107 B Grid Compression
H, W = map(int, input().split())
l = []
for i in range(H):
l.append(input())
y = [False] * H
x = [False] * W
for i in range(H):
flg = True
for j in range(W):
if l[i][j] != '.':
flg = False
break
if flg:
y[i] = True
for i in range(W):
flg = True
for j in range(H):
if l[j][i] != '.':
flg = False
break
if flg:
x[i] = True
for i in range(H):
if y[i]:
continue
for j in range(W):
if x[j]:
continue
print(l[i][j], end='')
print()
決まった要素数で「リスト」に追加する (splitしない場合)
l = []
for i in range(H):
l.append(input())
この 3行 は 1行 で出来る
l = [input() for i in range(H)]
「リスト」 を 指定した値 ならびに 要素数 で 初期化 する
「リスト」 y、値が すべて False、要素数 H の場合
y = [False] * H
この問題では ’.’ または ’#’ より構成される「文字列」が 複数行 与えられ
縦1列が すべて ’.’ ならば 該当する 縦1列 を除いて詰める。
横1列が すべて ’.’ ならば 該当する 横1行 を除いて詰める。
縦、横、それぞれ1列、1行ずつ すべて ’.’ かどうか確認し
すべて ’.’ ならば True を格納する。
縦が 「リスト」 y、横が 「リスト」 x。
ABC 106 B 105
import math
def divisor(div, N):
# 約数
i = 1
n = N
while i <= math.sqrt(n):
if n % i == 0:
div.append([i, n / i])
i += 1
N = int(input())
cnt = 0
for i in range(1, N + 1):
if i % 2 == 0:
continue
div = []
divisor(div, i)
if len(div) == 4:
cnt += 1
print(cnt)
約数 を 「リスト」 に 格納 する
関数 divisor を作成し、「リスト」 div に N の 約数 を格納する。
ここでは 約数 の ペア を 「リスト」 として
その 「リスト」 を 「リスト」 div に格納している。
N の 約数 の ペア とは
例えば N の 約数である 「1」 の ペア は 「N」 であるように
ペア 同士 を 掛け合わせると N になるもの。
ここでは 関数 divisor 引数で受け取った 「リスト」 div に 格納している為
関数 divisor は return する必要がない。
n の 平方根を求める
math.sqrt(n) で n の 平方根を求める。
math の import が必要。
このやり方でなくても、平方根 は 2分の1乗 であり
a ** b で a の b 乗の為
n ** (1 / 2) = n ** 0.5 でも求まる。
ABC 105 B Cakes and Donuts
N = int(input())
flg = False
for i in range(101):
for j in range(101):
if 100 < i + j:
break
if 4 * i + 7 * j == N:
flg = True
continue
if flg:
break
print("Yes" if flg else "No")
合計が N ドルとなる 1個 4ドルのケーキ と 1個 7ドルのドーナツ の買い方
N が 1 以上 100 以下の 整数 と 小さい。
全探索しても 100 * 100 = 10,000 (1万) 程度の為、素直に全探索。
この値 が 1千万 だと 危ないかも知れない という感覚。
しかし、Python3 では この 感覚 が 危ないことを 後述する。
(ABC 051 B Sum of Three Integers参照)
全探索のループではなく、ズバッと O(1) オーダー1 で計算で求めきれるなら
そのやり方がよいが、その試みは自分の場合、よく失敗する。
ケース の 想定漏れ が 起こりにくい のが、全探索 の良いところ。
ABC 104 B AcCepted
S = input()
flg = True
if S[0] != 'A':
flg = False
cnt = 0
for i in range(2, len(S) - 1):
if S[i] == 'C':
cnt += 1
if cnt != 1:
flg = False
cnt = 0
for i in range(len(S)):
if 'A' <= S[i] <= 'Z':
cnt += 1
if cnt != 2:
flg = False
print("AC" if flg else "WA")
「文字列」のチェック
先頭が 'A'
先頭から 3 文字目 と 末尾から 2 文字目の間（両端含む）に
大文字の 'C' がちょうど 1 個
以上の 'A', 'C' を除く すべて の 文字 は 小文字
各条件を一つずつ確認。
間違えやすい。
「文字列」 は 0-indexed。
末尾から 2文字目 という時に
in range の 終了条件 の インデックス は len(S) - 1 とする。
終了条件 の インデックス の 文字自体 は 含まず、一つ前の文字までとなるので注意する。
以上の 'A', 'C' を除く すべて の 文字 は 小文字 の チェック
'A', 'C' に注意をとられて、「すべて」「小文字」を忘れてしまう。
'A' <= S[i] <= 'Z' で 「大文字」 を すべて チェックして
確かに大文字は 'A', 'C' の 2つだけ であることを確認する。
ABC 103 B String Rotation
S = input()
T = input()
flg = False
for i in range(len(S)):
S = S[-1] + S[:-1]
if S == T:
flg = True
break
print("Yes" if flg else "No")
「文字列」の末尾を切り取り、先頭に持ってくる
S = S[-1] + S[:-1]
S[-1] は 末尾1文字。
S[:-1] は 「文字列」から 末尾1文字 を 除いたもの。
ABC 100 B Ringo's Favorite Numbers
D, N = map(int, input().split())
if N == 100:
N += 1
print(100 ** D * N)
100 でちょうど D 回 割りきれる 正の整数 の中で N 番目に小さいものを出力
100 ** D * N で 間違える。
制約 N は 以上 100 以下 の 整数 に 注意。
もし、N が 100 の 場合だけは、100 番目 が D + 1 回 割り切れる事になってしまう。
N が 100 の 場合だけは、N += 1 で プラス1 しておく。
ABC 098 B Cut and Count
N = int(input())
S = input()
ans = 0
num = len(S)
for i in range(num):
X = set(S[:i + 1])
Y = set(S[i + 1:num])
ans = max(ans, len(X & Y))
print(ans)
「文字列」S を「文字列」X と 「文字列」Y に分割、X と Y 両方に含む文字種類数最大化
「文字列」S を 各位置 で 分割して、「集合」X と 「集合」Y に格納する。
「集合」X と 「集合」Y の 論理積(AND) の 要素数 を 最大化することで求めることができる。
「集合」X と 「集合」Y の 論理積(AND) は X & Y で求めることができる。
ABC 095 B Bitter Alchemy
N, X = map(int, input().split())
l = []
for i in range(N):
l.append(int(input()))
sorted(l)
print(N + (X - sum(l)) // min(l))
「お菓子の素」 X グラムで N 種類のドーナツを作る、最大何個作れるか
各種類 の ドーナツ の 必要「お菓子の素」グラム数が与えられる。
各種類 の ドーナツ は 最低でも 1個 作るので 全て足したものを X から 引く。
その値 を 「お菓子の素」最小量で作れるドーナッツの「お菓子の素」グラム数で割る。
その値 と N を足すことで求めることができる。
「リスト」 の すべて の 要素 の 合計
sum(「リスト」) で 求めることができる。
ABC 093 B Small and Large Integers
A, B, K = map(int, input().split())
s = set()
for i in range(A, min(A + K, B + 1)):
s.add(i)
for i in range(B, max(A - 1, B - K), -1):
s.add(i)
s = sorted(s)
for i in s:
print(i)
A 以上 B 以下の整数、小さい方 K 番目以内、大きい方 K 番目以内、昇順
制約
1 <= A <= B <= 10 の 9 乗
1 <= K <= 100
A と B の 間 を 全探索 したら TLE となる。
A と B の 間 は 最大で 10 の 9 乗 離れている為。
次に素直に A から K 個 取り、B から K 個 取り、集合に格納する。
これも A から K 個 取った時に、Bを超えるとダメで、逆も同様。
そこで、in range の 終了条件に min max を使う。
min(A + K, B + 1) ならば A + K - 1 と B のうち、小さい方までとなる。
max(A - 1, B - K) ならば A と B - K + 1のうち、大きい方までとなる。
in range の 終了条件 の インデックス 自体 は 含まず
一つ前のまでとなるので注意する。
ABC 091 B Two Colors Card Game
N = int(input())
st = set()
s = []
for i in range(N):
tmp = input()
st.add(tmp)
s.append(tmp)
M = int(input())
t = []
for i in range(M):
t.append(input())
ans = -100
tmp = 0
for x in st:
tmp = s.count(x)
tmp -= t.count(x)
ans = max(ans, tmp)
print(ans if 0 <= ans else 0)
for ～ in 「集合」:
集合の要素を一つずつ取り出す。
ABC 088 B Card Game for Two
N = int(input())
a = sorted([int(i) for i in input().split()], reverse=True)
Alice, Bob = 0, 0
for i in range(len(a)):
if i % 2 == 0:
Alice += a[i]
else:
Bob += a[i]
print(Alice - Bob)
「リスト」 の 降順ソート:
sorted(「リスト」, reverse=True) は 「リスト」 の 降順ソート。
「リスト」.sort(reverse=True) も 「リスト」 の 降順ソート。
前者は元となる 「リスト」 自体は ソート されず 元のままだが
前者は元となる 「リスト」 自体が ソート される。
ABC 087 B Coins
A = int(input())
B = int(input())
C = int(input())
X = int(input())
ans = 0
for i in range(A + 1):
for j in range(B + 1):
for k in range(C + 1):
if (X == 500 * i + 100 * j + 50 * k):
ans += 1
print(ans)
500円、100円、50円、それぞれA、B、C枚で、合計金額をちょうど X円何通り
制約
0 <= A, B, C <= 50
50 * 50 * 50 = 125,000 (12万5千)
全探索で数える。
ABC 086 B 1 21
ab = int(input().replace(' ', ''))
i = 0
flg = False
while i * i <= ab:
if i * i == ab:
flg = True
break
i += 1
print("Yes" if flg else "No")
「文字列」に含まれる半角スペースを除去
「文字列」.replace(' ' (半角スペース) , '' (空文字) )
半角スペース を 空文字 に 置換する。
このとき 「文字列」 自体は置換されない為、変数に保持しておくことに注意。
ABC 082 B Two Anagrams
s = sorted(input())
t = sorted(input(), reverse=True)
print("Yes" if s < t else "No")
「文字列」の中の文字を昇順、降順ソート
「リスト」 と同じように
s = sorted(「文字列」) で 「文字列」の中の文字を昇順ソート。
t = sorted(「文字列」, reverse=True) で 「文字列」の中の文字を降順ソート。
この問題では、この後、s < t で 「文字列」辞書順比較をしている。
ABC 081 B Shift only
N = int(input())
A = [int(i) for i in input().split()]
ans = 0
flg = True
while flg:
for i in range(N):
if A[i] % 2:
flg = False
break
else:
A[i] >>= 1
if flg:
ans += 1
print(ans)
右シフトの代入演算子
変数 >>= 1 で 変数 を 1 ビット右シフト したものを 変数 に入れることができる。
ABC 078 B ISU
X, Y, Z = map(int, input().split())
for i in range(1, 100000):
if X < i * Y + (i - 1) * Z + 2 * Z:
break
print(i - 1)
for 変数 in range(～) の 変数 は、forブロックの外でも使える
C++ や Java の 変数スコープ とは 異なり
Python3 では for 変数 in range(～) の 変数 は、forブロックの外でも使える。
特に構造化せず、そのままフラットに書いてしまっている変数は、グローバル変数に近い。
関数に引数を定義しなくても、使えたりする。
ABC 075 B Minesweeper
# 下、右、上、左、右下、右上、左下、左上
dy = [1, 0, -1, 0, 1, -1, 1, -1]
dx = [0, 1, 0, -1, 1, 1, -1, -1]
H, W = map(int, input().split())
field = []
for i in range(H):
field.append(list(input()))
for y in range(H):
for x in range(W):
if field[y][x] == '#':
continue
cnt = 0
for k in range(8):
ny = y + dy[k]
nx = x + dx[k]
if ny < 0 or H <= ny\
or nx < 0 or W <= nx:
continue
if field[ny][nx] == '#':
cnt += 1
field[y][x] = str(cnt)
for y in range(H):
print("".join(field[y]))
8方向走査
'.' は 空き、 '#' は爆弾の1行から複数行の「文字列」が与えられるので
Minesweeperのように、空きのマスに周囲8方向にある爆弾の数を埋める。
コンテスト中に実装すると、間違えることがあるので、dy や dx それらを使う部分は
予めスニペットなどで直ぐに読み出せるように準備しておく。
8方向走査の他、4方向走査、2方向走査も出題されるので準備しておく。
「文字列」 は 作成後に変更することができない。
ここでは、「文字列」 を 文字 の 「リスト」 とすることで 変更を可能にしている。
行継続文字はバックスラッシュ(円記号)
例えば if 条件 が長くなった場合、バックスラッシュを入れることで
その後の改行が無視されて行が継続していると見なされる。
上記のプログラム
if ny < 0 or H <= ny\
or nx < 0 or W <= nx:
バックスラッシュ無しで改行の場合、SyntaxError になる。
''(空文字).join(「リスト」)
「リスト」の 各要素 を 区切り文字 なし で結合して出力することができる。
' '(半角スペース).join(「リスト」)とすれば
「リスト」の 各要素 を 区切り文字 半角スペース で結合して出力することができる。
ABC 072 B OddString
s = input()
print(s[::2])
「文字列」の奇数個目の文字のみ、または偶数個目の文字のみ取得
「文字列」[::2] で 先頭から見て奇数個目の文字のみ
「文字列」[1::2] で 先頭から見て偶数個目の文字のみ取得できる。
「文字列」[開始インデックス:終了インデックス:増分step] で
開始インデックス、終了インデックスを省略すると先頭まで、末尾まで(両端込み)となる。
文字列だけでなくリストにも使える。
ABC 071 B Not Found
S = list(input())
flg = True
for i in range(ord('a'), ord('z') + 1):
if S.count(chr(i)) == 0:
flg = False
ans = chr(i)
break
print("None" if flg else ans)
ord と chr
ord('文字') は 文字 を表す整数。
chr(整数) は 文字を表す整数 を 文字に変える。
やりたいことは、文字のインクリメントだが、Python3 では ord と chr を使う。
ABC 070 B Two Switches
A, B, C, D = map(int, input().split())
l = [0] * 102
l[A] += 1
l[B] -= 1
l[C] += 1
l[D] -= 1
for i in range(1, len(l)):
l[i] += l[i - 1]
ans = 0
for i in range(0, len(l)):
if l[i] == 2:
ans += 1
print(ans)
2人ともスイッチを押していた秒数
1人目が A秒 から B秒 まで、2人目が C秒 から D秒 までスイッチを押していた。
2人ともスイッチを押していた秒数を求める問題。
累積和を使っていく。
最初に先述の、「リスト」 を 指定した値 ならびに 要素数 で 初期化 する方法で
ゼロで初期化した 「リスト」 l を作っておく。
「リスト」 のインデックス位置、A、B、C、D に 1 ならびに -1 を加える。
加えるのが大事で、一度 A = 1、B = -1、 C = 1、D = -1、としてバグらせてしまった。
次に累積和、1から前の要素を足し込む方法で作成。
len(l) で 最後まで抜かりなく足し込む。
その累積和の結果をチェックする。
先頭 0 から len(l) まで 抜かりなくチェックする。
先頭 0 から が大事で、一度 1 から としてバグらせてしまった。
値が 2 の 要素数 を数えて、出力すれば完成だ。
ABC 068 B Break Number
N = int(input())
ans = 1
while True:
if N < ans << 1:
break
ans <<= 1
print(ans)
左シフトの代入演算子
変数 <<= 1 で 変数 を 1 ビット左シフト したものを 変数 に入れることができる。
ABC 066 B ss
S = input()
S = S[:-2]
flg = True
while flg:
flg = False
x = 0
for i in range(len(S) // 2):
if S[x] != S[len(S) // 2 + x]:
flg = True
S = S[:-2]
break
x += 1
print(len(S))
動的に変わる in range 終了条件
この問題は同じ 「文字列」 を 2 回 ならべてできる 「文字列」 かどうかを判定する。
偶 「文字列」 と呼ぶ。
偶 「文字列」 が与えられる。1文字以上消して作れる 偶 「文字列」 の最大長を求める。
最初に末尾から2文字を削除。
偶 「文字列」 でなければ、さらに末尾から2文字を削除。
これは 「文字列」 = 「文字列」[:-2] でできる。
「文字列」 の 長さ を 2 で割った数 を in range 終了条件 としている。
このように 動的に変わる 終了条件 を in range で使用することができる。
ABC 065 B Trained?
N = int(input())
a = []
for i in range(N):
a.append(int(input()) - 1)
done = [False] * N
i = 0
ans = 0
while True:
if done[i] == False:
done[i] = True
ans += 1
if a[i] == 1:
break
i = a[i]
else:
ans = -1
break
print(ans)
要素数が 10 の 5乗 を 超える ときの 入力
この問題は、要素数が 10 の 5乗 まである。
この問題の AtCoder での 実行時間 は 225 ミリ秒。
他の 要素数が少ない問題 と比べ 大幅に 実行時間 が 増えている。
このような場合に、sys.stdin を使うと 読み込み時間 が 短縮 される。
import sys
l = [int(i) - 1 for i in sys.stdin]
N = l[0] + 1
a = l[1:]
done = [False] * N
i = 0
ans = 0
while True:
if done[i] == False:
done[i] = True
ans += 1
if a[i] == 1:
break
i = a[i]
else:
ans = -1
break
print(ans)
sys.stdin
input() は 1行ずつ の取得。
sys.stdin は 標準入力 の ファイルオブジェクト。
1行単位ではなく入力まるごとを読み込む為、後者の方が 読み込み時間 が 短縮 される。
後者の場合、sys のインポートが必要となる。
これで AtCoder での 実行時間 が 225 ミリ秒 から 81 ミリ秒 になった。
sys.stdin でも、キーボード から 入力 を与えることができる。
いつも通り python3 プログラムファイル名.py [enterキー]
入力待ちになるので、入力する。
Windows なら [Ctrlキー] + [Zキー]
Linux なら [Ctrlキー] + [Dキー] で 入力の完了 となる。
この問題の入力形式は
N
a1
a2
…
an
もし入力形式が以下のような場合、splitしていない為、エラーになる
N a1 a2 … an
入力については下記のサイトに大変良くまとまっている。
open(0).read().split() や sys.stdin.readline() や sys.stdin.readlines() は
使うことが多くなりそう。
Python3で競技プログラミングする時に知っておきたいtips（入力編）
「リスト」 の切り取り
「文字列」 の 切り取り と同じように
「リスト」[1:] なら インデックス 1 から末尾まで取得できる。
ABC 062 B Picture Frame
H, W = map(int, input().split())
sh = '#'
print(sh * (W + 2))
for i in range(H):
print(sh + input() + sh)
print(sh * (W + 2))
文字 あるいは 「文字列」 * 回数
文字 あるいは 「文字列」 * 回数 で
文字 あるいは 「文字列」 を 回数 だけ 繰り返した 「文字列」 を作ることができる。
この問題では、絵として「文字列」が与えられるので 「#」 で 縁取り をして出力している。
ABC 061 B Counting Roads
N, M = map(int, input().split())
l = [0] * N
for i in range(M):
# 0-indexed
a, b = [int(i) - 1 for i in input().split()]
l[a] += 1
l[b] += 1
for i in range(N):
print(l[i])
N 個の都市、M 本の道路
M 本の道路の起点と終点の都市が与えられる。
各都市から何本の道路が伸びているか求める問題。
知っている知識が邪魔をしてグラフから考えてしまうが
単純に都市をインデックスとし 「リスト」 を インクリメントする と求まる。
ABC 060 B Choose Integers
A, B, C = map(int, input().split())
for i in range(A, A * B + 1, A):
if i % B == C:
flg = True
break
else:
flg = False
print("YES" if flg else "NO")
A の倍数 を B で 割った 余り が C となる 整数が存在するか
着想 が 難しい。
B で 割った 余り が 0 から B - 1 を 循環する ことから
A の 1倍 から A の B倍 までを テストする と 求まる。
ABC 059 B Comparison
A = input()
B = input()
num = len(B) if len(A) < len(B) else len(A)
A = A.rjust(num, '0')
B = B.rjust(num, '0')
print("GREATER" if B < A else "LESS" if A < B else "EQUAL")
100桁まである正整数同士の比較
Python3 では メモリの許す限り大きな値 が 入るので、そのまま比較できる。
そこまでは出来ないとしたらどうするか。
先頭ゼロ埋めの数字 「文字列」 を比較するとよい。
「文字列」.rjust(全体文字数, 埋める文字 ここでは '0')
A = int(input())
B = int(input())
print("GREATER" if B < A else "LESS" if A < B else "EQUAL")
ABC 057 B Checkpoints
INF = 1000000007
N, M = map(int, input().split())
ab = []
for i in range(N):
ab.append([int(i) for i in input().split()])
cd = []
for i in range(M):
cd.append([int(i) for i in input().split()])
for i in range(N):
ans = 0
dst = INF
for j in range(M):
tmp = abs(cd[j][0] - ab[i][0]) + abs(cd[j][1] - ab[i][1])
if tmp < dst:
# 0-indexed
dst = tmp
ans = j + 1
print(ans)
マンハッタン距離 |x| + |y| で 一番近いチェックポイント
この問題では、xy格子上を縦、横に無駄なく歩いた場合の距離がマンハッタン距離。
人がいる座標 (a, b) N 個、チェックポイントの座標 (c,d) M 個を 「リスト」 に格納。
各人ごとに M 個 のチェックポイントをテストすることで、各人のマンハッタン距離が
一番近いチェックポイントを求めることができる。
INF
この問題には関係ないが、INF とは 答えがとても大きくなる時に使う値。
言語間で値の取り扱いに差がでないように、INFで割った余りを解答させる問題が多い。
10 の 9 乗 プラス 7 の場合が多い。
ABC 055 B Training Camp
INF = 1000000007
def modmulti(a, b):
# aとbを掛けた値をmodする(a * b mod p)
res = 0
mod = a % INF
while b > 0:
if b & 1 == 1:
res += mod
if res > INF:
res -= INF
mod <<= 1
if mod > INF:
mod -= INF
b >>= 1
return res
N = int(input())
ans = 1
for i in range(1, N + 1):
ans = modmulti(ans, i)
print(ans)
a と b を掛けた値を INF で 割る
a と b を 掛けた 瞬間に オーバーフロー することがあるので、慎重に計算。
ところが Python3 で 使用できる数の桁数はメモリ依存で
問題の制約上からも、1回の掛け算は問題にならない。
(1 <= N <= 10 の 5乗)
その為、下記のように、素直に1回掛けた値を INF で 割れば事足りる。
INF = 1000000007
def modmulti(a, b):
# aとbを掛けた値をmodする(a * b mod p)
return a * b % INF
N = int(input())
ans = 1
for i in range(1, N + 1):
ans = modmulti(ans, i)
print(ans)
ABC 054 B Template Matching
def match(y, x):
ret = True
for i in range(M):
for j in range(M):
if A[y + i][x + j] != B[i][j]:
ret = False
return ret
N, M = map(int, input().split())
A = []
for i in range(N):
A.append(list(input()))
B = []
for i in range(M):
B.append(list(input()))
flg = False
for i in range(N - M + 1):
for j in range(N - M + 1):
if match(i, j):
flg = True
print("Yes" if flg else "No")
画像B が 画像A に 含まれるか
’.' は 白色、'#' は 黒色 として 「文字列」 が 与えられる。
「文字列」 は 画像 を表していて、画像A が N × N、画像B が M × M。
M <= N で 画像 A は 画像 B 以上 の サイズ。
画像 B が 画像 A に 含まれるか確認する為
画像 A の 各マス に 画像 B の 左上 のマス に 合わせていく。
合わせた後、パターンが一致しているかテストする。
方針は立てやすいが、間違えるポイントがある。
画像 B が はみ出さないように移動する。
画像 B の 左上 の マス は 画像 A の 何マス目 まで移動できるかを考える。
はじめ in range の 終了条件 を N - M としていたが、正しくは N - M + 1。
画像 A の 右端 の マス から マイナス M - 1 の 位置まで
画像 B の 左上 の マス は 移動できる。
次に、パターンが一致しているかテストする。
はじめ A[y + i][y + j] としていたが、正しくは A[y + i][x + j]。
前者、終了条件の間違いについては
例えば 3 × 3 と 2 × 2 くらいの小さなサイズで正確に理解する。
後者、配列のインデックスの間違いは、ケアレスミス
あと X と Y を 完全に逆 に 間違える ケースがあり
完全に逆 は 間違いに 気づきにくい。
ABC 051 B Sum of Three Integers
K, S = map(int, input().split())
ans = 0
for x in range(K + 1):
for y in range(K + 1):
if S < x + y:
break
if (S - x - y) <= K:
ans += 1
print(ans)
2500 × 2500 = 6,250,000 (625万件) 1,650 ミリ秒
0 <= X, Y, Z <= K、X + Y + Z = S を満たす X, Y, Z は何通りあるか。
全探索、大丈夫と思ってやってみたら、危なかった。
実行時間制限 が 2,000 ミリ秒 に 対して、1,650 ミリ秒 だった。
1,000 万件 まで大丈夫だと思っていたが、Python3 では 600 万件で既に危ない。
同様の解答で、C++で 8 ミリ秒、Javaで 91 ミリ秒だった。
ABC 048 B Between a and b ...
def f(n, d):
if n == -1:
return 0
return n // d + 1
a, b, x = map(int, input().split())
print(f(b, x) - f(a - 1, x))
a 以上 b 以下の整数のうち、x で割り切れるものの個数
割った時の 余り が 0 ではなくて、割った時の 商 に注目すれば
全探索する必要が無くなる。
b 以下の整数 のうち x で割り切れる個数から
a より小さい整数 のうち x で割り切れる個数を引くことで求めることができる。
ABC 047 B すぬけ君の塗り絵 2 イージー / Snuke's Coloring 2 (ABC Edit)
W, H, N = map(int, input().split())
minx = 0
maxx = W
miny = 0
maxy = H
for i in range(N):
x, y, a = map(int, input().split())
if a == 1:
minx = max(minx, x)
elif a == 2:
maxx = min(maxx, x)
elif a == 3:
miny = max(miny, y)
else:
maxy = min(maxy, y)
ans = (maxx - minx) * (maxy - miny)
print(ans if minx < maxx and miny < maxy else 0)
最小値は最小値か、最大値は最大値か
xy平面、左下の座標が (0, 0)、右上の座標が (W, H) の白い長方形。
x, y, a が 繰り返し与えられるので、以下の条件で黒く塗りつぶす。
a = 1 のときは長方形の x より小さい領域
a = 2 のときは長方形の x より大きい領域
a = 3 のときは長方形の y より小さい領域
a = 4 のときは長方形の y より大きい領域
塗りつぶしが終わった後の白い部分の面積を求める問題。
長方形の x の 最小値 と 最大値、y の 最小値 と 最大値 を 更新しておき
最後に出力すればよいが、はじめ print(0 if ans < 0 else ans) として失敗した。
このプログラムでの更新の仕方の場合、
最小値が最小値、最大値が最大値であるとは限らず
x と y 両方の最小値、最大値が逆ならば、マイナス × マイナス = プラス となる為
上記の判定は間違いとなる。
丁寧に x も y も 最小値 < 最大値 を確認すべきだった。
ABC 045 B 3人でカードゲームイージー / Card Game for Three (ABC Edit)
from collections import deque
SA = deque(list(input()))
SB = deque(list(input()))
SC = deque(list(input()))
turn = 'a'
while True:
if turn == 'a' and len(SA) == 0:
ans = 'A'
break
elif turn == 'b' and len(SB) == 0:
ans = 'B'
break
elif turn == 'c' and len(SC) == 0:
ans = 'C'
break
if turn == 'a':
turn = SA.popleft()
elif turn == 'b':
turn = SB.popleft()
else:
turn = SC.popleft()
print(ans)
deque 先入れ先出し popleft()
両端キューというデータ構造で、先入れ先出しをする。
popleft() で 先入れ先出し になる。
pop() で 後入れ先出し になる。
「リスト」にもpop()があるが、要素数が増えるほど、dequeの方が効率的に動作する。
ここでは、「リスト」の要素をdequeに格納しているが
appendで1要素ずつ右側から要素を追加することもできる。
deque を 使う為には collections から deque を インポートする必要がある。
ABC 043 B バイナリハックイージー / Unhappy Hacking (ABC Edit)
from collections import deque
s = input()
q = deque()
for c in s:
if c == 'B':
if q:
q.pop()
else:
q.append(c)
for i in range(len(q)):
print(q.popleft(), end='')
print()
deque 後入れ先出し pop()
両端キューというデータ構造で、後入れ先出しをする。
deque を 使う為には collections から deque を インポートする必要がある。
ABC 040 B □□□□□
n = int(input())
mn = 100001
for i in range(1, n + 1):
if n < i * i:
break
dif = abs(i - n // i)
rem = n - i * (n // i)
mn = min(mn, dif + rem)
print(mn)
for ～ in range の 終了条件
1メートル四方の タイル n 枚 を なるべく正方形になるように並べる。
縦と横の長さの差の絶対値と、余ったタイルの枚数の和を最小にする問題。
これまでにもあったが
終了インデックスの数自体は for の処理の対象にならない。
n ではなく n + 1 となる。
間違えやすいので注意する。
1 から n までテストする。
小数点を扱う必要はないので 割るときは // を使う。
縦と横の長さの差の絶対値は abs (i - n // i)
余ったタイルの枚数は n - i * (n // i) で求めることができる。
ABC 039 B エージェント高橋君
import math
X = int(input())
print(math.floor(X ** (1 / 4)))
4乗根を求める
a ** b で a の b 乗。
a ** (1 / 2) = a ** 0.5 で 平方根。
a ** (1 / 4) = a ** 0.25 で 4乗根。
小数点の切り捨てを floor で行う。
floor を 使うときには、math の インポート が 必要となる。
ABC 036 B 回転
N = int(input())
s = []
for i in range(N):
s.append(list(input()))
t = [['' for i in range(N)] for j in range(N)]
for i in range(N):
for j in range(N):
t[j][N - i - 1] = s[i][j]
for i in range(N):
print(''.join(t[i]))
「リスト」 の 「リスト」 を 指定した値 ならびに 要素数 で 初期化 する
ここでは
t = [['' for i in range(N)] for j in range(N)] で
N行N列の空文字の 「リスト」 の 「リスト」 を初期化している。
「リスト」 の 「リスト」 を初期化したことにより
インデックス指定の代入で値を更新することができる。
t[j][N - i - 1] = s[i][j]
ABC 035 B ドローン
S = input()
T = int(input())
x, y, q = 0, 0, 0
for c in S:
if c == 'L':
x -= 1
elif c == 'R':
x += 1
elif c == 'D':
y -= 1
elif c == 'U':
y += 1
else:
q += 1
dst = abs(x) + abs(y)
mx = dst + q
mn = dst - q
if mn < 0:
mn = 0
if (q - dst) % 2:
mn = 1
print(mx if T == 1 else mn)
マンハッタン距離の最小
xy平面、原点にドローンがあり、移動を指示する「文字列」が与えられる。
'L' x軸方向に-1
'R' x軸方向に+1
'D' x軸方向に-1
'U' x軸方向に+1
これとは別に、'?' が ある。
それぞれの '?' を 'L' 'R' 'D' 'U' のうちいずれも入れることができる時
マンハッタン距離の最大値と最小値を求める問題。
最小値を求めるところで間違えた。
戻り過ぎて原点を通り越してしまう場合を見落としやすい。
原点を通り越してしまう場合は、その残りの距離が偶数ならば、行って戻るでゼロになるが
奇数ならば、完全に戻ることができず、1になる。
ABC 032 B 高橋君とパスワード
s = input()
k = int(input())
st = set()
if k <= len(s):
for i in range(len(s) - k + 1):
st.add(s[i:i + k])
print(len(st))
部分「文字列」がいくつあるか
「文字列」と長さが与えられるので考えられる部分「文字列」の数を求める。
長さは「文字列」全体の長さより大きい場合があると問題文に明記されている。
長さが「文字列」全体の長さよりも大きい場合、部分「文字列」の数はゼロとなる。
その条件 if k <= len(s) を入れるのを忘れていた。
「文字列」の切り取り、「文字列」の長さがkならば、s[i:i + k] となる。
終了インデックスの文字自体は含まれないことに注意する。
ABC 030 B 時計盤
n, m = map(int, input().split())
n = n - 12 if 12 < n else n
dn = 360 / 12 * n + 30 / 60 * m
dm = 360 / 60 * m
d = max(dn, dm) - min(dn, dm)
print(min(d, 360 - d))
時計の長針と短針のなす角度のうち小さい方
0時0分から23時59分までの 時間 n、分 m が与えられるので
時計の長針と短針のなす角度のうち小さい方を出力する。
時間が12時間より大きければ、まず12を引いておく。
角度を求める基準を 真上 0 時 0 分 とした。
長針と短針の角度の大きい方から、小さい方を引く。
その角度 と 360 から その角度 を 引いたもののうち、小さい方を出力する。
絶対誤差 または 相対誤差 が 10 の -4乗以下とあるので
Python3 の 浮動小数点数割り算 「/」 とした。
ABC 027 B 島と橋
N = int(input())
a = [int(i) for i in input().split()]
if sum(a) % N != 0:
print(-1)
else:
bridge = 0
person = 0
num = 0
average = sum(a) // N
for i in range(N - 1):
person += a[i]
num += 1
if average != person // num or person % num != 0:
bridge += 1
else:
num = 0
person = 0
print(bridge)
橋を架けて人の往来を作ることで島の人口をまったく同じにする
横一列に並んだN個の島があり、各島の現在の人口が与えられる。
橋を架けて人の往来を作ることで島の人口をまったく同じにすることはできるか。
できる場合、架ける必要のある最小の橋の数を求める問題。
全ての島の人口を足して N で割った時に、余りが出るならば、同じに出来ない。
全体平均をもとめておく。
左から順番に見ていくとき、次の島の人口を見る前に、次の島との間に
橋を架ける必要があるかどうかは確定できる。
今見ている島までの人口が、平均と全く同じならば、
次の島との間に橋を架ける必要がない。
今見ている島までの人口の平均を求める時に
割り算の余りがゼロでない場合は、橋を架ける必要がある。
商 (平均) だけに注目していると間違えるので注意する。
ABC 026 B N重丸
import math
N = int(input())
l = []
for i in range(N):
l.append(int(input()))
l.sort(reverse=True)
ans = 0
for i in range(N):
circle = l[i] * l[i] * math.pi
if i % 2 == 0:
ans += circle
else:
ans -= circle
print(ans)
定数 math.pi
原点を中心とした、全て半径が異なるN個の円を書く。
外側から、赤白交互に色を塗った場合、赤く塗られる部分の面積を求める問題。
与えられる半径の大きさの順番で半径が与えられるわけではないので
降順ソートしておく。
外から 0個目の円、1個目の円、・・、N - 1 個目の円という数え方をするとき
その数を2で割った時の余りがゼロになる時に、円の面積を足す。
それ以外の時に、円の面積を引く。
円周率のパイは、Python3 の math.pi を使うことができる。
math.pi を 使う為には math を インポートする必要がある。
ABC 022 B Bumble Bee
N = int(input())
done = [False] * 100000
ans = 0
for i in range(N):
# 0-indexed
A = int(input()) - 1
if not done[A]:
done[A] = True
else:
ans += 1
print(ans)
ミツバチによる花の受粉
ミツバチが訪れた花の種類が与えられる。
ミツバチが訪れた花の数は N 個。
訪れたかどうかを、bool型 「リスト」 として用意しておく。
はじめ 「リスト」 の要素数を N としていたが、実行時エラー になった。
問題文をよく読むと、与えられる花の種類が N 以下で与えられる保証が見つからない。
上限値の 10 の 5 乗 で 「リスト」 を準備すると、正解となった。
ABC 019 B 高橋くんと文字列圧縮
s = input()
ans = ''
cnt = 1
c = s[0]
for i in range(1, len(s)):
if c == s[i]:
cnt += 1
else:
ans += c + str(cnt)
cnt = 1
c = s[i]
print(ans + c + str(cnt))
「文字列」と数字をくっつけた文字列を作る
「文字列」 と 数字 をくっつけた 「文字列」 を作るとき
あらかじめ str(数字) とすることで、数字を 「文字列」 としておく。
ABC 017 B choku語
import re
X = input()
while 0 < len(X):
num = len(X)
X = re.sub("ch$", "", X)
X = re.sub("o$", "", X)
X = re.sub("k$", "", X)
X = re.sub("u$", "", X)
if num == len(X):
break
print("NO" if len(X) else "YES")
正規表現をつかって行末の「文字列」が一致する時に、その「文字列」を除去する
正規表現で $ は 行末。
re.sub(正規表現パターン, 置換先「文字列」, 処理対象の「文字列」)
このとき 処理対象の 「文字列」 自体は置換されない為、変数に保持しておくことに注意。
ABC 014 B 価格の合計
n, X = map(int, input().split())
a = [int(i) for i in input().split()]
ans = 0
for i in range(X.bit_length()):
if X % 2:
ans += a[i]
X //= 2
print(ans)
商品の選び方を2進法で表現した数字を10進法で表した場合の価格の合計
問題文がとても詳しく、このやり方が初めてならば是非読みたい問題文となっている。
数字.bit_length() は 数字を2進法で表したときに必要な桁数。
1桁ずつ1が立っているか確認していき、1が立っていたらその商品の価格を足す。
ABC 011 B 名前の確認
S = input()
print(S.capitalize())
最初の文字を大文字にし、残りを小文字にする
ABC 009 B 心配性な富豪、ファミリーレストランに行く。
N = int(input())
A = set()
for i in range(N):
A.add(int(input()))
A = sorted(A, reverse=True)
print(A[1])
「集合」 を 降順ソート する
「集合」 を A とした場合
A = sorted(A, reverse=True) で 降順ソートになる。
ここで注意したいのが、ソート前の A は 「集合」 だが
ソート後の A は 「リスト」 になること。
ABC 008 B 投票
from collections import defaultdict
N = int(input())
S = defaultdict(lambda: 0)
for i in range(N):
S[input()] += 1
# value 降順
S = sorted(S.items(), key=lambda x:x[1], reverse=True)
print(S[0][0])
「辞書」 の value を 降順ソート する
「辞書」 を S とした場合
S = sorted(S.items(), key=lambda x:x[1], reverse=True) で
降順ソートになる。
ソート後の S は key と value の 「タプル」 が 「リスト」 に格納されたものになる。
print(S[0][0]) の 最初 の [0] は リストの 0 の インデックス の 要素 を表していて
次 の [0] は タプル の 0 の インデックス の 要素 (辞書のときの key) を表す。
タプルは丸括弧。
空のタプルをつくる。
t = ()
1個の要素を持つタプルを定義する場合には、末尾にカンマをつける。
t = 'a',
複数の場合には、最後の要素の後ろにカンマを付けなくてもよい。付けてもよい。
t = 'a', 'b'
タプルは生成後は更新できない（イミュータブル）。
ABC 006 B トリボナッチ数列
INF = 10007
def modadd(a, b):
# aとbを足した値をmodする(a + b mod p)
return (a + b) % INF
def tribonacci(n):
a = []
a.append(0)
a.append(0)
a.append(1)
if n < 2:
return a[1]
if n == 3:
return a[2]
for i in range(3, n):
a.append(
modadd(modadd(a[i - 1], a[i - 2]), a[i - 3]))
return a[n - 1]
n = int(input())
print(tribonacci(n))
トリボナッチ数列 の 第 n 項 を INF で割った余りを求める
ABC 004 B 回転
c = []
for i in range(4):
c.append(list(input()))
for i in range(2):
c[i], c[-i-1] = reversed(c[-i-1]), reversed(c[i])
for i in range(4):
print(''.join(c[i]))
文字の 「リスト」 を 逆順 に 並び替える
この問題では、4 × 4 の 文字 の 「リスト」 を 180度回転させている。
reversed(「リスト」) は、「リスト」 の 要素 の 並び を 今 の 並び の 逆順 にする。
ABC 003 B AtCoderトランプ
a = "atcoder"
S = input()
T = input()
flg = True
for s, t in zip(S, T):
if s == t:
continue
if s == '@' and t != '@' and t in a:
continue
elif s != '@' and t == '@' and s in a:
continue
else:
flg = False
break
print("You can win" if flg else "You will lose")
for で 複数の 「文字列」 から 1 文字ずつ取り出すことが出来る
for s, t in zip(S, T) で 「文字列」 S と T から 1文字ずつ取り出している。
同じやり方で、複数の 「リスト」 から 1 要素ずつ取り出すこともできる。
ABC 002 B 罠
a = "aeiou"
W = input()
for i in range(len(W)):
if W[i] not in a:
print(W[i], end='')
print()
if 文字 not in 「文字列」
「文字列」 に 文字があるかどうかテストする
論理式の否定 は not を 使う。
論理式の否定 で ! を使うとエラーになる。
bool型 「リスト」l を 条件に使うような場合
if !l[i]：だとエラーになる。
if not l[i]:が正しい。
終わりに
ABC C問題 をすべて解き終わった時には、また別の記事で書きたいと思います。