見出し画像

AtCoder Beginner Contest 145 / Python 【参加】

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

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

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



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


結果、

画像3


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

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




r = int(input())

print(r**2)
円の面積は半径の2乗に比例する。




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:] の方が良かった。



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

a = "012345"

print(a[5])

# 5

print(a[:5])

# 01234

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





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)  

これは・・・。

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


町1→町2への道を a 、町1→町3への道を b 、町2→町3への道を c 。

経路  通る道
123  a c
132  b c
213  a b   
231  c b   
312  b a
321  c a     平均 ( a + b + c ) × 4 ÷ 6

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

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


何でこれで良いんだ??


×4 は何処から出て来るかといえば、
1経路に道 2つ × 経路の数 6つ ÷ 道の種類 3つ

÷6 は経路の数 6つ


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

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

= ( n-1 ) ×  n! ÷  nC2 ÷ n!
= ( n-1 ) ÷  nC2         
= ( 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分。





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

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


※ 時間オーバーするやつ

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)



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

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

ついでにx+yが3の倍数でないなら弾くという条件も入れた。

これなら通る。

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 が3の倍数である。
 (1、2)(2、1)方向へ進む回数をそれぞれ求める連立方程式を解く。
  解が共に正の整数((m、n)とする)
     (m + n)C m
        組合せで何通りの経路があるか出す。
  解が正の整数でない
      0を出力
x + y が3の倍数でない。
  0を出力



メモ:


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

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)

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


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

画像3

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


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



連立方程式

画像2

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






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

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



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 普通の配列から最大値を取り出す



画像4






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




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




いつもありがとうございます(´っ・ω・)っ サポートから決済手数料(クレカ5%、ケータイ15%) & プラットフォーム利用料10%が引かれてしまいます、 予めご了承ください(´;ω;`)。 残りは僕のご飯になります。ベリベリありがとうございます。