tz_atcoder/abc351_c.py at main · tztechno/tz_atcoder · GitHub

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
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
abc351_c.py
#################################################
#################################################
#################################################
#################################################
#################################################
[shakayami]
N=int(input())
A=[int(i) for i in input().split()]
stack=[A[0]]
for i in range(1,N):
    if stack[-1]==A[i]:
        stack[-1]+=1
    else:
        stack.append(A[i])

    while(len(stack)>=2 and stack[-1]==stack[-2]):
        stack.pop()
        stack[-1]+=1

print(len(stack))
#################################################
[titia]
import sys
input = sys.stdin.readline

N=int(input())
A=list(map(int,input().split()))

Q=[]

for a in A:
    Q.append(a)

    while len(Q)>=2:
        if Q[-1]==Q[-2]:
            x=Q.pop()
            y=Q.pop()
            Q.append(x+1)
        else:
            break

print(len(Q))
#################################################
[AC]
[popで端から削りながら取得するか、削らずappendを使うか]

import sys
input = sys.stdin.readline

N=int(input())
A=list(map(int,input().split()))

stock=[]
for ai in A:####DIFFERENCE
  stock+=[ai]###DIFFERENCE
  while len(stock)>=2:
    if stock[-2]==stock[-1]:
      a=stock.pop()
      b=stock.pop()
      stock+=[a+1]
    else:
      break

print(len(stock))
#################################################
[my TLE]
[この操作はリストの長さに比例して時間がかかります。要素を取り出した後にリスト全体が1つずつずれるためです。
 そのため、リストの先頭から順番に要素を取り出すたびに、リスト全体をシフトする必要があり、処理に時間がかかります。]

import sys
input = sys.stdin.readline

N=int(input())
A=list(map(int,input().split()))

stock=[]
for i in range(N):
  stock+=[A.pop(0)]
  while len(stock)>=2:
    if stock[-2]==stock[-1]:
      a=stock.pop()
      b=stock.pop()
      stock+=[a+1]
    else:
      break

print(len(stock))
#################################################
[AC]
import sys
input = sys.stdin.readline

N=int(input())
A=list(map(int,input().split()))

stock=[]
for ai in A:######DIFFERENCE
  stock+=[ai]#####DIFFERENCE
  while len(stock)>=2 and stock[-2]==stock[-1]:
    a=stock.pop()
    b=stock.pop()
    stock+=[a+1]

print(len(stock))
#################################################
[my TLE]
import sys
input = sys.stdin.readline

N=int(input())
A=list(map(int,input().split()))

stock=[]
for i in range(N):
  stock+=[A.pop(0)]
  while len(stock)>=2 and stock[-2]==stock[-1]:
    a=stock.pop()
    b=stock.pop()
    stock+=[a+1]

print(len(stock))
#################################################