問題文 : CatChecker概要 : 文字列$s$ が次のBNF に従っているか判定せよ.<cat> := "" | 'm' + <cat> + 'e' + <cat> + 'w'$1 \leqq |s| \leqq 500$</cat></cat></cat>

問題文 : Twenty Questions概要 :長さ$m $ のビット列が$n$ 個ある. これらを一意に識別するために必要なビット数はいくらか？ ただし, あるビットの情報を得た後に次の戦略を考えても良い.$1 \leqq m \leqq 11,\ 1 \leqq n \leqq 128$

問題 : Marked Ancestor問題概要 : 大きさ$N$ の木が与えられる. 最初頂点$0$ は赤色で, その他の頂点は青色である. 次の$Q$ 個のクエリに答えよ :・頂点$v$ の色を赤色に変える. ・頂点$v$ から赤色の先祖ノードのうち, もっとも近いものの番号をこたえる.$…

"連続する正整数の和" に関する問題を2 題考えたのでそれについて.

問題文 : THE☆たこやき祭り2012

問題文 : 鉄道路線

問題 : ザ・スクエアーズ

問題文 : IkaNumber

問題文 : Xenia and Tree概要 : 大きさ$n$ の木が与えられる. 最初頂点0 は赤色で, その他の頂点は青色である. 次の$m$ 個のクエリに答えよ :・頂点$v$ の色を赤色に変える. ・頂点$v$ から赤色のノードまでの最短距離を求める.$1 \leqq n,\ m \leqq 10^5$

問題文 : Sereja and Subsequences概要 :数列${a_n}$ がある. ${a_n}$ の相異なる全ての非減少部分列${b_n}$ について, $b_1b_2\cdots b_n$ を求め, その和をmod $10^9+7$ で求めよ.$n \leqq 10^5$

問題 : Ben Toh

問題文 : Minimum Spanning Tree概要 : 無向重み付きグラフ$G(V, E)$ が与えられる. すべての$e \in E$ について, $G - e$ の最小全域木の重さを求めよ.$1 \leqq n \leqq 10^5$ (頂点数) $1 \leqq m \leqq 2 \times 10^5$ (辺数)

問題文 : World Eater Brothers問題概要 :$N$ 頂点からなる有向全域木$G$ が与えられる. 高々2 つの頂点を選んで, この頂点から他の頂点への有向パスが存在するようにするために変えなければならない辺の向きの最小値を求めよ.$N \leqq 3000$

問題文 : Pie Chart is as easy as pie.

問題 : Xenia and Hamming概要 :文字列$x$ を$n$ 回繰り返した文字列$a$ と, 文字列$y$ を$m $ 回繰り返した文字列$b$ がある. $a$ と$b$ のハミング距離を求めよ. ただし, ハミング距離とは$\displaystyle \sum_{i=1}^{n} [a_i \neq b_i]$ で定義され, $a_i…

問題文 : Queue概要 : 長さ$n$ の文字列があり, 'M' と'F' から構成されている. 1 ターンの間に次の動作を行う : "MF" という部分文字列を"FM" に置き換える.文字列が"FF.....MM" という形になるのは何ターン後か？$n \leqq 10^6$

問題 : -平-均-ものすごくJOI 本選に出そうな問題だった.部分点1 が$n \leqq 20$ 部分点2 が$n \leqq 50,\ a_i \leqq 100,\ T \leqq 100$ 満点が問題文の通り, みたいな感じ.

lowlink という概念について説明しています. 実装は簡単ですが, いろいろと応用が効いて面白いです.