Problem:

日本沈没 (Japan Sinks)

問題文

日本列島は細長い列島である．日本列島は平行な境界線により N 個の区画に分けられている．区画には端から順に 1 から N の番号が付けられている．区画 i (1 ≦ i ≦ N) の高さは A_i である．

日本列島は海に囲まれており，海面の高さは場所によらず一定である．高さが海面の高さより高い区画を陸地と呼ぶ．

陸地が連続している部分のことを島と呼ぶ．より正確に書くと以下の通りである．整数 l, r (1 ≦ l ≦ r ≦ N) について，日本列島のうち区画 l，区画 l+1，...，区画 r からなる部分を領域 [l, r] という．以下の条件を満たす領域 [l, r] を島という：

区画 l，区画 l+1，...，区画 r はすべて陸地である．

l>1 ならば区画 l-1 は陸地ではない．

r<N ならば区画 r+1 は陸地ではない．

海面の上昇により，日本列島は少しずつ沈没している．現在の海面の高さは 0 であるが，これは時間が経つにつれて徐々に上がり，ついには日本全体が海になってしまう．

JOI 君は，海面の高さが上昇すると，日本の島の数が増減することに気付いた．現在から，日本に陸地がなくなるまでの間 (現在も含む) における，島の数の最大値を求めたい．

制約

1 ≦ N ≦ 100000 (= 10^5)

0 ≦ A_i ≦ 1000000000 (= 10^9) (1 ≦ i ≦ N)

入力・出力

入力

入力は以下の形式で標準入力から与えられる．

N

A_1 A_2 ... A_N

出力

現在から，日本に陸地がなくなるまでの間 (現在も含む) における，島の数の最大値を 1 行で出力せよ．

7 点) N ≦ 2000, A_i ≦ 2000 (1 ≦ i ≦ N)

(8 点) N ≦ 2000

(85 点) 追加の制約はない．

-->

入出力例

入力例 1

6
0 1 2 1 3 2

出力例 1

2

海面の高さが 0 以上 1 未満のとき，区画 2, 3, 4, 5, 6 が陸地である．領域 [2, 6] が唯一の島なので，島の数は 1 である．

海面の高さが 1 以上 2 未満のとき，区画 3, 5, 6 が陸地である．領域 [3, 3] と領域 [5, 6] が島なので，島の数は 2 である．

海面の高さが 2 以上 3 未満のとき，区画 5 のみが陸地である．領域 [5, 5] が唯一の島なので，島の数は 1 である．

海面の高さが 3 になると，陸地はなくなり，島の数は 0 になる．

よって島の数の最大値は 2 なので，2 を出力する．

入力例 2

6
3 2 3 0 2 0

出力例 2

2

海面の高さが 0 以上 2 未満のとき，区画 1, 2, 3, 5 が陸地である．領域 [1, 3] と領域 [5, 5] が島なので，島の数は 2 である．

海面の高さが 2 以上 3 未満のとき，区画 1, 3 が陸地である．領域 [1, 1] と領域 [3, 3] が島なので，島の数は 2 である．

海面の高さが 3 になると，陸地はなくなり，島の数は 0 になる．

よって島の数の最大値は 2 なので，2 を出力する．

入力例 3

10
4 1 2 1 2 3 5 4 3 2

出力例 3

3

情報オリンピック日本委員会作 『第 18 回日本情報オリンピック JOI 2018/2019 予選競技課題』



Sample input:
6
0 1 2 1 3 2


Sample output:
2

Submission status: Time Limit Exceeded

Solution code:
N = int(raw_input())
a = map(int, raw_input().split())
field = []
for i in range(0, N):
	field.append(a[i])
a.sort()
heightlist = [a[0]]
for i in range(1, N):
	if heightlist[-1] != a[i]:
		heightlist.append(a[i])
island = []
lst = [-1, -1]
for i in range(0, N):
	if lst[0] == -1:
		if field[i] != 0:
			lst[0] = i
	else:
		if field[i] == 0:
			lst[1] = i-1
			island.append(lst)
			lst = [-1, -1]
	if i == N-1 and lst[0] != -1:
		lst[1] = N-1
		island.append(lst)
