第2回Atcoder（ABC137）

ABC137のネタバレあります！

というわけでAtcoder編第2回始まりました，三十三間党です．

とりあえず今回から，ABCの復習をしていこうと思います．

ちなみに先週のABC136のパフォーマンスは299でした．

16分ほどでAとBを解き，CかDが解けそうだと思ったのですが，TLEが出てしまい爆死，残り20分ほどでDに取り組み，紙の上では解けても，実装が間に合いませんでした．

ではABC137の反省をしていこうと思います．パフォーマンスは609でした．

AはA+B,A-B,A*Bの中で最大の問題を出せとのことでしたのでその通りに実装しました．

a,b = map(int,input().split())
print(max(a+b,a-b,a*b))

Bは数直線上に連続して石が置かれていて，連続K個が黒で塗られている．で，ある座標Xにある石は黒いらしいと．で，塗られている可能性のある座標をすべて出力せいということでした．

これはXが連続した黒石の右端から左端になる可能性があるので，

k,x = map(int,input().split())
for i in range(x-k+1,x+k):
print(i)

と書きました．ここまでで6分54秒でした．

そしてC．

文字列を与えるのでその中で並べ替えて一致するものが何個あるか，という問題でした．

  1. import collections
  2. n = int(input())
  3. str_list = [input() for i in range(n)]
  4. col_list = []
  5. count = 0
  6. for i in range(n):
  7. c = collections.Counter(str_list[i])
  8. col_list.append(c)
  9. if c in col_list:
  10. count+=col_list.count(c)-1
  11. print(count)

最終的には上記のように書いたのですが，TLEでした．for文1つなので間に合うかと思ったのですが…countとかが遅かったのか？

最後にD.夏休み

  1. n,m = map(int,input().split())
  2. ablist = [list(map(int,input().split())) for i in range(n)]
  3. ablist = sorted(ablist,reverse = True,key = lambda x:x[1])
  4. sumh = 0
  5. count = 0
  6. for i in range(n):
  7. if ablist[count][0] <= m+1:
  8. sumh += ablist[count][1]
  9. m -= 1
  10. count += 1
  11. print(sumh)

なぜか2ケースしか合わない．かす．落ち着いてみるとなぜか報酬で並び替えとる．日数で並べ替えようね．

 

辞書，lamda，計算量の目安のことをよく知らないので調べようと思いました．

追記

CのTLEを自分なりに直して提出してACもらいました．

  1. n = int(input())
  2. str_tuple = [tuple(sorted(tuple(input()))) for i in range(n)]
  3. str_dict = {}
  4. ans = 0
  5. for i in range(n):
  6. if str_tuple[i] in str_dict:
  7. ans += str_dict[str_tuple[i]]
  8. str_dict[str_tuple[i]] += 1
  9. else:
  10. str_dict[str_tuple[i]] = 1
  11. print(ans)