AtCoder Programming Guide for beginners(APG4B) EX16 ~ EX26の回答
~ AtCoder 300代の貧弱プログラマが脳筋コードでとくAPG4B
概要
なぜEX16 ~ 26の範囲なのか?
APG4BをPythonで解いてみたサイトを見てみたが、EX16 ~ EX21までしか解かれているものがなかったため
自分で解いたほうが早くね??と考えたのが始まり
まぁ、ごちゃごちゃいうよりさっさと解いていく
EX16 - 隣り合う同じ値を探す -
この問題を解いてく
// Aの値をlist型で受け取る
A = list(map(int, input().split()))
// Aの要素数-1回だけループする
for i in range(len(A) - 1):
// リストAのi番目の要素とi+1番目の要素が等しいか判定する
if A[i] == A[i+1]:
// 隣り合う同じ値があったためYESを出力する
print("YES")
// プログラムを終了させる
exit()
// 隣り合う同じ値がなかったためNOを出力する
print("NO")
EX16の補足
for文のrangeをAの配列の要素数-1回分ループしているが、問題は5つの要素で固定しているため、
A = list(map(int, input().split()))
for i in range(4):
if A[i] == A[i+1]:
print("YES")
exit()
print("NO")
でも大丈夫である。
※ もう少し簡略化して書くとするならば、
A = list(map(int, input().split()))
// 隣り合う同じ値が1組でも存在すればTrueを返す
flag = any(A[i] == A[i+1] for i in range(4))
if flag:
print("YES")
else:
print("NO")
と書くこともできる。
EX17 ~ 果物屋さんでお買い物
この問題を解いていく
// N, S の値を受け取る
N, S = map(int, input().split())
// Aの値をlist型で受け取る
A = list(map(int, input().split()))
// Pの値をlist型で受け取る
P = list(map(int, input().split()))
// Sと同じ値段になった組み合わせの個数をカウントする変数
count = 0
for a in A:
for p in P:
// (aの値段 + pの値段) が 指定された値段Sと等しいか判別する
if a + p == S:
// 同じの場合カウントを1増やす
count += 1
// カウントを出力する
print(count)
EX17の補足
EX16ではfor i in range(指定範囲)を使っていたが、リストから直接値を受け取ることができるため、for i in リスト名を使うこともできる。
※ 今回は例として i を使っているが、 i の部分は任意の変数名で大丈夫である
EX18 ~ ゲーム大会 ~
この問題を解いていく
NとMの値を受け取る
N, M = map(int, input().split())
l = []
// N行N列のリストlの初期化を行う
for i in range(N):
tmp = []
for j in range(N):
tmp.append('-')
l.append(tmp)
// M試合文ループする
for _ in range(M):
// A, Bの値を受け取る
A, B = map(int, input().split())
// リストlのA-1行B-1列目をoにする
l[A-1][B-1] = 'o'
// リストlのB-1行A-1列目をxにする
l[B-1][A-1] = 'x'
// N行N列分ループする
for i in range(N):
for j in range(N):
// i行目の最後の要素ではないか判別する
if j != N - 1:
// i行目の最後の要素ではない場合 -> リストlのi行j列目の要素と空白文字を出力する
print(l[i][j], end=' ')
else:
// i行目の最後の要素の場合 -> リストlのi行j列目の要素を出力して改行する
print(l[i][j])
EX18の補足
この問題は簡略化することができる。以下が簡略したコードである
N, M = map(int, input().split())
// リスト内包表記を使用したリストlの初期化
l = [['-' for _ in range(N)] for _ in range(N)]
for _ in range(M):
A, B = map(int, input().split())
l[A-1][B-1] = 'o'
l[B-1][A-1] = 'x'
for l_i in l:
// リストを空白文字つきで出力する
print(*l_i)
Pythonリスト内包表記の使い方を参考にすると良い
print文で使用している記法は、例えば以下のリスト
arr = [1, 2, 3, 4, 5]
があったとする。この時print(*arr)を実行すると、
1 2 3 4 5
と出力される。しかも最後の要素の後ろには空白文字は出力されないため覚えておくといいだろう
EX19 ~ 九九の採点 ~
この問題を解いていく
// リストarrに2次元配列の入力を受け取る
arr = [list(map(int, input().split())) for _ in range(9)]
// 正解数をカウントする変数を宣言
correct_cnt = 0
// 不正解数をカウントする変数を宣言
wrong_cnt = 0
// 九九なので9 × 9 回ループする
for i in range(1, 10):
for j in range(1, 10):
// arrのi行j列目の値がi×jと等しいか判別する
if arr[i-1][j-1] == i * j:
// 等しい場合は正解数を1増やす
correct_cnt += 1
else:
// 違う場合は不正解数を1増やす
wrong_cnt += 1
// 間違っていた場所を正しい値に変更する
arr[i-1][j-1] = i*j
// 正しい九九表を出力する
for a in arr:
print(*a)
// 正解数を出力する
print(correct_cnt)
// 不正解数を出力する
print(wrong_cnt)
EX19の補足
最初この問題を解いた時、
arr = [list(map(int, input().split())) for _ in range(9)]
correct_cnt = 0
wrong_cnt = 0
correct_arr = []
for i in range(1, 10):
tmp_arr = []
for j in range(1, 10):
tmp_arr.append(i*j)
if arr[i-1][j-1] == i * j:
correct_cnt += 1
else:
wrong_cnt += 1
correct_arr.append(tmp_arr)
for ca in correct_arr:
print(*ca)
print(correct_cnt)
print(wrong_cnt)
以上のコードのように新しい配列(リスト)に九九を入れて出力していたが、問題文を見てみると、誤った値が書き込まれたマスを正しい値に書き直す とあるため、新しく配列を生成するのではなく元の配列を更新する形に変更した。
EX20 ~ 報告書の枚数 ~
この問題を解いていく
def count_report_num(children, x):
if children.get(x) == None:
return 1
sum = 0
for c in children[x]:
sum += count_report_num(children, c)
sum += 1
return sum
N = int(input())
arr = list(map(int, input().split()))
p = [-1]
for i in range(1, N):
p.append(arr[i-1])
key = list(dict.fromkeys(p))
children = {}
for i in key:
value_list = []
for j in range(N):
if i == p[j]:
value_list.append(j)
children[i] = []
for k in value_list:
children[i].append(k)
for i in range(N):
print(count_report_num(children, i))
EX20の補足
今回の問題は解答が思いつかなかっため、C++の回答例を参考にPythonコードに起こした。
EX21 ~ 計算量の見積もり ~
この問題を解いていく
def f0(N):
return 1
def f1(N, M):
s = 0
for i in range(N):
s += 1
for i in range(M):
s += 1
return s
def f2(N):
s = 0
for i in range(N):
t = N
cnt = 0
while (t > 0):
cnt += 1
t //= 2
s += cnt
return s
def f3(N):
s = 0
for i in range(3):
for j in range(3):
s += 1
return s
def f4(N):
s = 0
for i in range(N):
for j in range(N):
s += i + j
return s
def f5(N, M):
s = 0
for i in range(N):
for j in range(M):
s += i + j
return s
N, M = map(int, input().split())
a0, a1, a2, a3, a4, a5 = -1, -1, -1, -1, -1, -1
// 計算量が多いものをコメントアウトする
a0 = f0(N)
a1 = f1(N, M)
a2 = f2(N)
a3 = f3(N)
# a4 = f4(N)
# a5 = f5(N, M)
print(f'f0: {a0}')
print(f'f1: {a1}')
print(f'f2: {a2}')
print(f'f3: {a3}')
print(f'f4: {a4}')
print(f'f5: {a5}')
EX21の補足
Pythonは107までは計算できるが、108になるとTLEが出てしまうので注意が必要
計算量
- f0の場合 : O(1) = 1 のため、TLEが出る事はない
- f1の場合 : O(N + M) = 106 + 102 < 108 のため、TLEが出る事はない
- f2の場合 : O(NlogN) = 106 * log106 ≒ 106 * 2 * 101 < 108のため、 TLEが出る事はない
- f3の場合 : O(1) = 1 のため、 TLEが出る事はない
- f4の場合 : O(N2) = 106 * 106 > 108 のため、TLEが出る
- f5の場合 : O(NM) = 106 * 102 = 108 のため、TLEが出る
基本的にAtCoderではO(N2)の計算量になるとTLEが出ると考えていいだろう
ただしN<104 程度だとO(N2)でもTLEが出る事はほとんどない(<108になるため)
そのため入力上限を見て適宜計算量を考えていこう
EX22 ~ 2つ目の値でソート ~
この問題を解いていく
N = int(input())
// リスト型とリスト内包表記を使用して二次元配列を作成する
arr = [list(map(int, input().split())) for _ in range(N)]
// lambda(無記名関数)を使用して、リストの2番目の要素でソートをかける
arr = sorted(arr, key=lambda x: x[1])
for a in arr:
print(*a)
EX22の補足
lambda式と呼ばれる無記名関数を使用して2番目の要素でソートをかけた
Pythonのlambda（ラムダ式、無名関数）の使い方を参考にすると良いだろう
sorted()は()内に指定されたlistやsetなどをソートした配列を返す関数となっている
同様の処理を行うsort()があるが、こちらはもとのlistやsetをソートする関数となっている
Pythonでリストをソートするsortとsortedの違いを参考にすると良いだろう
ちなみに、sortの計算量はO(NlogN)となっている
EX23 ~ 最頻値 ~
この問題を解いていく
// collectionsライブラリからCounterメソッドをインポート
from collections import Counter
N = int(input())
arr = list(map(int, input().split()))
arr = Counter(arr)
arr = sorted(arr.items(), key=lambda x: x[1], reverse=True)
print(*arr[0])
EX23の補足
今回は頻度を数えるためにcollectionsライブラリからCounterメソッドをインポートした
PythonのCounterでリストの各要素の出現個数をカウントを参考にすると良いだろう
sorted()の中でreverse=Trueを入れることで降順で並び替えることができる
EX24 ~ 時計の実装 ~
この問題を解いていく
// Clockクラスを定義する
class Clock:
// Clockオブジェクトを生成した際に自動的に実行される
def __init__(self):
self.hour = 0
self.minute = 0
self.second = 0
// 時間を設定する
def set(self, h, m, s):
self.hour = h
self.minute = m
self.second = s
// HH:MM:SS表記にする
def to_str(self):
time = f'{self.hour:02d}:{self.minute:02d}:{self.second:02d}'
return time
// 時間を進めたり戻したりする
def shift(self, diff_second):
multiple = 1
if diff_second < 0:
multiple = -1
diff_second *= multiple
diff_hour = int(diff_second / (60 * 60))
diff_minute = int((diff_second / 60) % 60)
diff_second = diff_second % 60
if multiple > 0:
self.second += diff_second
if self.second >= 60:
self.second -= 60
self.minute += 1
self.minute += diff_minute
if self.minute >= 60:
self.minute -= 60
self.hour += 1
self.hour += diff_hour
if self.hour >= 24:
self.hour -= 24
else:
self.second -= diff_second
if self.second < 0:
self.second += 60
self.minute -= 1
self.minute -= diff_minute
if self.minute < 0:
self.minute += 60
self.hour -= 1
self.hour -= diff_hour
if self.hour < 0:
self.hour += 24
h, m, s = map(int, input().split())
diff_second = int(input())
clock = Clock()
clock.set(h, m, s)
print(clock.to_str())
clock.shift(diff_second)
print(clock.to_str())
EX24の補足
文字列に変数の値を組み込むときにformatを指定している
またその際に、0埋めを行っている
Pythonで文字列・数値をゼロ埋め（ゼロパディング）を参考にすると良いだろう
さらに、今回はClockクラスを定義している
EX25 ~ 集合の操作 ~
この問題を解いていく
N = int(input())
A = set(map(int, input().split()))
M = int(input())
B = set(map(int, input().split()))
op = list(input().split())
if len(op) > 1:
x = int(op[1])
command = op[0]
if command == 'intersection':
print(* (A & B))
elif command == 'union_set':
print(* (A | B))
elif command == 'symmetric_diff':
print(* (A ^ B))
elif command == 'subtract':
A.remove(x)
print(*A)
elif command == 'increment':
A = list(map(lambda a: a + 1 - 50 if a + 1 >= 50 else a + 1, A))
print(*sorted(A))
elif command == 'decrement':
A = list(map(lambda a: a - 1 + 50 if a - 1 < 0 else a - 1, A))
print(*sorted(A))
EX25の補足
setが持っている操作を使えばいいだけなのでそこまで補足するものはないと思う
Python, set型で集合演算（和集合、積集合や部分集合の判定など）を参考にすると良いだろう
EX26 ~ 電卓を作ろう ~
この問題を解いていく
from collections import defaultdict
# command = int
def cmd_int(cmd, intdict):
num = 0
op = cmd[1]
i = 1
while True:
if i == len(cmd) or cmd[i] == ';':
break
if cmd[i] == '+':
if cmd[i+1] in intdict:
num += intdict[cmd[i+1]]
i += 2
else:
num += int(cmd[i+1])
i += 2
elif cmd[i] == '-':
if cmd[i+1] in intdict:
num -= intdict[cmd[i+1]]
i += 2
else:
num -= int(cmd[i+1])
i += 2
elif cmd[i] in intdict:
num += intdict[cmd[i]]
i += 1
elif cmd[i].isdecimal():
num += int(cmd[i])
i += 1
else:
i += 1
return op, num
# command = vec
def cmd_vec(cmd, vecdict, intdict):
vec = []
op = cmd[1]
ops = []
vec_list = []
for i in range(1, len(cmd)):
tmp = []
if cmd[i] == ';':
break
if cmd[i] == '[':
for j in range(i, len(cmd)):
if cmd[j] == ']':
i = j
vec_list.append(tmp)
break
elif cmd[j] == ',' or cmd[j] == '[':
continue
elif cmd[j] in intdict:
tmp.append(intdict[cmd[j]])
else:
tmp.append(int(cmd[j]))
elif cmd[i] in vecdict:
vec_list.append(vecdict[cmd[i]])
elif cmd[i] == '+' or cmd[i] == '-':
ops.append(cmd[i])
if ops == []:
return op, vec_list[0]
i, j = 0, 0
res = []
while True:
if i == len(vec_list):
break
if i == 0:
if ops[j] == '+':
res = [x + y for (x, y) in zip(vec_list[i], vec_list[i+1])]
i += 2
j += 1
elif ops[j] == '-':
res = [x - y for (x, y) in zip(vec_list[i], vec_list[i+1])]
i += 2
j += 1
else:
if ops[j] == '+':
res = [x + y for (x, y) in zip(res, vec_list[i])]
i += 1
j += 1
elif ops[j] == '-':
res = [x - y for (x, y) in zip(res, vec_list[i])]
i += 1
j += 1
return op, res
# command = print_int
def cmd_print_int(cmd, intdict):
num = 0
i = 1
while True:
if i == len(cmd) or cmd[i] == ';':
break
if cmd[i] == '+':
if cmd[i+1] in intdict:
num += intdict[cmd[i+1]]
i += 2
else:
num += int(cmd[i+1])
i += 2
elif cmd[i] == '-':
if cmd[i+1] in intdict:
num -= intdict[cmd[i+1]]
i += 2
else:
num -= int(cmd[i+1])
i += 2
else:
if cmd[i] in intdict:
num += intdict[cmd[i]]
i += 1
else:
num += int(cmd[i])
i += 1
print(num)
# command = print_vec
def cmd_print_vec(cmd, vecdict, intdict):
vec_list = []
ops = []
for i in range(1, len(cmd)):
tmp = []
if cmd[i] == ';':
break
if cmd[i] == '[':
for j in range(i, len(cmd)):
if cmd[j] == ']':
i = j
vec_list.append(tmp)
break
elif cmd[j] == ',' or cmd[j] == '[':
continue
elif cmd[j] in intdict:
tmp.append(intdict[cmd[j]])
else:
tmp.append(int(cmd[j]))
elif cmd[i] in vecdict:
vec_list.append(vecdict[cmd[i]])
elif cmd[i] == '+' or cmd[i] == '-':
ops.append(cmd[i])
i, j = 0, 0
res = []
if ops == []:
print('[ ', end='')
print(*vec_list[0], end='')
print(' ]')
return
while True:
if i == len(vec_list):
break
if i == 0:
if ops[j] == '+':
res = [x + y for (x, y) in zip(vec_list[i], vec_list[i+1])]
i += 2
j += 1
elif ops[j] == '-':
res = [x - y for (x, y) in zip(vec_list[i], vec_list[i+1])]
i += 2
j += 1
else:
if ops[j] == '+':
res = [x + y for (x, y) in zip(res, vec_list[i])]
i += 1
j += 1
elif ops[j] == '-':
res = [x - y for (x, y) in zip(res, vec_list[i])]
i += 1
j += 1
print('[ ', end='')
print(*res, end='')
print(' ]')
# main部分
N = int(input())
intdict = defaultdict(int)
vecdict = defaultdict(int)
for _ in range(N):
cmd = input().split(' ')
if cmd[0] == 'int':
op, num = cmd_int(cmd, intdict)
intdict[op] = num
elif cmd[0] == 'vec':
op, vec = cmd_vec(cmd, vecdict, intdict)
vecdict[op] = vec
elif cmd[0] == 'print_int':
cmd_print_int(cmd, intdict)
elif cmd[0] == 'print_vec':
cmd_print_vec(cmd, vecdict, intdict)
EX26の補足
この問題は基本的に今までの知識の総復習のようなものと考えて良いだろう
今回の解くコツとして、最小の機能ごとに作っていくことが重要である
今回の場合
- 変数を出力する機能
- 配列を出力する機能
- 変数を定義(計算)する機能
- 配列を定義(計算)する機能
この4つの機能を段階的に実装すれば良かった
今回自分が書いたコードには、同じような処理をするところがあったりしたので、そこをさらに関数として切り分けた方が簡潔になる
そうすることによって、
- コードの総量が減り、見やすくかつ管理がしやすくなる
- コードを打つ量が減るため、負担が減る
- 間違っていた場合の手間が減る
などのメリットがあるため、繰り返す処理がある場合は関数化した方が良いと思う(個人の感想なので人それぞれ組みやすいコードを組む方が良い)
補足2
ただ、今までに紹介していなかったcollectionsライブラリのdefaultdictについて少し紹介する
このdefaultdictは存在しないキーがあってもデフォルト値が返ってくる辞書型風のデータ構造である
使い方の例
from collections import defaultdict
# デフォルトの型をint型にする
d1 = defaultdict(int)
print(f'd1: {d1[0]}') # => d1: 0
d2 = defaultdict(lambda : 100)
print(f'd2: {d2[1]}') # => d2: 100
詳しい使い方はPython defaultdict の使い方を参考にすると良いだろう
zip関数とリスト内包表記を使うことで、2つのリストで演算を行うことができる
その例
li1 = [1, 2, 3]
li2 = [4, 5, 6]
add_li1_li2 = [x + y for (x, y) in zip(li1, li2)] // li1の要素とli2の要素の足し算
print(add_li1_li2) // => [5, 7, 9]
mul_li1_li2 = [x * y for (x, y) in zip(li1, li2)] // li1の要素とli2の要素の掛け算
print(mul_li1_li2) // => [4, 10, 18]
もっと詳しく知りたい -> 【python】リスト(list)の要素の四則演算、平均の計算方法【要素ごと、zip、map、lambda】を参考にすると良いだろう
