AtCoder Beginner Contest 145 ／ Python 【参加】

●　初学者です。（ 2019 / 9 ～ 現在３ヵ月目 ）
●　AtCoder の問題に Python で取り組んでいます。
●　ABC で４問目（茶か緑）まで解けることを目標にしています。

完全に独学なのでコードは酷いと思います。

AtCoder やってる方、お気軽にコメントくださいませ。

初参加しました。いやぁ無意味に緊張しました。

結果、

レーティング２ケタという驚異の低レートを叩き出しました。

いや、A、B、C は解いたんですけどね。最初はそういう仕様らしいですね。

A - Circle

r = int(input())

print(r**2)

円の面積は半径の２乗に比例する。

B - Echo

N = int(input())

S = input()

if N % 2 == 0:
   if S[:int(N/2)] == S[int(N/2):]:
       print("Yes")
   else:
       print("No")
else:
   print("No")

文字数が偶数なら、
　　前の半分と後ろの半分が同じなら
　　　　”Yes”
　　違うなら
　　　　”No”
文字数が奇数なら、
　　”No”

こんなんで良いのか、と思ったが解説もこうなってるから良いらしい。

S[:int(N/2)] == S[int(N/2):]　は　S[:N//2] == S[N//2:]　の方が良かった。

これの意味を間違えていて１回不正解になった、初心者感が出てしもうた。

a = "012345"

print(a[5])

# 5

print(a[:5])

# 01234

[:5] は 0番～５番 を出すのかと思ったら、0～5個目までを出すのね。

C - Average Length

N = int(input())

P = []

S = 0

for i in range(N):
   P.append(list(map(int,input().split())))


for i in range(N-1):
   for j in range(N-1-i):
       
       S += (((P[i][0] - P[i+j+1][0])**2 + (P[i][1] - P[i+j+1][1])**2)**0.5)*2
       
print(S/N)  

これは・・・。

改めて見ると、謎の公式を生み出してしまっている・・・、
確かに答えは出るが、何でこれで答えが出るのかわからない。

町１→町２への道を a 、町１→町３への道を b 、町２→町３への道を c 。

経路　　通る道
１２３　　a c
１３２　　b c
２１３　　a b　　　
２３１　　c b　　　
３１２　　b a
３２１　　c a　　　　　平均　( a + b + c ) × 4 ÷ 6

こうやって出そうと思っていたのだが、

コードは何故か　( a + b + c ) × 2 ÷ 3　で答えを出している。

何でこれで良いんだ？？

×４　は何処から出て来るかといえば、
１経路に道 ２つ × 経路の数 ６つ　÷　道の種類 ３つ

÷６　は経路の数 ６つ

文字式にする、町の数をｎとするとき。

１経路に道 ( n-1 )　×　経路の数 n!　÷　道の種類 nC２　÷　経路の数 n!

= ( n-1 )　×　 n!　÷　 nC２　÷　n!
= ( n-1 )　÷　 nC２　　　　　　　　　
= ( n-1 )　÷　 ( n( n-1 ) ÷ 2・1 )
= 2 　÷　 n　　　　　　　　　　

こんなこと考えたっけな、記憶に無い。

プログラミング能力が無いから解き方が数学寄りになってしまうのかも。

他の解答を見たら itertools を使っているのが多かったので。

import itertools


N = int(input())

P = [list(map(int,input().split())) for i in range(N)]

S = 0


route = list(itertools.combinations(P, 2))

for i in route:
   
   S += ((i[0][0] - i[1][0])**2 + (i[0][1] - i[1][1])**2)**0.5
   
print(S*2/N)   

後やっぱり入力のところ内包表記の方が良いなぁ、内包表記なぁ・・・

ここで、残り43分。

D - Knight

（1、2）（2、1）方向へ進む回数をそれぞれ求める連立方程式を解く。
解が共に正の整数（（m、n）とする）
　　　（m + n）！／m！n！
　　　　　　同じものを含む順列で何通りの経路があるか出す。
解が正の整数でない
　　　　０を出力

と考えたが、実行時間制限超過。時間を無視すれば答えは出ている。

※　時間オーバーするやつ

import math
import numpy as np

x,y = map(int,input().split()) 

A = np.array([[1, 2],
           [2, 1]])

b = np.array([x, y])

N = np.linalg.solve(A, b)


if N[0].is_integer() == True and N[1].is_integer() == True and N[0] >=0 and N[1] >=0:
  
  k = math.factorial(N[0]+N[1])/(math.factorial(N[0])*math.factorial(N[1]))

  print(int(k%1000000007))

else:
  print(0)

遅い原因は階乗の計算だった。

階乗をやめて、フェルマーの小定理を利用してコンビネーションを計算するとかいう意味不明なやつを使ったら実行時間制限を突破した。

ついでにｘ+ｙが３の倍数でないなら弾くという条件も入れた。

これなら通る。

import math
import numpy as np

def cmb(n, r, mod):
  r = min(r, n-r)
  return g1[n] * g2[r] * g2[n-r] % mod

mod = 10**9+7 
N = 10**6
g1 = [1, 1] 
g2 = [1, 1] 
inverse = [0, 1] 

for i in range( 2, N + 1 ):
  g1.append( ( g1[-1] * i ) % mod )
  inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
  g2.append( (g2[-1] * inverse[-1]) % mod )

x,y = map(int,input().split()) 

if (x+y) % 3 == 0:

  A = np.array([[1, 2],
                [2, 1]])

  b = np.array([x, y])

  N = np.linalg.solve(A, b)


  if N[0].is_integer() == True and N[1].is_integer() == True and N[0] >=0 and N[1] >=0:
        
      print(cmb(int(N[0]+N[1]),int(N[0]),mod))

  else:
      print(0)

else:
  print(0)

x + y が３の倍数である。
　（1、2）（2、1）方向へ進む回数をそれぞれ求める連立方程式を解く。
　　解が共に正の整数（（m、n）とする）
　　　　　（m + n）C m
　　　　　　　　組合せで何通りの経路があるか出す。
　　解が正の整数でない
　　　　　　０を出力
x + y が３の倍数でない。
　　０を出力

メモ：

意味わからんコンビネーションを求めるやつ。

def cmb(n, r, mod):
   if ( r<0 or r>n ):
       return 0
   r = min(r, n-r)
   return g1[n] * g2[r] * g2[n-r] % mod

mod = 10**9+7 
N = 10**4
g1 = [1, 1] 
g2 = [1, 1] 
inverse = [0, 1] 

for i in range( 2, N + 1 ):
   g1.append( ( g1[-1] * i ) % mod )
   inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
   g2.append( (g2[-1] * inverse[-1]) % mod )

a = cmb(n,r,mod)

全く意味がわからないから上限を上げて、要らない条件式を１つ消しただけでコピペして使っている。for 文の中身何してんのこれは。

フェルマーの小定理を使ってる的なことが書いてあったが、

何処にどう使っとる？？どなたかこのコードの意味を解説しているところを知っている方がいらっしゃれば教えてもらえませんか。

やっぱりD問題厳しいなぁ。

連立方程式

import numpy as np

A = np.array([[6, -4],
            [8, 11]])

b = np.array([22, 13])

x = np.linalg.solve(A, b)

print(x)

階乗

import math

a = math.factorial(5)

print(a)

# 120

整数かどうか調べる

a = 0.23
b = 1.23
c = 1.00

print(a.is_integer(),b.is_integer(),c.is_integer())
  
# False False True

E - All-you-can-eat

最近見たばかりなので動的計画法だということはすぐわかった。

わかっただけでコードは考える時間すらなかったですけどね。

import numpy as np

n, t = map(int, input().split())
a = []
b = []

for _ in range(n):
    a_tmp, b_tmp = map(int, input().split())
    a.append(a_tmp)
    b.append(b_tmp)
   
arg = np.argsort(a)
a = np.array(a)[arg]
b = np.array(b)[arg]

dp = np.zeros((n, t), dtype=np.int)


for i in range(n - 1):
    dp[i+1, :a[i]] = dp[i, :a[i]]
    dp[i+1, a[i]:] = np.maximum(dp[i, a[i]:], dp[i, :-a[i]] + b[i])
 
print(np.max(dp[:, -1] + b))

動的計画法を知っていれば D より簡単な気がする。

numpy わからないマンのメモ：

a = [2, 5, 8, 1, 3]
b = [5, 3, 6, 2, 4]

arg = np.argsort(a)          並べ替えてインデックスを返す
    = [3 0 4 1 2]

a = np.array(a)[arg]　　　　　　       a を arg の順番に並べる
  = [1 2 3 5 8]
b = np.array(b)[arg]
  = [2 5 4 3 6]

dp = np.zeros((n, t), dtype=np.int)      n = 5 , t = 10
   = [[0 0 0 0 0 0 0 0 0 0]
      [0 0 0 0 0 0 0 0 0 0]
      [0 0 0 0 0 0 0 0 0 0]
      [0 0 0 0 0 0 0 0 0 0]
      [0 0 0 0 0 0 0 0 0 0]]

dp = [[0 0 0 0 0 0 0 0 0 0]        ループから抜けたとき
      [0 2 2 2 2 2 2 2 2 2]
      [0 2 5 7 7 7 7 7 7 7]
      [0 2 5 7 7 9 11 11 11 11]
      [0 2 5 7 7 9 11 11 11 11]]

dp[:, -1] =     [ 0  2  7 11 11]
dp[:, -1] + b = [ 2  7 11 14 17]

np.max(dp[:, -1] + b) = 17

np.maximum　要素ごとを比較して大きい値を取り出す。

np.max　普通の配列から最大値を取り出す

F - Laminate

見てない、どうせ無理なやつ。

マガジン：他の回もやっていきます。

AtCoder Beginner Contest｜もやし｜note