生徒の合計点の配列を ０ に初期化して，科目ごとの点を足し込んでいく． そして，それらのうちの最大値を見つけて出力すればよい． 配列は 1 次元のものひとつだけでことたりる．

ニューヨークのマンハッタンや京都のように碁盤目状の街路では， 2 地点間の距離はおおよそ東西の距離と南北の距離の合計になる． このように二次元座標中の 2 点間の距離を X 座標の違いと Y 座標の違いの合計とする定義をマンハッタン距離という． 数式で書くなら |x₁−x₂|+|y₁−y₂| になる． この定義は三角不等式などの距離の公理を満たし，普通の距離（ユークリッド距離）と同様にさまざまな局面で使われる定義である．

さて，この問題でスクリーンキーボード上のあるセルから別のセルまで強調表示を動かすには， 行と列の両方向を合せなければならないが， そのためにボタンを押す回数は行の違いと列の違いの合計，つまりマンハッタン距離になる． 行と列をどの順に押しても合計回数は変わらない．

最後に OK を押す必要があるので，

• 左上隅からから最初の文字の場所までのマンハッタン距離 + 1
• 最初の文字の場所から 2 番目の文字の場所までのマンハッタン距離 + 1
• ...
• 最後から 2 番目の文字の場所から最後の文字の場所までのマンハッタン距離 + 1

を合計したものが答になる．

強調表示セルを動かす際に，どの順に動かすかは関係ない，というのがポイントといえばポイントだろう．

問題をきちんと整理できれば, 率直な解法はすぐ見つけられよう. そうした方法でも計算量が大きくなりすぎないことを見積もれれば, そのままプログラムに書き下せばよい. 高度なアルゴリズムの知識などは必要としない問題である.

分銅の使い方

各分銅の使い方は

• 薬品と反対側の皿に置く
• 薬品と同じ側の皿に置く
• 使わない

のいずれかである.

薬品の計量方法

重さ a の薬品を, 既有の分銅を薬品と反対側の分銅の重さが合計 x, 同じ側の分銅の重さが合計 y となるように使って量る方法は, 以下の 3 通りがある.

• a = x − y なら, 分銅を追加せずとも, そのまま量れる.
• a > x − y なら, 重さ a − (x − y) の分銅を追加して薬品と反対側に置けば, 反対側の分銅は合計 x + (a − (x − y)) = a + y になり, 薬品の側は y なので, 重さ a の薬品が釣り合う.
• a < x − y なら, 重さ (x − y) − a の分銅を追加して薬品と同じ側に置けば, 薬品の側の分銅は合計 y + (x − y) − a = x − a になり, 反対側は x なので, 重さ a の薬品が釣り合う.

どの方法を用いることができるかと追加すべき分銅の重さは, 両方とも w = x − y だけで決まる.

想定解法手順

1. 既有の分銅の使い方を表す w = x − y の集合 W を求める. 既有の分銅 m 個のそれぞれについて上記 3 通りの使い方があるので, それを組合せた 3^m 通りを再帰的に列挙すればよい.
2. まず既有の分銅だけで量り取れる重さ, つまり W の要素については, 量り取るべき重量のリストから除外する. 全部除外できるようなら分銅の追加は不要であることがわかり, それで終わり.
3. 残った重さのうちのひとつ a₁ を適宜選び, 追加すればこれを量り取ることができる分銅の候補を列挙する. W の要素 w の各々について
   • a₁ > w なら薬品の反対側に a₁ − w の分銅,
   • a₁ < w なら薬品と同じ側に w − a₁ の分銅
   を追加すればよい. どちらにしても abs(a₁ − w) の分銅を追加すればよいわけである. この追加分銅候補の集合を C = {abs(a₁ − w) | w ∈ W} とする. 重さ a₁ を量り取るには C の要素の重さの分銅が必要なのだから,
   • 追加すべき分銅の重さはこの中にある
   • 分銅ひとつの追加では全部の重さを量れない
   のいずれかである.
4. C の各要素 c について, 量り取るべき他の重さ a_i (i = 2, ..., n) をすべて量れるか調べて絞り込んでいく. 重さ a_i を量り取るには a_i + c または a_i − c のどちらかが W に入っている必要がある. W の要素か否かのテストを効率的に行うには W をハッシュ表で表現すればよい. 量れない重さがひとつでもある c は C から除外していく.
5. C に残った候補のうち最小のものが答えである. C が空になってしまったら, 分銅ひとつの追加で全部量れるようにはできないことがわかる.

想定解法の計算量

計算量は追加分銅候補の集合を狭めていくステップ 4 が最大で, O(n × 3^m) である. n ≤ 100, m ≤ 10 だから n × 3^m ≤ 100 × 3¹⁰ = 5 904 900 と, さほど大きくはならない.

各カウンタに対して実際の値は重要ではなく，ボタンを押した回数のみが重要である． そこで，c_i = (b_i − a_i) % m とすると，各カウンタは c_i + k × m (k ≥ 0) 回押される必要がある．

