この問題は素直に題意通りの操作を繰り返せば解ける． ビー玉は合計高々 400 個で，それが操作ごとに少なくとも 1 個は減るのだから， 計算時間も問題ない． しかし実はこの問題の答は椀中のビー玉数の最大公約数なのだ．

操作前の椀の中のビー玉数 a, b, c, d の最大公約数を g とすると a'=a/g, b'=b/g, c'=c/g, d'=d/g はすべて整数である． 空でない椀のうち最少のビー玉 a 個とすると， 1 回の操作後の各椀の中のビー玉数は a'g, (b'-a')g, (c'-a')g, (d'-a')g であり，操作後にも g はビー玉数の公約数である．

操作後に残るビー玉数の最大公約数を h とすると a''=a/h, b''=(b-a)/h, c''=(c-a)/h, d''=(d-a)/h はすべて整数である．これを使って操作後のビー玉数を表すと a''h, (b''-a'')h, (c''-a'')h, (d''-a'')h となる．操作で取り除いたビー玉 a = a''h 個を元に戻すと， 操作前のビー玉数は a''h, b''h, c''h, d''h と表せるので，h は操作前のビー玉数の公約数でもあることがわかる． 操作前には g が最大公約数なので h ≤ g, 操作後には h が最大公約数なので g ≤ h, だから h = g, つまり操作はビー玉数の最大公約数を変えない． 繰返し操作の終了時には空でない椀はひとつだけで， その椀の中のビー玉数が全部の椀内の個数の最大公約数であり， それが初期状態のビー玉数の最大公約数に等しいわけである．

ユークリッド互除法で最大公約数を求める計算量は， ビー玉数の対数×椀の数のオーダーで， 入力のビー玉数や椀の数をかなり大きくしても計算時間はごく短く済むのだが， この問題では素朴な解法で解ける入力値の範囲とした．

この問題は，与えられた問題（百ます計算の逆問題）の解が一意であるかどうかを 判定する問題である．

問題の入力サイズが小さいことから，解答マスの数をもとに，上端・左端の数を一つずつ決定していくような単純なアルゴリズムによっても解くことができる． 例えば，単純なアルゴリズムの一つは， 解答マスの数によって新しく上端・左端を決定するというステップを， 最大 w + h − 1 ステップ行うというものだ． このアルゴリズムの計算量は O((w + h)²) である．

実はこの問題では， 問題として与えられるパズルが解を少なくとも一つ持つことが保証されているので， 解答マスの数の位置だけが必要で，値は必要ではない． このことに気付くと，多少コードを短くすることができる．

なお，この問題はより小さな計算量で解くことができる． 以下のようなグラフを考える．上端の数と左端の数をそれぞれノードとする． それぞれの解答マスの数に対し，その上端ノードと左端ノードを辺で結ぶ． すると，ノード数 w + h，エッジ数 w + h − 1 のグラフとなる． このグラフが木であれば，解が一意となる． グラフが木であるかどうかを判定することは頂点数のオーダーで可能なので，この方法であれば計算量は O(w + h) となる．

基本的には，構文解析と探索を行う問題である． 入力として与えられる算術式の構文は一般のものより単純なので，以下では，探索のパートに関する解説を行う．

この問題で，ナイーブな探索を行うと計算量が爆発する． まずは，2 種類の操作を繰り返し適用することで，与えられた算術式に対応する木から，どのような木が生成できるかを把握することが大事である． 以下のような考察を行うと，葉以外のノードが根ノードとなるすべての木を考え，それらの木が表現する算術式の値の最大値を求めれば良いことがわかる．

• 2 種類の操作を繰り返し適用すると．葉以外の任意のノードを根ノードとすることができる．
• 根ノードが決まるとノード間の親子関係は一意に決まる．
• 兄弟ノードは，1 番目の操作により自由に左右を入れ替えることができる．

根ノードを一つ固定して兄弟ノード間の左右の関係を自由に入れ替えたとき，各ノードが取りうる値の最大値と最小値は次のような考え方で求めることができる．

• 葉ノードについては，最大値も最小値もそのノードのラベルと一致する．
• 演算子 + のノードの最大値は子ノードの最大値の合計であり，最小値は子ノードの最小値の合計である．
• 演算子 − のノードの最大値は，最左の子ノードの最大値からそれ以外の子ノードの最小値を引いたものである．また最小値は，最左の子ノードの最小値からそれ以外の子ノードの最大値を引いたものである．

メモ化や動的計画法を用いて同じ計算を 1 回しか行わないようにすれば，葉以外のノード数をN としたときの計算量は O(N ) になる． これを，N 個の葉以外のノードそれぞれを根ノードとして繰り返せば，全体の最大値を求めることができる． 単純に考えると全体の計算量は O(N ²) になりそうだが，同じ計算の繰り返しが多いため，メモ化や動的計画法により，全体の計算量も O(N ) に抑えることができる．

