torus711 のアレ

主に競技プログラミングの問題について書きます

Codeforces #165, Division 2, B : Multithreading

概要

スレッド式の掲示板があり、各スレッドは、新着書き込みがあると一覧の最上位に移動する。
画面更新後の各スレッドについて、それぞれの更新前の位置が与えられる。
確実に新しい書き込みがあると言えるスレッドの数を求めよ。

解法

リストの末尾は、新着があると言うことはできません。
また、末尾方向で昇順が保たれている部分については新着が無い可能性があります。
従って、リストの末尾から、そのような部分を除去した残りが、新着があるスレッドです。

コード

import Control.Applicative
import Control.Monad
import Data.List

main = do
	n <- readLn
	as <- reverse . map read . words <$> getLine
	print $ n - solve as n

solve [] _ = 0
solve (a:as) prev
	| prev < a = 0
	| otherwise = 1 + solve as a