max = len(island)
for i in range(0, len(heightlist)):
	newisland = []
	for j in range(0, len(island)):
		newlst = [-1, -1]
		for k in range(island[j][0], island[j][1]+1):
			if newlst[0] == -1:
				if field[k] != heightlist[i]:
					newlst[0] = k
			else:
				if field[k] == heightlist[i]:
					newlst[1] = k-1
					newisland.append(newlst)
					newlst = [-1, -1]
			if k == island[j][1] and newlst[0] != -1:
				newlst[1] = k
				newisland.append(newlst)
	if max < len(newisland): max = len(newisland)
	island = newisland

print max

Submission status: Accepted

Solution code:
from collections import defaultdict
 
N = int(input())
A = list(map(int, input().split()))
if all(a == 0 for a in A):
    print(0)
    exit()
 
position = defaultdict(list)
for i, a in enumerate(A):
    position[a].append(i)
 
ans = 0
use = 0
link = 0
for a in sorted(set(A), reverse=True):
    use += len(position[a])
    for i in position[a]:
        if i > 0 and A[i] < A[i - 1]:
            link += 1
        if i < N - 1 and A[i] <= A[i + 1]:
            link += 1
    ans = max(ans, use - link)
print(ans)

Submission status: Accepted

Solution code:
def sort_key(end):
    if end[1]:
        return end[0]*2+1
    return end[0]*2

n = int(input())
a = [int(i) for i in input().split()]
a.append(0)

ends = []
top = 0
up = True
for i in range(0, n+1):
    if not up and (i == n or a[i+1] > a[i]):
        ends.append((a[i], True))
        ends.append((top, False))
        up = True
    elif i != n and up and a[i+1] < a[i]:
        top = a[i]
        up = False
ends.sort(key=sort_key)
max_overlaps = 0
overlaps = 0
for end in ends:
    if end[1]:
        overlaps += 1
        if overlaps > max_overlaps:
            max_overlaps = overlaps
    else:
        overlaps -= 1
print(max_overlaps)

Submission status: Accepted

Solution code:
from collections import defaultdict
n,*h=map(int,open(0).read().split())
h=[y for x,y in zip([-1]+h,h) if x!=y]
d=defaultdict(list)
for i,x in enumerate(h):d[x].append(i+1)
t=ans=int(h!=[0])
h=[-1]+h+[-1]
for y,l in sorted(d.items()):
	for i in l:
		if h[i-1]<y>h[i+1]:t-=1
		elif (h[i-1]>y)^(h[i+1]>y):pass
		else:t+=1
	ans=max(t,ans)
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
R = {}
*A, = map(int, input().split())
for i, a in enumerate(A):
    R.setdefault(a, []).append(i)

if N == 1:
    print(+(min(A) > 0))
else:
    res = 1; ans = +(min(A) > 0)
    for k in sorted(R):
        for i in R[k]:
            if 0 < i < N-1:
                if A[i-1] <= A[i] > A[i+1]:
                    res -= 1
                if A[i-1] > A[i] <= A[i+1]:
                    res += 1
            elif i == 0:
                if A[i] > A[i+1]:
                    res -= 1
            else:
                if A[i-1] <= A[i]:
                    res -= 1
        ans = max(ans, res)
    print(ans)

Submission status: Accepted

Solution code:
# 区画数
section_count = int(input())
# チェック済みチェック
checked = [False] * section_count
# 区画毎の高さ
section_list = list(map(int, input().split()))
sorted_section_list = sorted(zip(section_list, range(section_count)))

# 海面の高さ(前)
pre_sea_level = 10 ** 9

