| 作成日 | 2025/06/09 |
| 最終更新日 | 2025/06/11 |
自身の提出でdfsを含みACを取っているもの、かつ主催者解説でDFSが取り上げられていないものを振り返ります。
基本的に脳筋解法になります。全探索しようとしてるししょうがないね。
問題は こちら 。
提出コードは こちら 。
今作るならまだ走ってないランナーを管理してDFSしますね。N人のランナー見て走ったかどうか管理するのは効率が悪い気がします。
さて、本題に入って計算量の見積もりです。
雑に全探索する場合、襷渡しをするとき全てのランナーについて見るので、O(N^N)になってしまいます。
ここから、走ったランナーに襷を渡すパターンを刈ります。
今までに走ったランナーがk人だった場合、襷を渡せる残りのランナーはN-k人になります。kが0~N-1の範囲で動き、そのパターン数をかければよいので、
となり、N!通りとなります。N^Nと比べると大分探索範囲が減りました。N!通りの探索は想定解法と同じ探索量です。
∏は総積記号です。ギリシャ文字πの大文字でProductから来ています[1]。
今回の設定では襷を渡せない人の組み合わせがM組存在します。これを含めた計算量の見積もりをしてみましょう。
1人当たり 人に渡せないことになります。
M組のペアに登場する人数が2M人いて、それをN人に分配して平均を出しています。
1人目から2人目に襷を渡せない確率は残り人数がN-1人なので、 です。
簡単化のために、この確率で残りの襷も渡せると考えましょう。襷渡しはN-1回行われるのでの確率をN-1回乗じればよいです。
よって見積もった探索量は、
となります。
Mが大きくなればなるほど渡せない組み合わせが増えて探索量が減る形になってるのであってそうです。
平均人数で見て組み立てたので実際の探索量は違います。
あとは途中まで走った時点で最速タイムより遅かった場合、その組み合わせは最後まで見る必要がないのでもう少しだけ削れますね。
振り返りのついでに追加課題のM<=18の場合について考えます。
残念ながら先ほどのコードでは、N=18にしたときに探索範囲がとんでもないことになってしまうのでTLEです。Mが最大値の半数としても、log(18!)-18log(2)≒10となり10の10乗以上の探索範囲が出てきます。
全員の全区間のタイムが950以上だとするとスコアによる枝刈りも全然できないのでまったく歯が立ちません。最後の1人まで見ないとスコアの比較ができないからです。
問題はこちら。
提出コードはこちら。
雑に全探索を考えると、N個の点をK個のグループに分ければいいので、K^Nです。この全ての場合分けに対して距離を見れば題意を満たせます。
しかしK<N≤15なので、最大14^15となり当然TLEです。ここから枝刈りを行います。
まずK個のグループに分ける行為ですが、都度K個のグループを見る必要はありません。1つ目の点は必ず自身のみのグループだけに属し、2つ目の点は1つ目の点と同居させるか、別居させるかの2通りしかありません。2つの点が1つ目の点と別居していた場合、3つ目の点の入れ先は3パターンになります。
これを踏まえて最後の15個目の点まで計算するとどれだけ多くても15!通りですみます。14^15から大分落とせました。……でもまだまだTLEです。
この問題で大事なのはK個のグループを作る必要があるということです。先ほどの見積もりではK個のグループが作れない点の分け方、例えば全ての点がグループ1に入っているパターンが生まれてしまいます。これを弾きましょう。
15個の点を14個のグループに分けるには、あるグループに3個以上の点が入ってはいけません。この状態になってしまうと、12個の点を13個のグループに分けなくてはなりませんからね。これは不可能です。
それ以降の点をどう割り振っても条件を満たさない場合に探索を打ち切ることで探索量を大幅に落とせます。こうすることで条件を満たすグループ分けだけを確認することができます。提出コードの63行目がこれに当たります。
ここまでが枝刈りでいけそうという話で、 ここからは実際のパターン数の計算を行います。
K=14 N=15の場合、同居する点1組を決めれば他は自動的に決まるので、15C2で105通りです。全探索できる範囲です。
N=15 K=12で考えましょう。 この場合同居させる必要がある点は3個です。グループ分けのパターンは以下の3通りです。
1つ目は15C2*13C2*11C2/6です。2個とる操作を3回行うのでCが3つです。3個のものを並べる方法が3!なので6で割るとよいはずです。12,34,56と取り出したパターンの並び替えは6通りありますからね(例えば34,12,56)。これは75,075通りです。
2つ目は15C2*13C3です。2個選んだ後に3個選びます。これは並び変えが発生せず、30,030通りです。逆でも計算結果は同じです。結局15P5/2!/3!なので。
3つ目は15C4なので1,365通りです。
当初の雑の全探索では13^15通りですが、分配が成功するパターンだけ見ると大体10^5ですみます。充分高速です。
見積もりの簡略化に挑戦してみます。
KとNの差が3なので、別の点と同居させるべき点が3個あります。この3個の点を15個から取り出す方法は15C3で455通りです。
選択した点を分ける方法は以下の3通りです。
3個のグループに分ける方法はただ1通りです。
123の点を最初に取り出していたとき、残りの4~15の点と組ませることができます。組ませる残りの点を順番を気にして取り出すと12P3=1320通りになります。
後者をPにする理由は123を最初に3個取り出していたときに、(1,11)(2,12)(3,10)をそれぞれペアにした場合と、(1,12)(2,11)(3,10)をペアにしたときを区別したいからです。
2個のグループに分ける方法は、全てのグループに前もって1個入れておいて残り1個をどこかに入れればいいので、2C1で2通りです。
この点のペアと組み合わせ残りの点の選び方は12P2で132通りです。
1つのグループに分ける方法は当然1通り。残りの点からこのグループと組ませる点を1つ決めるのでただ12通りです。
3個の点をピックして、残りの点を組ませる方法が上記の和なので、探索量は次の通りです。
455*(1320+2*132+12)=726,180
大分膨らみましたが、場合分けの数を減らせることと、上限として用いるのでまぁ目をつむりましょう。
これでK=8の場合を考えます。重複させる点を選ぶ方法は15C7なので6,435通りです。
| グループ数 | 分ける点の数 | 点の分け方数 | 組ませる点 |
| 1 | 0 | 1 | 8P1 |
| 2 | 6 | 7C1 | 8P2 |
| 3 | 5 | 7C2 | 8P3 |
| 4 | 4 | 7C3 | 8P4 |
| 5 | 3 | 7C4 | 8P5 |
| 6 | 2 | 7C5 | 8P6 |
| 7 | 1 | 7C6 | 8P7 |
上記の和と積を取ると10の9乗を超えます。……ダメですね。上限の設定が甘かった様です。目をつむってはいけませんでした。
これは順番を気にして取り出した結果、重複して数えている部分があるからです。「123を選んで456と組み合わせる場合」と、「124と選んで356と組み合わせる場合」で(1,5)(2,6)(3,4)と(1,5)(2,6)(4,3)が重複します。
K=12のときに丁寧に導出した式と、雑にCに落とした式を比較してみます。これは複数要素が入ったグループ数が3個の場合のパターン数を示します。
実に15倍近く余計に数えています。こりゃ使い物になりませんね。
雑な上限はあんまり意味がないことがわかったので、諦めて列挙します。急がば回れでした。
| グループサイズ | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | パターン数 |
| 各グループの数 | 6 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 5,005 |
| 5 | 1 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 135,135 | |
| 5 | 0 | 1 | 0 | 0 | 0 | 1 | 0 | 0 | 360,360 | |
| 5 | 0 | 0 | 1 | 0 | 1 | 0 | 0 | 0 | 630,630 | |
| 5 | 0 | 0 | 0 | 2 | 0 | 0 | 0 | 0 | 378,378 | |
| 4 | 2 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 1,351,350 | |
| 4 | 1 | 1 | 0 | 0 | 1 | 0 | 0 | 0 | 6,306,300 | |
| 4 | 1 | 0 | 1 | 1 | 0 | 0 | 0 | 0 | 9,459,450 | |
| 4 | 0 | 2 | 0 | 1 | 0 | 0 | 0 | 0 | 6,306,300 | |
| 4 | 0 | 1 | 2 | 0 | 0 | 0 | 0 | 0 | 7,882,875 | |
| 3 | 3 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 6,306,300 | |
| 3 | 2 | 1 | 0 | 1 | 0 | 0 | 0 | 0 | 37,837,800 | |
| 3 | 2 | 0 | 2 | 0 | 0 | 0 | 0 | 0 | 23,648,625 | |
| 3 | 1 | 2 | 1 | 0 | 0 | 0 | 0 | 0 | 63,063,000 | |
| 3 | 0 | 4 | 0 | 0 | 0 | 0 | 0 | 0 | 7,007,000 | |
| 2 | 4 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 14,189,175 | |
| 2 | 3 | 1 | 1 | 0 | 0 | 0 | 0 | 0 | 94,594,500 | |
| 2 | 2 | 3 | 0 | 0 | 0 | 0 | 0 | 0 | 63,063,000 | |
| 1 | 5 | 0 | 1 | 0 | 0 | 0 | 0 | 0 | 14,189,175 | |
| 1 | 4 | 2 | 0 | 0 | 0 | 0 | 0 | 0 | 47,297,250 | |
| 0 | 6 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 4,729,725 |
(4,0,2,0,1,0,0,0,0)の行はサイズ1のグループが4つ、サイズ3のグループが2つ、サイズ5のグループが1つあることを示します。この列のパターン数は となります。分母の真ん中の括弧は3個選ぶ組み合わせが2つあるので3!を2回、この3個のペアが重複する可能性があるので2!で割ります。
これに基づいて総和を取ると408,741,333となりました。4×10^8なのでギリギリすぎます。よく通りましたね。……見積もり間違ってるのかな?
N=15に対してKを変更した場合の値は次の表の通りです。
| K | パターン数 |
| 2 | 16,383 |
| 3 | 2,375,101 |
| 4 | 42,355,950 |
| 5 | 210,766,920 |
| 6 | 420,693,273 |
| 7 | 408,741,333 |
| 8 | 216,627,840 |
| 9 | 67,128,490 |
| 10 | 12,662,650 |
| 11 | 1,479,478 |
| 12 | 106,470 |
| 13 | 4,550 |
| 14 | 105 |
K=6の時が最大になるんですね。7か8だろうと予想していたので意外でした。見積もりの精度上げる能力が欲しいですね。
場合分けをするだけでこれだけ必要で、実際の提出コードは都度N個の点を見て距離を求めているのでこれのN倍以上かかります。
……TLEしてますね。handがないのでランダムしかなくて救われてます？この感じならN=15かつ5≤K≤8以外なら通せます。入力を見たい……。見積もりが間違っている可能性も捨てきれないので……。
ある集合の最大距離を事前に計算しておけばO(1) で求まるので、適切に設計していれば間に合うとも言えそうです。事前計算は愚直に立っているビットを見ても2^N×N^2ですみますし。
まぁ全探索ばっかりうまくなってもしょうがないので、想定解法の勉強をした方が意味があります。この問題はこの辺でおわりにします。
見積もりもDFSでやりました。DFS使いすぎ。
これがどこか間違ってるのかな……。
#include <bits/stdc++.h>
using namespace std;
int N, K;
vector<int> digitNum;
long long ans = 0;
void dfs(
vector<int> num,
int min,
int sum)
{
if (N < sum)
{
return;
}
if (num.size() == K)
{
if (sum != N)
{
return;
}
vector<int> list(N - K + 1);
for (auto n : num)
{
list[n - 1]++;
}
cout << "<tr>";
long long tmp = 1;
for (int i = 1; i <= N; i++)
{
tmp *= (long long)i;
}
for (int i = 0; i < list.size(); i++)
{
int n = list[i];
cout << "<td>" << n << "</td>";
for (int j = 0; j < n; j++)
{
for (int k = 1; k <= i + 1; k++)
{
tmp /= (long long)k;
}
tmp /= (long long)(j + 1);
}
}
cout << "<td>" << tmp << "</td>";
ans += tmp;
cout << "</tr>" << endl;
return;
}
for (int i = min; i <= N - K + 1; i++)
{
auto v = num;
v.push_back(i);
dfs(
v,
i,
sum + i);
}
}
int main()
{
// 入力
cin >> N >> K;
// N = 15;
// for (K = 2; K <= 14; K++)
// {
ans = 0;
// 全探索
dfs(
vector<int>(0),
1,
0);
// cout << "<tr>";
// cout << "<td>" << K << "</td>" << "<td>" << ans << "</td>";
// cout << "</tr>";
// }
cout << ans << endl;
return 0;
}
問題はこちら。
提出コードはこちら。
全ての商品を買うか買わないかの2値で管理すると、2^Nとなります。そのうち買うを選んだ物がK個のパターン数を数え上げれば答えが出せます。
今回Nの最大値は40なので、2^10≒1000より、2^40≒1000^4=10^12となり、TLEです。
これはK個選択していない場合も全部数えてしまっていて、大幅に余計なパターンを見ているからです。
i個目の商品までみて、j個選んでいた場合、残りの商品の個数はN-i個です。選ぶ必要がある商品の数はK-j個なので、N-i = K - jになった段階で、全ての商品を選ぶ必要があるとして、パターン数を加算して探索を打ち切ります。金額が設定を超えた場合も打ち切って上げると早くなりますね。
N個の要素からK個を選択する方法は です。
N=40・K=20の時が最大で、137,846,528,820≒10^11となります。まぁ相変わらずTLEです。
さらなる高速化を狙います。
まず最初に、商品を高い順に並べ替えます。
そして先ほどと同様に商品を買うか買わないかを選びながらdfsを行います。
i個目の商品まででj個の商品を選択していた場合、追加で選ぶ必要がある商品の数はK - j個です。ここまではさっきと同じです。ここまでの金額の合計を としておきましょう。
残っている商品のうち、高い方からK - j個商品を選択してみます。このときの金額を とします。
この がP以下ならば、i+1以降の商品はどのように選んでもよいことになります。
N-i個の要素からK-j個の要素を選ぶ問題に帰結できるので、 を計算するだけで済みます。
探索しないで数を出せるので、計算量が落とせます。
前半の35個からP以下の値段の組み合わせを作って、最後の5個から2個を自由に選べるとすると、これだけで となり、10倍の高速化が図れます。
最後の10個から5個選べるとしたら252倍の高速化です。
高い方から20個選んでも条件を満たしていた場合、一度の探索で答えを出せるので爆速です。
手前からi個の商品を見て、j個選んだ時点で予算オーバー、または、手前からi個見て、j個選んで、残りのN-i個からK-j個をどう選んでも予算に収まる場合に枝刈りが行われます。
探索を打ち切るパターンが、これ以降は絶対に条件を満たす/満たさないの2パターンあるのが面白いですね。
ざっくり結論としては の高速化です。
厳密に考えると複雑すぎるのでこの辺でおしまいです。
問題はこちら。
提出コードはこちら。
他と合わせるために計算量考察と言っていますが、枝刈りはしていません。bit全探索の代わりにdfsを用いているだけですね。
ただ、自作コードは38ms、主催者解のコードは52msと実行時間に差があるので理由を考えてみましょう。
一番の違いは選択している列情報をサイズHで保持しているか、都度要素を追加するかです。配列サイズHを確保して、再起呼び出し実行した結果50msかかっているので間違いなさそうです(こちら)。
配列サイズをHで保持していると毎回Hかかりますが、選択したものしか保持しないようにすれば平均の大きさは、 となります。これは計算すると になります。
と の平均は です。コンビネーションの部分の値が同じでなので。
#include <bits/stdc++.h>
using namespace std;
int main()
{
int H = 16;
int cn = 1;
int ans = 0;
for (int i = 1; i <= H; i++)
{
cn *= (H - i + 1);
cn /= i;
cout << cn << endl;
ans += cn * i;
}
cout << (double)ans / (double)(1 << H) << endl;
return 0;
} 列についてのループの大きさがざっくり半分になることがわかりました。
半分まで落ちていないのは、配列の値を変更する操作と、配列の要素を削除する操作の分の差です。値を変えるだけなのと、要素を追加したり削除したりは前者の方が軽いですよね。あとは関数呼び出しの処理が多いことも影響がありそうです。
前者が130ms程度、後者が2500ms程度です。 今回の問題はH=8なのでループ回数は高々256で、誤差ですね。
#include <bits/stdc++.h>
#include <chrono>
#include <ctime>
using namespace std;
int main()
{
{
vector<int> a(1);
auto start = chrono::system_clock::now();
for (long long i = 0; i <= 100000000; i++)
{
a[0] = 1;
a[0] = 0;
}
auto end = chrono::system_clock::now();
auto sduration = start.time_since_epoch();
auto smills = chrono::duration_cast<chrono::milliseconds>(sduration).count();
auto eduration = end.time_since_epoch();
auto emills = chrono::duration_cast<chrono::milliseconds>(eduration).count();
cout << emills - smills << endl;
}
{
vector<int> a(1);
auto start = chrono::system_clock::now();
for (long long i = 0; i <= 100000000; i++)
{
a.push_back(1);
a.erase(--(a.end()));
}
auto end = chrono::system_clock::now();
auto sduration = start.time_since_epoch();
auto smills = chrono::duration_cast<chrono::milliseconds>(sduration).count();
auto eduration = end.time_since_epoch();
auto emills = chrono::duration_cast<chrono::milliseconds>(eduration).count();
cout << emills - smills << endl;
}
return 0;
}
以上、実行時間の差について考えてみました。枝刈りとは違いますが、考えることがあって楽しかったです。
以上、dfsで解いた問題について振り返りました。
意外と色んな問題で使える一方、全探索はやっぱり探索量が爆発するので使いどころには気を付けないとなりませんね。