atcoder　めも

```python:Ans.py
import io,sys,os
os.system("cls")
with open("HandInput.txt") as txt_open:
    INPUT=txt_open.read() 
sys.stdin = io.StringIO(INPUT)
# --------------------------------------------------------

# --------------------------------------------------------
```

```python:Cheat.py
# 時間の計測
import time
start_time=time.time()
print ("end_time:{0}".format(time.time() - start_time) + "[sec]")

# テストケース作成
path="D:\\test.txt"
n=10**5
a=[1]*n
s=""
for i in range(n):
    if i<n-1:s+=str(a[i])+" "
    else:s+=str(a[i])
with open(path, mode='w') as f:
    f.write(s)

# 地図の入力
h,w=map(int, input().split())
tizu=[]
for i in range(h):
    tizu.append(list(input()))

# 二次元配列を一次元化
# xはa,b,cのすべてより大きい数
x=10**6
a,b,c=map(int, input().split())
tmp=a*x**2+b*x+c
# 取り出し
a=tmp//(x**2)
b=(tmp//x)%x
c=tmp%xx

# 誤差の考慮(pypyを使うとTLEするので注意)
from decimal import Decimal
# a=Decimal(1.01)

import itertools
#(1,1,1),(1,1,2),---,(9,9,9)
for seq in itertools.combinations_with_replacement(range(1,10),3):
# (1,2,3),(1,2,4),---,(7,8,9)
for seq in itertools.combinations(range(1,10),3):
#(1,1),(1,2),(1,3),(2,1),(2,2),---(3,3)
for seq in itertools.product(range(1,4),range(1,4)):
#(1,2,3),(1,3,2),(2,1,3),(2,3,1),---,(3,2,1)
for seq in itertools.permutations(range(1,4)):
 
from collections import deque

import heapq
# heapq.heapify(list) heapq.heappop(list):最小値を取得 heappush(list,x):xを挿入 
 
# 素因数分解(1は空のリストを作成する)
def prime_factorize(n):
    a=[]
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f=3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a

# # n以下の素数リスト
def prime_list(n):
    a=list(range(2,n+1))
    p=list()
    while a[0]**2<=n:
        tmp=a[0]
        p.append(tmp)
        a=[e for e in a if e%tmp!=0]
    return p+a

# nCr mod(modは素数)
def ncr(n,r,mod):
    ue=1
    for i in range(n-r+1,n+1):
        ue*=i
        ue%=mod
    sita=1
    for i in range(1,r+1):
        sita*=i
        sita%=mod
    sita=pow(sita,mod-2,mod)
    return (ue*sita)%mod

# 階乗 mod
def fact(n,mod):
    tmp=1
    for i in range(2,n+1):
        tmp*=i
        tmp%=mod
    return tmp

# リストの最大公約数
import math
def gcd_list(x_list):
    tmp=x_list[0]
    if len(x_list)==1:return tmp
    for i in range(1,len(x_list)):
        tmp=math.gcd(tmp,x_list[i])
    return tmp

#最小公倍数
import math
def lcm(x, y):
    return (x * y) // math.gcd(x, y)

# リストの最小公倍数
import math
def lcm_list(x_list):
    tmp=x_list[0]
    if len(x_list)==1:return tmp
    for i in range(1,len(x_list)):
        tmp=(tmp*x_list[i])//math.gcd(tmp,x_list[i])
    return tmp

#総積
def prod(x):
    kotae=1
    for i in x:
        kotae*=i
    return kotae

#約数列挙
def make_divisors(n):
    lower_divisors , upper_divisors=[], []
    i=1
    while i*i <= n:
        if n % i == 0:
            lower_divisors.append(i)
            if i != n // i:
                upper_divisors.append(n//i)
        i += 1
    return lower_divisors + upper_divisors[::-1]

#切り上げ (マイナスでも常に大きくなる方へ(-2.2→-2))
def ceil(x):
    x=float(x)
    if x.is_integer():
        return int(x)
    else:
        if x>0:
            return int(x)+1
        else:
            return int(x)
#切り捨て (マイナスでも小さくなる方へ(-2.2→-3))
def floor(x):
    x=float(x)
    if x.is_integer():
        return int(x)
    else:
        if x>0:
            return int(x)
        else:
            return int(x)-1

# 配列の累積和
def cum_sum(x):
    tmp=[x[0]]
    for i in range(1,len(x)):
        tmp.append(x[i]+tmp[i-1])
    return tmp

# UnionFind
class UnionFind:
    # 初期化 nは要素数
    def __init__(self, n):
        # 全体の大きさ
        self.n=n
        # -x:サイズxのグループの親,k(正):親がk
        self.parent_size=[-1]*n
    # aとbを結合
    def merge(self, a, b):
        # a,bの親をx,yへ
        x, y=self.leader(a), self.leader(b)
        # 親が同じなら終了
        if x == y: return 
        # 親のサイズを比較　サイズの小さい方を大きい方につなげるため
        if abs(self.parent_size[x])<abs(self.parent_size[y]): x, y=y, x
        # 大きい方のサイズに小さい方のサイズを足す
        self.parent_size[x] += self.parent_size[y]
        # 小さい方の親を大きい方の親につなげる
        self.parent_size[y]=x
        return 
    # 同じグループか判定　同じならTrue
    def same(self, a, b):
        # 親を比較して同じならTrue
        return self.leader(a) == self.leader(b)
    # 要素のリーダー＝属するグループの番号を返す
    def leader(self, a):
        # それ自体が親ならそれを返す
        if self.parent_size[a]<0: return a
        # 親じゃないならもとをたどる＋親の更新
        self.parent_size[a]=self.leader(self.parent_size[a])
        # 返す
        return self.parent_size[a]
    # 属するグループのサイズを返す
    def size(self, a):
        # 親の絶対値=サイズ
        return abs(self.parent_size[self.leader(a)])
    # groupの全体を返す
    def groups(self):
        # グループの格納リストを作る
        result=[[] for _ in range(self.n)]
        # 親の番号に子を入れる
        for i in range(self.n):
            result[self.leader(i)].append(i)
        # 空の要素を消す
        return [r for r in result if r != []]

# BFS
# グラフは木
from collections import deque
class BFS:
    # 初期化(ノード数)
    def __init__(self,n):
        # ノード数
        self.num=n
        # つながっている場所と距離(コスト)
        self.connect=[[] for _ in range(self.num)]
    # a,bはつながっている(0_index)
    def edge_add(self,a,b,cost):
        # 無向グラフ
        self.connect[a].append((b,cost))
        self.connect[b].append((a,cost))
    # 距離の作成(スタート地点)
    def make_dist(self,start):
        dist=[0]*self.num
        que=deque()
        que.append(start)
        end=[False]*(n)
        end[start]=True
        # スタート地点は距離0
        dist[start]=0
        while que:
            now=que.popleft()
            now_dist=dist[now]
            for to,cost in self.connect[now]:
                if end[to]==False:
                    que.append(to)
                    dist[to]=now_dist+cost
                    end[to]=True
        return dist

# セグメントツリー
#演算
def segfunc(x,y):
    return x^y
class segtree:
    # 初期化(元のリスト、単位元、演算)
    def __init__(self,x_list,init,segfunc):
        # 単位元
        self.init=init
        # 演算
        self.segfunc=segfunc
        # 高さ=もとの数列の長さのビット長+1
        self.Height=len(x_list).bit_length()+1
        # tree最下層の一番左のインデックス
        self.num=2**(self.Height-1)
        # 木
        self.tree=[init]*(2**self.Height)
        # 最下層に要素をセット
        for i in range(len(x_list)):
            self.tree[2**(self.Height-1)+i]=x_list[i]
        # 構築
        for i in range(2**(self.Height-1)-1,0,-1):
            self.tree[i]=segfunc(self.tree[2*i],self.tree[2*i+1])
    # 更新(k番目(0インデックス),値)
    def update(self,k,x):
        k+=self.num
        self.tree[k]=x
        while k>1:
            if k%2==0:
                self.tree[k//2]=self.segfunc(self.tree[k],self.tree[k+1])
            else:
                self.tree[k//2]=self.segfunc(self.tree[k-1],self.tree[k])
            k//=2
    # 区間の処理
    def query(self,l,r):
        # 下から処理
        # とりあえず単位元を入れる
        res=self.init
        # 最下層のインデックスに合わせる
        l+=self.num
        # 右は開区間にするため+1
        r+=self.num+1

        while l<r:
            # 左端が奇数だったら
            if l%2==1:
                # 値を使って
                res=self.segfunc(res,self.tree[l])
                # 一個右に移動
                l+=1
            # 右端が偶数だったら
            if r%2==1:
                # 値を使って
                res=self.segfunc(res,self.tree[r-1])
            l//=2
            r//=2
        return res
    # 参照
    def select(self,x):
        return self.tree[x+self.num]

from heapq import heappush, heappop
class dijkstra:
    # 初期化(ノード数)
    def __init__(self,n):
        # ノード数
        self.num=n
        # エッジ情報の格納先　edge[start]=[(end,cost),(end,cost),・・・]
        self.edge=[[]for _ in range(n)]
    # エッジの追加(0index)
    def edge_add(self,start,end,cost):
        self.edge[start].append((end,cost))
    # スタート地点からそれぞれの点への最短距離を計算
    # O((ノード数+エッジ数)log(ノード数)
    def to_end(self,start):
        # 到達不能距離
        inf=10**15
        # スタートからの距離
        dist=[inf]*self.num
        # 固定されているかどうか
        fixed=[False]*self.num
        # スタート地点からスタート地点への距離は0
        dist[start]=0
        # スタート地点をキューに入れる
        hq=[(0,start)]
        while hq:
            # now_cost=今いる場所に書いてるコスト、now_place=今いる場所
            now_cost,now_place=heappop(hq)
            # すでに終わっていれば
            if fixed[now_place]==True:
                continue
            # 今いる場所のコストを固定
            fixed[now_place]=True
            # 今いる場所から行ける場所を順に回る
            for to_place,to_cost in self.edge[now_place]:
                # 固定されていなくて、よりコストが低いなら
                if fixed[to_place]==False and now_cost+to_cost<dist[to_place]:
                    # コストを書き換え
                    dist[to_place]=now_cost+to_cost
                    # キューに入れる
                    heappush(hq,(dist[to_place],to_place))
        return dist

# --------------------------------------------------------
```