Atcoder Beginner Contest 145 振り返り 【Python】

はじめに

AtCoder Beginner Contest 145の振り返りをします。
3完です。D問題はTLE＆WAでした。

atcoder.jp

A - Circle

提出したプログラム

r = int(input())
print(r*r)

特にコメントなし！

B - Echo

提出したプログラム

N = int(input())
S = input()
N_half = N//2
if S == S[:N_half]+S[:N_half]:
    print("Yes")
else:
    print("No")

入力した文字を半分に切り、前半 + 前半 = 入力文字になってるときに"Yes"と出力するようにコードを書きました。今考えたら半分に切って前半文字と後半文字が一致するかどうかで判断したほうがきれいですね。

C - Average Length

提出したプログラム

import itertools
import math
 
N = int(input())
List=[list(map(int,input().split())) for i in range(N)]
roots = list(itertools.permutations(range(N)))
sum_length = 0
for root in roots:
    first_city = 100 # 存在しない
    for city in root:
        if first_city == 100:
            first_city = city
            continue
        x = List[first_city][0] - List[city][0]
        y = List[first_city][1] - List[city][1]
        sum_length += math.sqrt(pow(x,2)+pow(y,2))
print(sum_length/len(roots))

やりたいことはすぐ理解できたのですが実装に少し手こずりました。
手順は

1. Nの順列を求める (= 町を訪れる経路)
2. 1つの経路の移動距離を求める
3. 全経路の合計を経路数で割る

他の人のプログラム

import math
N = int(input())
XY = [[int(x) for x in input().split()] for _ in range(N)]
s = 0
for i in range(N):
    for j in range(i+1, N):
        xi, yi = XY[i]
        xj, yj = XY[j]
        s += (math.sqrt((xi-xj)**2 + (yi-yj)**2))
print(2*s/N)

実行時間が短い人は大体こんな感じで実装していました。3個の町がある場合, 1→2→3 と 3→2→1 みたいに移動距離が同じ経路があるから片方だけ計算して2倍するって感じなのかな？詳しくはよくわかりませんでした。時間があるときにでも考察したいです。

D - Knight

提出したプログラム

from operator import mul
from functools import reduce

def cmb(n,r):
    r = min(n-r,r)
    if r == 0: return 1
    over = reduce(mul, range(n, n - r, -1))
    under = reduce(mul, range(1,r + 1))
    return over // under

x,y=map(int,input().split())
if not(-(-x//2) <= y and y <= x*2):
    print(0)
    exit()
flag = True
count = 0
while flag:
    count += 1
    x += 1
    y -= 1
    if y*2 == x: # yC0
        print(cmb(y, count)%1000000007)
        exit()
    if y*2 < x: # ない
        print(0)
        exit()

最初はナイトを動かした図を書きました。

コンテスト中の図なので汚いです。すみません

この図を書いてるときにパスカルの三角形ができることに気が付きました。 ja.wikipedia.org

後は組み合わせを出力するコードを書いて完成！！！ ドヤ顔で (999999 999999) を入力して気持ちよくエンターキーをターン！！と押したら実行終了まで20秒ぐらいかかりました('ω')
コンテストでの実行時間は2秒です。間に合うはずもありません。
何か別の方法があるはずだと思って問題文を読んでいると で割った余りを求めてください。 に時間短縮のコツがありそうだと思いました。そして「組み合わせ　あまり」でググったらこの記事がみつかりました。

www.smartbowwow.com

どうやら膨大な数の組み合わせを計算するときにフェルマーの小定理を使うことで計算量を大幅に省略できるらしいです。因みにフェルマーの小定理は順列計算や重複組み合わせ計算などにも応用できるみたいです。

qiita.com

途中ですが今回はここまで m(__)m

終わりに（余談）

フェルマーの小定理を知ることができたのでワース。

コンテスト中の落書き