count = 0
ans = 0
while sorted_section_list:
    # 海面の高さ、ソート前の要素番号を取得
    sea_level, number = sorted_section_list.pop()
    if sea_level != pre_sea_level:
        ans = max(ans, count)
    if sea_level <= 0:
        break

    count += 1
    checked[number] = True
    
    # 隣の区画が海面より上かをチェック。隣合っていれば地続きとしてカウントダウン
    if number > 0 and checked[number - 1]:
        count -= 1
    if number < section_count - 1 and checked[number + 1]:
        count -= 1
    
    pre_sea_level = sea_level

ans = max(ans, count)
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
A = [int(a) for a in input().split()]

for i in range(N):
    A[i] = (A[i], i)

L = [0]*N
A.sort(reverse=True)
cnt = 0
ans = 0
for i in range(N):
    cnt += 1
    L[A[i][1]] = 1
    if A[i][1] > 0 and L[A[i][1]-1] == 1:
        cnt -= 1
    if A[i][1] < N-1 and L[A[i][1]+1] == 1:
        cnt -= 1

    if i < N-1 and A[i][0] == A[i+1][0]:
        continue
    if A[i][0] == 0:
        break
    ans = max(ans, cnt)

print(ans)

Submission status: Accepted

Solution code:
import sys
input() # no use
lst = list(map(int, input().split()))
# print(lst)
# すべて同じ数の場合は 0 or 1
if len(lst) == 1 or set(lst) == 1:
    if lst[0] == 0:
        print(0)
    else:
        print(1)
    sys.exit()
   
# 同じ数字の並びは不要なため削除する
tmp = []
prev = -1
for now in lst:
    if now != prev:
        tmp += [now]
        prev = now
lst = tmp

# 両端が０でない場合、0を追加
if lst[0] != 0:
    lst = [0] + lst
if lst[-1] != 0:
    lst = lst + [0]

# 頂点と底以外は不要なため削除する
tmp = []
for i in range(1, len(lst) -1):
    prev = lst[i-1]
    now = lst[i]
    next = lst[i+1]
    if prev < now and now < next:
        continue # 右上がりの途中
    if prev > now and now > next:
        continue # 右下がりの途中
    tmp += [now]

lst = tmp

# この時点で以下のようなリストになる
# 島海島(奇数) or 島海島海(偶数)

top = lst[0::2]
bot = lst[1::2]

# top.sort(reverse=True)
# bot.sort(reverse=True)
top.sort()
bot.sort()

# 両端に0を追加
lst = [0] + lst + [0]

# print(top, bot, lst)

jpHeightList = lst
seaHeightList = set(jpHeightList)
maxCount = 0

topLen = len(top)
botLen = len(bot)
topNext = 0
botNext = 0

# 島の数＝海面上の頂点ー海面上の底面の最大値を求める
for i, seaHeight in enumerate(sorted(list(seaHeightList))):
    # 海面上の頂点
    # topCount = topLen - i -1
    # topCount = sum(list(map(lambda x:1 if x-seaHeight>0 else 0, top)))
    for j in range(topNext, topLen): # 一回沈んだ底はみなくてよい
        if top[j] > seaHeight:
            topNext = j  # j → 沈んだ島の数。
            break
        elif j == topLen -1:
            topNext = topLen
    topCount = topLen - topNext 
    
    # 海面上の底面 
    for j in range(botNext, botLen): # 一回沈んだ底はみなくてよい
        if bot[j] > seaHeight:
            botNext = j  # j → 沈んだ島の数。
            break
        elif j == botLen -1:
            botNext = botLen
    botCount = botLen - botNext 

    tmpCount = topCount - botCount
    if tmpCount > maxCount:
        maxCount = tmpCount

print(maxCount)

Submission status: Accepted

Solution code:
#17D8104010B 宮本拓輝 再提出10/31 Prolem D AOJ0655 Japan Sinks python3


import sys


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

if max(A)==0:
  print(0)
  sys.exit()

A.insert(0,0)
A.append(0)

top_valley=[] #[i][0]に標高,[i][1]は1なら頂点,0なら谷
up_down=True #登りならTrue,下りならfalse

