Problem:


Score : 900 points

Problem Statement

Takahashi has an empty string S and a variable x whose initial value is 0.

Also, we have a string T consisting of 0 and 1.

Now, Takahashi will do the operation with the following two steps |T| times.

Insert a 0 or a 1 at any position of S of his choice.

Then, increment x by the sum of the digits in the odd positions (first, third, fifth, ...) of S. For example, if S is 01101, the digits in the odd positions are 0, 1, 1 from left to right, so x is incremented by 2.

Print the maximum possible final value of x in a sequence of operations such that S equals T in the end.

Constraints

1 \leq |T| \leq 2 \times 10^5

T consists of 0 and 1.

Input

Input is given from Standard Input in the following format:

T

Output

Print the maximum possible final value of x in a sequence of operations such that S equals T in the end.

Sample Input 1

1101

Sample Output 1

5

Below is one sequence of operations that maximizes the final value of x to 5.

Insert a 1 at the beginning of S. S becomes 1, and x is incremented by 1.

Insert a 0 to the immediate right of the first character of S. S becomes 10, and x is incremented by 1.

Insert a 1 to the immediate right of the second character of S. S becomes 101, and x is incremented by 2.

Insert a 1 at the beginning of S. S becomes 1101, and x is incremented by 1.

Sample Input 2

0111101101

Sample Output 2

26



Sample input:
1101


Sample output:
5

Submission status: Wrong Answer

Solution code:
t = input()

odd1  = 0
even1 = 0
for i,ti in enumerate(t):
    if ti == "1":
        if i%2 == 0: even1 += 1
        else: odd1 += 1

odd_num = len(t)//2
even_num = len(t) - odd_num

ans = (1 + odd1)*odd1 //2 + odd1 * (odd_num-odd1)
ans += (1 + even1)*even1 //2 + even1 * (even_num-even1)

print(ans)

Submission status: Wrong Answer

Solution code:
T = input()
x = 0
y = T.count("0")
while True:
  if not "0" in T:
    break
  T = T.replace("0","",1)
  
  for i in range(len(T)):
    if i % 2==0:
      x += int(T[i])
      
while T:
  T = T.replace("1","",1)
  for i in range(len(T)):
    if i % 2==0:
      x += int(T[i])
print(x+y)

Submission status: Wrong Answer