1 つ目のカウンタに着目してみる． 最適な操作列において，このカウンタが押される回数は c₁ 回であるとしてよい． 余分に m 回押すのであれば，その部分はすべて次のカウンタから操作したものとすればよい．

2 つ目以降のカウンタについて考える際，道具をどこから使ったかを考える必要はない． 1 つ前のカウンタを押した回数より多く押すことはそこから新たに道具を使うことを意味し，少なくすることはその直前までで道具を使ったことを意味する． 1 つ目のカウンタの議論と同様に，各カウンタでの押される回数の増減は m 回以下であるとしてよい．

これらを考慮すると，あるカウンタまで見たときの最後のカウンタを押した回数に対する最小の操作回数を計算するような動的計画法が考えられる． カウンタを押す回数は n × m 回で抑えられるため，状態数は O(n²m) となる． このままでは状態数が多すぎるが，各カウンタを押す回数は c_i + k × m (k ≥ 0) 回であることを考えると，押した回数の代わりに何周余分に押したかを表す k だけを覚えていれば十分である． これにより，状態数は O(nm) となり，各状態に対して遷移は増やすか減らすかだけの O(1) でできるため，全体の計算量も O(nm) となり十分高速に解答できる．

6つのピースを適切に並べて組み合わせることで立方体 (の表面) を作ることができるかどうかを判定する問題である． ピースをひとつ固定することで，残りのピースを配置する方法は 5!×8⁵ となる．立方体ができているかの判定には，立方体の 1 辺の長さに比例する時間で計算できる．

審判団の想定解法は，ピースを配置していく過程で枝刈りを行うものである．立方体ができているかの判定はそれほど簡単ではないので，枝刈りをしない素直な (バグの入りにくい) コードを書いて計算結果が出るのを (数分程度) 待つ作戦をとったチームもみられた．

最終的な辺の色は，操作を行う順番には依存しない． ある頂点Aの周りの辺を反転してから別の頂点Bの周りの辺を反転するのも， 逆の順番で行うのも結果は同じである． また，同じ頂点での色の反転を2回行っても元の色に戻るだけであるから，意味がない． したがって，各頂点についてその頂点の周りの色反転を行うか行わないかの， 計 2ⁿ 通りの場合を考えればよいことになる．

2ⁿ の全通りを試すには計算時間が足りないが， 目標となる最終状態が木であることを考えると，試すべき範囲を大幅に減らすことができる．

具体的には，木には必ず繋がっている辺が1つだけの頂点（次数1の頂点）が存在することに着目する． このような頂点を a，そして a と繋がっている唯一の頂点を b とする． a と b を決めると，a と赤い辺で繋がっている頂点が b だけとなるような反転の仕方は唯一に定まることがわかる． （頂点a周辺の反転は行わず，頂点bについては辺 a-b が初期状態で黒だったときのみ反転， a，b 以外の頂点xについては，辺 a-x の初期状態の色が赤のとき反転． あるいは全頂点についてこの逆を行っても同じ色のグラフが得られる．） よって，頂点a，bの候補 n(n-1) 通りを全通り試し， それぞれについて上記の唯一に定まる反転を行った結果が全域木になっているかを深さ優先探索などで判定すれば， すべての全域木の可能性を調べあげることができている．

辺の本数が n(n-1)/2 本あるため上記の解法をナイーブに実装すると n⁴ に比例する時間がかかってしまうが，辺の反転を実際には行わず頂点毎に反転するか否かのフラグを持っておき， 全域木判定の際に考慮して探索するなどの工夫で計算時間を O(n³) に抑えることができ， 入力データのサイズ n ≤ 300 に対しては十分高速に解答することができる．

また詳細は略するが，別解として，木はサイクルを持たないという性質に着目すると， 赤い辺が2本繋がった形 a-b-c が確定すると残りの頂点の反転方法は高々1通りに定まることなどを用いて， O(n²) 時間の解法を得ることもできる．

行う操作の回数が非常に多いので1つ1つの操作を愚直にシミュレーションする方法は現実ではない． 繰り返し表記によって生成される大量の操作をまとめて行う必要がある．

ここで操作列のシミュレーションとしてはタイル全体を時計回りまたは反時計回りに移動させるような操作列だけを考えればよいことに留意されたい． 例えば時計回りの操作列は DLURDLURDLUR...，反時計回りの操作列は RULDRULDRULD... のような形である． もちろん，入力で与えられる操作列はこのような形になっていない． しかし，操作列上でまったく盤面の状態を変えない操作や，時計回りで移動させているときに反時計回り方向へ移動させる箇所があった場合その箇所を取り除くによって，すべての操作列は時計回りまたは反時計回りに移動させる操作列と同じ結果を生むものだとみなせる．

例えば時計回り移動を何回もやる場合，そのシミュレーションは以下のようにしてできる． 時計回り移動を一周するとそれぞれのタイルの位置は変化する． しかし，タイルが存在するマスの集合は一周する前と後で変動しない (なぜなら，一回の操作を行ってもタイルが存在するマスの集合は上下または左右に反転するのみになるので，一周すると元に戻る)． 例えば DLURDLURDLUR... という反時計回り移動を繰り返すとき，一周分の移動は以下のようになる．

  ..ABC  D  .....  L  .....  U  FEC..  R  ..FEC
  ...DE ==> ....F ==> F.... ==> DB... ==> ...DB
  ....F     ...DE     DE...     A....     ....A
  .....     ..ABC     ABC..     .....     ..... 

