ARC149回答メモ

0.はじめに
　レギュラーコンテストは1問解くことを目標に参加してます。

1.A - Repdigit Number
　考え方１）
　　大きい方からぞろ目数を作っていき、割り切れたところで終わらせれば早い！勝てる！
　　と、以下のような大きい方からぞろ目作るロジックを作り提出
　

X=10**N                    #10のN乗作成             ex.N=6、1000000
while(N>0):                #
    X-=1                   #↑から1を引き9のぞろ目    ex.999999
    Y=X//9                 #ぞろ目数の推移用値を用意  ex.111111
    for i in range(9):     #
        if(X%M==0):        #あまり0判定
            print(X)       #割り切れたらプリントし
            exit()         #終了
        elif(X>Y):         #割り切れない、かつXが1のぞろ目じゃない時
            X-=Y           #ぞろ目数の推移用値を減算  ex.999999→888888
    N-=1                   #9～１が終わったらNを減らす(countにしか使用しない)
    X-=(Y//10)             #Xを1桁減らす             ex.111111→100000

　　我ながら、いい感じのぞろ目作成器！と思いましたが、TLE続出。
　　9万回くらいしか計算しないでしょ！と思ったけど
　　10000桁以上の数値となると、さすがに無理みたいでした。

　考え方２）（というか、試験終了後解説見ました）
　　j桁の数字iのぞろ目というペアをメモ的に用意して
　　割り切れたペアのうち最大のペア（大小比較は桁を表すjが先）
　　を元に回答の値を作る。という感じで回答しました。
　　
　　前提となる、
　　　(1)　1をMで割った余りに10かけて1を足した数字をMで割った余り
　　　(2)　11をMで割った余り
　　が、同じになるという部分を理解するのに半日かかりました。

　　自分的理解メモ
　　　(3,1)＝111の次は(4,1)＝1111ですが、これは、111*10+1と言える。

　　　Mが4の場合、
　　　111÷４のあまりは３
　　　1110(111を10倍したもの)を割った余りは
　　　111を4であった余り10個(40)を4で割った数(0)
　　　さらに、1桁目に加える1を４で割れば余りが求まる（１）

　　　そのようにして、ｊとｉを設問上限まで増加していき
　　　解を求める。
　　　これで時間足りなければもう一工夫できそうでしたが
　　　時間は足りたのでＯＫでした。

　　　回答は、答えのペアをもとに、ｊをｉ回繰り返したものを表示します。

ans=(0,0)
for i in range(1,10):
    X=0
    for j in range(1,N+1):
        X=(10*X+i)%M
        if(X==0):
            ans=max(ans,(j,i))
if(ans[0]==0):
    ans_X=-1
else:
    ans_X=str(ans[1])*ans[0]
print(ans_X)

　https://atcoder.jp/contests/arc149/submissions/35388274

B問題以降はそのうち・・・。