プログラミングコンテストチャレンジブック 4-5 その2

4-5 「GCJ の問題に挑戦してみよう(2)」の続きです。

• Endless Knight - チェスのKnightの動きでX,Y座標が両方とも増加する方向のみで(H,W)に移動する経路。ただし何箇所か障害物があって入れないマスがある
  • ナイトの動きでX,Y双方が増加する移動は2通りしかなくて (1,2) or (2,1) それぞれ (1,0) (0,1) になるように座標変換する
  • 障害物のあるマスの数(R)は小さいので、障害物がない場合の全経路(これは組み合わせの数で計算可能)から障害物があって選択できない経路を引く方法を取る
• The Year of Code Jam - プログラミングコンテストに参加する日と迷っている日があって幸福度を最大にする。ただし今度は隣接する日(前後の日と前後の月の同じ日)にコンテストがあると幸福度が下がる
  • 日付をノードとしたグラフにして、隣接する日を辺で繋ぎノードを白、青、？でマーク
  • 2部グラフとして青のノードは始点から∞コストの辺を、白のノードは終点へ∞コストの辺を貼って最大流最小カットで必ず青白が分離されるようにする
  • ? のノードは負の辺が生じないように、終点に向けてコスト4の辺を貼る。ちなみにここの説明には誤植がありますね

これでプログラミングコンテストチャレンジブックは終わりです。最後はかなり駆け足で読み飛ばしたのであまり理解できてないところもあります。実際のコンテンストでは解法を憶えただけではだめで、問題文から問題の構造を読み解いて、どの解き方に帰着できるのかというのを見抜く力が必要そうですね。それは簡単には身につかなさそうです。

さて次はがらっと趣向を変えて「アジャイルサムライ」を読もうと思います。