一周すると個々のタイルは別々のところに移動する． 上の例では A のタイルは F のタイルの位置に，B のタイルは E のタイルの位置に移動する… といった具合である． このような移動の置換を求めておけば，何周させるのであっても操作列の実行後の結果は高速に求めることができる．

したがって，操作列を実行したあとでタイル全体が時計回りまたは反時計回りに何周したのかがわかればよい． このために，部分操作列に対して次の情報を逐次的に計算することを考える．

• UL という操作を行った後で，部分操作列を行った後に時計回りまたは反時計回りに何周することになるか．
• 同様に，最初に行う操作を UR, DL, DR, U, R, D, L に変えたときについての情報も同様求める．

この情報の計算は以下のようにしてできる． まず操作列の長さが 0 である場合は自明である． ある2つの操作列 X と Y を続けて行う操作列(つまり，XY)については，それぞれの開始位置(UL, UR, ...)から X を行うと次にどの位置にいるのかは分かるので Y の情報と合わせることで XY によって時計回りまたは反時計回りに何周するかの情報を得ることができる． 繰り返し表記 (X)k に対しては単に繰り返し二乗法をすればよい． この情報があれば，最終的に操作列全体でタイルが時計回りに反時計回りに何周したのかを計算できる．

計算時間は O(n^2 + 入力の操作列文字列の長さ * log(繰り返し回数)) 程度である．

後述するように， 凸多角形 R, S に対して R = S + R' となるような R' は存在すれば一意に定まる． このような R' が存在するとき， R' を R - S と表すことにする． 引き算ができるならユークリッドの互除法のような操作ができ，その操作を R, S に適応すると解 P, Q を求めることができる．

R と S に関して以下の3パターンに分けられる:

• R - S が存在する，
• S - R が存在する，
• R - S も S - R も存在しない．

1つ目の条件が成り立っている場合， (R, S) を (R - S, S) で置き換えて同じ問題を解いても同じ解になる． つまり (R, S) に対する非自明な解 (a, b, c, d, P, Q) に対しては

R - S = (a - c)P + (b - d)Q
S = cP + dQ

で (R - S, S) に対する解が作れ， (R - S, S) に対する解 (a', b', c', d', P', Q') に対しては

R = (a' + c')P' + (b' + d')Q'
S = c'P' + d'Q'

で (R, S) に対する解が作れる． 上の a - c と b - d が負の整数にはならないことを説明しよう． ad - bc = 1 なので，「a > c かつ b ≥ d」または「a ≤ c かつ b < d」または「a = d = 1 かつ b = c = 0」が成り立っていることに注意する． R - S が存在するという仮定と， (a, b, c, d, P, Q) が非自明な解であるという仮定から ， 「a > c かつ b ≥ d」しかありえないことがわかる． よって， a - c と b - d は非負となる． 以上より， (R, S) を (R - S, S) で置き換えてよい．

同様に，2つ目の条件が成り立っている場合には， (R, S) を (R, S - R) で置き換えてもよい．

これを繰り返していくと，どの凸多角形も整数座標で面積の和が小さくなっていくため，いずれ3つめのパターンになる． そのときの (R, S) が解 (P, Q) になる． 「割った余り」を求める部分の計算量は後で考えるとして， a, b, c, d は R と S の座標の幅程度にしか大きくできないので， (P, Q) を求める部分は O(log(座標の大きさ) * (凸多角形の割り算の計算量)) となる．

R - S を求める方法について述べよう． R や S を平行移動しても R - S も平行移動されるだけなので，平行移動の違いについては無視してよい． S の一点 v を固定して R の内部で S を R の辺に沿って動かしながら v の軌跡をたどれば R - S を作ることができる． R の内部をぴったり移動できない場合には R - S は存在しない，と判定できる． 凸多角形であることを利用すると O(頂点数) でできる．

もうすこし凸多角形の和について考察すると，以下のようなことがわかる． 頂点の配列を v として，凸多角形の辺のベクトル v[i + 1] - v[i] の集合に着目する． R + S の辺のベクトルの集合は

• R と S の向きが同じ辺のベクトルを足したもの
• R の辺のベクトル (S に同じ向きの辺がない場合)
• S の辺のベクトル (R に同じ向きの辺がない場合)

からなるので， R - S の計算はこれを逆にすればいい．つまり

• R と S の向きが同じ辺のベクトルを引く (引いたときに向きが変化する場合は R - S は存在しない)
• R の辺のベクトル (S に同じ向きの辺がない場合)
• S の辺に対応する辺がなければ R - S は存在しない

という操作で R - S の辺のベクトルの集合が求まる． 結局 R の辺と S の辺で，向きが同じものどうしでユークリッドの互除法をする，というのを辺の数だけ同時にする感じになる． 全体で計算量は O((頂点数)*log(座標の大きさ)) となる．