昨年度に比べてかなり易化したと思われる．とにかく問題文を落ち着いて読めるかどうかがポイント．今年度はグラフの問題が多い．
（注）下記の解釈には誤りがあるかもしれません．
- Problem A
- 問題自体はすぐに理解できるが，解法はサパーリ．
- Problem B
- グラフに落として Dijkstra という超典型問題（だけどちょっと面倒）．
- Problem C
経路を共通な場合は距離が一度しか勘定されないところがミソで，そこの工夫をどうするかがちょっと見えない．
Dijkstra をうまく変形すれば解ける気がしてきた．
考えてみれば Prim 法を適用して最小部分木を生成するだけだ．- Problem D
- 高々 10 回しかシャフルしないわけだから，正常なシャフルの結果と比較すれば何とかなるかな．
- Problem E
- 素直な図形問題．
- Problem F
- 可変長メッシュにもとづいてマップを生成して塗りつぶす．
- Problem G
- 問題の意図は明瞭だが，ヒントを与えている文章の意図するところが非常に理解しにくい（ヒントが理解できても解法がすぐにわかるわけでもないし）．
- Problem H
- キャッシュつきの幅優先探索をすれば終わりかな？
- Problem I
どん欲法のような，動的計画法のような，う〜む．
テント数の最小化は単純などん欲法で可能．あとは人数を適当な方法（たぶん優先順位つき探索）で最小化すればよい．
どん欲法は利用できなさそう．単純に優先順位つき探索かな．- Problem J
- 単純に客の数を動的計画法の要領で数えればよい．
Problem G のヒントと Figure 1 の関係 †
L 字型の左下隅を (0,0) として，次の座標にある点に注目する．
A(1,4) B(0,4) C(0,3) D(3,0) E(4,0) F(4,1)
このとき AB と ED，BC と FE，CD と AF はそれぞれ合同であるから，六角形 ABCDEF とみなせば平面に配置できる．すなわち AB と ED，BC と FE，CD と AF がそれぞれ重なりあうように配置すればよろしい．ここで，たとえば辺 CD は，もとの多角形の辺のうち点 C から点 D までの部分，つまり (0,3)--(0,0)--(3,0) になる．
- Ｇは、線分の長さの max が指定されてないことに注目。線分の途中に点があるかも、といいつつ実は本当に限られた点しか使いません。 -- かさはら?
- Ｉは２部グラフの最大マッチングですよ。（同じ部屋で２以上ミーティングしない、という制約を仮定してよければ） -- かさはら?
- Ｄはそれでシャッフル回数は分かります。その先は？（同じカードが２回ミスる場合もあるからね） -- かさはら?
- Ｃは、"頂点数最小and辞書順で最初の解"という条件をPrimの変形で実現するやり方が思いつかなかったです。（というかいまだにわからない。） -- 稲葉
- 動的計画法でJは簡単には解けない気がします。VertexCoverはNP困難問題だったような。 -- 桜庭＠GNC?
- C : 辞書順最小の条件は読み落としていました． D : 同じカードが 2 回ミスする場合は…一応あるのかな（ただし連続する 2 回では並び順の関係でありえない）． G : 点についてはそんな気がしましたが，可能性をちゃんと整頓していなかったので…． I : 確かに． J : N が小さいからたぶん大丈夫． -- 泉
- C : 頂点通過に対して微小なペナルティを与えて，かつ頂点番号の小さいほうを優先する規則をとればうまくいくような気がする． -- 泉
- Hも2部グラフのマッチングだと思います。幅優先は探索空間が大きすぎて無理だと思うのですが… -- 田中
- Ｃは人数少ないので各頂点で全通りを保持しておけば・・・ -- かさはら?
- Gは条件さえ読めば全探査という気がします。結局辺上の格子点についてだけ考えればよいので。 -- 桜庭＠GNC?
- H : 探索空間は広くても実際には途中で探索を止めてしまうわけだから（∵解が見つかる），多少工夫すれば何とかなるような気がする． C : 確実ですが少々面倒ですね． G : 辺の長さの最大値に関する記述がない点が不気味． -- 泉
