ホームに戻る
TopCoder の傾向と対策２（Ｊａｖａ編）
０、はじめに
TopCoder の div2 の midium 以上を解くための練習問題集です。
TopCoder では問題を理解してコードにする技術が必要です。
しかし、これだけではシステムテストを通すことはできません。
例えば、１０００００００００個の要素を扱うときでも、
TopCoder では実行時間を２秒以内に抑えないといけません。
１０００００００００個のループは普通は２秒で回りません。
探索をいかに早く回すかという技術も必要になります。
ここでは探索をいかに短い時間で行うかを考えます。
まず、実行時間は２秒以内です。
ループは１０００００００回程度であれば回ります。
１００００００００回は非常にキツイと思います。
回数はループ内で行う処理の程度にもよるので、
最大のケースを入れてみて実行時間を計る必要があります。
使用できるメモリは int 型で 10000000 個程度。
20000000 個では確実にオーバーします。
メモリの制限をオーバーすると実行時に以下のエラーがでます。
java.lang.OutOfMemoryError: Java heap space
このエラーはコンパイル時には出ないので注意しましょう。
アリーナのＥｘａｍｐｌｅのテストを１つはしておくと良いです。
以降、例えば１０の２乗は １０＾２ と表記します。
１、例題１
問題
Ｎ個（最小１〜最大５０）の数字がある。
１つの数字は最小１〜最大１０００の範囲内にある。
また、それぞれの数字は重複することがある。
このときＮからいくつか数字を取り出し、
足し算をして数字をちょうどＫ（最小１〜最大５００００）にしたい。
ただし、１つの数字は１回のみしか使えない。
可能であるかどうかを判定せよ。
例えば２、２、５の３つの数字があり、
Ｋ＝７であれば２＋５＝７なので可能である。
Ｋ＝８であれば２＋５＝７でも２＋２＋５＝９でも８にならない。
よって、Ｋ＝８のときは可能でない。
考え方
まず全探索するとどうなるか考える。
１つの数字について数字を使う場合と使わない場合があるので、
数字１つにつき２通りの場合がある。
また、数字は最大５０個あるので、
全探索すると ２＾５０ が必要になる。
これは 1125899906842624 通りに相当する。
この方法では２秒で終了させるのは無理である。
少し考えると、
全探索をして足し算しＫを超えたら以降の処理をやめる、
というような処理で計算を減らせそうである。
しかし、この方法は有効で無い。
例えば、１０００が５０個あり、Ｋが５００００であるとき、
足し算の結果が５００００を超えることは無い。
よって、２＾５０ の探索が回ってしまう。
ここでメモ化を利用します。
メモ化を行うとある値からデータを高速に取り出すことができます。
例えば、１００のとき３、２１２のとき５などの対応を記録するとします。
２個や３個のデータであれば早くアクセスできますが、
データ量が１００００などと多くなってくると、
この中からデータを探すのに最大１００００のループを回す必要があります。
このときにメモ化を使って１回の探索？でデータを取り出すことができます。
例えばデータのキーの値が０から１０００００までなどと制限されている場合、
int data[100001];
といった配列を用意します。
例えば１００のとき３という対応を記録する際には、
data[100] = 3;
と記録します。
キーが１００のデータを取り出す場合は data[100] を参照すれば良い。
メモ化の弱点はメモリを大量に使用するところです。
使用できるキーの値の最大値も制限されます。
では、メモ化を使ってみましょう。
まず、数字の最大の個数×Ｋのとり得る値の最大の配列を用意します。
Ｋの最大のケースは数字が５０個でどの数字も１０００の場合です。
よって、Ｋの最大値は５０×１０００で５００００になります。
dp[51][50001] という配列を用意したとします。
では、１、３、４、７という４つの数字があった場合に、
メモをしていく過程を書いていきます。
dp[12][34] == 1 の場合は、
１２個目までの要素で３４を表現できることを意味します。
１つ目の数字は 1 なので、
dp[1][1] = 1; // １つ目の数字で１は表現可能
２つ目の数字は 3 、
dp[2][3] = 1; // 3 の数字を使えば可能
dp[2][1] = 1; // 3 は使用しないが dp[1][1] == 1 なので可能
dp[2][4] = 1; // 3 を使用して dp[1][1] == 1 なので可能
３つ目の数字は 4 、
dp[3][4] = 1; // 4 の数字を使えば可能
dp[3][1] = 1; // 4 は使用しないが dp[2][1] == 1 なので可能
dp[3][3] = 1; // 4 は使用しないが dp[2][3] == 1 なので可能
dp[3][4] = 1; // 4 は使用しないが dp[2][4] == 1 なので可能
dp[3][5] = 1; // 4 を使用して dp[2][3] == 1 なので可能
dp[3][7] = 1; // 4 を使用して dp[2][1] == 1 なので可能
dp[3][8] = 1; // 4 を使用して dp[2][4] == 1 なので可能
この時点で１、３、４、５、７、８が可能であるのがわかります。
４つ目の数字は 7 、以降も同様の操作を行う。
この方法を使えば最大５０×５００００＝２５０００００の探索で済む。
時間を測定してみたが最悪の場合でも０．１秒ほどで結果がでる。
サンプルコード１−１
int[] d = new int[]{1, 3, 4, 7};
int k = 12;
int[][] dp = new int[51][50001];
for(int i = 0; i < d.length; i++){
dp[i + 1][d[i]] = 1; // 現在の数字で表現できる
for(int t = 0; t <= 50000; t++){
if(dp[i][t] == 1){ // これより前の数字で表現できる
dp[i + 1][t] = 1;
}
else if(t - d[i] >= 0){ // 負の値のチェック
if(dp[i][t - d[i]] == 1){ // これまでの数字に現在の数字を足して表現できる
dp[i + 1][t] = 1;
}
}
}
}
if(dp[d.length][k] == 1){
System.out.println("YES");
}
else{
System.out.println("NO");
}
上の例では dp[51][50001] という配列を用意したが、
じつはこの問題は dp[50001] でも解ける。
サンプルコード１−２
int[] d = new int[]{1, 3, 4, 7};
int k = 12;
int[] dp = new int[50001];
for(int i = 0; i < d.length; i++){
for(int t = 50000; t > 0; t--){
if(t - d[i] >= 0){
if(dp[t - d[i]] == 1){
dp[t] = 1;
}
}
}
dp[d[i]] = 1;
}
if(dp[k] == 1){
System.out.println("YES");
}
else{
System.out.println("NO");
}
メモを１次配列で行うようにしてみた。
探索の量はサンプルコード１−１と比べて減っていない。
サンプルコード１−２はサンプルコード１−１の処理と異なる部分があり、
探索の順番や評価の順番が入れ替わっている。
サンプルコード１−２はこの順番で無いと正確な答えがでない。
省メモリを行うほど処理を行う際の制限が増える。
使えるのであればメモリは贅沢に使うべきであるが、
問題によっては省メモリをせざるを得ない場合もでてくる。
２、例題２
問題
Ｎ個（最小１〜最大５０）の数字がある。
１つの数字は最小１〜最大１０００の範囲内にある。
また、それぞれの数字は重複することがある。
このときＮからいくつか数字を取り出し、
足し算をして数字をちょうどＫ（最小１〜最大５００００）にしたい。
ただし、１つの数字は１回のみしか使えない。
この場合に使用する数字の個数の最小値を求めよ。
Ｋにするのが不可能であれば０を答えとする。
例えば１、１、２、５の４つの数字があり、
Ｋ＝７であれば１＋１＋５＝７なので数字の個数は３個である。
しかし、２＋５＝７で数字を２個しか使わない場合もありうる。
よって、答えは３ではなく２である。
考え方
配列は例題１と同じように用意する。
例題２が例題１と違うのは配列に入れる数値の意味である。
配列に入れる数値の意味を以下のようにする。
dp[12][34] == 5 の場合は、
１２個目までの要素で３４を表現するには最少で５個の数字が必要。
値の更新は次のように行う。
以前までの数字でしか表現できないのであればその個数を最小の個数として使用する。
ただ、以前の結果に現在の値を足した場合の個数がより少ない数字の個数になるのであれば、
以前の結果の個数に現在の数字の個数 1 を足した個数を最小の個数とする。
現在の数値のみで表現できるのであれば、最小の個数を 1 にする。
サンプルコード２−１
int[] d = new int[]{1, 3, 4, 7};
int k = 8;
int[][] dp = new int[51][50001];
for(int i = 0; i < d.length; i++){
for(int t = 0; t <= 50000; t++){
dp[i + 1][t] = dp[i][t];
if(t - d[i] >= 0){ // 負の値のチェック
if(dp[i][t - d[i]] > 0){
if(dp[i][t] != 0){
// これより前の数字を使う場合と現在の数字を足す場合で比較
dp[i + 1][t] = Math.min(dp[i][t], dp[i][t - d[i]] + 1);
}
else{ // これまでの数字に現在の数字を足して表現できる
dp[i + 1][t] = dp[i][t - d[i]] + 1;
}
}
}
}
dp[i + 1][d[i]] = 1; // 現在の数字のみで表現できるなら 1 である
}
System.out.println(dp[d.length][k]);
３、例題３
問題
Ｎ個（最小１〜最大５０）の数字がある。
１つの数字は最小１〜最大１０００の範囲内にある。
また、それぞれの数字は重複することがない。
このときＮからいくつかの数字を取り出し、
足し算をして数字をちょうどＫ（最小１〜最大５００００）にしたい。
数字はどの数字を何度使っても良いものとする。
可能であるかどうかを判定せよ。
例えば２、７、９の３つの数字があり、
Ｋ＝１０であれば２＋２＋２＋２＋２＝１０なので可能である。
考え方
全探索するとＮ＝５０のときに５０＾５０の探索になり、
8881784197001252323389053344726562500000000000000000000000000000000000000000000000000 回
の探索を行う必要がありますが当然無理です。
メモ化を使うと５０×５００００＝２５０００００で探索できます。
サンプルコード３−１
int[] d = new int[]{10, 6, 300};
int k = 5555;
int[][] dp = new int[51][50001];
for(int i = 0; i < d.length; i++){
dp[i][d[i]] = 1;
for(int t = 0; t <= 50000; t++){
dp[i + 1][t] = dp[i][t]; // 過去の数字をコピー
if(t - d[i] >= 0){ // 負の値のチェック
if(dp[i + 1][t - d[i]] == 1){ // 現在の数字を積み重ねて足していく
dp[i + 1][t] = 1;
}
}
}
}
if(dp[d.length][k] == 1){
System.out.println("YES");
}
else{
System.out.println("NO");
}
４、例題４
問題
Ｎ個（最小１〜最大５０）の数字がある。
１つの数字は最小１〜最大１０００の範囲内にある。
また、それぞれの数字は重複することがある。
このときＮからちょうどＭ個（最小１〜最大Ｎ）の数字を取り出し、
足し算をして数字をちょうどＫ（０ではない）にしたい。
ただし、１つの数字は１回のみしか使えない。
可能であるかどうかを判定せよ。
例えば２、２、４、５、８の５つの数字があり、
Ｍ＝２、Ｋ＝８であるとき、
和が８なのは２＋２＋４＝８であるが数字の個数は３個である。
また、数字１つで８があるがこれも数字を１個しか使わない。
よって、数字２個で８を表現することはできない。
考え方
Ｍ＝２であるという縛りがあればＮが最大の５０であったとしても、
５０×４９＝２４５０の探索で解ける。
ただし、最悪の場合はＮ＝５０、Ｍ＝５０のときで、
探索は５０！になる。
５０！回の探索というと
30414093201713378043612608166064768844377641568960512000000000000 回
の探索を行うことなのでとてもではないが全探索を行えない。
探索を回せるのはせいぜいＭ＝４のときまででＭ＝５以降は無理である。
探索する発想として、
目的の数字になるには１つの数字、３つの数字で可能という状態を記録し、
１つ数字が増えるたびに更新していくというものがある。
１、３、４、７という４つの数字があった場合に、
メモをしていく過程を書いていきます。
１つ目の数字は 1 なので、
１つの数字で１を作ることは可能
２つ目の数字は 3 なので、
１つの数字で 3 を作ることは可能
２つの数字で 4 を作ることは可能
３つ目の数字は 4 なので、
１つの数字で 4 を作ることは可能
１つの数字で 3 を作ることは可能
２つの数字で 4 を作ることは可能
２つの数字で 7 を作ることは可能
３つの数字で 8 を作ることは可能
というふうに更新をしていきます。
さて、ここで問題が発生します。
３つ目の数字の段階で、
１つの数字でも２つの数字でも 4 を作ることができます。
「１つの数字」と「２つの数字」は両方とも必要な情報です。
この先も処理を行っていくのであれば複数の情報を保持する必要があります。
この情報をビットの状態を使って保持する工夫をします。
例えば、１つの文字でも２つの文字でも 4 を作ることができるなら、
dp[3][4] に 00000000000000000000000000000011（２進数） と記録します。
下位１ビットめと下位２ビットめが１になっています。
１であれば可能である、０であれば可能でないということです。
こうすることで３２個までの情報を保持することができます。
実際には５０個まで記録する必要があるので int ではなく long を使用します。
この方法だと２５０００００の探索で収まります。
サンプルコード４−１
int[] d = new int[]{1, 3, 4, 7};
int m = 2;
int k = 14;
long[][] dp = new long[51][50001];
for(int i = 0; i < d.length; i++){
for(int t = 0; t <= 50000; t++){
dp[i + 1][t] |= dp[i][t];
if(t - d[i] >= 0){ // 負の値のチェック
if(dp[i][t - d[i]] > 0L){ // これまでの数字に現在の数字を足して表現できる
dp[i + 1][t] |= (dp[i][t - d[i]] << 1);
}
}
}
dp[i + 1][d[i]] |= 1L; // 現在の値のみを使用する １回 を有効にする
}
if(((dp[d.length][k] >> (m - 1)) & 1L) == 1L){
System.out.println("YES");
}
else{
System.out.println("NO");
}
この方法ではＮ＝１００には対応できない。
対応するには１００のサイズの配列を用意する方法がある。
他には long を２つ使って対応する方法もある。
どちらの場合も処理を追加変更する必要がありメモリや速度への配慮が必要になる。
５、例題５
問題
Ｎ個（最小１〜最大５０）の数字がある。
１つの数字は最小１〜最大１０００の範囲内にある。
また、それぞれの数字は重複することはない。
このときＮから２つ以上の数字を選び昇順に並べたい。
昇順に並べる場合には条件があり、
２番目以降の数字はひとつ前の数字で割り切れなければならない。
並べ方は何通りあるか？
例えば１、２、３、９の４つの数字があったとき、
（１、２）（１、３）（１、９）（３、９）（１、３、９）
の５通りの並べ方がある。
考え方
単純に考えてみる。
まず昇順にソートする。
次に、数字を使うか使わないかでリストを作り、
作ったリストが割り切れる条件を満たすか調べる。
条件を満たすケースをカウントする。
この方法は ２＾５０ の探索が必要になる。
よって、この方法は採用できない。
次のように考えます。
例えば、数字が１、２、４、８の４つあったとする。
ここから表に書いて考えます
１つ目の選び方は以下のようです。
１｜ １ （数字の１を１つだけ選んで１通り）
２｜ １ （数字の２を１つだけ選んで１通り）
４｜ １ （数字の４を１つだけ選んで１通り）
８｜ １ （数字の８を１つだけ選んで１通り）
２つ目の選び方は以下のよう
１｜ １ ０（１の次に１は選べないので０通り）
２｜ １ １（１→２の１通り）
４｜ １ ２（１→４、２→４の２通り）
８｜ １ ３（１→８、２→８、４→８の３通り）
３つ目の選び方は以下のよう
１｜ １ ０ ０（１の次に１は選べないので０通り）
２｜ １ １ ０（２の次に２は選べないので０通り）
４｜ １ ２ １（（１→２の１通り）→４の１通り）
８｜ １ ３ ３（（１→２の１通り）→８、（１→４、２→４の２通り）→８の３通り）
４つ目の選び方は以下のよう
１｜ １ ０ ０ ０（１の次に１は選べないので０通り）
２｜ １ １ ０ ０（２の次に２は選べないので０通り）
４｜ １ ２ １ ０（３の次に３は選べないので０通り）
８｜ １ ３ ３ １（（（１→２の１通り）→４の１通り）→８の１通り）
数字の並べ方は表の数字を全部足せば全通りを調べたことになります。
よって １＋１＋１＋１＋２＋１＋１＋３＋３＋１＝１５ 通りになります。
問題では１つのみは選択できないので４つ引いて１５−４＝１１通りになります。
（この表を使えば３つの数字からなる列という条件があっても１＋３＝４通りがわかる）
この方法を使用するとＮ＝５０であっても
探索は５０×５０×５０＝１２５０００で終了します。
メモリも int 型で５０×５０＝２５００しか使用しません。
サンプルコード５−１
int[] d = new int[]{1, 2, 3, 9};
int[][] dp = new int[50][50];
for(int i = 0; i < d.length; i++){
dp[0][i] = 1;
}
for(int i = 0; i < d.length - 1; i++){
for(int t1 = 0; t1 < d.length; t1++){
for(int t2 = 0; t2 < d.length; t2++){
if(d[t1] < d[t2] && d[t2] % d[t1] == 0){
dp[i + 1][t2] += dp[i][t1];
}
}
}
}
int total = 0;
for(int i = 0; i < d.length; i++){
for(int t = 0; t < d.length; t++){
total += dp[i][t];
}
}
System.out.println(total - d.length);
６、例題６
問題
Ｎ個（最小１〜最大１０００）の数字がある。
１つの数字は最小１〜最大１００００００００の範囲内にある。
また、それぞれの数字は重複することがない。
このときＮから３つの数字を使って、
足し算をして数字をちょうどＫ（最小３〜最大３００００００００）にしたい。
使う数字は同じものを何回も使用できる。。
可能であるかどうかを判定せよ。
例えば、２００００００１、２０００００１３の２つの数字があったとする。
２００００００１と２０００００１３を２度使って３つの数字とする。
Ｋ＝６０００００２６であれば、
２００００００１＋２０００００１３＋２０００００１３＝６０００００２７
としても６０００００２６にはならないので可能ではない。
考え方
これまでの例題と違って数字が大きい。
ただし、選ぶ数字の個数は３個なのでここは制限が緩くなっている。
全探索する場合、
１０００×１０００×１０００＝１０００００００００でありできない。
メモ化を行う場合、
dp[300000000] という量のメモリを必要とするがこれもできない。
よって、他の方法を試す必要がある。
ここでは探索の回数の負荷の一部をメモリに負担させる方法を考えます。
２分探索という有名な方法を使用します。
まず３つの数字の検証方法を変えます。
問題の場合であれば、
if(n1 + n2 + n3 == k)
の検証を行うのが素直なやりかたですが、
if(n1 + n2 == k - n3)
で検証を行うことにします。
まず、k - n3 の結果を配列に入れます。
配列のありえる最大サイズは１０００です。
次に n1 と n2 で探索を行います。
そして n1 + n2 の結果が配列内に含まれるかどうかを調べます。
このとき２分探索を使用します。
２分探索を使用する前に配列をソートします。
java のソートはバブルソートなので nlogn ほどで終了します。
配列のサイズは１０００なのでこの場合の回数は３００ほどです。
ソートが終わったら２分探索を行います。
配列のサイズが１０００であれば探索回数は
計算すると２＾ｘ＝１０００なのでｘ＝１０ほどで終了します。
よって、探索回数は最大１０００×１０００×１０＝１０００００００です。
これくらいなら２秒以内に回せます。
サンプルコード６−１
int[] d = new int[]{1, 2, 3, 9};
int[] array = new int[1000];
int k = 20;
for(int i = 0; i < d.length; i++){
array[i] = k - d[i];
}
Arrays.sort(array);
int ans = 0;
for(int i = 0; i < d.length; i++){
for(int t = 0; t < d.length; t++){
if(Arrays.binarySearch(array, d[i] + d[t]) > 0){
ans = 1;
}
}
}
if(ans == 1){
System.out.println("YES");
}
else{
System.out.println("NO");
}
じつはこの方法は４つの数字の足し算にも対応します。
サンプルコード６−２
int[] d = new int[]{1, 2, 3, 9};
int[] array = new int[1000000];
int k = 22;
for(int i = 0; i < d.length; i++){
for(int t = 0; t < d.length; t++){
array[1000*i+t] = k - d[i] - d[t];
}
}
Arrays.sort(array);
int ans = 0;
for(int i = 0; i < d.length; i++){
for(int t = 0; t < d.length; t++){
if(Arrays.binarySearch(array, d[i] + d[t]) > 0){
ans = 1;
}
}
}
if(ans == 1){
System.out.println("YES");
}
else{
System.out.println("NO");
}
７、例題７
問題
Ｎ個（最小３〜最大５０）の数字がある。
１つの数字は最小１〜最大１００００００００の範囲内にある。
また、それぞれの数字は重複することはない。
ここで全ての数字を使って１つの輪を作る。
このとき隣り合う数字の差をとり絶対値をとる。
これらの絶対値の最大値が最小になる場合の値を求めよ。
例えば、３、６、９、１０の４つの数字があったとする。
以下のように輪にしてみる。
３ １０
６ ９
このとき差の絶対値は ３、３、１、７ で最大値は７である。
では、次のように輪にしてみる。
３ ９
６ １０
このとき差の絶対値は ３、４、１、６ で最大値は６である。
この問題の場合では最小となる最大値は６である。
考え方
全探索はＮ＝５０のとき４９！であり無理である。
ここでも例題６と同じく２分探索を使用する。
まず、あらゆる数字に対して答えが １００００００００ 以下になるのはわかる。
しかし、答えが ５０００００００ 以下かどうかはわからない。
例えば、１、１０００、６０００００００のときは ５０００００００ を上回る。
３、４２、２０１ であれば ５０００００００ を下回るであろう。
よって、５０００００００ を超えるようなら ７５００００００ を試す。
逆に、５０００００００ 以下なら ２５００００００ を試す。
これを繰り返していくと最終的には１つの値に行き着く。
最初の数値が １００００００００ であれば探索は２７回程度で終わる。
サンプルコードでは条件を満たすかのチェックに５０×５０の探索を用いているので、
すべての探索には５０×５０×２７＝６７５００の探索で済む。
条件を満たすかについては、まず最小値の位置を固定する。
次に、条件を満たすように次の数字を選んでいくが、できるだけ大きい数字を選ぶ。
条件を満たす数字が選べなかったら輪にする数字が用意できないことになる。
もし輪にするための数字が用意できたらその最後の数字は可能な限り小さな数字である。
この数字が最初の数字につながれば輪ができるといえる。
サンプルコード７−１
int[] d = new int[]{3, 6, 9, 10};
int min = 1;
int max = 100000000;
Arrays.sort(d);
while(min < max){
int mid = (max + min) / 2;
int index = 0;
int r_num = d[index];
Set<Integer> set = new HashSet<Integer>();
set.add(0);
for(int i = 0; i < d.length - 1; i++){
index = 0;
for(int t = 0; t < d.length; t++){
if(set.contains(t) == false){
if(Math.abs(r_num - d[t]) <= mid){
if(d[index] < d[t]){
index = t;
}
}
}
}
set.add(index); // いちど使った数字は使えないようにする
r_num = d[index]; // 現在の数字を更新
}
// すべての要素を使い かつ 最初と最後がつながるか をチェック
if(set.size() == d.length && d[index] - d[0] <= mid){
max = mid;
}
else{
min = mid + 1;
}
}
System.out.println(min);
８、例題８
問題
１からＮ（最小１〜最大２０００００００００）までの数字がある。
この全ての数字について以下のことを調べる。
条件１：各桁に０〜９を１つずつ使う。ただし、最上位桁に０は使えない。
条件２：数字は ７ｎ＋１（ｎは自然数）の条件を満たす。
このとき条件１と条件２の両方を満たす数字はいくつあるか数えよ。
例えば、Ｎ＝２０００００００００のとき、
１６３７２４８５０９ は０〜９の数字をすべて使っている。
また、１６３７２４８５０９ は ７×２３３８９２６４４＋１ である。
よって、１６３７２４８５０９ を条件を満たすものとして数える。
考え方
全探索であれば、１から２０００００００００で探索を行い、
すべての桁の数字を調べて７ｎ＋１の条件を確認する方法がある。
少し考えると条件１を満たす最小の数字は １０２３４５６７８９ であるから、
１０２３４５６７８９ より小さい数字については考えなくても良いことがわかる。
また、条件１を満たす最大の数値は １９８７６５４３２０ である。
ただ、１０２３４５６７８９ から探索を開始したとしても、
１９８７６５４３２０−１０２３４５６７８９＋１＝９６４１９７５３２ 回
の探索回数が必要であり探索は回らない。
ここで最上位の桁の数字は１だとわかっているので、
あとは０と２〜９の数字を重複しないように並べて検証することを考えます。
数字が９個あるので探索回数は９！です。
９！というと ３６２８８０ 回の探索のことです。
これなら探索が回せそうです。
順列は１０！が ３６２８８００ で １１！が ３９９１６８００ になります。
１０！くらいまでなら探索が回せそうですね。
以下のサンプルコード８−１は再帰関数で順列を生成しています。
サンプルコード８−１
// n >= 1000000000 && n <= 2000000000 であること
private int f(int n, int num, int mask){
if(mask == 0x03FF){
num += 1000000000; // 順列ができたら頭に１をつける
if(num <= n && (num - 1) % 7 == 0){
System.out.println(num);
return 1;
}
return 0;
}
int count = 0;
// 各桁が０と２〜９からなる数字を作成する
for(int i = 0; i < 10; i++){
if(((mask >> i) & 1) == 1)continue;
count += f(n, num * 10 + i, mask | (1 << i));
}
return count;
}
サンプルコード８−２ではサンプルコード８−１の再帰関数を使用する。
サンプルコード８−２
int n = 2000000000;
if(n < 1000000000){ // 1000000000 より小さい数字は問題の条件を満たさない
System.out.println(0);
}
else{
System.out.println(f(n, 0, 0x02)); // １は順列作成の要素から省く
}
９、例題９
問題
Ｎ個（最小１〜最大５００００）の数字が１列に並んでいる。
１つの数字は最小１〜最大１００００の範囲内にある。
また、それぞれの数字は重複することがある。
このときこの列から隣り合ういくつかの数字を取り出す。
取り出したすべての数字の和がＫ（最小１〜最大５００００００００）になるとき、
取り出す数字の個数を求めよ。
すべての数字を選んでもＫにならない場合は０を答えとする。
例えば、３、１０、３、５の５つの数字があったとする。
Ｋ＝１６のとき、
数字を１つ選ぶやりかたは３、１０、３、５の４通りだが１６にはならない。
数字を２つ選ぶやりかたは（３、１０）（１０、３）（３、５）の３通りだが、
和が１３、１３、８でありいずれも１６にはならない。
数字を３つ選ぶやりかたは（３、１０、３）（１０、３、５）の２通り。
この場合は和が１６、１８で１６のとき条件を満たす。
数字を４つ選ぶやり方は（３、１０、３、５）の１通り。
和は２１となり１６にはならない。
このとき（３、１０、３）を選ぶやりかたが和で１６になる。。
考え方
数字の個数が最大の５００００のとき全探索は
５００００×（５００００＋１）／２＝１２５００２５０００ になる。
ここでは数字が１列で動かせず隣り合った範囲でしか数字を選べないことを利用する。
まず左端と右端を用意し共に０とする。
右端を１つずつ移動し合計に右端で増えたぶんを加算する。
もし合計がＫであれば、
右端から左端までの要素数を数えて記録する。
続けてもし合計がＫ以上であれば、
左端を１つ右に動かし合計から左端で減ったぶんを減算する。
再び右端を１つずつ移動する操作に戻る。
この操作を最右端まで行う。
なんと探索は数字の個数が最大の５００００であれば５００００回程度で終わる。
サンプルコード９−１
int[] d = new int[]{3, 10, 3, 5};
int k = 16;
int ans = Integer.MAX_VALUE;
int sum = 0;
int left = 0, right = 0;
while(true){
while(right < d.length && sum < k){
sum += d[right];
right++;
}
if(sum < k){
break;
}
if(sum == k){
ans = Math.min(ans, right - left);
}
sum -= d[left];
left++;
}
if(ans == Integer.MAX_VALUE){
System.out.println(0);
}
else{
System.out.println(ans);
}
１０、例題１０
問題
Ｎ個（最小１〜最大５０）の数字が書かれたマスが１列に並んでいる。
１つの数字は最小１〜最大４９の範囲にある。
また、それぞれの数字は重複することがある。
自分は最初にいちばん左端のマスに立っている。
１回の動作でできることは
右に１マス進む、左に１マス進む、右に現在のマスの数字の数だけ進む、
のいずれかを好きなように選択できる。
ただし、移動する際に左右の端を出ることはできない。
最小の回数でいちばん右端のマスまで移動したい。
最小の回数を求めよ。
例えば、「４、１、３、６、３、５、２、４、１、７」のマスがあったとする。
右端に移動するのであるから数字の数だけ移動すれば良いようであるが、
４→３→ と４つ右へ移動、３つ右へ移動とすると、
次の４は右端を越えてしまうので１しか進めない。
１る右のマスは１なので１つ右に移動して右端に到着する。
よって ４→３→４→１→７ の４回移動になる。
しかし、３から左に１つ戻れば４→３→６→７ と移動して３回である。
考え方
単純に考えてみる。
最初のマスで右に１進むかマスの数字だけ進むことの両方を考える。
１回をカウントし、現在のマスにフラグを立てる。
次のマスでは１進むかマスの数字だけ進むか１つ戻るか考える。
１つ前のマスにフラグが立っていれば戻ることはできない。
すべての試行をおこなったら１回をカウントしマスにフラグを立てる。
この操作を繰り返して右端に到着したときの回数の最小を答えとする。
サンプルコード１０−１に探索用に再帰関数を書いてみた。
サンプル１０−２からこの関数を使っている。
さて、この場合マスの数字がすべて １ で３０個あったとしよう。
このときの探索数は２＾２９になる。
これは５億ほどの探索になるので探索は無理だといえる。
そこで探索方法を次のように考える。
スタート地点を０とする。
次に１回で行ける地点に１を記録する。
スタート地点から行けるすべての地点へ分身して移動する。
このとき行ける地点の数字が最小のものから次の操作を行う。
この場合は数字はすべて１のはずだから順番はどれでも良い。
すでに行った地点は除いて次に行けるすべての地点に
現在の地点の数字＋１ を記録する。
もし記録する地点の数字がすでにあったなら、
すでにある数字と現在の地点の数字＋１で小さいほうを記録する。
次に、すでに行った地点は除いて現在の地点から行ける地点へ分身して移動する。
行ける地点の数字が最小のものから上と同様の操作を行う。
このとき現在の数字は１の場合と２の場合があると思うので、
１の場合を２の場合より優先して先に行う必要がある。
これをひたすら繰り返す。
全操作が終了したときにその地点の数値がその地点へ行く最短回数である。
この方法をダイクストラ法という。
ある地点からある地点へいく最短距離を求めることができる。
この方法はたとえば地点間の距離が違っても対応できる。
ただし、地点間の数値がマイナスであるとうまく動作しない。
マイナスがある場合はベルマンフォード法を使う。
サンプルコード１０ー３ではデータ構造にグラフを使って
ダイクストラ法で最短経路を求めています。
この方法ではマスの数字がすべて １ で３０個 の場合、
１０００回ほどの探索で答えを出しました。
サンプルコード１０−１
int min = Integer.MAX_VALUE;
void f(int[] d, int[] flag, int index, int count){
if(index < 0 || index >= d.length)return;
if(index == d.length - 1){
min = Math.min(min, count);
return;
}
int[] f = new int[flag.length];
for(int i = 0; i < f.length; i++){
f[i] = flag[i];
}
f[index] = 1;
f(d, f, index + 1, count + 1);
f(d, f, index + d[index], count + 1);
if(index != 0 && f[index - 1] != 1){
f(d, f, index - 1, count + 1);
}
}
サンプルコード１０−２
int[] d = new int[]{4, 1, 3, 6, 3, 5, 2, 4, 1, 7};
int[] flag = new int[d.length];
f(d, flag, 0, 0);
System.out.println(min);
サンプルコード１０−３
int[] d = new int[]{4, 1, 3, 6, 3, 5, 2, 4, 1, 7};
int[] flag = new int[d.length]; // その地点へ行ったかどうかのフラグ
int[] ans = new int[d.length]; // その地点へ行く最小回数が入る
Arrays.fill(ans, Integer.MAX_VALUE);
ArrayList<ArrayList<Integer>> l = new ArrayList<ArrayList<Integer>>();
// グラフを作る
for(int i = 0; i < d.length; i++){
l.add(new ArrayList<Integer>());
if(i > 0){
l.get(i).add(i - 1);
}
if(i < d.length - 1){
l.get(i).add(i + 1);
}
if(i < d.length - d[i]){
l.get(i).add(i + d[i]);
}
}
ans[0] = 0; // スタート地点を０にする
while(true){
int r = -1;
// まだ行っていない場所で回数が最小の場所を検索
for(int i = 0; i < d.length; i++){
if(flag[i] == 0 && ((r == -1) || (ans[i] < ans[r]))){
r = i;
}
}
if(r == -1)break;
flag[r] = 1;
// そのままの場合と回り道した場合の小さいほうを採用する
for(int i = 0; i < l.get(r).size(); i++){
ans[l.get(r).get(i)] = Math.min(ans[l.get(r).get(i)], ans[r] + 1);
}
}
System.out.println(ans[d.length - 1]);
１１、例題１１
問題
Ｎ個（最小１〜最大５０）の数字がある。
１つの数字は最小１〜最大１０００の範囲内にある。
また、それぞれの数字は重複することがない。
ここから２つの数字をとりだして次の条件をチェックする。
条件：２つの数字の和が素数である。
この条件を満たす２つの数の組み合わせ数を最大にしたい。
ただし、このとき同じ数は２回使えない。
このときの最大の組み合わせ数を求めよ。
例えば、１、２、４、５、７、１０、１１ の７つの数字がある。
１＋１０＝１１、２＋１１＝１３、４＋７＝１１
このとき最大の組み合わせは３個できることになる。
考え方
数字が５０個であれば５０！で組み合わせを探索できる。
ただし、５０！の探索は回らない。
まず、次のように考える。
最小の和は１＋２ のとき３である。
よって、最小の素数は３であり２にはならない。
よって、和でできる素数は必ず奇数である。
したがって、和の組み合わせは必ず 奇数＋偶数 である。
（偶数＋偶数、奇数＋奇数はいずれも偶数になる。）
ただし、奇数＋偶数をすれば必ず素数になるわけではない。
よって、奇数群と偶数群で素数になる可能性のあるペアを登録する。
このとき最大数のペアを作ることを考えればよい。
では、最大数のペアを作るにはどうするか？
例えばＥ１、Ｅ２、Ｏ１、Ｏ２について次の関係が成り立つとする。
Ｅ１はＯ１、Ｏ２とペアを組める。
Ｅ２はＯ１のみとペアを組める。
線でつなぐと以下のようになる
Ｅ１ーＯ１
Ｘ
Ｅ２ Ｏ２
つなげることができるものからつないでいくと
Ｅ１とＯ１をつないだ時点でＥ２がペアを作れなくなる。
これではＥ１とＯ２、Ｅ２とＯ１という最大数のペアにならない。
このときに次のような操作が可能である。
「使用していない左→右への移動」と「使用している左→右の移動の逆行」
によって左から右へ移動する新しいルートが存在する場合、
すでにできているペアを解消して新たなペアに更新することができる。
上の例でやってみる。
Ｅ１ーＯ１
Ｘ
Ｅ２ Ｏ２
まず、Ｅ１→Ｏ１はペアを作ることができる。
次に、Ｅ２→Ｏ１は使用していない左→右の移動なので移動できる。
Ｏ１→Ｅ１は使用しているＥ１→Ｏ１の逆行なので移動できる。
Ｅ１→Ｏ２は使用していない左→右の移動なので移動できる。
よって、Ｅ２→Ｏ１→Ｅ１→Ｏ２の移動が可能であり、
このときペアの成立を反転させる。
すなわち、Ｅ２とＯ２がペアとなり、Ｏ１とＥ１がペア解消、
また、Ｅ１とＯ２がペアになる。
この例は２つと２つのペアなので非常に単純であるが、
この方法はどんな複雑なペアマッチングの場合でも正しく動作する。
サンプルコード１１−１は素数判定の関数
サンプルコード１１−２はマッチング用の再帰関数
サンプルコード１１−３はグラフの作成と再帰関数の呼び出し
サンプルコード１１−２は
互いにマッチング相手がいなければマッチングし、
マッチング相手がいれば逆行の探索を繰り返し、
逆行の試行が可能であれば再マッチングを行う。
１つの再帰関数で２つの
サンプルコード１１−１
// n が素数であれば 1 を返す そうでなければ 0 を返す
private int isPrime(int n){
int i;
if(n < 2){
return 0;
}
else if(n == 2){
return 1;
}
if(n % 2 == 0){
return 0;
}
for(i = 3; i * i <= n; i += 2){
if(n % i == 0){
return 0;
}
}
return 1;
}
サンプルコード１１−２
ArrayList<ArrayList<Integer>> l;
int[] match; // マッチング相手を記録する なければ -1
int[] flag; // すでに調べたかどうかを記録するフラグ
int f(int v){
flag[v] = 1;
for(int i = 0; i < l.get(v).size(); i++){
int d = l.get(v).get(i); // v の相手を d とする
int dm = match[d]; // d のマッチング状態を dm とする
if(dm == -1 || (flag[dm] == 0 && f(dm) == 1)){
match[v] = d;
match[d] = v;
return 1;
}
}
return 0;
}
サンプルコード１１−３
int[] d = new int[]{1, 2, 4, 5, 7, 10, 11};
flag = new int[d.length];
match = new int[d.length];
l = new ArrayList<ArrayList<Integer>>();
Arrays.fill(match, -1);
for(int i = 0; i < d.length; i++){
l.add(new ArrayList<Integer>());
for(int t = 0; t < d.length; t++){
if(i == t)continue;
if(isPrime(d[i] + d[t]) == 1){
l.get(i).add(t);
}
}
}
int count = 0;
for(int i = 0; i < d.length; i++){
if(d[i] % 2 == 0 && match[i] == -1){
Arrays.fill(flag, 0);
count += f(i);
}
}
System.out.println(count);