for i in range(1,len(A)-1):
  #頂点
  if up_down==True:
    if A[i]>A[i+1]:
      top_valley.append([A[i],1])
      up_down=False
  #谷
  elif up_down==False:
    if A[i]<A[i+1]:
      top_valley.append([A[i],0])
      up_down=True


top_valley.sort()


cnt=1
max_cnt=1
for i in range(len(top_valley)-1):
  if top_valley[i][1]==1:
    cnt-=1
  elif top_valley[i][1]==0:
    cnt+=1

  if top_valley[i][0]<top_valley[i+1][0]:
    max_cnt=max(max_cnt,cnt)

print(max_cnt)

"""
6
3 2 3 0 2 0
2
"""

Submission status: Accepted

Solution code:
#!/usr/bin/python3

import array
from fractions import Fraction
import functools
import itertools
import math
import os
import sys


def main():
    N = read_int()
    A = read_ints()
    print(solve(N, A))


def solve(N, A):
    height_map = {}
    for i, a in enumerate(A):
        if a not in height_map:
            height_map[a] = []
        height_map[a].append(i + 1)

    heights = list(height_map)
    heights.sort(reverse=True)

    landscape = [0] * (N + 2)
    count = 0
    best = 0
    for h in heights:
        if h == 0:
            break
        for i in height_map[h]:
            l, r = landscape[i - 1], landscape[i + 1]
            if l == 0 and r == 0:
                count += 1
            elif l == 1 and r == 1:
                count -= 1
            landscape[i] = 1

        best = max(best, count)

    return best


###############################################################################
# AUXILIARY FUNCTIONS

DEBUG = 'DEBUG' in os.environ


def inp():
    return sys.stdin.readline().rstrip()


def read_int():
    return int(inp())


def read_ints():
    return [int(e) for e in inp().split()]


def dprint(*value, sep=' ', end='\n'):
    if DEBUG:
        print(*value, sep=sep, end=end)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def main():
    N = int(input())
    pre_A = [int(i) for i in input().split()]
    A = []
    for i in range(N):
        if i != 0 and pre_A[i-1] == pre_A[i]:
            continue
        A.append(pre_A[i])
    N = len(A)
    A = [(int(i), idx) for idx, i in enumerate(A)]
    cur = 0
    for i in range(N):
        sea_level = 0
        if (i == 0 or A[i-1][0] <= sea_level) and A[i][0] > sea_level:
            cur += 1

    B = sorted(A)
    ans = 0
    pre_h = 0
    for h, idx in B:
        if h == 0:
            continue
        if pre_h != h:
            ans = max(cur, ans)
        # 高さがhになったときの、島の数の増減を考える
        if (idx != 0 and A[idx - 1][0] > h) and (idx != N-1 and A[idx + 1][0] > h):
            cur += 1
        elif (idx == 0 or A[idx - 1][0] < h) and (idx == N-1 or A[idx + 1][0] < h):
            cur -= 1
        pre_h = h
    print(max(cur, ans))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#
# 　　  ⋀_⋀　 
#　　  (･ω･)  
# .／ Ｕ ∽ Ｕ＼
#  │＊　合　＊│
#  │＊　格　＊│ 
#  │＊　祈　＊│ 
#  │＊　願　＊│ 
#  │＊　　　＊│ 
#      ￣
#
import sys
sys.setrecursionlimit(10**6)
input=sys.stdin.readline
from math import floor,ceil,sqrt,factorial,log #log2ないｙｐ
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
inf=float('inf')
mod = 10**9+7
def pprint(*A): 
    for a in A:     print(*a,sep='\n')
