週に一回は書きますよ 月に4つ記事を書けばノルマは満たされます。
上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

問題E。今回の問題の最難問のひとつです。解けたチームがなく、また大会後の解説ではあまりよくわからなかったので、いまだにどう解けばよいのかよくわかりません。

問題は、m×nのマス目中に2と3が二つずつ入っていて、それらを線でつなげることが出来るでしょうか、という、いわゆる「ナンバーリンク」です。ニコリのナンバーリンクとの違いはサイズが9×9までに制限されていることと、つなげる文字が二組しかないことと、あと線が通れないマスがあること。線の長さの合計のもっとも短いものを答えるので、当然線が入らないマスが出てくる、ということもニコリとは違いますね。

問題に書かれているサンプルの中に非常に親切なものがあり、それが解けるプログラムなら大丈夫かとはじめは思いました。しかしそのほかにもいろいろはまりそうです。 まず、線が引けるかどうかの判定だけで非常にたくさんのトラップが存在します。

______
__23__
__32__
______
______
_2323_
______
______
_232__
___3__
______
______
_232__
__×3__
______
____×____
_2__×__2_
_________
_3__×__3_
____×____

さらに、解をひとつ見つけてもだめで、線の長さを最小にしなければいけません。解をひとつ見つけ、そこから冗長な迂回路をなくすなどの手段が考えられます。しかしそのように解を徐々に変形させるだけでは最適解にたどり着かない場合がサンプルに載っています。どうしたものか。暇があったら考えます。

スポンサーサイト
コメント
この記事へのコメント
コメントを投稿する
URL:
Comment:
Pass:
秘密: 管理者にだけ表示を許可する
 
トラックバック
この記事のトラックバックURL
http://gusmachine.blog49.fc2.com/tb.php/94-977798d1
この記事にトラックバックする(FC2ブログユーザー)
この記事へのトラックバック
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。