問題文では 1 人の人が一度に三つずつ風船をとって子供たちに手渡していくことになっているが， 3 人の係（Aさん，Bさん，Cさんとしよう）がそれぞれポールの横に立って， タイミングを合わせて各自 1 個ずつ風船をとって子供に渡す風景を想像した方が考えやすいかもしれない．

ポールの並び順を一つ定めると，n 本のポールは A さんが手渡しを担当するポールと，B さん担当のポール，C さん担当のポールに分かれることになる． この時，担当ポールの風船の個数の和ができるだけ均等に近くなるよう， つまり，和が最小の係の風船の個数が最大になるようにすると， もっとも多くの子供が風船をもらえるのである．

つまりこの問題は結局， {b₁, b₂, ..., b_n} を三つの集合 B₁ ⊍ B₂ ⊍ B₃ に分割して， 和の最小値 min(ΣB₁, ΣB₂, ΣB₃) が最大になるようにせよ，という問題になっている．そのような集合の分割が得られた時に， 実際にその分割に合わせてポールが 3 人の係に割り振られるように並べることは， 少し考えると必ず可能であるとわかる．

この整理された問題は Subset Sum Problem によく似ており，実際よく似た動的計画法で解くことができる．具体的には， dp[k][x][y] = "{b₁, ..., b_k} を 3 分割して和が (x, y, (Σ^k_i=1 b_i)-x-y) となるようにできるか否か" という表を埋めればよい．

この問題はタクシースタンドを頂点，歩道・車道を辺とするグラフとして考えることができる． そのグラフ上で複数の最短経路を求める問題である．

頂点 n に到達するのに必要なタクシーに乗る最小の回数を k とする． この場合の待ち時間の合計は 2 ^k - 1 分である． 高々 n 回の移動があり，そのコストは各 1000000 分以下であり n は 20000 以下なので， タクシーに乗る回数がちょうど k 回の経路にかかる時間は 2 * 10 ¹⁰ + 2 ^k - 1 以下である． タクシーに乗る回数 k+1 回の待ち時間の合計 2^k+1-1 は k が 35 以上の場合はちょうど k 回乗る経路にかかる時間より大きい． そのため，k が 35 以上の場合はタクシーに乗る回数がちょうど最小値 k になる経路だけ考えればよい．

タクシーに乗っている状態と乗っていない状態を区別するために頂点数を 2 倍したグラフを作る． 車道や歩道のコストを 0，タクシーに乗っていない状態から乗っている状態への辺のコストを 1 にしたグラフで幅優先探索などでタクシーに乗る最小回数 k を求めることができる． k が 35 未満の場合と 35 以上の場合で分けて解く．

k が 35 未満の場合，頂点を更に増やしてタクシーに乗った回数 (0 回から 34 回) を区別できるグラフを作る．車道や歩道はその移動にかかる時間をコストにし，タクシーに乗るときの辺はその待ち時間をコストにする． このグラフ上で最短経路問題をダイクストラ法で解くことで答えを求めることができる．

k が 35 以上の場合，タクシーに乗る回数が最小値 k になる経路の中で，車道や歩道にかかる時間の最小値を求めたい． これはグラフの移動のコストを (タクシーに乗った回数，車道や歩道を移動した時間の合計) の順番に比較するような 2 要素のコストにして 最短経路問題をダイクストラ法で解くことで答えを求めることができる．

スパイと任務をそれぞれ頂点，割り当て可能な組を辺として 2 部グラフを作ると， このグラフの完全マッチングが王女様が満足できる任務割り当てになります． すなわち，この問題は，完全マッチングを持つ 2 部グラフを入力とし， そのグラフに最少の辺を追加して，どの辺 e を指定されても， e を含む完全マッチングが存在するようにする問題と言い換えられます． 2 部グラフの Dulmage–Mendelsohn (DM) 分解を知っていれば， 結果として得られる 2 部グラフの各連結成分が DM 既約となる （すなわち DM 分解の結果が唯一の成分からなる）ようにすることとも言い換えられます．

まず入力グラフの完全マッチングを一つ求め，これを M とします． 辺 e として M に含まれる辺が指定されたときは，明らかに条件を満たします． M に含まれない辺 e に関して， e がある完全マッチングに含まれうる必要十分条件は， e を通るような M に関する交互閉路 (alternating cycle) が存在することです． この条件は，M の辺を両向きの有向辺で置き換え， それ以外の辺をスパイ側から任務側に向けた有向辺で置き換えて得られる有向グラフで， e の任務側の端点からスパイ側の端点に到達可能であることとも同値です． 追加する辺は M に含まれず，上記の手順ではスパイ側から任務側に向き付けられるので， この問題は「入力 2 部グラフから上記の手順で得られる有向グラフにスパイ側から任務側に向けた有向辺を最小本数追加して， 結果として得られる有向グラフの各連結成分が強連結となるようにすること（強連結でなければ，強連結成分を跨ぐ辺を指定されると完全マッチングに含められない）」と言い換えられます． ここで，完全マッチング M の辺が両向きに向き付けられているため，「スパイ側から任務側に向けた」という条件は実質無視できます．