def INT_(n): return int(n)-1
def MI(): return map(int,input().split())
def MF(): return map(float, input().split())
def MI_(): return map(INT_,input().split())
def LI(): return list(MI())
def LI_(): return [int(x) - 1 for x in input().split()]
def LF(): return list(MF())
def LIN(n:int): return [I() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]
def LLIN_(n: int): return [LI_() for _ in range(n)]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def I(): return int(input())
def F(): return float(input())
def ST(): return input().replace('\n', '')
# UnionFind
class UnionFind():
    def __init__(self, n):
        self.nodes=[-1] * n  # nodes[x]: 負なら、絶対値が木の要素数

    def get_root(self, x):
        # nodes[x]が負ならxが根
        if self.nodes[x] < 0:
            return x
        # 根に直接つなぎ直しつつ、親を再帰的に探す
        else:
            self.nodes[x]=self.get_root(self.nodes[x])
            return self.nodes[x]

    def unite(self, x, y):
        root_x=self.get_root(x)
        root_y=self.get_root(y)
        # 根が同じなら変わらない
        # if root_x == root_y:
        # pass
        if root_x != root_y:
            # 大きい木の方につないだほうが計算量が減る
            if self.nodes[root_x] < self.nodes[root_y]:
                big_root=root_x
                small_root=root_y
            else:
                small_root=root_x
                big_root=root_y
            self.nodes[big_root] += self.nodes[small_root]
            self.nodes[small_root]=big_root

def main():
    N=I()
    A=LI()
    timing = list(set(A))
    timing.sort(reverse=True)
    appear = defaultdict(list)
    for i,a in enumerate(A):
        appear[a].append(i)
    
    exist=set()

    ans = 0
    num = 0
    for t in timing:
        if t <= 0:
            break
        for land in appear[t]:
            exist.add(land)
            # if land == 0:
            #     if land+1 in exist:
            #         pass
            #     else:
            #         num += 1
            # elif land == N-1:
            #     if land-1 in exist:
            #         pass
            #     else:
            #         num+=1
            # else:
            left = land-1 in exist
            right = land+1 in exist
            if left and right:
                num-=1
            elif left or right:
                pass
            else:
                num+=1
        # print(t, num)
        ans = max(ans, num)

    print(ans)
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def main():
    _ = int(input())
    A = list(map(int, input().split()))

    A.append(-1)
    A = [a for a, b in zip(A, A[1:]) if a != b]
    A.insert(0, -1)
    A.append(-1)
    A = [b for a, b, c in zip(A, A[1:], A[2:]) if (a < b) != (b < c)]

    A.append(-1)
    A = sorted((a, (1 if a < b else -1)) for a, b in zip(A, A[1:]))

    n = 1
    n_max = 0
    prev = 0
    for a, s in A:
        if prev < a:
            if n_max < n:
                n_max = n
            prev = a
        n += s
    print(n_max)
main()

Submission status: Accepted

Solution code:
def merge_unit(array1, array2, n1, n2):
    n = n1 + n2
    ret = [0] # outofindexを避けるため便宜上入れるが、たまたま呼び出し側で最初に0が必要なのでこのままにしとく
    csr1 = 0
    csr2 = 0
    for i in range(n):
        if csr1 >= n1:
            if not ret[-1] == array2[csr2]:
                ret.append(array2[csr2])
            csr2 += 1
        elif csr2 >= n2:
            if not ret[-1] == array1[csr1]:
                ret.append(array1[csr1])
            csr1 += 1
        else:
            if array1[csr1] < array2[csr2]:
                if not ret[-1] == array1[csr1]:
                    ret.append(array1[csr1])
                csr1 += 1
            else:
                if not ret[-1] == array2[csr2]:
                    ret.append(array2[csr2])
                csr2 += 1
    return ret

def main():
    N = int(input())
    A = [int(v) for v in input().split()]

    if all([v == 0 for v in A]):
        print(0)
        return

    tyou_t = []
    tyou_b = []
    next = 0 # ダウン 1 -> アップ
    for i in range(1, N):
        if next == 0 and A[i] - A[i - 1] < 0:
            tyou_t.append(A[i - 1])
            next = 1
        elif next == 1 and A[i] - A[i - 1] > 0:
            tyou_b.append(A[i - 1])
            next = 0

    if next == 0:
        tyou_t.append(A[-1])

    tyou_t.sort()
    tyou_b.sort()
    len_t = len(tyou_t)
    len_b = len(tyou_b)
    tyou = merge_unit(tyou_t, tyou_b, len_t, len_b)

    cnt_t = 0
    cnt_b = 0
    max_island = 1
    for x in tyou:
        while cnt_b < len_b and tyou_b[cnt_b] <= x:
            cnt_b += 1
        while cnt_t < len_t and tyou_t[cnt_t] <= x:
            cnt_t += 1
        island = 1 + cnt_b - cnt_t
        if max_island < island:
            max_island = island

    print(max_island)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#  corutopiさんとkuwaaaaaaaaaaaaaaaaaさんの解答を参考にした。
