ひらめの日常

日常のメモをつらつらと

計算量

AtCoder: ABC176-D Wizard in Maze (400)

問題はこちら atcoder.jp 縦マス、横マスからなる迷路がある。マス(i, j) は # のとき壁であり、. のとき道である。ます目 (C_h, C_w) から(D_h, D_w) に移動することを考える。 以下の二つの移動方法がある。 移動A: 現在いるマスと上下左右に隣接する道の…

AtCoder: ABC140-E Second Sum (500)

問題はこちら atcoder.jp 長さ の順列 が与えられた時、区間 に対して以下を計算せよ。 全ての重複しない区間において、二番目に大きい数の和。 考え方 簡単バージョンとしてこの問題があるので見ると良い。 atcoder.jp step1 - 問題の言い換え 愚直にやると…

Codeforces Round #582 (Div. 3) D. Equalizing by Division

問題はこちら codeforces.com 長さ の 配列 が与えられる。一回の操作によって任意の要素一つ、 を2で割って切り捨てることを行う。 (つまり、 ) 個の等しい要素を 中で得るには、何回操作を行えばいいか、その最小値を求めよ。 考え方 全ての を、0になる…