dohatsutsu’s diary

日記を書いています。

【No.030】「AdventCalendar用の記事 (1つ目) 」

 

自分が過去に合宿で出題した問題の中から3つ選び、簡単な解説と当時の感想などを書いていきます。 (この記事はその1つ目です)

2014/9/24 会津合宿2014 1日目 D問題 DrawPuzzle (ACPC2014 Day1 D)

問題URL

http://judge.u-aizu.ac.jp/onlinejudge/cdescription.jsp?cid=ACPC2014Day1&pid=D

 

長方形のフィールドと持っているパネルについての情報が入力で与えられるので、フィールドの右側から左側への道を作れるかを判定する問題です。

 

フィールドはグリッド状になっており横に何マス並んでいるのかは入力で与えられますが、縦に並んでいるマスの数は必ず3マスで固定されているところがこの問題の最大の特徴です。

f:id:dohatsutsu:20161220151636p:plain

 

 

 

この問題には次のようなコーナーケース(?)が存在しており、たくさんのWAが出ていました。

f:id:dohatsutsu:20161220152239p:plain

 

この問題の想定解法は動的計画法です。

今いる座標と、どのパネルを何枚持っているかを状態に持ちます。

 

一列に3枚のパネルを置かなければならないケースがあるので、遷移は全部で12種類あります。

パネルを1枚だけ置く4種類の遷移と、まとめて1列に3枚置く8種類の遷移です。

f:id:dohatsutsu:20161220153452p:plain

 

・この問題が出題された会津合宿2014では会津大学だけで2セット作った年で、かなり大変だった思い出があります。

 

・一列に3枚置かなければクリアできないケースをサンプルに入れるべきだったかどうかは当時とても悩みましたが結局入れませんでした。

 

以下は当時学部2年生だった僕が書いたコードです。( 幅優先探索で解いています )

gist.github.com