蟻本の練習問題埋め2-1(2)

蟻本

全列挙

POJ 2718 - Smallest Difference

http://poj.org/problem?id=2718

問題

0~9の整数からなる集合の部分集合が与えられる。
その集合を２つの部分集合に分割し、好きなように並べ替えて２つの整数を作ることを考える。
このようにして作られる２つの整数の差の最小値にせよ。
ただし、0から始まるような整数を作ってはいけない。

制約

特になし

解法

入力がだるいがgetlineとstringstreamで対応する。
分割の仕方は最大2^10乗、各分割に対して並べ替えが分割された集合の要素数の階乗だけある。
普通にやると多分間に合わないので、分割された集合をSとTとすると、
abs(|S|-|T|) >= 2
のときは無視することにより間に合わせる。
abs(|S|-|T|) >= 2
のときは各々並び替えて出来上がる数値は2桁以上違うことになり、答えにはならない。
あとは0から始まるような整数(0以外)を作らないことに注意する。

POJ 3187 - Backward Digit Sums

http://poj.org/problem?id=3187

問題

整数1~Nを並べ変えた数列を、パスカルの三角形のように足しあわせて1つの整数を作る。
最後に残った整数が与えられるので、元の数列として考えられるもののうち辞書順最小のものを求めよ。

制約

N<=10

解法

N!で全探索
初め順列ではないと思い、N^Nかかると思って悩んでしまった。
左からi番目の数列は、{}_{N-1}\mathrm{C}_{i-1}回足し合わされることを利用すると良い。

POJ 3050 - Hopscotch

http://poj.org/problem?id=3050
5*5*4^5試してsetに突っ込むだけ

AOJ 0525 - おせんべい

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0525
多分やるだけ