提案： 鵜川 始陽
主担当： 山口 文彦
題意通りの条件を満たすデータの個数を数える問題である．
まずは，データセットを整数の配列などに読み込んでおくのが素直な解法であろう． 問題文の通りに v1 から vn が与えられているとき， 最初と最後はピークにならないので， vi-1 < vi かつ vi > vi+1 であることを， i が 2 以上 n-1 以下の範囲で検査する． ピーク数を数えるための変数を用意して 0 に初期化しておき， 条件を満たす場合に 1 ずつ加算していけばよい．
n は最大でも 1000 であるから，高々 998 回の検査をすればよく， 計算時間はごく短く済む．
提案： 柴山 悦哉
主担当： 柴山 悦哉
この問題は，ババ抜きに似たカードゲームのシミュレーションを行うものである．与えられたゲームのルールに忠実にしたがったプログラムを作れば良い．
このシミュレーションを行うためには，環状に並んだプレイヤーの手札を保持するデータ構造が必要になるが，配列，連結リスト，双方向連結リスト等のどれを用いても良い．シミュレーションの過程は，次にカードを引かれるプレイヤー (p) の選択，そのときにカードを引くプレイヤー (p′) の選択，p の手札の中で番号が最小のカードの p′ の手札への移動，同じ番号のカードが揃ったときの手札からの削除，終了判定を組み合わせたものであり，それぞれは単純な記述で実現可能である．
プレイヤーの人数は高々 1000 人で，カードを引く回数はプレイヤーの人数の高々 2 乗のオーダーになる．したがって，高速なアルゴリムを工夫する必要はない．
提案： 森田 晃平
主担当： 森田 晃平
n 日の練習日はなるべく大きくまとめた方が能力は高まり，m 日の休息日はなるべく平均的に分散した方があまり能力を低めずに済む．
休息日の連続を k 回に分散すると決めたら，初日と最終日を休息にして、練習日は 1 日ずつの k−2 回と，残り全部をまとめた連続を 1 回とするのが最適である．休息日は ⌊m/k⌋ 日の連続と ⌊m/k⌋+1 日の連続を組み合わせるのが最適になる．この方針で，最も能力を高められる k を見つければ良い．
提案： 稲葉 一浩
主担当： 稲葉 一浩
仮に分割後の各列がソート済みであれば，この問題に示された最後のステップの操作は，マージソートにおけるマージ操作のようなものになっている．この問題ではソート済みでないような列も考える必要があるが，そのような場合にも成り立つような性質を考察することで，効率的な解法を得ることができる．
特に重要なのが，マージされる各々の列は，必ずマージ後の列の部分列になっているという性質である． この性質を満たすためには， 聴衆の最初の並び順と最終的な入場順が逆転しているような箇所では，必ず列を分割しなければならない．
そのような必須の箇所で分割した後，さらに細かく分割することが可能な場合もあるが，その場合はマージによって順番が変わらないようにする必要がある．そうでないと部分列であるという性質が壊れてしまう． 順番を変えないためには，チケットの番号が，前にいる全ての人のチケット番号よりも大きいような人のところで列を区切るとよい．そのような箇所では列を区切っても区切らなくてもよい．
以上から，切らなければいけない箇所と，切っても切らなくてもいい箇所の数を数えることができる． それらの候補から最大 k-1 箇所を選ぶ場合の数を求めれば，欲しい答えが得られる． そもそもどのように区切っても目標の列を作れない場合は 0 を返すことには注意する必要がある．
提案： 隈部 壮
主担当： 隈部 壮
グリッド上に
グリッドの i 行目をバランスの取れた括弧列にするためには，左端の文字を
提案： 楠本 充
主担当： 山口 勇太郎
式の長さを m とする． 構文解析をし，構文木上の適切な動的計画法を設計することで，たとえば O(m2 log m) 時間でこの問題を解くことができる． 以下ではその一例を述べる．
まず，構文木として，各ノードが以下のいずれかであるような，root を根とする二分木を作る． これは O(m) 時間で可能であり，ノードの数は高々 2m 個である．
?(...) に対応する．）構文木の各ノード v で，以下の文字列 dp[v][l][r] を計算すると，dp[root][0][0] が求める答えである．
dp[v][l][r] =（ノード v が持つ文字列について，自身を含まない祖先において左側 l 文字と右側 r 文字が削られるとき，自身以下の ? を処理した結果として得られる文字列のうち辞書順で最初に現れるもの）
これは素朴なメモ化再帰で top-down に計算できる．
たとえば，問題文中の例 ?(?(icp)c) であれば，root とその唯一の子 v は文字列 icpc を持ち，dp[root][0][0] = min{dp[v][1][0], dp[v][0][1]} を計算できればよい．
v は結合ノードであり，左右の子をそれぞれ u, w とすると，それぞれが持つ文字列は icp, c であり，dp の値は計算できる．（ + は文字列の結合を，ε は空文字列を表す．）
dp[v][1][0] = dp[u][1][0] + dp[w][0][0] = min{p,c} +c=cc
dp[v][0][1] = dp[u][0][0] + dp[w][0][1] = min{cp,ic} + ε =cp
ただし，削る文字数よりノードが持つ文字数が少なくなる場合には，該当部分を空文字列として扱う，結合ノードであれば反対側のノードにはみ出して削るなど，多少の追加処理が必要となる．
素朴にすべてを計算すると，ノードと左右の削れ具合のすべてのパターンについて dp[v][l][r] を計算することになり，文字列の辞書順比較を素朴に行うと全体で O(m4) 時間となる．
全体が空文字列にならないことから，実際に機能する ? は高々 m/4 ≤ 250 個であり，この計算量でも最悪少し待てば終わる程度である．
さらに，以下の工夫を施すことで冒頭に述べた程度の計算量に削減でき，十分高速に動作することが保証できる．
提案： 城下 慎也
主担当： 城下 慎也
まず，A, B ともに線分上を移動する場合を考える．このとき，開始端を同時に出発し，終端に同時に到着するようそれぞれ一定の速度で移動することで，エージェント間の距離を max{開始端間の距離, 終端間の距離} 以下に抑えることができる．また，これより距離の最大値を縮めることはできない．
次に A がある線分から別の線分に乗り換える場合を考える．このとき，B は現在いる線分上で A に最も近い点（線分の一方の端点か，A がいる頂点から線分に引いた垂線の足）にいると仮定して良い．
証明：最適解において B が線分上で A がいる頂点に最も近い点 X とは異なる点 Y にいると仮定する．このとき，A が線分を変える直前に B のみが Y から X に移動し，変えた直後に B のみが X から Y に移動する動作を追加しても，AX 間の距離が AY 間の距離以下であることから最適解は変化しない．この処理を順に適用することで，点 A が線分を変える瞬間には，B が線分上で最も近い点にいるように最適解を変更できる．
B についても同様の議論ができる．さらに，乗り換えが発生してから次の乗り換えが発生するまでの間はどちらのエージェントも単一の線分上を移動するため，最適解は，「（A, B いずれも頂点または垂線の足にいる状態）の列であり，隣接する要素間は A, B いずれも単一の線分上の移動で実現できるもの」に限定しても求めることができる．このとき，各列における最長距離は max{各要素における A, B 間の距離} となる．
A, B の位置 (頂点または垂線の足) のペアを頂点とし，A, B ともに単一の線分の移動となるような頂点間を辺で結んだグラフを考える．各辺の重みを，対応する線分移動における距離の最大値としたとき，初期状態 (A, B ともに潜入経路の開始端にいる状態) から終了状態 (A, B ともに潜入経路の終端にいる状態) まで移動するために用いる辺の重みの最大値として考えられる最小値を求める問題となる．これは，グラフの最小全域木における，初期状態と終了状態を結ぶパス上の辺の重みの最大値に等しい．
計算量について考える．A, B のいずれも折れ線の頂点上にいないケースは考慮しなくて良いため，それらを取り除くことでグラフの頂点数は O(nm)，辺数は O(n2m2) となる．全体の計算量は O(n2m2 log (nm)) で抑えられる．
提案： 楠本 充，隈部 壮
主担当： 佐藤 遼太郎
ボールを頂点，紐を無向辺と解釈すると，本問題は最終的に構築されたグラフの二部性の判定を要求している．更に二部グラフである場合は，各頂点を同色の頂点同士が隣接しないよう赤と青の 2 色で塗り分けるとき，赤く塗らねばならない最小の頂点数を問うている．
最終的な頂点数を n とすると，二部性の判定は要素数 2n の素集合データ構造 (Union-Find) を用いて行える．2 頂点 (u, v) の連結クエリに対しては Union-Find における各要素対 (n + u, v), (u, n + v) について各要素を含む集合を統合する．また複製クエリに対しては，複製前の頂点数を m として，要素 1, ..., m, n + 1, ..., n + m の統合の状態を要素 m + 1, ..., 2m, n + m + 1, ..., n + 2m にコピーする．最終的に i = 1, ..., n の全てについて Union-Find の 2 要素 i, n + i が同一の集合に含まれていないことが，グラフが二部性を満たす必要十分条件である．
ここで更に，Union-Find の各集合に塗り分けの情報を持たせることが可能である．具体的には，Union-Find の各要素 i に対する値 f(i) を，i ≤ n のときグラフの頂点 i を赤色に塗った場合，i > n のとき頂点 i − n を青色に塗った場合のその連結成分全体の赤色の頂点数として定める．すると，Union-Find 上で同一の集合に含まれる全ての要素 i に対して f(i) は常に共通の値をとるので，f(i) の値は Union-Find の各集合の代表点に関してのみ管理すればよく，連結クエリに対しても高速に更新できる．
この情報を使用すると，グラフ全体で赤く塗る必要のある最小の頂点数の値も各クエリに対して随時更新できる．連結クエリ (u, v) に対しては u, v の属する連結成分に関する差分が計算でき，複製クエリに対しては現時点の値を単に 2 倍すればよい．
最後に，本問の解を求めるには要素数 2n の Union-Find を持つ必要はなく，上述の更新操作に必要な要素のみを管理すれば十分である．具体的には，各連結クエリに現れる頂点について，その頂点自身に加えてそれらの複製元となる頂点たちの情報のみを管理すれば上記の解法で述べた処理は全て問題なく行える．したがって，データセット中のクエリ数を m，特に複製クエリ数を k とすると，要素数 O(km) の Union-Find で本問題が解ける．