提案： 稲葉 一浩
主担当： 稲葉 一浩
与えられた整数の列の中で，もっとも 2023 に近いものを探す問題である．
各言語の標準的な関数を使って abs(a[i] - 2023) (C, C++, Python) や Math.abs(a[i] - 2023) (Java) といったコードで 2023 との差が求められるので，これが一番小さくなるものを答えとして返せばよい．もちろん，abs 関数を使わずに if 文などで求めることもできる．
提案： 石畑 清
主担当： 石畑 清
あみだくじに横線を 1 本加えることによって，目標の品物に到達できるようにするやり方を求める問題である．
まず，ルールに従って P から下端まで移動する経路を求める必要がある． この操作は，x1, …, xm を入れた配列を前から順に見て行くだけで，簡単に実現できる． 答を見つける方法は，いろいろ考えられる． (1) (n − 1) × (m + 1) 箇所の候補位置をすべて調べる． (2) P から下端に至る経路の途中に横線を新設する方法をすべて試す． (3) P から下端に至る経路と Q から上端に至る経路が隣り合っている場所を見つける． 計算量は，それぞれ O(nm2)，O(m2)，O(m) である． いずれの方法でも，大した計算時間にはならない．
提案： 楠本 充
主担当： 山口 文彦
題意通りの条件を満たす席の配置を答える問題である．規則的な並べ替えを，うまく見つけられるとよい．いろいろな解法がありえるが，たとえば次のような解法がある:
ある行について，偶数列目に座っている生徒を順に前半に，奇数列目に座っている生徒を順に後半に移動すると，隣り合って座っていた生徒の新しい列の番号の差は ⌊ n / 2 ⌋ 以上になる．
1,2,3,4,5,6,7 → 2,4,6,1,3,5,7すべての行に対してこのような席替えを行った後，すべての列に対して同様の席替えを行って得られる配置は，条件を満たす．
提案： 佐藤 遼太郎
主担当： 山口 勇太郎
答えが 7 以下であることが示せるので，あり得る配点の組合せを適切に全探索することで時間内に正答を得ることができる．
まず，K = 20 + 21 + ... + 2k ≤ n を満たす最大の整数 k に対し，20, 21, ..., 2k 点の問題を 1 つずつ準備すれば，0 点以上 K 点以下の全ての得点が現れ得る． K < n の場合は追加で (n − K) 点の問題を 1 つ準備することで，(k + 2) 問以下で n 点満点かつ 0 点以上 n 点以下の全ての得点が現れ得る問題セットを作ることができる． n ≤ 100 であるため，k ≤ 5 であり，7 問以下で十分である．
したがって，6 問以下の配点の組合せ全てに対して要件を満たすかどうかを確認すれば，この問題に正しく答えることができる． m (≤ 6) 個の正整数の組であって，総和が n であるようなものを 1 つ固定すると，その組で所望の得点が実現できるかどうかは，ナップサック問題と同様の素朴な動的計画法 (DP) により O(mn) 時間で計算できる． また，そのような組は，並べ替えて同じになるものを区別した場合に n-1Cm-1 通りである．
上記の見積りで素朴に実装すると時間が掛かり過ぎてしまうが，以下に挙げるもののような何らかの工夫を施せば十分高速に動作する．
提案： 佐藤 遼太郎
主担当： 佐藤 遼太郎
本問題は，入力として与えられる 0 以上 n 未満の整数の組の列 (yi, xi) (i = 1, ... n) について，いくつかの整数を変更して辞書順比較で単調非増加列にするとき，必要となる変更の最小回数を求めるものである． この問題は以下の動的計画法 (dynamic programming, DP) による解法が有効である．
2 次元配列 dp を用意し，dp[i][j] には列の初項から第 i 項までに j 回以下の変更を行うことで条件を満たすことが可能かどうかという情報や，さらに可能であるならば j 回以下の変更後の (yi, xi) としてあり得る最大値を持たせることにする． 整数の変更は 2n 回（より厳密には n 回）行えば十分なので，i = 1, ..., n と j = 0, ..., 2n の範囲のみについてこれを計算すればよい． dp[i][j] から dp[i + 1][j + k] (k = 0, 1, 2) への遷移はそれぞれ O(1) で行えるので， i および j の昇順にこれらの値を埋めていけばよい．
以上より本問題は O(n2) 時間で解ける．
提案： 楠本 充
主担当： 城下 慎也
穴や自己交差のない n 頂点の多角形 P のコピーを有限個並べることで凸多角形を作成できるかを判定する問題である．
P の凸包を C とおく．C 内には P に属さない多角形領域が複数あるが，それぞれを穴と呼ぶこととする．このとき，C の各辺 e は以下のいずれかの条件を満たす．
このとき，P を有限個並べることで凸多角形を作成できることと，C のどの辺も完全または部分被覆されていることが同値となる．この判定は凸包の構成と P の各辺との位置関係が計算できれば良く，O(n log n) で動作する．ただし，入力サイズが小さいため，これより多少効率の悪いアルゴリズムでも高速に動作する．
以下，条件の同値性を示す．
どのように並べても凸多角形とならないことを示す．C の被覆されていない辺を 1 つ固定する．C が以下の条件を満たすと仮定しても一般性を失わない．
このとき，P のコピーのうち，x 座標が最大であるもの、複数ある場合はそのうち y 座標が最小であるものを取ると，そのコピーの p から y 軸正の方向に微小に動いた点はどのコピーにも含まれないが，コピー全体で凸包を取ったときの周上に現れることとなる．よってコピー全体が凸多角形となることはない．
すべての辺が完全被覆されている（P が凸多角形である）場合は明らかに条件を満たす．以下，部分被覆された辺がある場合を考える．
凸包上の穴に対し，以下の条件を満たすときにその穴を e に属するとする．
以下の条件を満たしながら繰り返し P を変形することで凸多角形を作成する方法を考える．
初期状態は明らかに条件を満たす．凸包上から，部分被覆された辺 1 本と，その辺の真向かいにある辺の集合（真向かいに平行な辺があるなら 1 本，そうでないなら真向かいにある頂点に接続する辺 2 本）を選ぶ．選ばれた辺が 2 本なら直線状に，3 本なら三角形状に多角形を配置することを考える．すなわち，2 本の場合は辺の向きに沿ったベクトル v に対し av（ただし a はある整数 M に対し 0 ≤ a ≤ M を満たす整数）ずつずらして重ねる配置全体を，3 本の場合は各辺が 3 本の辺とそれぞれ平行な三角形を考え，その三角形のある頂点から他 2 頂点へのベクトルをそれぞれ v, w としたとき，v と w の整数倍の足し合わせ av + bw（ただし a, b は非負整数であり，ある整数 M に対し a + b ≤ M を満たす）ずつずらして重ねる配置全体を考える．
このとき，配置後の図形の凸包を取ると，元の凸包のうち，選ばれた辺だけが伸ばされた図形となる．実数 ε を「各辺 e について，e に属する穴と，e 以外の辺自身またはそれに属する穴，あるいはどの辺にも属さない穴との距離の最小値をとったときの，全ての辺における最小値」と定義する．条件 (b) より，この値は正となる．ベクトル v, w, v - w の長さがいずれも ε 未満となるようにベクトルを取ることで，操作後のコピー全体が上記 (a), (b) に加え，以下の条件 (c) を満たすように配置できる．
条件 (a) は操作前の凸包の仮定より成立する．
条件 (b) が成立しない場合，凸包は頂点に接する穴を持つか，接続するいくつかの穴によって分断されることとなる．前者は構成方法よりないことが言える．後者についても，P の外周から ε 以下の領域全体からなる帯を考えると，コピーされた帯全体の集合は連結となるため，分断されないことが言える．
条件 (c) について考える．選ばれた辺に属するどの穴についても，その辺に沿って ε 未満の間隔で別のコピーが配置されるため，すべての穴が消失し完全被覆される．選ばれなかった辺のうち，完全被覆された辺はそのまま残るため，部分被覆とはならない．
操作後のコピー全体を P と置き換えて，上記の操作を部分被覆された辺がなくなるまで繰り返すことで，すべての辺が完全被覆されるようになる．
最後に，この多角形にはどの辺にも属さない穴が含まれる可能性があるが，次の操作を行うことで取り除くことができる：多角形の外周から穴への距離の最小値を ε として上記同様に 2 本または 3 本の辺を選び，ε 未満の間隔で配置する．
提案： 丸茂 直貴
主担当： 丸茂 直貴
(x − y)2 の期待値は「x − y の期待値の二乗」と「x − y の分散」の和に等しい．
dp[i][j][k] を「i 番目までのサイコロのうち j 個を 2 人のプレイヤに配り，x − y の期待値の絶対値が k に等しくなるようにするときの，x − y の分散の最小値」と定義する． 問題の答えは，k を動かしたときの k2 + dp[n][m][k] の最小値である． ここで，問題文中の「どちらのプレイヤも少なくとも 1 つのサイコロを受け取る」という条件を無視しても問題の答えは変わらないことを用いた．
x − y の分散が各サイコロの出目の分散の和に分解できることに注意すると，上の DP テーブルは，ナップサック問題の場合と似た方法で計算できる．
サイコロの面に記された数の上限を a とすると，k として考慮すべき値の候補は 6ma 通り程度であり，解法全体の計算量は O(nm2a) となる． 上記解法は浮動小数点数を使わずに実装できる．
提案： 岩田 陽一
主担当： 岩田 陽一
\(i\) 番目のバス停の座標を \((a_i,b_i)\) とすると、以下のLPを解けば良いことになる。 $$ \begin{align} \min \sum_{ij\in E} (|a_i-a_j|+|b_i-b_j|)\\ {\rm subject\ to\ } |a_i-x_i|+|b_i-y_i| \leq r_i \end{align} $$ 絶対値を外すと以下のようになる。 $$ \min \sum_{ij\in E} \{\max(0, a_i-a_j)+\max(0,a_j-a_i)+\max(0,b_i-b_j)+\max(0,b_j-b_i)\} $$ $$ {\rm subject\ to\ } \begin{align} a_i-x_i+b_i-y_i&\leq r_i\\ a_i-x_i-b_i+y_i&\leq r_i\\ -a_i+x_i+b_i-y_i&\leq r_i\\ -a_i+x_i-b_i+y_i&\leq r_i\\ \end{align} $$ ここで、制約式が全て \(a-b\leq c\) の形であれば、最小費用流問題をLPで書いた場合の式に一致するため、最小費用流に帰着することで多項式時間で解くことが出来る。 しかし、今回の問題では、１つ目と４つ目の制約が \(a+b\leq c\) と \(-a-b\leq c\) という形で符号が揃ってしまっている。 そこで、新しい変数を導入して、\(a_i=a_i^+=-a_i^-, b_i=b_i^+=-b_i^-\) とした気分で以下のLPを解くことにする。 $$ \min \frac{1}{2}\sum_{ij\in E} \left\{\begin{align}\max(0, a_i^+-a_j^+)+\max(0,-a_i^-+a_j^-)+\\ \max(0,a_j^+-a_i^+)+\max(0,-a_j^-+a_i^-)+\\ \max(0, b_i^+-b_j^+)+\max(0,-b_i^-+b_j^-)+\\ \max(0,b_j^+-b_i^+)+\max(0,-b_j^-+b_i^-)\end{align}\right\} $$ $$ {\rm subject\ to\ } \begin{align} a_i^+-x_i-b_i^--y_i&\leq r_i\\ -a_i^--x_i+b_i^+-y_i&\leq r_i\\ a_i^+-x_i-b_i^++y_i&\leq r_i\\ -a_i^--x_i+b_i^-+y_i&\leq r_i\\ -a_i^++x_i+b_i^+-y_i&\leq r_i\\ a_i^-+x_i-b_i^--y_i&\leq r_i\\ -a_i^++x_i+b_i^-+y_i&\leq r_i\\ a_i^-+x_i-b_i^++y_i&\leq r_i\\ \end{align} $$ これは最小費用流の形になっているので\(O(m^2 \log n)\) 時間で解くことが出来る。 \(a_i=a_i^+=-a_i^-, b_i=b_i^+=-b_i^-\) とした気分で作ったこのLPは、この等号制約を実際に入れた場合は元のLPと完全に一致し、等号制約を入れずに緩和したものであるから、その最適値は元のLPの最適値以下であることが分かる。 得られた解に対して、\(a_i=(a_i^+-a_i^-)/2, b_i=(b_i^+-b_i^-)/2\) として \(a_i, b_i\) を構築すると、これは元のLPの制約を満たし(例えば、新しいLPの１つ目と２つ目の制約式を足すことで、元のLPの一つ目の制約式が得られる)、目的関数値が大きくはならない(例えば、\(\max(0,a_i^+-a_j^+)+\max(0,-a_i^-+a_j^-)\geq\max(0,(a_i^+-a_i^-)-(a_j^+-a_j^-))=2\max(0,a_i-a_j)\)が成り立つ)ことが分かるため、元のLPの最適解である。 よって、新しいLPを最小費用流に帰着して解くことで元のLPの最適解が求まる。