問題 横一列にn台の駐車スペースがあり、左から順に1, ..., nと名前がついている。 ここにm個の車の到着または出発のクエリが来るので処理せよ。 車は以下のアルゴリズムで駐車場所を選ぶ。 全ての空きスペースの中で、一番近くにある他の車までの距離が最大…

問題 n項からなる数列a[i]が与えられる。これに対してq個のクエリに答えよ。 クエリ： 区間l, rが指定される。 [l, r]と長さが等しく、[l, r]に交わらない区間[s, t]で、a[l + i] = a[s + i] = constとなる区間はいくつあるか求めよ。 制約条件 n, q≦10^5 a[…

問題 英小文字のうちa-xの24文字のどれか、3文字からなる単語がn個与えられる。 24文字のうち好きな文字を母音にしてよい。 母音が一文字以上含まれている単語はよい単語である。 2^24の母音の選び方に対して、(良い単語の数)^2を求め、それらを全てxorした…

問題 長さnの数列a[i]が与えられる。 aの任意の空でない区間[l, r]で、a[i]の符号を好きに反転してよい。 このようにして[l, r]内の総和が0になるようにする方法は何通りあるか。 制約条件 n≦1000 -1000≦a[i]≦1000 a[i]の総和≦10000

問題 1番のノードが根であるような木が与えられる。各ノードは値a[i]をもっている。 木に対して次のクエリを行うことができる。 1 x val : x番の頂点にvalを足す。x番の直接の子に-valを足す。x番の頂点の２代目の子孫にvalを足す３代目の頂点に-valを足す………

問題 nxnのグリッドがあり(1, 1)から(n, n)へ、上または右に移動することを繰り返して進む。 グリッドのうちm個には障害物があり、そのマスへは入れない。 (1, 1)から(n, n)へ進むことはできるか。 制約条件 n≦10^9 m≦10^5