2/16 AtCoder(入力受け取りまとめ、数列の部分和、ユークリッドの互除法)/ss
解くに至った問題(15問)
キーエンスプログラミングコンテスト2019:A,B
エイジングプログラミングコンテスト2019:A,B
CADDi 2018 for Beginners:A
Tenka 1 Programmer Beginner Contest:2018A,B/2017B
CODE FESTIVAL 2016 Final:A
第5回 ドワンゴからの挑戦状 予選:A
AGC:023A/030A
ABC:058B/118A,B
listの中から未ACの100点問題が消えました わいわい
CODE FES A
また入力で詰まった 一回入力を受け取る方法を整理しておいた方がよさそう
思いつく限りでは、競プロC問題くらいまでで登場する入力のタイプは
① 'A'や'BC'といった文字列(一行、一列)
②1,23,456といった数字(一行、一列)
③'A BC'や'1 23'といったスペース区切りの文字列(一行、複数列)
④'A BC DEF......' や '1 2 3 4 5 .......'といったリストで受け取った方がいいもの(一行、複数列)
⑤1
2
3......という縦に並んだ入力(複数行、一列)
⑥1 2 3
4 5 6
7 8 9 といったような数字の行列(複数行、複数列)
⑦AB CD EF
GH IJ KL
MN OP QR といったような文字列の行列(複数行、複数列)
くらい(ほかにもありそうだけど) pythonでの受け取り方を整理
[3/1 ⑧模様の受け取りを追加しました]
① 'A'や'BC'といった文字列(一行、一列)
S = input()
②1,23,456といった数字(一行、一列)
N = int(input())
③'A BC'や'1 23'といったスペース区切りの文字列(一行、複数列)
文字列であれば、
S,T = input().split()
数字であれば、
N,M = map(int,input().split())
とする
④'A BC DEF......' や '1 2 3 4 5 .......'といった、スペース区切りで要素数が多いため、リストで受け取った方がいいもの(一行、複数列)
文字列であれば、
L = input().split() か L = list(input().split()) (L = [input().split()]でもよい)
が使える 出力はどちらも同じなので前者を推します
数字の列であれば
L = list(map(int,input().split()))
でよい
⑤1
2
3......という縦に並んだ入力(複数行、一列)
文字列であれば、数がすくなければ、
S = input()
T = input()
......
と個々に受け取ることができる
数が大きくなった時は、リストに入れることを考えて、
L =
for i in range(行の数):
L.append(input())
とするのがよい
数字はinput() を int(input())に変えればよい
⑥1 2 3
4 5 6
7 8 9 といったような数字の行列(複数行、複数列)
L =
for i in range(行数):
L.append(list(map(int,input().split())))
とすれば、
L = [[1,2,3],[4,5,6],[7,8,9]]
となる
リストの要素のは、
1は L[0][0]、6はL[1][2]などとあらわされる
L.sort()とするとLの一番目の要素(L[j][0])で小さい順にソートされる
⑦AB CD EF
GH IJ KL
MN OP QR といったような文字列の行列(複数行、複数列)
L =
for i in range(行数):
L.append(input().split())
これで、L = [['AB','CD',EF'],['GH','IJ','KL'],['MN','OP','QR']]
となる
⑧
#.#
.#.
#.# みたいに#と.でマスが塗ってあるみたいなのを要素ごとで受け取りたい
L =
for i in range(N): #Nは行数
L.append(list(input()))
とすれば、
L = [['#','.','#'],['.','#','.'],['#','.','#']]
と受け取ってくれる
[注意]input().split()ってやると[[#.#],[.#.],[#.#]]と入ってしまう
AGC023A
数列の部分和で0になる箇所がいくつあるかを数える問題 わからなかったんだけど解説見て賢すぎてハゲ散らかした
第0項から各項までの和をリストに加えていく この中で等しいものを二つ選ぶと、0~i項と0~j項の差は0→i~j項という部分列の和は0になる 結局そこまでの和が同じものの中から二つ選んでくる場合の数の総和と同じになる
かしこい かしこい かしこい むかつく むかつく むかつく
解けなかった問題
ABC118C
今日のABCのC問題 無限にバグらせて通らなかった
一番最初に提出したのは、リストをソートして最小のやつで割り切れなかったら1を、割り切れたらリストの最小を返すやつ 3つ通らないのがあり再検討
のちに18,22,20,22みたいな組では2が答えになることから、リストの中の最小値と他を比べて最大公約数を持って来ればよいことに気づく、も時間が足りず惨敗
ユークリッドの互除法を使う x,yに対し最大公約数を求めるアルゴリズムは、
def gcd(x,y):
while y != 0:
k = x
x = y
y = k%y
return x
とする
今回は、隣り合う数の最大公約数をユークリッドの互除法のアルゴリズムを用いて、候補と比較してより小さいものに更新し続け、最終的に最も小さいものを答えとして返せばよい
悔しい