#
n = int(input())
height_list = [0] + list(map(int, input().split())) + [0]

# 山と谷のみに制限する
use_list = []

# 高度が上昇中が下降中かのフラグ
# True: 上昇中
# False: 加工中
# 左→右で探索する
up_flag = True
for i in range(len(height_list)-1):
    if up_flag:
        if height_list[i] > height_list[i+1]:
            # 山を検出した。山の高さを登録
            use_list.append(height_list[i])
            up_flag = False
    else:
        if height_list[i] < height_list[i+1]:
            # 谷を検出した。谷の高さを登録
            use_list.append(height_list[i])
            up_flag = True

            
# ソートしたリスト
len_list = len(use_list)
use_list2 = sorted(zip(use_list, range(len_list)))


# 沈んだかの判定
sink_list = [False] * len_list

# 島の最大値
max_count=0
# 島の数
count=1

# リストの前回使った高さ
pre_height = -1

if len_list == 1:
    max_count = 1
else:
# 低いところから沈んでいく
    for height, location in use_list2:
    
    
        if pre_height != height:
            max_count = max(max_count, count)
    

        sink_list[location] = True
    
        # 両隅が海
        if (location > 0 and not sink_list[location - 1]) and (location < (len_list - 1) and not sink_list[location + 1]):
            count += 1
        # 両隅が陸
        if (location > 0 and sink_list[location - 1]) and (location < (len_list - 1) and sink_list[location + 1]):
            count -= 1
        #  隅が沈んだ
        elif location == 0 and sink_list[1]:
            count -= 1
        elif location == (len_list - 1) and sink_list[len_list-1]:
            count -= 1
        
        pre_height = height
    
        # print(max_count, "height = ", height, ",location = ", location, ", count =" , count)
        # print(sink_list)
    
print(max_count)

Submission status: Accepted

Solution code:

def solve():
    N = int(input())
    A = [0] + [int(i) for i in input().split()] + [0]
    A_edge = []
    # 頂点と底辺のみにデータを絞る
    up_flg = True
    for i in range(1, len(A) - 1):
        if up_flg:
            if A[i] > A[i + 1]:
                A_edge.append([A[i], up_flg])
                up_flg = not up_flg
        else:
            if A[i] < A[i + 1]:
                A_edge.append([A[i], up_flg])
                up_flg = not up_flg
    A_edge.sort()  # 沈んでいく順に並べ替え
    # 島を数える
    island_count = 1
    max_island_count = 1
    for i in range(len(A_edge) - 1):
        if A_edge[i][1]:
            island_count -= 1
        else:
            island_count += 1
        if A_edge[i][0] < A_edge[i + 1][0]:
            max_island_count = max(max_island_count, island_count)
    # 島の高さがすべて0の時の考慮
    if max(A) <= 0:
        max_island_count = 0
    print(max_island_count)


if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
n = int(input())
alst = list(map(int, input().split()))
raised = [False] * n
count = 0
ans = 0
pre_height = 10 ** 10
sorted_alst = sorted(zip(alst, range(n)))

while sorted_alst:
    height, number = sorted_alst.pop()
    if height != pre_height:
        ans = max(ans, count)
    if height <= 0:
        break

    count += 1
    raised[number] = True
    
    if number > 0 and raised[number - 1]:
        count -= 1
    if number < n - 1 and raised[number + 1]:
        count -= 1
    
    pre_height = height

ans = max(ans, count)
print(ans)