برنامه نویسی در المپیاد کامپیوتر (۱)

بسم الله الرحمن الرحیماز آنجایی که سی‌پلاس‌پلاس تنها زبان برنامه نویسی المپیاد کامپیوتر است و درس برنامه نویسی یکی از ۴ درس اصلی المپیاد کامپیوتر (ترکیبیات، گراف، الگوریتم و برنامه‌نویسی) و البته کوچکترین آنهاست، امید است این پست و چند پستی که در آینده منتشر خواهد شد، اکثر مباحث و برخی نکات این درس را پوشش دهد.پیش نیاز های این مطلب:آشنایی اولیه با زبان سی پلاس پلاس و توابع و استراکت. (نیازی به یادگیری کلاس های سی‌پلاس‌پلاس در المپیاد کامپیوتر وجود ندارد.) میتونید از بخش سی‌پلاس‌پلاس w3schools کمک بگیرید.آشنایی با پشته، صف، لیست پیوندی، درخت جستجوی دودویی و هیپ.آشنایی با تحلیل اردر.بیتستوی برنامه نویسی مسابقاتی به جای اینکلود کردن همه چیزایی که لازم دارم بیتس میزنیم. ولی ممکنه یکم کامپایل رو کند بکنه.#include <bits/stdc++.h> using namespace std; int main() { cout << &quotSalam!&quot << endl; }وکتوروکتور یک دربرگیرنده (container) سریع و جالب برای نگهداری داده های ماست. اولین چالشی که در استفاده از آرایه بهش بر می‌خوریم این است که وقتی تعداد داده های ورودی‌مان را دقیق ندانیم یا اینکه بخواهیم یک دنباله عدد داشته باشیم که راحت بتوانیم یک عنصر به انتهایش اضافه کنیم یا یک عنصر را پاک کنیم، از وکتور استفاده می‌کنیم.وکتور یه داده ساختار پیاده شده در سی پلاس پلاس هستش که خواص آرایه رو شبیه سازی می‌کنه. ممکنه از لحاظ سرعت مزیت کمتری داشته باشه ولی برخی جاها به دلیل اهمیت سریع و تمیز کد زدن و یا داشتن آرایه با سایز متغیر، از وکتور استفاده می‌شود.تعریف یک وکتور:تعریف یک وکتور خیلی شبیه تعریف اینتیجر است. ولی داخل <> می‌توان هر دربرگیرنده، کلاس، وکتور و نوع داده های اولیه مثل int و double استفاده نمود.int x; vector<int> MyVec; vector<char> CharVec; vector<vector<int>> VecVec;برخی متد های تعریف شده برای وکتور: پوش بک:یه عنصر به انتهای دنباله اضافه می‌کند.MyVec.push_back(10);اپراتور قلاب (کروشه):دقیقا مثل آرایه می‌توانید به خونه با شماره‌اش دسترسی داشته باشید. (توجه کنید که اگر عدد بزرگتری مساوی اندازه وکتور را درون قلاب بگذارید ممکن است یک مکان نامربوطی از حافظه باشد که مثلا به یک اینتیجر دیگر یا وکتور دیگر یا ... اختصاص یافته باشد.) vec[0] = 1;پاپ بک:عنصر انتهایی رو حذف می‌کند.MyVec.pop_back();بک:عنصر انتهایی رو باز می‌گرداند.y = MyVec.back();سایز:تعداد عناصر موجود در وکتور رو خروجی می‌دهد.توجه کنید که متد size ما unsigned int برمی‌گرداند.MyVec.size();کلییِر:پاک کردن تمامی عناصر داخل وکتور. (سایز مساوی ۰ می‌شود.)نکته: کلییر در اکثر دربرگیرنده ها وجود دارد.MyVec.clear();ظرفیت:توی بخش بعدی باهاش آشنا می‌شویم.MyVec.capacity();پشت پرده وکتور چیست؟ْ! وکتور با کمک آرایه پیاده سازی شده و این آرایه یک مکان به عنوان سایز انتخاب شده است و تا زمانی که سایز ما به ظرفیت آرایه نرسیده ادامه پیدا می‌کند. وقتی سایز به به ظرفیت رسید، آرایه جدید به ظرفیت دو برابر از حافظه می‌گیرد و اعضا رو در آن کپی‌ می‌کند. مثلا پوش بک "مشابه" شبه‌کد زیر است:push_back(integer x): if arr.size == arr.capacity: arr_new := آرایه با سایز دو برابر arr_new[0 to size - 1] = arr[0 to size - 1] arr را آزاد کن از حافظه arr = arr_new arr[size] = x size := size + 1مثال:کد زیر رو اجرا کنید.#include <bits/stdc++.h> using namespace std; int main() { vector<int> vec; for (int i = 0; i < 10; i++) { vec.push_back(i); cout << vec.size() << ' ' << vec.capacity() << '\n'; } for (int i = 0; i < vec.size(); i++) cout << &quotvec[&quot << i << &quot] = &quot << vec[i] << '\n'; }ایتریتور:مفهومیست که در وکتور و سایر دربرگیرنده (container) های سی‌پلاس‌پلاس مطرح می‌شود و مشابه پوینتر برای آرایه است.تعریف ایتریتور:vector<int>::iterator it = vec.begin();توجه: vec.begin متدی است که ایتریتوری برمی‌گرداند که به خانه اول وکتور اشاره می‌کند. و vec.end هم خانه پایانی را نشان می‌دهد. (خانه پایانی همان خانه size ام و خانه اول همان خانه صفرم است.)نکته: اینجا می‌توان از کلیدواژه auto استفاده نمود.auto it = vec.begin();در کل عبارت auto x = y تقریبا به این معناست که تایپ x را مساوی تایپ y قرار بده. مثلا:auto x = 1; auto y = 1LL; auto z = y;در نتیجه x می‌شود int و y و z هم می‌شوند long long. نمی‌توان این کار را به شکل انجام داد:auto it; it = vec.begin();اپراتور ستاره:*it = 5;کد بالا، مشابه پوینتر، مقدار خانه‌ای که ایتریتور it به آن اشاره می‌کند را مساوی ۵ قرار می‌دهد.جمع با عدد در ایتریتور وکتور:برخی از ایتریتور ها، مثل ایتریتور وکتور را می‌توان با عدد ها جمع و تفریق کرد. vec.begin() + 5;اما ایتریتور دربرگیرنده های دیگر را می‌توان از کد زیر استفاده کرد:advance(it, 10);که شبیه اجرای it = it + 10 با ایتریتور وکتور هستش.و همچنین تکه کد زیر:it2 = next(it1, 5);که مشابه it2 = it1 + 5 هستش.در اکثر ایتریتور های دربرگیرنده های متفاوت می‌توان از ++ و - - هم استفاده کرد.it++;به تکه کد زیر توجه کنید.vector<int> vec; for (int i = 0; i < 10; i++) vec.push_back(i); for (auto it = vec.begin(); it != vec.end(); it++) cout << *it << ' ';نکته:دربرگیرنده stack هم در سی‌پلاس‌پلاس وجود دارد ولی با توجه به اینکه پیاده سازی مشابه وکتور با امکانات کمتر دارد، از وکتور استفاده می‌کنیم.درج:vec.insert(vec.begin() + i, 10); vec.insert(it, x);پارامتر های متد درج، یک ایتریتور و مقدار مورد نظر است.اردر خط اول را O(size - i) و خط دوم را نیز مشابها به تعداد عناصری که بعد از it* قرار گرفته اند، در نظر بگیرید. (به تمرین بعدی توجه کنید تا منظور از "در نظر بگیرید" را متوجه شوید.)بعد از خط اول، vec[i] مساوی با 10 می‌شود، و تمامی عناصر بعد از i یک واحد جلو می‌روند. (امتحان کنید تا بهتر متوجه شوید.)تمرین:ثابت کنید اگر در کدی n بار push_back و pop_back و clear اجرا شوند و وکتور اولیه تعریف شده خالی باشد، کد ما O(n) است.مثلا کد زیر همواره O(n) است حتی در بدترین حالت. vector<int> vec; for (int i = 0; i < n; i++) { int r = rand() % 3; if (r == 0 && vec.size() != 0) vec.pop_back(); if (r == 1) vec.push_back(1); if (r == 2) vec.clear(); }پس اگر هر کدام از این سه متد را O(1) در نظر بگیریم، به جوابی مشابه می‌رسیم. پس در کل این سه متد را برای سادگی محاسبات O(1) در نظر می‌گیریم (البته زمانی که چیزی مثل int پوش شود نه یک وکتور مثلا)روش های دیگر تعریف وکتور:وکتور را ‌می‌توان به شکل های زیر هم تعریف کرد:با طول وکتور: وکتوری با طول داده شده می‌سازد.vector<int> vec(10);با طول وکتور و مقادیر: وکتوری با طول داده شده می‌سازد که همگی مساوی مقدار داده شده هستند.vector<int> vec(10, -1);با لیست مقداردهنده! (initializer list)vector<int> vec = {1, 2, 3, 4};در خیلی از دربرگیرنده ها می‌توان از روش بالا استفاده کرد.ست!ست یک دربرگیرنده ای در زبان سی‌پلاس‌پلاس است که به کمک درخت جستجوی دودویی متوازن (نه ساده) پیاده سازی شده است. و در واقع مشابه مجموعه عمل می‌کند، به این گونه که وقتی عنصری که قبلا درونش بوده را اضافه کنی، بعد بررسی تکراری بودن، آن عنصر اضافه نمی‌شود. و اگر عنصری حذف کنی که در مجموعه نیست،‌اتفاق خاصی نمی‌افتد.تعریف ست:تعریف ست مشابه سایر دربرگیرنده هاست.set<int> st; set<vector<int>> st;درج عنصر:st.insert(10);درج یک عنصر O(log(size)) است.پاک کردن عنصر:st.erase(x); st.erase(st.begin());پاک کردن عدد O(log(size)) است. در ضمن می‌توان به جای x یک ایتریتور هم استفاده کرد. که اردر آن O(1) است.شمردن تعداد عنصر‌:y = st.count(x);مقدار برگردانده شده ۰ یا ۱ است، اگر در ست وجود داشته باشد ۱ در غیر این صورت ۰.این هم O(log(size)) است!یافتن مکان یک عنصر:auto it = st.find(2);حتی این یکی هم O(log(size)) است!مقدار برگردانده شده تابع find یک ایتریتور (به توضیحات وکتور مراجع شود.) به عنصر مد نظر است. اگر عنصر یافت نشده بود، st.end بازگردانده می‌شود.سایز:st.size();این متد ولی O(1) است.مولتی ستگاها برای ترتیب ورود عناصر مهم نیست ولی میخواهیم در زمانی مناسب بفهمیم که یک عنصر وجود دارد یا نه. اینجاست که مولتی ست مطرح می‌شود. تفاوت مولتی ست و ست در این است که در ست وقتی عنصر تکراری اضافه می‌کنیم. این عنصر نا دیده گرفته می‌شود ولی در مولتی ست یک گره (Node) برای عناصر تکراری نیز ساخته می‌شود.multiset<int> ms;درج:ms.insert(x);اردر:‌ O(log(ms.size))شمردن:y = ms.count(x);تعداد x ها را در مولتی ست بازمی‌گرداند.اردر: O(log(ms.size) + count(x))پاک کردن:ms.erase(x); ms.erase(it);خط اول: همه‌ی عناصری در مولتی ست که مساوی x اند را پاک می‌کند.اردر: O(log(ms.size) + count(x))خط دوم: عنصری که ایتریتور به آن اشاره می‌کند را پاک می‌کند.اردر: O(log(ms.size))یافتن و سایز:ms.find(x); ms.size();مشابه ست.پاک کردن کردن یک عنصر:می‌توان فقط یک عنصر مساوی x را (نه همه‌ی آنها) پاک کرد به روش زیرms.erase(ms.find(x));پس دو کد زیر با هم متفاوت اند.ms.erase(ms.find(x)); ms.erase(*ms.find(x)); مثال: تکه کد زیر همه عناصر ms را به ترتیب چاپ می‌کند.while (ms.size()) { cout << *ms.begin() << ' '; ms.erase(ms.begin()); }دِکیودکیو ساختاری است مشابه وکتور با این تفاوت که می‌توان از جلو و عقب به آن عنصر افزود.deque<int> dq; deque<char> dq = {'c'};پوش ها و پاپ ها:dq.push_back(x); dq.push_front(y); dq.pop_back() dq.pop_front();همه O(1)اپراتور قلاب:dq[x] = y; مشابه وکتور O(1).ایتریتورها:for (auto it = dq.begin(); it != dq.end(); it++) { cout << *it; }مشابه وکتورفرانت و بک:x = dq.front(); y = dq.back();عناصر ابتدایی و انتهایی را باز می‌گردانند.چرا به جای وکتور از دکیو استفاده نمی‌کنیم؟دکیو کندتر از وکتور است و زمانی که میدانیم از پوش فرانت و پاپ فرانت استفاده نمی‌کنیم، از وکتور استفاده می‌کنیم.نکته:دربرگیرنده queue هم در سی‌پلاس‌پلاس وجود دارد ولی با توجه به اینکه پیاده سازی مشابه دکیو با امکانات کمتر دارد، از دکیو استفاده می‌کنیم.لیستلیست پیوندی نیز در سی‌پلاس‌پلاس پیاده سازی شده است.list<int> ls;پوش‌ها و پاپ‌ها و فرانت و بک:ls.push_back(x); ls.pop_back(); ls.push_front(y); ls.pop_front(); z = ls.front() + ls.back()همگی O(1).پس تفاوت دکیو و لیست چیست؟دکیو و لیست دو تفاوت اصلی دارند.۱- ایتریتور های آنها متفاوت است. در لیست وقتی عنصری را درج می‌کنی، تا زمانی که آن را پاک نکرده ای ایتریتور آن تغییر نمی‌کند ولی در عوض it + 10 نمی‌توان استفاده کرد. ولی در وکتور و دکیو این برقرار نیست. مثال:list<int> ls = {1}; auto it = ls.begin(); ls.push_back(2); ls.push_back(3); ls.push_front(4); ls.push_front(5); cout << *it << '\n'; // 1 در لیست هم می‌توان از ++it و --it استفاده کرد. (ایتریتور عنصر بعدی/قبلی در لیست را در it قرار می‌دهد.)۲- درج کردن (insert) و پاک کردن (erase) در لیست O(1) و در دکیو، O(size - i) است.ls.insert(it, x);صف اولویتصف اولویت در سی‌پلاس‌پلاس همان هیپ است که متد های push و top و pop و size را دارد.priority_queue<int> pq;پوش:pq.push(x);عنصر x را اضافه می‌کند به هیپ.اردر: O(log(size))پاپ:عنصر بالایی هیپ (عنصر ماکسیسمم) را حذف می‌کند.اردر: O(log(size))pq.pop();تاپ:عنصر بالایی را بازمی‌گرداند.اردر: O(log(size))x = pq.top();سایز:x = pq.size();مشابه بقیه و O(1).چرا صف اولویت؟ممکن است این سوال برایتان ایجاد شده باشد که وقتی مولتی‌ست وجود دارد چرا باید از صف اولویت استفاده کنیم؟ درست است که ست امکانات بیشتری در اختیار ما قرار می‌دهد اما هیپ داده ساختاری بسیار سبک تر از ست است و سرعت بیشتری دارد و حافظه کمتری اشغال می‌کند.نکته: صف اولویت ایتریتور ندارد!جفت!!!فرض کنید میخواهیم n نقطه صفحه مختصات را نگهداری کنیم. از آنجایی که اینها به هم وابسته اند نمیتوان ۲n تا عدد متفاوت نگهداری کرد. گاهی اوقات که میخواهیم تعدادی عنصر وابسته به یک‌دیگر را نگهداری کنیم،‌ از جفت ها استفاده می‌کنیم.pair<int, int> pr; pair<char, int> pci = {'x', 1}; cout << pci.first << ' ' << pci.second; // x 1 pair<pair<int, int>, int> ppi;برای دسترسی به عنصر اول از first و عنصر دوم از second استفاده می‌توان کرد.نکته:مقایسه ۲ جفت در سی‌پلاس‌پلاس مشابه زیر است. (آن که اولی کوچکتر دارد کوچکتر است و اگر اولی ها برابر بود دومی ها را مقایسه می‌کنیم.)(p1 < p2): if (p1.first != p2.first) return p1.first < p2.first; return p1.second < p1.second;نمونه استفاده از جفت: Bubble_Sort(pair<int, int> pr[100]) for (int i = 0; i < 100; i++) for (int j = 0; j < 99; j++) if (pr[j] > pr[j + 1]) swap(pr[j], pr[j + 1]);نکته: تابع swap دو عنصر را جا‌به‌جا می‌کند.مپفرض کنید میخواهیم یک آرایه بسیار بزرگ داشته باشیم مشابه زیر:int arr[1000 * 1000 * 1000]; for (int i = 0; i < 1000; i++) arr[i * 1000 * 1000] = i; for (int i = 0; i < 1000; i++) cout << arr[i * 1000 * 1000] << ' ';در واقع برای داشتن چنین چیزی نیاز به حداقل ۹^۱۰ تا اینتیجر هستیم که معادل تقریبا ۴ گیگابایت است!در حالی که ما فقط ۱۰۰۰ خانه آن را استفاده کرده ایم.در واقع مپ یک نوع ستی (set) است که از جفت ها کمک میگیرد ولی با set<pair<int, int>> st تفاوت دارد.map<int, int> mp; map<char, string> mcs;مثلا mcs، از تعدادی جفت که اولی‌آنها کرکتر و دومی رشته است، تشکیل شده‌است.اپراتور قلاب و مساوی:map<int, int> arr; for (int i = 0; i < 1000; i++) arr[i * 1000 * 1000] = i; for (int i = 0; i < 1000; i++) cout << arr[i * 1000 * 1000] << ' ';این همان کد بالاست که با مپ پیاده سازی شده است.در اینجا دو نوع عملیات وجود دارد. mp[x] و mp[x] = y.فرض کنید اولی می‌رود و درخت را‌ می‌گردد ببیند که آیا جفتی وجود دارد که عنصر اول (first) آن x باشد؟ اگر بله، عنصر دوم (second) آن را باز می‌گرداند. (نه دقیقا همین ولی تا همین حد دانستن کافی است.)و فرض کنید دومی هم مشابه قبلی می‌رود و درخت را می‌گردد ببیند که آیا جفتی وجود دارد که عنصر اول (first) آن x باشد؟ اگر بله، عنصر دوم (second) آن را مساوی y می‌گذارد. وگرنه یک جفت x و y را درون درخت اضافه می‌کند. (این هم نه دقیقا همین.)اردر این عملیات ها O(log(size)) است.پاک کردن:mp.erase(x);اگر جفتی وجود داشته باشد که اولی آن مساوی x باشد، آن را پاک می‌کند.اردر این عملیات هم O(log(size)) است.شمردن:‍mp.count(x);مشابه ست، اگر اگر جفتی وجود داشته باشد که اولی آن مساوی x باشد، ۱ و در غیر این صورت ۰ بازمی‌گرداند.حلقه‌ی اتوfor (int x: vec) { cout << x; }برای هر دربرگیرنده ایتریتور دار می‌توان از روش بالا برای فور زدن روی عناصر آن استفاده کرد که همگی O(n) اند. (به شرطی که شی ای که با آن فور میزنیم، خودش O(1) باشد، مثلا int در مثال بالا)می‌توان به جای int از auto استفاده کرد.for (auto x: vec) { cout << x; }برای رشته هم استفاده می‌شود.for (char c: string) { cout << c; }می‌توان دید که با اینکه در حلقه زیر x را مساوی ۱۰ می‌گذاریم ولی هیچ تغییری به وجود نمی‌آید.for (auto x: vec) { x = 10; }زیرا x یک کپی از عناصر vec است. ولی اگر بخواهیم رفرنس بگیریم (مثل رفرنس پاس دادن به تابع) از روش زیر استفاده می‌کنیم.for (auto &x: vec) { x = 10; } این هدف ما (همه عناصر را مساوی ۱۰ قرار دادن) را برآورده می‌کند و یک مزیت دیگری که دارد این است که x دیگر کپی نمی‌شود،‌ بلکه یک رفرنس از آن است و سرعت ما افزایش می‌یابد. اما برای مپ و ست نمیتوان از آن استفاده کرد.for (const auto &x: st) { cout << x << ' '; } for (const auto &x: mp) { cout << x.first << ' ' << x.second << '\n'; }وقتی از const استفاده می‌کنیم دیگر نمی‌توان x را تغییر داد ولی سرعتش به دلیل کپی نشدن بیشتر می‌شود ولی با توجه به اینکه این حلقه روی ست و مپ O(n) با ظریب بالایی است مثلا 10n، تغییر محسوسی ایجاد نمی‌شود.for (auto [x, y]: mp) { cout << x << ' ' << y << '\n'; }برای مپ می‌توان از روش بالا استفاده کرد.for (auto &[x, y]: mp) { y = 10; } for (auto &[x, y]: mp) { cout << y << '\n'; }تکه کد بالا امتحان کنید. خواهید دید که می‌توان y را تغییر داد. (به & قبل [x, y] توجه کنید).ولی تکه کد زیر ارور کامپایل خواهد داد. چون x یک رفرنس (&) ثابت (const) است.for (auto &[x, y]: mp) { x = 10; }ایتریتور معکوس.با متد های begin و end آشنا شدیم. حال با rbegin و rend آشنا می‌شویم. set <int> st = {1, 7, 2, 5, 3}; for (auto it = st.begin(); it != st.end(); it++) { cout << *it << ' '; } cout << '\n'; for (auto it = st.rbegin(); it != st.rend(); it++) { cout << *it << ' '; }اردر ایتریتور ها:هر ۴ تابع begin و end و rbegin و rend، اینگونه نیستند که هر دفعه محاسبه شوند، اینها در زمان تغییر خود دربرگیرنده، اینها نیز به‌روزرسانی می‌شوند. و در زمان استفاده از این توابع، O(1) جواب را بر‌می‌گردانند.نکات نهاییتایپدف و دیفاین:#include <bits/stdc++.h> using namespcae std; typedef long long ll; typedef pair<int, int> pii; #define F first #define S secondاحتمالا اگر رفته باشید در سایت کدفورسز و کد چند نفر را دیده باشید این تکه کد و مشابه آن را خواهید دید.مثلا در مثال بالا، کامپایلر قبل هر کاری، به جای هر F، یک first می‌نوسید و به جای هر S یک second.به جای هر ll هم long long و به جای pii هم جفت int و int.نکته: تایپدف فقط برای تایپ ها استفاده می‌شود.تبدیل سایز:for (int i = 0; i < vec.size() - 1; i++) cout << vec[i] << ' ';در نگاه اول، کد زیر n - 1 تا عنصر اول vec را چاپ می‌کند، اما اگر vec.size مساوی ۰ باشد، کد به مشکلات عجیب می‌خورد.(قبل خواندن جواب فکر کنید)شاید با خود بگویید که i < -1 که هیچ‌گاه وارد حلقه نمی‌شود، مشکل کجاست؟از آنجایی که تایپ بازگردانده شده توسط متد سایز، unsigned int است نه int، و int - (unsigend int) یک unsigend int است. پس vec.size() - 1، یک unsigend int و یک عدد بسیار بزرگ است. و از این سبب به مشکل می‌خوریم. (البته ممکن است در سیستم های ۶۴ بیتی، unsigned long long باشد. که باز هم به مشکل بالا میخوریم)پس همواره به جای vec.size از روش زیر استفاده کنید.for (int i = 0; i < (int)vec.size() - 1; i++) cout << vec[i] << ' ';ست و مپ نامرتب:unordered_set<int> st; st.insert(x); st.erase(x); y = st.count(x); it = st.find(x); unordered_map<int> mp; mp[x] = y; y = mp.count(x); mp.erase(x);توجه: در ست و مپ نامرتب، st.begin لزوما عنصر مینیمم نیست. unordered_set <int> st = {4, 2, 1, 3, 5, 7}; for (int x: st) cout << x << ' ';مثلا کد بالا ممکن است نامرتب چاپ کند.نکته: unordered_multiset هم مشابه unordered_set است اما در آن عنصر تکراری می‌توان داشت.اردر اعمال در unordered_set و unordered_map به طور میانگین کمتر از set و map است. زیرا این دو از hash table استفاده می‌کنند، اما چند برابر حافظه مصرف می‌شود و همه اعمال set و map در دسترس نیست.اشکالات:در صورتی که بخشی از مطالب بالا در مورد دربرگیرنده ها متوجه نشده اید، می‌توانید از بخش reference قسمت Containers سایت cplusplus.com استفاده نمایید. و همچنین در بخش نظرات بپرسید.تمرین نهایی:سوال 1282E را به کمک لیست و مپ و ست و وکتور، حل کنید.