最近AtCoderを始めました。
3回しか参加していないのでまだ灰色です。できたら水色くらいまで行きたいな〜〜〜と思っています(願望)。
何回かやってみて、レベルの高い低いは置いといてコケた箇所を備忘録としてまとめておきました。
プログラミング上手いマンにとっては常識だと思いますが、初心者にとってはあるある(多分)なので生暖かい目で見守っていただけると嬉しいです。
使用言語はpython3です。
切り捨て徐算するときはint(A/B)ではなくA//Bを使うべし
ARC112 B問題
コストをかけて整数を1引いたり-1倍したりする問題。
問題の本質的な部分ではないのですが、ある値Cを2で割った商の切り捨てを算出する必要がありました。
なので、int(C/2)としてその値を出しました。
【結果】
WA(これだけが原因ではないですが)
【原因】
浮動小数点の有効桁数。int(C/2)でははじめにC/2をfloatとして算出して、切り捨てを行う。floatは桁落ちが発生するので、Cが1018程度になるとずれる。
例：int(987654321098765432/2)を計算すると493827160549382720になる。
【対策】
切り捨て除算を行うときはint(A/B)とするのではなく、A//Bを使う。
実行時間が微妙にオーバーするならPypy3を使うべし
ARC113 A問題
何も考えずに全探索コードを書いたところTLE。
【原因】
Pythonは遅い。コードテストで検証したら制限時間2秒のところ、4秒弱と微妙?にオーバー。
【対策】
早いことで定評のあるPyPy3を利用。
【修正後】
0.2秒かからずクリア。はっやーい！
(本来は効率的なアルゴリズムを考えるべきかもしれないですが、まぁ)
累乗の剰余を求めるときはpow(base,exp,mod)を使うべし
ARC113 B問題
ABCの1の位を求める問題。
A,B,Cをそれぞれ10,4,2で割った余り1を%によって算出し(それぞれa,b,cとする)、abcを10で割った余りを結果として出力2。
【結果】
WAがいくつか発生。時間内に修正できずタイムオーバー。
【原因】
例えば B=4,C=2 のとき、本来指数部分は BC=42=16と計算するべきところ、B,Cそれぞれ%による剰余計算をしているためb=0,c=0となっており、bc=00=1となっている3ことが原因。
十進数での1の位はABのBが4増えるごとに循環するため、1だけずれてると致命的。
【対策】
累乗の剰余を計算するときはpow(base,exp,mod)を使う。そうすればpow(4,2,4)=0とちゃんと計算してくれる。
【修正後】
この2行のコードでAC。初めからpow使っていれば良かった・・・・・・
pow(b,c,4)に4を足しているしているのはbc≡0 (mod4)になること対策。
(例：242=216=65536≡6 (mod 10)なのに+4がないと20≡1 (mod 10)となる。BC>0なので+4の処理で問題なし)
a,b,c = map(int,input().split())
print(pow(a,pow(b,c,4)+4,10))
小数がでたらfloat誤差警報発令
ABC191 D問題
ABC189 B問題
高々小数第4位までの数とか整数を100で割るとかが出たら、まずは浮動小数点数の誤差がテーマと思うべし。
(何も考えずに計算したらほぼ間違いなくWA)
【対策】
適当な値(10000とか100とか)をかけて整数にすれば(intで扱えば)誤差の問題は気にしなくてOKになる。Pythonなら。
X in listが遅いときはX in setを使う
ABC179 E問題
長さが105位あるリストにある値aが含まれるかチェックする必要が発生。
初めはlistの中からinにより検索していたが、TLE。listをsetにしたところACとなった。
この記事に詳しいことが書いてあった。
if a in a_list: #リストの中からaを検索 →TLE
if a in a_set: #セットの中からaを検索 →AC
問題文はちゃんと読む
あたりまえ体操
いくら行列計算だからといってnumpyはやめとけ
dtype= intとしたところで、見た目が整数型になるだけで計算はfloatだから(多分)数が大きくなるとオーバーフローする。
行列計算は気合で手動実装。
# numpyで計算
import numpy as np
a = np.array([[10000,10000],[10000,10000]],dtype=int)
b = np.eye(2,dtype=int)
for i in range(5):
b = b @ a
print(b)
"""
output:
[[10000 10000]
[10000 10000]]
[[200000000 200000000]
[200000000 200000000]]
[[4000000000000 4000000000000]
[4000000000000 4000000000000]]
[[80000000000000000 80000000000000000]
[80000000000000000 80000000000000000]]
[[-4866734412730990592 -4866734412730990592]
[-4866734412730990592 -4866734412730990592]]
"""
# 気合の手動実装(同じ次数の正方行列用)
def mat_dot(mat1_,mat2_):
ans_mat = []
for i in range(len(mat1_)):
bb = []
for j in range(len(mat1_)):
temp = 0
for k in range(len(mat1_)):
temp =(temp + mat1_[i][k] * mat2_[k][j])
bb += [temp]
ans_mat += [bb]
return ans_mat
a = [[10000,10000],[10000,10000]]
b = [[1,0],[0,1]]
for i in range(5):
b = mat_dot(b,a)
print(b)
"""
output:
[[10000, 10000], [10000, 10000]]
[[200000000, 200000000], [200000000, 200000000]]
[[4000000000000, 4000000000000], [4000000000000, 4000000000000]]
[[80000000000000000, 80000000000000000], [80000000000000000, 80000000000000000]]
[[1600000000000000000000, 1600000000000000000000], [1600000000000000000000, 1600000000000000000000]]
"""