第５回日本情報オリンピック 本選 (JOI 2006 本選 問題・データ) の 問題4 (リンク)、問題5 (リンク) の問題文が曖昧だったので、厳密な問題文に直しました。
問題4 (リンク)
修正後の問題文
1, 2, ..., 100 までの番号がついた頂点をもつ、自己ループをもたない 100 頂点 n 辺の無向グラフがある。このグラフのパスであって、同じ頂点を 2 度通らないものの長さとしてありえる最大値を求めよ。
何が悪いか
元々の問題文では「鎖」という単語が 2 回定義されており、微妙に違う意味であるところ。2 回目の定義から後の「鎖」はすべて 2 回目の定義を指すと思えば解釈はできる。また、「同じ数の付いたリングは一度だけたどるつながった複数の紐」という表現では、枝分かれが禁止されているかどうかが読み取りにくい。(実際は禁止されている。)
問題5 (リンク)
修正後の問題文
修正前の問題文と同様。ただし、複数の長方形で覆われた部分 S の周長とは、S の境界の長さの合計である。点集合 S の境界とはある x, y に対して (x, y)-(x, y+1) 間、または (x, y)-(x+1, y) 間を結ぶ線分であって、線分を辺として含むちょうど 2 個の正方形のうち 1 個が S に含まれ、もう 1 個と S の共通部分の面積が 0 であるようなものである。(特に、S 内部に空洞がある場合、その周囲も境界として扱われることに注意されたい。)
何が悪いか
「周長」に内部の空洞の長さを含めるのかどうかが問題文から読み取れず、またサンプルに内部に空洞を含む例がないためサンプルからも推測できない。修正後の問題文のように仮定して実装したら AC が取れたので、修正後の問題文の解釈が正しかったか、内部に空洞を含むテストケースがなかったかのどちらかである。
