PythonでAtCoder Beginner Contest 155参加記

50の手習いで、pythonでのプログラミングを始めました。モチベーション維持のためにAtCorderでのBeginners Contestに参加してます。

今回は、AtCoder Beginner Contest 155参加記です。

結果

A～Fの6問中、3問がAcceptされました。

前回は5問Acceptで気分を良くしていたいのですが、今回は苦戦しました。4問はACされて、もう１問行けるかどうかくらいと前回思ってしまっていましたが甘かったです。

Acceptされた3問も苦労しました。

恥ずかしながら回答紹介

今回は、D問題で挫折中です。

解説PDFを見て、マイナス/ゼロ/プラスに場合分けしている方針、尺取り法＋二分探索という方法に近いことをしているというところは確認したのですが、まだAcceptされてません。

コンテスト時間中にも、その方針は思いついていたのですが、実装が面倒そう時間内に終わらないだろうと思ってそこまでやってませんでした。

解説PDFを見て、方針はあってそうなのですが、まだエラーが出ます。

問題は、以下の通りです。コンテストでのD問題のページはこちら

はるきちの回答コードは、以下の通りですが、これまだAcceptされていません。

尺取り法については、きちんと確認してなくて似たことしてたな程度なのですが、たぶん境界条件かまとめ加算をしている部分がおかしいのだと思います。

# スペース区切りの整数入力 N,K = map(int, input().split()) # スペース区切りの整数をリストに入力 #a = [] am = [] az = [] ap = [] iam = [] for x in list(map(int, input().split())): if x > 0: ap.append(x) elif x == 0: az.append(x) else: am.append(x) iam.append(-x) # a.append(x) ap.sort() az.sort() am.sort() iam.sort() #n = len(a)*(len(a)-1) // 2 nm = len(am)*len(ap) nz = len(az)*(len(az)-1) // 2 + len(az)*(len(am)+len(ap)) np = len(am)*(len(am)-1) // 2 + len(ap)*(len(ap)-1) // 2 #カウント関数 def cnt_func(x): ''' #工夫無し版 res1 = 0 for i in range(N-1): for j in range(i+1,N): if a[i]*a[j] <= x: res1 += 1 ''' #場合分け＆尺取り法もどき res2 = 0 if x < 0: nj = 0 for i in range(len(am)-1,-1,-1): res2 += nj for j in range(nj,len(ap)): if am[i]*ap[j] <= x: res2 += 1 else: #nj = j nj = 0 break return res2 elif x == 0: res2 += nm + nz return res2 else: res2 += nm + nz nj = 0 for i in range(len(iam)-1,0,-1): res2 += min(nj,i) for j in range(nj,i): if iam[i]*iam[j] <= x: res2 += 1 else: #nj = j nj = 0 break nj = 0 for i in range(len(ap)-1,0,-1): res2 += min(nj,i) for j in range(nj,i): if ap[i]*ap[j] <= x: res2 += 1 else: #nj = j nj = 0 break return res2 #二分探索 #下限と上限 l = -(10**18) h = 10**18 #探索本体 while h > l+1: m = (l + h) // 2 kk = cnt_func(m) if kk >= K: h = m else: l = m print(h)

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92

# スペース区切りの整数入力 N,K = map(int, input().split()) # スペース区切りの整数をリストに入力 #a = [] am = [] az = [] ap = [] iam = []   for x in list(map(int, input().split())):     if x > 0:         ap.append(x)     elif x == 0:         az.append(x)     else:         am.append(x)         iam.append(-x) #    a.append(x) ap.sort() az.sort() am.sort() iam.sort()   #n = len(a)*(len(a)-1) // 2 nm = len(am)*len(ap) nz = len(az)*(len(az)-1) // 2 + len(az)*(len(am)+len(ap)) np = len(am)*(len(am)-1) // 2 + len(ap)*(len(ap)-1) // 2   #カウント関数 def cnt_func(x):     '''     #工夫無し版     res1 = 0     for i in range(N-1):         for j in range(i+1,N):             if a[i]*a[j] <= x:                 res1 += 1     '''     #場合分け＆尺取り法もどき     res2 = 0     if x < 0:         nj = 0         for i in range(len(am)-1,-1,-1):             res2 += nj             for j in range(nj,len(ap)):                 if am[i]*ap[j] <= x:                     res2 += 1                 else:                     #nj = j                     nj = 0                     break         return res2     elif x == 0:         res2 += nm + nz         return res2     else:         res2 += nm + nz         nj = 0         for i in range(len(iam)-1,0,-1):             res2 += min(nj,i)             for j in range(nj,i):                 if iam[i]*iam[j] <= x:                     res2 += 1                 else:                     #nj = j                     nj = 0                     break         nj = 0         for i in range(len(ap)-1,0,-1):             res2 += min(nj,i)             for j in range(nj,i):                 if ap[i]*ap[j] <= x:                     res2 += 1                 else:                     #nj = j                     nj = 0                     break         return res2   #二分探索 #下限と上限 l = -(10**18) h = 10**18 #探索本体 while h > l+1:     m = (l + h) // 2     kk = cnt_func(m)     if kk >= K:         h = m     else:         l = m print(h)

提出すると、こんな感じです。ACな問題とWA（間違い）の混在状況です。全部間違いならまだいいのですが、どこかでずれてしまっているようです。手元の問題だと、安直版と同じ答えなので大丈夫と思っていたのですが。

今後に向けて

本来はデバッグさせて完成を目指すところなんでしょうが、問題が公開されていないこともあり、苦労しそうです。既にもう何時間かこれやってここまでなので。

尺取り法のサンプルコードを見て理解して、書き直した方が今後のためにも良さそうです。

今回は苦戦＆挫折のまま終了です。

はるきち