Solution code:
t = list(map(int, input()))
one = t.count(1)
print(one*(one+1)//2-2)

Submission status: Wrong Answer

Solution code:
t = list(input())

zero = t.count("0")
one = len(t) - zero
rev = 1
count = 0
zero_n = 0
ans = 0

for i in range(len(t)):
    if t[i] == "1" and i % 2 == 0 and rev == 1:
        count = count + 1
    elif t[i] == "1" and i % 2 == 1 and rev == -1:
        cont = count + 1
    elif t[i] == "0":
        ans = ans + count * (zero - zero_n)
        rev = rev * -1
        zero_n = zero_n + 1

n = len(t)

if n % 2 == 0:
    ans = ans + ((n - 2) // 2) * ((n - 2) // 2 + 1) + n // 2
else:
    ans = ans + (n // 2) * (n // 2 + 1)


print(ans)

Submission status: Wrong Answer

Solution code:
str = input()
 
str_len = len(str)
 
result_count = 0
 
for i in range(str_len):
  result_count = result_count + (i+1)//2

zero_count = 0
for i in range(str_len):
  if(str[i] == '0'):
    if(i%2 == 1):
      zero_count = zero_count + 1
      result_count = result_count - zero_count

print(result_count)

Submission status: Wrong Answer

Solution code:
import sys
stdin = sys.stdin
sys.setrecursionlimit(10**6)
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
nn = lambda: list(stdin.readline().split())
ns = lambda: stdin.readline().rstrip()

t = ns()
n = len(t)

ans = 0

for i in range(n):
    m = n-i
    if i%2 == 0:#奇数
        if t[i] == '1':
            ans += m
    else:#偶数
        if t[i] == '1' and t[i-1] == '0':
            ans += m if i == n-1 and t[0] == '1' else (m-1)

print(ans)

Submission status: Wrong Answer

Solution code:
from functools import lru_cache
import sys
sys.setrecursionlimit(50000)

t = input()
s = t

def calc(s):
    return len([i for i in list(s[::2]) if i == '1'])

@lru_cache(maxsize=None)
def loop_cache(s):
    if len(s) == 0:
        return 0
    elif s[-1] == '0':
        return calc(s) + loop_cache(s[:-1])
    else:
        return calc(s) + max([loop_cache(s[:j]+s[j+1:]) for j in range(len(s))])

res = loop_cache(s)
print(res)

Submission status: Wrong Answer

Solution code:
t = input()
one = t.count("1")
zero = t.count("0")
if one % 2 == 0:
    tmp = one // 2
    ans = tmp * (tmp + 1)
else:
    tmp = one // 2
    ans = (tmp + 1) ** 2
    
before_zero = []
zero_cnt = 0
zero_start = 99999999
for i, num in enumerate(t):
    before_zero.append(zero_cnt)
    if num == "0":
        zero_cnt += 1
        if zero_start == 99999999:
            zero_start = i

ans_tmp = ans
for i, num in enumerate(t):
    if num == "0":
        continue
    if (i + before_zero[i]) % 2 == 0:
        ans += (zero - before_zero[i]) + (before_zero[i]) // 2
    else:
        ans += (before_zero[i] + 1) // 2

for i, num in enumerate(t):
    if num == "0":
        continue
    if i < zero_start:
        if i % 2 == 0:
            ans_tmp += zero
        continue
    if (i + before_zero[i]) % 2 == 1:
        ans_tmp += (zero - before_zero[i] + 1) + (before_zero[i] - 1) // 2
    else:
        ans_tmp += (before_zero[i]) // 2

print(max(ans, ans_tmp))

Submission status: Wrong Answer

Solution code:
T = list(str(input()))
x = 0

def count(T):
    x = 0
    for i in range(len(T)):
        if i % 2 == 1 and T[i] == "1":
            x += 1
    return x
    

for i in range(len(T)):
    x += count(T)
    try:
        T.remove("0")
    except ValueError:
        pass

print(x)

Submission status: Wrong Answer

Solution code:
T = list(map(int, input()))
# print(T)
ans = 0
for i in range(len(T)):
    ans += sum(T[::2])
    if 0 in T:
        T.remove(0)
    else:
        T.pop()
print(ans)

Submission status: Wrong Answer

Solution code:
t = input()
one = t.count("1")
zero = t.count("0")
if one % 2 == 0:
    tmp = one // 2
    ans = tmp * (tmp + 1)
else:
    tmp = one // 2
    ans = (tmp + 1) ** 2
    
even_one = 0
before_zero = []
zero_cnt = 0
for i, num in enumerate(t):
    if i % 2 == 0 and num == "1":
        even_one += 1
    before_zero.append(zero_cnt)
    if num == "0":
        zero_cnt += 1
        
for i, num in enumerate(t):
    if num == "0":
        continue
    if (i + before_zero[i]) % 2 == 0:
        ans += (zero - before_zero[i]) + (before_zero[i]) // 2
    else:
        ans += (before_zero[i] + 1) // 2
print(ans)

Submission status: Wrong Answer

Solution code:
t = input()

l = len(t)

x = 0

for i in range(l):
    x += sum(list(map(int, t[0 : i + 1: 2])))

print(x)

Submission status: Wrong Answer

Solution code:
t = list(input())

ans = 0
zero = 0

for i in range(len(t)):
    if t[i] == "0":
        zero = zero + 1
    elif i % 2 == 0 and t[i] == "1":
        ans = ans + 1

for i in range(zero):
    t.remove("0")
    for i in range(len(t)):
        if i % 2 == 0 and t[i] == "1":
            ans = ans + 1

n = len(t)

if n % 2 == 0:
    ans = ans + ((n - 2) // 2) * ((n - 2) // 2 + 1) + n // 2
else:
    ans = ans + (n // 2) * (n // 2 + 1)


print(ans)

Submission status: Wrong Answer

Solution code:
t = list(map(int, input()))
one = 0
zero = 0
for i in range(len(t)-1):
    if t[i] == 1:
        one += 1
        if t[i+1] == 0:
            zero += 1
if t[-1] == 1:
    one += 1
ans = one * (one+1) // 2
ans -= zero
print(ans)

Submission status: Wrong Answer

Solution code:
t = list(map(int, input()))
one = 0
zero = 0
for i in range(len(t)-1):
    if t[i] == 1:
        one += 1
        if t[i+1] == 0:
            zero += 1
print(one)
if t[-1] == 1:
    one += 1
ans = one * (one+1) // 2
ans -= zero
print(ans)

Submission status: Time Limit Exceeded

Solution code:

n = input()

zero_list = []
z_count = 0
ans = 0
for i in range(len(n)):
    if n[i] == "0":
        z_count += 1
    else:
        zero_list.append(z_count)
        z_count = 0
zero_list.append(z_count)

ones = n.count("1")

for i in range(1,ones+1):
    if i % 2 == 0:
        ans += i//2
    else:
        ans += i//2 + 1
             
test_string = ""
if ones % 2 == 0:
    test_string = "10"*(ones//2)
else:
    test_string = "10"*(ones//2)+"1"

for i in range(len(test_string)):
    if test_string[i] == "0" and zero_list[i] > 0:
        test_string = test_string[0:i]+test_string[i:len(test_string)].replace("0","2").replace("1", "0").replace("2", "1") 
        zero_list[i] -= 1
        ans += test_string.count("1")

#remove more than 1 zeros
for i in range(len(zero_list)):
    while zero_list[i] > 1:
        zero_list[i] -= 2
        ans += test_string[0:i].count("1") * 2 + len(test_string) - i

#remove last zero from back
for i in range(len(zero_list)-1,-1,-1):
    if zero_list[i] == 1:
        test_string = test_string[0:i]+test_string[i:len(test_string)].replace("0","2").replace("1", "0").replace("2", "1") 
        zero_list[i] -= 1
        ans += test_string.count("1")

print(ans)

Submission status: Time Limit Exceeded

Solution code:

n = input()
zero_list = []
z_count = 0
ans = 0
for i in range(len(n)):
    if n[i] == "0":
        z_count += 1
    else:
        zero_list.append(z_count)
        z_count = 0
zero_list.append(z_count)

ones = n.count("1")

for i in range(1,ones+1):
    if i % 2 == 0:
        ans += i//2
    else:
        ans += i//2 + 1
             
test_string = ""
if ones % 2 == 0:
    test_string = "10"*(ones//2)
else:
    test_string = "10"*(ones//2)+"1"

for i in range(len(test_string)):
    if test_string[i] == "0" and zero_list[i] > 0:
        test_string = test_string[0:i]+test_string[i:len(test_string)].replace("0","2").replace("1", "0").replace("2", "1") 
        zero_list[i] -= 1
        ans += test_string.count("1")

#remove more than 1 zeros
for i in range(len(zero_list)):
    while zero_list[i] > 1:
        zero_list[i] -= 2
        ans += test_string[0:i].count("1") * 2 + len(test_string) - i

#remove last zero from back
for i in range(len(zero_list)-1,-1,-1):
    if zero_list[i] == 1:
        test_string = test_string[0:i]+test_string[i:len(test_string)].replace("0","2").replace("1", "0").replace("2", "1") 
        zero_list[i] -= 1
        ans += test_string.count("1")

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import math
import re
T=input()
x=0
Td=T
d = len(re.sub(r'0', '', Td))
x += math.ceil((d/2+1)*d/2)
spT = T.split('0')
lenT = list(map(len, spT))

tmpX = math.ceil(d/2)
bT = 0
aT = d
tmp = ''
for i in range(len(spT) - 1):
    tmp += spT[i]
    bT += lenT[i]
    aT -= lenT[i]
    if bT % 2==1:
        bT += 1
        if aT % 2 ==1:
            tmpX += 1
        x += tmpX
        tmp += '0'
    else:
        tmp +='+'
tmp += spT[-1]

spT = tmp.split('+')
vT =[]
aT = bT
bT = 0
odT = 0
tmpOd = True
for i in range(len(spT)):
    
    od = len(re.sub(r'0', '', spT[i][0 if tmpOd else 1::2]))
    ev = len(re.sub(r'0', '', spT[i][1 if tmpOd else 0::2]))
    odT += od
    vT.append(od - ev)
    if len(spT[i]) %2 == 1:
        tmpOd = not tmpOd

while len(vT) >1:
    odT = odT - vT[-1]
    x += odT
    vT[-2] = vT[-2] - vT[-1]
    vT = vT[:-1]

print(x)

Submission status: Time Limit Exceeded

Solution code:
import math
import re
T=input()
x=0
Td=T
d = len(re.sub(r'0', '', Td))
x += math.ceil((d/2+1)*d/2)
spT = T.split('0')
lenT = list(map(len, spT))

tmpX = math.ceil(d/2)
bT = 0
aT = d
tmp = ''
for i in range(len(spT) - 1):
    tmp += spT[i]
    bT += lenT[i]
    aT -= lenT[i]
    if bT % 2==1:
        bT += 1
        if aT % 2 ==1:
            tmpX += 1
        x += tmpX
        tmp += '0'
    else:
        tmp +='+'
tmp += spT[-1]

spT = tmp.split('+')
vT =[]
aT = bT
bT = 0
odT = 0
#ccT = 0
for i in range(len(spT)):
    vT.append([len(re.sub(r'0', '', spT[i][::2])), len(re.sub(r'0', '', spT[i][1::2]))])
    odT += vT[-1][0]
    #ccT += vT[-1][1]

while len(vT) >1:
    tmpIdx = len(vT)-1
    tmpL = 0
    tmpMax = -1
    for i in reversed(range(1, len(vT))):
        tmpL += vT[i][1] - vT[i][0]
        if tmpMax  < odT + tmpL:
            tmpIdx = i
            tmpMax = odT + tmpL

    for i in (range(tmpIdx, len(vT))):
        tmpVT = vT[i][1]
        vT[i][1] = vT[i][0]
        vT[i][0] = tmpVT
    odT = tmpMax
    x += odT
    vT[tmpIdx-1][0] += vT[tmpIdx][0]
    vT[tmpIdx-1][1] += vT[tmpIdx][1]
    del vT[tmpIdx]

print(x)

Submission status: Time Limit Exceeded

Solution code:
t = input()
keep = True
keeped_ones = 0
n0 = 0
ones = [] # (number of zeros before 1, is_odd)
for i, x in enumerate(t):
    if x == '0':
        n0 += 1
        keep = True
    elif x == '1':
        if keep:
            ones.append((n0, (i+1)%2))
            keep = False
        else:
            keeped_ones += 1
            ones = ones[:-1]
            keep = True

ans = keeped_ones * n0
for n0_before, is_odd in ones:
    ans += (n0_before + is_odd)//2 + (n0 - n0_before)
ans += (keeped_ones + (len(ones)+1)//2) * (keeped_ones + len(ones)//2 + 1)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
S=list(input())
N=len(S)
X=0

current = list(map(lambda x: int(x), S))
x = sum(current[0::2])

_current = current.copy()
for i in range(N):
  _n = len(_current)
  #print("_current=",_current,_n)
  _x_max = -1
  idx_max = -1
  for i in range(_n):
    _c = _current.copy()
    _c.pop(i)
    #print("_c=",_c)
    _x = sum(_c[0::2])
    if _x_max < _x:
      _x_max = _x
      idx_max = i
  
  x += _x_max
  _current.pop(idx_max)
  
print(x)

Submission status: Time Limit Exceeded

Solution code:
def calc(li):
    return li[0::2].count('1')


if __name__ == "__main__":
    t = list(input())
    s = ''
    x = 0

    for i in range(len(t)):
        pass

    while t:
        x += calc(t)
        temp = []
        for i in range(len(t)):
            s = t[0:i] + t[i+1:]
            temp.append(calc(s))
        t.pop(temp.index(max(temp)))

    print(x)

Submission status: Time Limit Exceeded

Solution code:
T = list(input())

x = 0
while len(T) != 0:
    x += sum([int(f) for f in T[::2]])

    xmax = 0
    delIdx = 0
    for i in range(len(T)):
        T_copy = T.copy()
        _tmp = T_copy.pop(i)

        _x = sum([int(f) for f in T_copy[::2]])

        if _x > xmax:
            xmax = _x
            delIdx = i

    T.pop(delIdx)

print(x)

Submission status: Time Limit Exceeded

Solution code:
def eval(string):
    return sum([int(s) if i % 2 == 0 else 0 for i, s in enumerate(string)])


def main():
    T = list(input())
    length = len(T)
    ans = eval(T)
    for _ in range(length-1):
        tmp = T[1:]
        next_T = tmp[:]
        max_score = eval(tmp)
        last_score = max_score
        for i in range(len(T)-1):
            score = last_score
            if i % 2 == 0:
                score = score + int(T[i]) - int(tmp[i])
            tmp[i] = T[i]
            if score > max_score:
                max_score = score
                next_T = tmp[:]
            last_score = score
        ans += max_score
        T = next_T[:]
    print(ans)


main()

Submission status: Time Limit Exceeded

Solution code:
T = list(input())

x = 0
while len(T) != 0:
    x += sum([int(f) for f in T[::2]])

    xmax = 0
    delIdx = 0
    for i in range(len(T)):
        if T[i] == "0":
            T_copy = T.copy()
            _tmp = T_copy.pop(i)

            _x = sum([int(f) for f in T_copy[::2]])

            if _x > xmax:
                xmax = _x
                delIdx = i

    T.pop(delIdx)

print(x)

Submission status: Time Limit Exceeded

Solution code:

T = tuple(map(int, input()))
N = len(T)

def cul(t):
  res = 0
  for i in range(0, len(t), 2):
    res = res + t[i]
  return res

ans = cul(T)


for k in range(N, 0, -1):
  p = list()
  for n in range(k):
    Td = list(T)
    del Td[n]
    pd = [Td, cul(Td)]
    p.append(pd)

  q = max(p, key=lambda x:x[1])
  ans = ans + q[1]
  T = tuple(q[0])

print(ans)

Submission status: Time Limit Exceeded

Solution code:
T = list(input())

x = 0
while len(T) != 0:
    x += sum([int(f) for f in T[::2]])

    xmax = 0
    delIdx = 0
    for i in range(len(T)):
        T_copy = T.copy()
        _tmp = T_copy.pop(i)

        _x = sum([int(f) for f in T_copy[::2]])

        if _x > xmax:
            xmax = _x
            delIdx = i

        if xmax == len(T_copy[::2]):
            break

    T.pop(delIdx)

print(x)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
# E

import sys
from collections import defaultdict, deque
from heapq import heappush, heappop
import math
import bisect
from itertools import accumulate

input = sys.stdin.readline

# 再起回数上限変更
# sys.setrecursionlimit(1000000)

T = list(input())[:-1]
T = [int(t) for t in T]

T1 = [0] + list(accumulate(T[0::2]))
T2 = [0] + list(accumulate(T[1::2]))

res = T1[-1]

for _ in range(len(T)):
    # print(T, T1, T2)
    val = -1
    same = len(T1)==len(T2)

    # 全て1ならどこでも同じ
    if sum(T) == len(T):
        idx = 0
        flg = True
        if (len(T)-1) % 2 == 0:
            res += (sum(T)-1) // 2
        else:
            res += sum(T) // 2
    else:
        for i in range(1, len(T1)):
            val1 = T1[i-1] + T2[-1] - T2[i-1]

            if (i == len(T1)-1) and (not same):
                val2 = -1
            else:
                val2 = T1[i] + T2[-1] - T2[i]
            # print(i, val1, val2)

            if max(val1, val2) > val:
                val = max(val1, val2)
                idx, flg = i-1, val1 > val2
        res += val

    # print(i, idx)
    if flg:
        T.pop(idx*2)
    else:
        T.pop(idx*2+1)

    T1 = [0] + list(accumulate(T[0::2]))
    T2 = [0] + list(accumulate(T[1::2]))

print(res)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
# E

import sys
from collections import defaultdict, deque
from heapq import heappush, heappop
import math
import bisect
from itertools import accumulate

input = sys.stdin.readline

# 再起回数上限変更
# sys.setrecursionlimit(1000000)

T = list(input())[:-1]
T = [int(t) for t in T]

T1 = [0] + list(accumulate(T[0::2]))
T2 = [0] + list(accumulate(T[1::2]))

res = T1[-1]

for _ in range(len(T)):
    # print(T, T1, T2)
    val = -1
    same = len(T1)==len(T2)

    for i in range(1, len(T1)):
        val1 = T1[i-1] + T2[-1] - T2[i-1]

        if (i == len(T1)-1) and (not same):
            val2 = -1
        else:
            val2 = T1[i] + T2[-1] - T2[i]
        # print(i, val1, val2)

        if max(val1, val2) > val:
            val = max(val1, val2)
            idx, flg = i-1, val1 > val2
    res += val

    # print(i, idx)
    if flg:
        T.pop(idx*2)
    else:
        T.pop(idx*2+1)

    T1 = [0] + list(accumulate(T[0::2]))
    T2 = [0] + list(accumulate(T[1::2]))

print(res)

Submission status: Time Limit Exceeded

Solution code:
T = list(input())

x = 0
while len(T) != 0:
    x += sum([True if f == "1" else False for f in T[::2]])

    xmax = 0
    delIdx = 0
    for i in range(len(T)):
        T_copy = T.copy()
        _tmp = T_copy.pop(i)

        _x = sum([True if f == "1" else False for f in T_copy[::2]])

        if _x > xmax:
            xmax = _x
            delIdx = i

    T.pop(delIdx)

print(x)

Submission status: Time Limit Exceeded

Solution code:
T = input()
ans = 0
length = len(T)


def eval(string):
    return sum([int(s) if i % 2 == 0 else 0 for i, s in enumerate(string)])


ans += eval(T)
for _ in range(length-1):
    max_score = -1
    next_T = T
    for i in range(len(T)):
        tmp = T[:i] + T[i+1:]
        score = eval(tmp)
        if score > max_score:
            max_score = score
            next_T = tmp
    ans += max_score
    T = next_T
print(ans)

Submission status: Accepted

Solution code:
from itertools import groupby, accumulate


def solve(t):
    grp = [(c, len(list(itr))) for c, itr in groupby(t)]
    even_ones = 0
    zeros_splitting_odd_ones = [0]
    for c, cnt in grp:
        if c == '1':
            if cnt % 2 == 0:
                even_ones += cnt
            else:
                even_ones += cnt - 1
                zeros_splitting_odd_ones.append(0)
        else:
            zeros_splitting_odd_ones[-1] += cnt

    # 初期状態で加算されるか
    ad = int(zeros_splitting_odd_ones[0] % 2 == 0)
    is_added_init = [ad]
    for cnt in zeros_splitting_odd_ones[1:]:
        ad ^= (cnt % 2) ^ 1
        is_added_init.append(ad)
    is_added_init.pop()
    acc_added_init = list(accumulate(reversed(is_added_init)))  # 自分より右で、初期状態で足される1の数
    acc_added_init.reverse()

    odd_ones = len(is_added_init)
    ans = 0

    if odd_ones > 0:

        # 先頭の0を全て除くまでのスコア
        zso = zeros_splitting_odd_ones[0]
        zso1 = zso // 2
        zso0 = zso - zso1
        ans += acc_added_init[0] * zso0
        ans += (odd_ones - acc_added_init[0]) * zso1

        # 1に挟まれた0を1箇所1つずつ残して全て除くまでのスコア
        ad = int(zeros_splitting_odd_ones[0] % 2 == 0)
        for i in range(1, odd_ones):
            zso = zeros_splitting_odd_ones[i] - 1
            zso1 = zso // 2
            zso0 = zso - zso1
            left_ones = i
            right_ones = odd_ones - left_ones
            ans += left_ones * zso  # 区間より左の"1"は全てスコアに足される
            ans += left_ones + (right_ones + 1) // 2  # 最後に1つ残った0を削除するときのスコア
            if ad:
                # 除外中の0区間の次の"1"が初期状態で足されるなら、区間を操作する直前にも足される
                ans += acc_added_init[i] * zso0
                ans += (right_ones - acc_added_init[i]) * zso1
            else:
                # 除外中の0区間の次の"1"が初期状態で足されるなら、区間を操作する直前には足されない
                ans += (right_ones - acc_added_init[i]) * zso0
                ans += acc_added_init[i] * zso1
            ad ^= zso % 2

        # 末尾の0を全て除くまでのスコア
        ans += zeros_splitting_odd_ones[-1] * odd_ones

    # 1だけの列を1つずつ除いていくスコア
    all_ones = odd_ones + even_ones
    ao1 = all_ones // 2
    ao0 = all_ones - ao1
    ans += (ao0 * (ao0 + 1) + ao1 * (ao1 + 1)) // 2

    # 0を除いている間の、偶数個の1によるスコア
    all_zeros = len(t) - all_ones
    ans += all_zeros * (even_ones // 2)

    return ans


t = input()
print(solve(t))

Submission status: Accepted

Solution code:
from itertools import groupby, accumulate


def solve(t):
    grp = [(c, len(list(itr))) for c, itr in groupby(t)]
    even_ones = 0
    zeros_splitting_odd_ones = [0]
    for c, cnt in grp:
        if c == '1':
            if cnt % 2 == 0:
                even_ones += cnt
            else:
                even_ones += cnt - 1
                zeros_splitting_odd_ones.append(0)
        else:
            zeros_splitting_odd_ones[-1] += cnt

    # 初期状態で加算されるか
    ad = int(zeros_splitting_odd_ones[0] % 2 == 0)
    is_added_init = [ad]
    for cnt in zeros_splitting_odd_ones[1:]:
        ad ^= (cnt % 2) ^ 1
        is_added_init.append(ad)
    is_added_init.pop()
    acc_added_init = list(accumulate(reversed(is_added_init)))  # 自分より右で、初期状態で足される1の数
    acc_added_init.reverse()

    odd_ones = len(is_added_init)
    ans = 0

    if odd_ones > 0:

        # 先頭の0を全て除くまでのスコア
        zso = zeros_splitting_odd_ones[0]
        zso1 = zso // 2
        zso0 = zso - zso1
        ans += acc_added_init[0] * zso0
        ans += (odd_ones - acc_added_init[0]) * zso1

        # 1に挟まれた0を1箇所1つずつ残して全て除くまでのスコア
        ad = int(zeros_splitting_odd_ones[0] % 2 == 0)
        for i in range(1, odd_ones):
            zso = zeros_splitting_odd_ones[i] - 1
            zso1 = zso // 2
            zso0 = zso - zso1
            fixed_ones = i
            right_ones = odd_ones - fixed_ones
            ans += fixed_ones * zso
            if ad:
                # 除外中の0区間の次の"1"が初期状態で足されるなら、区間を操作する直前にも足される
                ans += acc_added_init[i] * zso0
                ans += (right_ones - acc_added_init[i]) * zso1
            else:
                # 除外中の0区間の次の"1"が初期状態で足されないなら、区間を操作する直前には足される
                ans += (right_ones - acc_added_init[i]) * zso0
                ans += acc_added_init[i] * zso1
            ad ^= zso % 2

        # 末尾の0を全て除くまでのスコア
        ans += zeros_splitting_odd_ones[-1] * odd_ones

        # 1に挟まれた0を右から除いていくまでのスコア
        for i in range(1, odd_ones):
            left_ones = odd_ones - i
            right_ones = i
            ans += left_ones + (right_ones + 1) // 2

    # 1だけの列を1つずつ除いていくスコア
    all_ones = odd_ones + even_ones
    ao1 = all_ones // 2
    ao0 = all_ones - ao1
    ans += (ao0 * (ao0 + 1) + ao1 * (ao1 + 1)) // 2

    # 0を除いている間の、偶数個の1によるスコア
    all_zeros = len(t) - all_ones
    ans += all_zeros * (even_ones // 2)

    return ans


t = input()
print(solve(t))

Submission status: Accepted

Solution code:
from itertools import groupby, accumulate


def solve(t):
    if t[0] == '0':
        preceding_zeros = len(t)
        t = t.lstrip('0')
        preceding_zeros -= len(t)
    else:
        preceding_zeros = 0

    if len(t) == 0:
        return 0

    grp = [(c, len(list(itr))) for c, itr in groupby(t)]
    even_ones = 0
    zeros_splitting_odd_ones = [preceding_zeros]
    for c, cnt in grp:
        if c == '1':
            if cnt % 2 == 0:
                even_ones += cnt
            else:
                even_ones += cnt - 1
                zeros_splitting_odd_ones.append(0)
        else:
            zeros_splitting_odd_ones[-1] += cnt

    # print(even_ones)
    # print(zeros_splitting_odd_ones)

    # 初期状態で加算されるか
    ad = int(zeros_splitting_odd_ones[0] % 2 == 0)
    is_added_init = [ad]
    for cnt in zeros_splitting_odd_ones[1:]:
        ad ^= (cnt % 2) ^ 1
        is_added_init.append(ad)
    is_added_init.pop()
    acc_added_init = list(accumulate(reversed(is_added_init)))  # 自分より右で、初期状態で足される1の数
    acc_added_init.reverse()

    odd_ones = len(is_added_init)
    ans = 0

    if odd_ones > 0:

        # 先頭の0を全て除くまでのスコア
        zso = zeros_splitting_odd_ones[0]
        zso1 = zso // 2
        zso0 = zso - zso1
        ans += acc_added_init[0] * zso0
        ans += (odd_ones - acc_added_init[0]) * zso1
        # print(ans)

        # 1に挟まれた0を1箇所1つずつ残して全て除くまでのスコア
        ad = int(zeros_splitting_odd_ones[0] % 2 == 0)
        for i in range(1, odd_ones):
            zso = zeros_splitting_odd_ones[i] - 1
            zso1 = zso // 2
            zso0 = zso - zso1
            fixed_ones = i
            right_ones = odd_ones - fixed_ones
            ans += fixed_ones * zso
            if ad:
                # 除外中の0区間の次の"1"が初期状態で足されるなら、区間を操作する直前にも足される
                ans += acc_added_init[i] * zso0
                ans += (right_ones - acc_added_init[i]) * zso1
            else:
                # 除外中の0区間の次の"1"が初期状態で足されないなら、区間を操作する直前には足される
                ans += (right_ones - acc_added_init[i]) * zso0
                ans += acc_added_init[i] * zso1
            ad ^= zso % 2
        # print(ans)

        # 末尾の0を全て除くまでのスコア
        ans += zeros_splitting_odd_ones[-1] * odd_ones
        # print(ans)

    # 1に挟まれた0を右から除いていくまでのスコア
    for i in range(1, odd_ones):
        left_ones = odd_ones - i
        right_ones = i
        ans += left_ones + (right_ones + 1) // 2
    # print(ans)

    # 1だけの列を1つずつ除いていくスコア
    all_ones = odd_ones + even_ones
    ao1 = all_ones // 2
    ao0 = all_ones - ao1
    ans += (ao0 * (ao0 + 1) + ao1 * (ao1 + 1)) // 2
    # print(ans)

    # 0を除いている間の、偶数個の1によるスコア
    all_zeros = len(t) - all_ones + preceding_zeros
    ans += all_zeros * (even_ones // 2)

    return ans


t = input()
print(solve(t))

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SI(): return sys.stdin.readline()[:-1]

def main():
    s=SI()
    n=len(s)
    n2=n//2
    ans=n2*(n2+1)+n%2*(n2+1)
    #print(ans)
    rem=0
    for i,c in enumerate(s):
        if c=="1":continue
        ans-=(rem+1)//2
        if rem%2==0 and i%2==0:ans-=1
        if (i-rem)%2==0:rem+=1
    print(ans)

main()

Submission status: Accepted

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")

t = input()
s = t.replace("0", "")
q = len(s) # 1の数
n = len(t)
ps = [None]*(q+1)
c = 0
j = 0
for tmp in t:
    if tmp=="1":
        ps[j] = c
        j += 1
        c = 0
    else:
        c += 1
ps[-1] = c

dp = [0] * q # インデックスqの1までのベストな配置のときの奇数の個数
pp = [0] * (q+1) # 上を実現するために使うpsの個数
if not dp:
    print(0)
else:
    dp[0] = 1
    j = 1 # j : トータルのインデックス(1はじまり)
    for i in range(1,q):
        j += 1
        p = ps[i]
        if j%2:
            pp[i] = 0
            dp[i] = dp[i-1] + 1
        elif p:
            pp[i] = 1
            j += 1
            dp[i] = dp[i-1] + 1
        else:
            pp[i] = 0
            dp[i] = dp[i-1]
    if q%2==0:
        ans = q//2 * (q//2 + 1)
    else:
        ans = q//2 * (q//2 + 1) + q//2 + 1
    
    # 1をすべて入れたあとに得られる利得
    # ppを前から順にいれていく
    j = 0
    for i in range(q+1):
        j += 1
        if not pp[i]:
            continue
        # 0を１個いれる
        j += 1
        ans += dp[i]
        if j%2:
            ans += (q-i-1) // 2
        else:
            ans += (q-i-1) // 2 + (q-i-1)%2
    
    # 残りのpsを後ろから順にいれていく
    o = 0 # 現時点より後ろの(jを0としたときの)奇数番目の1の個数
    e = 0 # 現時点より後ろの(jを0としたときの)偶数番目の1の個数
    j = q + sum(pp) # 現在地のインデックス(1はじまり)
    for i in range(q, 0, -1):
        num = ps[i] - pp[i]
        if num>0:
            ans += dp[i-1] * num
            if num%2==0:
                ans += (num//2)*o + (num//2)*e
            else:
                ans += (num//2)*o + (num//2)*e + (e if j%2==0 else o)
                e,o = o,e
        j -= 1
        if pp[i-1]:
            j -= pp[i-1]
            e += 1
        else:
            o, e = 1 + e, o

    # 最初の0を入れる
    num = ps[0] - pp[0]

    if num%2==0:
        ans += (num//2)*o + (num//2)*e
    else:
        ans += (num//2)*o + (num//2)*e + e if j%2==0 else o

    print(ans)

Submission status: Accepted

Solution code:
import math
import re
T=input()
x=0
Td=T
d = len(re.sub(r'0', '', Td))
x += math.ceil((d/2+1)*d/2)
spT = T.split('0')
lenT = list(map(len, spT))

tmpX = math.ceil(d/2)
bT = 0
aT = d
tmp = ''
for i in range(len(spT) - 1):
    tmp += spT[i]
    bT += lenT[i]
    aT -= lenT[i]
    if bT % 2==1:
        bT += 1
        if aT % 2 ==1:
            tmpX += 1
        x += tmpX
        tmp += '0'
    else:
        tmp +='+'
tmp += spT[-1]

spT = tmp.split('+')
vT =[]
aT = bT
bT = 0

odT = 0
tmpOd = True

for i in range(len(spT)):
    
    od = len(re.sub(r'0', '', spT[i][0 if tmpOd else 1::2]))
    ev = len(re.sub(r'0', '', spT[i][1 if tmpOd else 0::2]))
    odT += od
    vT.append(od - ev)
    if len(spT[i]) %2 == 1:
        tmpOd = not tmpOd

for i in reversed(range(1, len(spT))):
    odT = odT - vT[i]
    x += odT
    vT[i-1] -= vT[i]


print(x)

Submission status: Accepted

Solution code:
T=input()
i=r=a=k=0
for c in T:a+=(i//2-k//2+(~k&1)*(len(T)-i))*(c=="1");i+=1;k-=(~k&1)*(c=='0')-1
print(a)

Submission status: Accepted

Solution code:
T=input()
i=r=a=k=0
for c in T:a+=(i//2-k//2+(~k&1)*(len(T)-i))*(c=="1");i+=1;k-=(~k&1)*(c=='0')-1;
print(a)

Submission status: Accepted

Solution code:
T=input()
n=len(T)
i=r=a=0
for c in T:k=i-r;r+=(~k&1)*(c=='0');a+=(i//2-k//2+(~k&1)*(n-i))*(c=="1");i+=1
print(a)

Submission status: Accepted

Solution code:
T=input()
n=len(T)
i=r=a=0
for c in T:
  k=i-r
  if c=='0':
    r+=~k&1
  else:
    a+=i//2-k//2+(~k&1)*(n-i)
  i+=1
print(a)

Submission status: Accepted

Solution code:
t=input()
n=len(t)
pos=[]
sum=0
for i in range(n):
  if t[i]=="1":
    sum+=1
  else:
    pos.append(sum)
x=(sum+1)//2*((sum+2)//2)
sz=len(pos)
cnt=0
res=[]
for i in range(sz):
  if ((pos[i]&1)^(cnt&1)):
    sum+=1
    cnt+=1
    x+=(sum+1)//2
  else:
    res.append(i)
res=res[::-1]
odd=0
even=0
for i in range(len(res)):
  sum+=1
  if i&1:
    odd = sz - res[i] - even
    x+=(sum+1)//2-odd
  else:
    even=sz-res[i]-odd
    x+=(sum+1)//2-even
print(x)