反転(2題)
プログラミングコンテストチャレンジブック [第2版] ~問題解決のアルゴリズム活用力とコーディングテクニックを鍛える~
この本(通称:蟻本)の章末で紹介されている練習問題をひたすらといている。
反転。端っこを決めるとそこからカタカタと自動的に全部決まる系のやる。端っこの部分は全列挙。
POJ3185: The Water Bowls
http://poj.org/problem?id=:3185title
問題概要
20個の 0 または 1 からなる数列が与えられる。 一つの項を反転させると、左右の隣接する項も反転する。すべての数を 0 にするには、最低で何回反転させればよいか。
解法
左端の数を反転させるかどうかを決めればあとは自動的にカタカタと決まる。