提案： 稲葉 一浩
主担当： 稲葉 一浩
与えられた整数の列の中で，もっとも 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 の各辺 e に対し，P の周上との共通部分（両端点含む） f を考える． このとき，f はいくつかの線分または孤立点の集合となり，以下のいずれかを満たす．
このとき，P を有限個並べることで凸多角形を作成できることと，C のどの辺も完全または部分被覆されていることが同値となる． この判定は凸包の構成と P の各辺との位置関係が計算できれば良く，O(n log n) で動作する．ただし，入力サイズが小さいため，これより多少効率の悪いアルゴリズムでも高速に動作する．
以下，条件の同値性を示す．
どのように並べても凸多角形とならないことを示す．C の被覆されていない辺を 1 つ固定する． C が以下の条件を満たすと仮定しても一般性を失わない．
このとき，P のコピーのうち，x 座標が最大であるもの、複数ある場合はそのうち y 座標が最小であるものを取ると， そのコピーの p から y 軸正の方向に微小に動いた点はどのコピーにも含まれないが，コピー全体で凸包を取ったときの周上に現れることとなる． よってコピー全体が凸多角形となることはない．
すべての辺が完全被覆されている（P が凸多角形である）場合は明らかに条件を満たす．
C のうちある 1 本の辺 e だけが部分被覆されている時を考える． このとき，以下のようにコピーを配置すれば凸多角形を作成できる．
実数 ε を e の両端点を含む辺の長さのうち小さい方の長さ以下の正の値とする． e に沿って ε ずつずらしながらコピーを配置していく． すると，高々有限個のコピーで e に沿った線分全体が完全被覆されるようにできる．
この過程でコピー全体の集合に穴ができることがあるが，以下のようにして塞ぐことができる．
また，この過程で e の真向かいに凹みができることがある．この凹みは以下のように解決できる．
最後に部分被覆された辺が複数ある場合を考える． ある辺に対して上記の操作を行った後の多角形全体に対する凸包を取ったとき，その凸包上には完全被覆または部分被覆された辺しかなく，かつ部分被覆された辺の本数が真に小さくなる． よって，部分被覆された辺がなくなるまで上記操作を繰り返すことで，凸多角形を得ることができる．
提案： 丸茂 直貴
主担当： 丸茂 直貴
(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|&\\ |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) $$ $$ \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} \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^-) $$ $$ \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の最適解が求まる。