microbeの活動日記

プログラミングコンテストとかいろいろ

全列挙 : POJ2718,POJ3187,POJ3050,AOJ0525

蟻本に掲載されている問題

2718 -- Smallest Difference
3187 -- Backward Digit Sums
3050 -- Hopscotch
おせんべい | Aizu Online Judge

POJ2718

数を組み合わせて2つの整数をつくり,その差の絶対値の最小値を求める
std::next_permutationを使うと幸せになれる

gista2d834daff05f9c5c2e8181542d9b59c

 

POJ3187

パスカルの三角形的なもので最終的な和がsumになるような1~Nの並びを求める.
std::next_permutationなら辞書順に生成されるので幸せになれる

gist43f11673ba894460accdc05e188ceee3

 

POJ3050

BFS

gista17b044b1a0e70d86410c6f68290a3bb

 

AOJ0525

行と列を全列挙してると時間が足りないのでひっくり返す行さえ決まればあとは1がr/2より多いものをひっくり返せばいい.行だけの全列挙なら多くてもパターンは2^{10}程度で済む.

gist77ba324305ea5711bc61df08410e3d27

 

やっぱり実装力がないので悲しい