Тэмцээний дүнг толилуулахад дараах байдалтай байна. Эхний гурван байранд орсон Хасан, 102662( хэн бэ?), Наранбаяр нарт баяр хүргэе. Нээрээ тоон нэртэй хүмүүс нэрээ мэдэгдвэл сайн байна шүү.
Дараа дараагийхаа тэмцээнийг мөн Хонгор бид 2 хамтарч ХакерРанк дээрээ хийнэ. Энэ жил Олон Улсын Мэдээлэл Зүйн Олимпиадад явна гэж бодож байгаа хүүхдүүд бэлтгэлээ сайн хийгээрэйдээ гэж хэлээд тус тусыхаа бодлогуудын анализыг сонирхуулъя.
Бэлэг
Хэрэв хөнгөлөлтийн карт байхгүй байсан бол бодолт хамгийн бага Z+U-г сонгох замаар бодогдоно. Хөнгөлөлтийн картыг ямар бэлгэндээр хэрэглэх вэ гэдэг нь асуудал. Нийт 1000-н бэлэг байгаа учираас хөнгөлөлтийн картыг бүх бэлэг дээр ашиглаж үзээд дээрх GREEDY санаагаар бусад бэлгээ сонгоод явж болно. Энэ бодолт O(N^2) учир хангалттай амжина. Дасгал болгох үүднээс энэ алгоритмаа цааш нь хөгжүүлээд O(N*logN) болгох асуудлыг уншигчид үлдээе.
Нэвтрэлт
Энэ бодлогыг бодох магадгүй хамгийн амархан бодолт Рекурс байх. Боломжит бүх илэрхийллүүдыг, замуудыг, шалгана. Рекурсын дуудалт болгон дээр нээлттэй хаалтуудын тоо '(', хаалттай хаалтуудын тоо ')' -г тоолоод явна. Гэхдээ Рекурс хийх дараалал нь хаалттай хаалт таарах л юм бол нээлттэй хаалтыг тоолж дуусаад хаалттай хаалтыг тоолж эхлэнэ. Ямар нэгэн зам шалгаж дуусна гэдэг маань хэрэв нээлттай хаалтны тоо, хаалттай хаалтны тоотой тэнцэх үед л дуусах юм. Өөр нэмж болох сайжруулалт нь нээлттэй хаалтнуудыг тоолцон байхад мэдээж үүсэж болох илэрхийллийн урт нь 2*(нээлттэй хаалтны тоо) байх ба энэ тоо маань бидний өмнө олсон хариунаас их байвал л бид шалгаж болох юм, эсрэг тохиолдолд угийн бага урттай илэрхийллийг байгаа эсэхийг шалгах нь илүү үйлдэл билээ.
Хамгийн богино зам
Энэ бодлого ойлгомжтой дурын бүх хоёр хотуудын хоорондахь богино замаас хамгийн уртыг нь олох байсан. Үүнийг графын Диаметр гэж нэрлэдэг ба мод биш бол үндсэн 2 алгоритм байгаа. Floyd Warshall O(N^3), мөн бүх хотуудаас Дижкстра хийх O(N^2*LogN). Сүүлийн алгоритм дээр Heap өгөгдлийн бүтэцийн тусламжтай хийдэг билээ. Энэ удаад уг нь 2 дахь алгоритмаар хийлгэх санаатай бодлогоо тавьсан боловч зарим Floyd бичсэн оролцогчидын бодолт давж байна лээ :), баяр хүргэе :).
Хачин улс
Ерөнхийдөө DFS хийгээд шалгаад явж болно. Гэхдээ илүү хялбар бодолт нь орой болгон руу яг нэг ирмэг чиглэсэн эсэхийг шалгах юм. Үүнийг хялбархан батлаж болно.
27
Энэ бодлого нь хялбархан динамик програмчлалын бодлого юм. N маань илүү том байж болох байсан ч 10^12 гэж өгсөн нь төөрөгдүүлэх бус олон төрлийн бодолт харахыг хүссэнд оршино. f(A,B,C)-р A оронтой, 27-д хуваагдахад B үлдэгдэл өгдөг, N-н эхний A оронгоос C зайтай хичнээн тоо байгааг тэмдэглэвэл манай бодлогын хариу SUM(f(length(N),0,C)) {c=0..K} байх болно.
Динамик програмчлалын бодлогууд дээр ямар нэгэн төлвийн утгыг олохдоо түүнээс ялгаатай өөр төлвүүдийн утгыг ашиглаж олдог (нийлбэр, ялгавар, min, max гэх мэт). Жишээ нь фибоначийн тоог олохдоо f(n) = f(n-1) + f(n-2) гэж олдог шүү дээ. Үүний оронд ямар нэгэн олдсон байгаа утга нь өөр ямар төлвүүдэд ашиглагдахаа мэдэж байгаа гэж үзээд f(n+2) += f(n); f(n+1) += f(n); гэж бичиж болно.
Уг бодлогыг бичихэд сүүлийн арга нь арай илүү тохиромжтой. Бид ямар нэгэн A, B, C-н хувьд f(A,B,C)-н утгыг мэдэж байгаа гэж үзээд уг төлөвт багтах тооны ард X цифрийг залгаж бичвэл дараагийн төлөв нь (A+1,(B*10+X)%27,C+|X-dA+1|) болно. Энэ хамаарлаас бид дараах кодыг бичиж чадна.
long long dp[13][27][120];
int main() {
int T;
scanf("%d", &T);
while (T--) {
string s;
int k;
cin >> s >> k;
memset(dp, 0, sizeof(dp));
dp[0][0][0] = 1;
for (int a = 0; a < s.size(); a++)
for (int b = 0; b < 27; b++)
for (int c = 0; c <= k; c++) {
if (a == 1 && b == 0) continue;
for (int x = 0; x < 10; x++)
dp[a + 1][(b * 10 + x) % 27][c + ABS(x - (s[a] - '0'))] += dp[a][b][c];
}
long long res = 0;
for (int i = 0; i <= k; i++)
res += dp[s.size()][0][i];
cout << res << endl;
}
return 0;
}
