AtCoder初心者によるAtCoder初心者がコケたポイント集

最近AtCoderを始めました。
3回しか参加していないのでまだ灰色です。できたら水色くらいまで行きたいな〜〜〜と思っています(願望)。
何回かやってみて、レベルの高い低いは置いといてコケた箇所を備忘録としてまとめておきました。
プログラミング上手いマンにとっては常識だと思いますが、初心者にとってはあるある(多分)なので生暖かい目で見守っていただけると嬉しいです。
使用言語はpython3です。

# 切り捨て徐算するときはint(A/B)ではなくA//Bを使うべし
[ARC112 B問題](https://atcoder.jp/contests/arc112/tasks/arc112_b)
コストをかけて整数を1引いたり-1倍したりする問題。
問題の本質的な部分ではないのですが、ある値Cを2で割った商の切り捨てを算出する必要がありました。
なので、int(C/2)としてその値を出しました。
【結果】
WA(これだけが原因ではないですが)
【原因】
浮動小数点の有効桁数。int(C/2)でははじめにC/2をfloatとして算出して、切り捨てを行う。floatは桁落ちが発生するので、Cが10<sup>18</sup>程度になるとずれる。
例：int(987654321098765432/2)を計算すると493827160549382720になる。
【対策】
切り捨て除算を行うときはint(A/B)とするのではなく、A//Bを使う。

# 実行時間が微妙にオーバーするならPypy3を使うべし
[ARC113 A問題](https://atcoder.jp/contests/arc113/tasks/arc113_a)
何も考えずに全探索コードを書いたところTLE。
【原因】
Pythonは遅い。コードテストで検証したら制限時間2秒のところ、4秒弱と微妙?にオーバー。
【対策】
早いことで定評のあるPyPy3を利用。
【修正後】
0.2秒かからずクリア。はっやーい！
(本来は効率的なアルゴリズムを考えるべきかもしれないですが、まぁ)

# 累乗の剰余を求めるときはpow(base,exp,mod)を使うべし<br>
[ARC113 B問題](https://atcoder.jp/contests/arc113/tasks/arc113_b)
A<sup>B<sup>C</sup></sup>の1の位を求める問題。
A,B,Cをそれぞれ10,4,2で割った余り[^1]を%によって算出し(それぞれa,b,cとする)、a<sup>b<sup>c</sup></sup>を10で割った余りを結果として出力[^2]。
【結果】
WAがいくつか発生。時間内に修正できずタイムオーバー。
【原因】
例えば B=4,C=2 のとき、本来指数部分は B<sup>C</sup>=4<sup>2</sup>=16と計算するべきところ、B,Cそれぞれ%による剰余計算をしているためb=0,c=0となっており、b<sup>c</sup>=0<sup>0</sup>=1となっている[^3]ことが原因。
十進数での1の位はA<sup>B</sup>のBが4増えるごとに循環するため、1だけずれてると致命的。

【対策】
累乗の剰余を計算するときはpow(base,exp,mod)を使う。そうすればpow(4,2,4)=0とちゃんと計算してくれる。
【修正後】
この2行のコードでAC。初めからpow使っていれば良かった・・・・・・
pow(b,c,4)に4を足しているしているのはb<sup>c</sup>≡0 (mod4)になること対策。
(例：2<sup>4<sup>2</sup></sup>=2<sup>16</sup>=65536≡6 (mod 10)なのに+4がないと2<sup>0</sup>≡1 (mod 10)となる。B<sup>C</sup>>0なので+4の処理で問題なし)

```python
a,b,c = map(int,input().split())
print(pow(a,pow(b,c,4)+4,10))
```

[^1]: なぜ4や2の余りを出しているかはこの記事の範囲外なのでatcoderの解説をご参照ください。
[^2]: b=2かつC=1の例外処理などありますが割愛します。なおpowを使えばこの場合分けはいらない模様。
[^3]: 0の0乗は定義されていないとか難しい話はありますがpythonでは1として扱われているのでそれで許してください。

# 小数がでたらfloat誤差警報発令
[ABC191 D問題](https://atcoder.jp/contests/abc191/tasks/abc191_d)
[ABC189 B問題](https://atcoder.jp/contests/abc189/tasks/abc189_b)
高々小数第4位までの数とか整数を100で割るとかが出たら、まずは浮動小数点数の誤差がテーマと思うべし。
(何も考えずに計算したらほぼ間違いなくWA)
【対策】
適当な値(10000とか100とか)をかけて整数にすれば(intで扱えば)誤差の問題は気にしなくてOKになる。Pythonなら。

# X in listが遅いときはX in setを使う
[ABC179 E問題](https://atcoder.jp/contests/abc179/tasks/abc179_e)
長さが10<sup>5</sup>位あるリストにある値aが含まれるかチェックする必要が発生。
初めはlistの中からinにより検索していたが、TLE。listをsetにしたところACとなった。
[この記事](https://qiita.com/kitadakyou/items/6f877edd263f097e78f4)に詳しいことが書いてあった。

```python
if a in a_list: #リストの中からaを検索 →TLE

if a in a_set: #セットの中からaを検索 →AC
```

# 問題文はちゃんと読む
あたりまえ体操

# いくら行列計算だからといってnumpyはやめとけ
dtype= intとしたところで、見た目が整数型になるだけで計算はfloatだから(多分)数が大きくなるとオーバーフローする。
行列計算は気合で手動実装。

```python
#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]]
"""
```