Cafecoder Tea Break 003 感想

Tea Break 003に参加しました。

全完21位

全完はしたものの考察がガバでWA_TLEして踏んだり蹴ったり。

A(Green) Hop Step Jump!

1,1,2,1,1,2...と移動してマスを踏むかの問題。4で割って3余るか調べればいいですね。

提出結果

n=int(input())
print("No"if n%4==3else"Yes")

B(Ceylon) Sound!

\(K\) から1づつ左or右に拡張していって指定した位置すべてに移動できるかの問題。

音階の最小値、最大値と \(K\) の差を足し合わせればOK。

最小値が \(K\) の右( \(K \lt min(A)\) )にあったり、最大値が \(K\) の左( \(K \gt max(A)\) )だったりしたときは0にするのを忘れずに!

提出結果

n,k=map(int,input().split())
l=sorted(list(map(int,input().split())))
cnt=max(0,l[-1]-k)+max(0,k-l[0])
print(cnt)

C(Dimbula) Good Triangle

3点が面積が整数になる3角形を作れるかの問題。面積が0は作れないことに注意して3重ループで頂点を全探索して公式に当てはめれば大丈夫です。

間違えないように変数を問題文と同じにするとバグが減りそうですね。

提出結果

n=int(input())
p=[]
for i in range(n):
  p.append(list(map(int,input().split())))
cnt=0
for i in range(n):
  for j in range(i+1,n):
    for k in range(j+1,n):
      a,b=p[i]
      c,d=p[j]
      e,f=p[k]
      if abs((c-a)*(f-b)-(d-b)*(e-a))%2==0 and abs((c-a)*(f-b)-(d-b)*(e-a))!=0:
        cnt+=1
print(cnt)

D(Darjeeling) Breaker

円形のテーブルを最も効率よく1周できる方法を求める問題。 スタート地点を全探索して実際に試して最小回数を出力します。

提出結果

n=int(input())
a=list(map(int,input().split()))
ans=10**25
for i in range(n):
  pos = i;cnt=0;flag=False
  while True:
    #print(pos)
    pos+=a[pos]
    cnt+=1
    if pos>=n:
      if flag:
        break
      pos-=n;flag=True
    if pos>=i and flag:
      break
  ans=min(ans,cnt)
print(ans)

E(Earlgray) Cafe Road

ここら辺から一筋縄ではいかなさそうな問題が出てきますね。

原点を通る直線を引いて一番 \(x_i,y_i\) が被るの時の個数はいくつという問題。

ありがたいことに原点を通ってくれるので各点 \(x\) , \(y\) を通る傾きを求めて同じ傾きが一番多い個数を出力します。

ここでx=0の時ゼロ除算が発生してREになるので注意です(自分が引っ掛かりました)

提出結果

import collections as C #重複要素を数えてくれるやつが欲しい
n=int(input())
pos=[list(map(int,input().split()))for i in range(n)]
l=[]
for a,b in pos:
  if a!=0: l.append(b/a)
  else: l.append(1e20)
c=C.Counter(l) #ここで傾きの個数を数えてdict型にしてくれる
print(int(max(c.values())))

F(Keemun) '0' or '1'

必ず左か下は現在地以下でなければいけないグリッドの総数を求める問題。

逆に言えば右or上に自分未満の数字が来ないことが分かる。

これは、実験したらわかるのですが、(0,0)から(n,m)へ上or右へしか行けないときの経路の総数と同じになります。(うまく言葉で説明できないので公式解説に期待...) DPっぽく数え上げてACです。

後、この解法ではPythonで通りません... 諦めてC++を使いました。

提出結果

一応Python解

n=int(input())
m=int(input())
table=[[0]*(m+1)]*(n+1)
for i in range(n+1): table[i][0]=1
for i in range(m+1): table[0][i]=1
for i in range(1,n+1):
  for j in range(1,m+1):
    table[i][j]=(table[i][j-1]+table[i-1][j])%(1e9+7)
print(int(table[n][m]))

実行時間厳しい

Pythonの高速化まわりでアドバイス募集してます...

後かふぇこでnumpyが使えないみたいな話もあったけどどうなんだろう...

※追記 どうやら数学でO(1)が存在するらしい?ので興味があったら是非