以上より，この問題は有向グラフの強連結化問題に帰着されました． この問題は，以下の手順で解くことができます．

• 強連結成分分解をし，各強連結成分を縮約して有向非巡回グラフ (DAG) を得る．
• 得られた DAG のソース（入る辺が無い頂点）とシンク（出る辺が無い頂点）を結ぶ有向道を， 互いに素になるように極大に取る．これは，ソースの集合から深さ優先探索を行えばよい．
• 極大に取った有向道の端点間に，全体が一つの大きな有向閉路をなすように有向辺を追加する．
• 残ったシンクから残ったソースに向かう有向辺を 1 本ずつ追加する．途中でどちらか一方のみが残れば，他方は任意に選んでよい．

追加辺はソースとシンクの少なくない方の数以上は必要（それぞれ少なくとも 1 本の入る辺と出る辺が必要なので明らか）であり，以上の手順でそれが達成できているので最小性が保証できます． あとは，得られた追加辺を元の 2 部グラフの辺に戻せば完了です．

強連結化問題への帰着後の計算量は O(n + m) です． 完全マッチングを求める部分は Hopcroft–Karp のアルゴリズム（最大流問題に対する Dinic 法）を用いて O(m√n) 時間ででき，（基本的には）こちらがボトルネックとなります． なお，完全マッチングを単純な増加道アルゴリズムにより求めたり，強連結化問題を解くのに追加辺を 1 本ずつ計算したりしたとしても，合計 O(nm) 時間となって許容範囲の時間で終了する設定となっています．

左右を壁に挟まれた空きマスを考える． そのマスから上下に連続する空きマスの集合を「通路」と呼ぶことにすると，通路上のどこかに灯りを一つは配置しなければならない． 上下を壁に挟まれた空きマスについても同様に，横方向の「通路」のどこかに灯りを一つは配置しなければならない． 問題文の条件 1 と条件 2 から， 全ての空きマスは少なくとも一つの通路に属することが証明できる． 従って，空きマスの部分集合 S について以下が成立する．

S に灯りを配置すると全ての空きマスが明るくなる ⇔ 全ての通路が S に含まれる空きマスを少なくとも一つ含む

問題文の条件 1 から，縦方向の通路は隣接しない．すなわち，(i, j) を通って下方向に通路が伸びているならば，その隣 (i, j+1) を通って下方向に通路が伸びていることはない． このことから，各行について，下方向に伸びている通路の本数は m/2 本以下であることが分かる． よって，左上から順に右下方向へ、現在のマスを通る横方向の通路上に既に灯りを置いたかの 2 通りと，下方向にまだ続いている高々 m/2 本の各通路について灯りを既に置いたか) の 2^m/2 通りを状態とした動的計画法により，灯りの配置の総数を求めることが出来る． 全体の計算量は O(2^m/2 nm) となり，n と m は 30 以下であることから，十分高速に計算が可能である．

まず，はじめに，N=1 での解法について議論する． ここで，簡単のために物見やぐらの位置を原点として考えたとき， 物見やぐらとの距離の条件は，座標 (x, y) と時刻 t を用いて (dx/dt)² + (dy/dt)² = (x² + y²)² と表せる．

ここで，z = x / (x² + y²)， u = y / (x² + y²) と 座標変換すると， (dz/dt)² + (du/dt)² = 1 になる． この座標変換は一般的に平面幾何学の反転操作として知られているものである． したがって，物見やぐらの座標を (0, 0)，敷地の左奥角の座標を (-50, 50)，右手前角の座標を (50, 50) としたとき， 敷地を表す正方形の辺は，四つの円弧に変換される． その外側をユークリッド距離で最短経路で移動すればよい． 例えば，(50, -50) と (50, 50) を端点とする辺は，中心を (0.01, 0) とする半径 0.01 の円の右半分の円周に変換される．

N=2 については，二つの物見やぐらの座標の垂直二等分線で折り返して考えれば， 正方形の辺に一度以上接触する経路のうち最短となるものを考えればよい． したがって，座標変換後の円周で鏡面反射するような経路も考慮すれば求められる． N ≥ 3 についても同様に求めることができる． N に値が大きい場合については，中間の経路のほとんどで正方形の奥または手前の辺に沿った経路が最適になるので， 左端と右端それぞれで二つずつの正方形の内部の最適な経路を調べれば十分である．

以上より，全て種類のクエリについてそれぞれ O(1) で求められる．