torus711 のアレ

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

Codeforces 164, B : Buttons

概要

n 個のボタンを備える鍵がある。
この鍵を開けるには、全てのボタンを正しい順序で押さなければならない。
正しい順序でボタンを押している限り、ボタンは押されたままになる。
間違ったボタンを押すと、全てのボタンは押されていない状態に戻る。
全てのボタンが押されている状態になったとき、鍵が開く。

Manao は正しい順序を知らないが、この鍵を開けようとしている。
Manao が最適な戦略を取ることができるとき、最も悪いケースでのボタンを押す回数を求めよ。

解法

  • 各段階に於いて、(残っているボタンの数) - 1 回の試行で間違ったボタンを全て調べることができる。
  • 全ての間違った順序が試行された後、n 回ボタンを押すと解錠することができる。

これらの条件を元に数え上げると解けます。

コード

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

main = do
	n <- readLn
	print $ solve 1 ( n - 1 )

solve :: Integer -> Integer -> Integer
solve t 0 = t
solve t n = n * t + solve ( t + 1 ) ( n - 1 )