三年目の初学者(4問目)
問題
topcoder SRM 601 div2 med
TopCoder Statistics - Problem Statement
使用言語
C++
所感
・vectorに少しづつ慣れてきた
・組み合わせ楽しい
・なんちゃってdp
コード
class WinterAndCandies { public: int getNumber(vector<int> type) { int ans = 0; int num_element = *max_element(type.begin(), type.end()) + 1; vector<int> num(num_element, 0); for (int i = 0; i < type.size(); i++) { num[type[i]]++; } int dp = 1; for (int i = 1; i < num_element && num[i] > 0; i++) { dp = dp * num[i]; ans += dp; } return ans; } };
三年目の初学者(3問目)
問題
topcoder SRM 601 div2 easy
TopCoder Statistics - Problem Statement
使用言語
C++
所感
・easy, 速さ勝負だと思った
・ソート気づかなかったら死にそう
コード
#define INF 1e9 class WinterAndMandarins { public: int getNumber(vector<int> bags, int K) { int ans = INF; sort(bags.begin(), bags.end()); for (int i = 0; i + K - 1 < bags.size(); i++) { ans = min(ans, bags[i+K-1] - bags[i]); } return ans; } };
三年目の初学者(2問目)
問題
topcoder SRM 600 div2 med 600
TopCoder Statistics - Problem Statement
問題の要約と方針
・与えられた数字群(numbers)からいくつかの数字を選んで(0から)ビット単位の論理和(OR)を繰り返し、目標(goal)にするゲーム。
・数字群をから数字を削除し、ゲームを破綻させる。そのための最小の個数をもとめる。
→goalより大きい数字とgoalのビットが0の位が1となる数字は削除。
→goalのビットが1の位で同じく1となる数字の個数を各位について数える。
使用言語
C++
所感
・全探索
・除外がカギ?
・ビットシフト便利&&楽しい。
コード
#include <cstdio> #include <cmath> #include <cstring> #include <ctime> #include <iostream> #include <algorithm> #include <set> #include <vector> #include <sstream> #include <typeinfo> #include <fstream> using namespace std; #define INF 1E9 class ORSolitaireDiv2 { public: int getMinimum(vector<int> numbers, int goal) { int ans = INF; //徐々にgoalを右シフトし、0になるまで各位について調べる for (int n = 0; goal>>n; n++) { int ans_tmp = 0; //書く数字について調べる for (int i = 0; i < numbers.size(); i++) { //除外する if (!(goal & (1<<n))) { ans_tmp = INF; break; } //数字iとgoalのビット和がgoal←ゲームの勝利に使われる可能性のある数字 //(numbers[i] & (1<<n)) >> n : nビット目が1なら1を返す if ((numbers[i] | goal) == goal) ans_tmp += (numbers[i] & (1<<n)) >> n; } ans = min(ans, ans_tmp); } return ans; } }; // CUT begin ifstream data("ORSolitaireDiv2.sample"); string next_line() { string s; getline(data, s); return s; } template <typename T> void from_stream(T &t) { stringstream ss(next_line()); ss >> t; } void from_stream(string &s) { s = next_line(); } template <typename T> void from_stream(vector<T> &ts) { int len; from_stream(len); ts.clear(); for (int i = 0; i < len; ++i) { T t; from_stream(t); ts.push_back(t); } } template <typename T> string to_string(T t) { stringstream s; s << t; return s.str(); } string to_string(string t) { return "\"" + t + "\""; } bool do_test(vector<int> numbers, int goal, int __expected) { time_t startClock = clock(); ORSolitaireDiv2 *instance = new ORSolitaireDiv2(); int __result = instance->getMinimum(numbers, goal); double elapsed = (double)(clock() - startClock) / CLOCKS_PER_SEC; delete instance; if (__result == __expected) { cout << "PASSED!" << " (" << elapsed << " seconds)" << endl; return true; } else { cout << "FAILED!" << " (" << elapsed << " seconds)" << endl; cout << " Expected: " << to_string(__expected) << endl; cout << " Received: " << to_string(__result) << endl; return false; } } int run_test(bool mainProcess, const set<int> &case_set, const string command) { int cases = 0, passed = 0; while (true) { if (next_line().find("--") != 0) break; vector<int> numbers; from_stream(numbers); int goal; from_stream(goal); next_line(); int __answer; from_stream(__answer); cases++; if (case_set.size() > 0 && case_set.find(cases - 1) == case_set.end()) continue; cout << " Testcase #" << cases - 1 << " ... "; if ( do_test(numbers, goal, __answer)) { passed++; } } if (mainProcess) { cout << endl << "Passed : " << passed << "/" << cases << " cases" << endl; int T = time(NULL) - 1517756231; double PT = T / 60.0, TT = 75.0; cout << "Time : " << T / 60 << " minutes " << T % 60 << " secs" << endl; cout << "Score : " << 600 * (0.3 + (0.7 * TT * TT) / (10.0 * PT * PT + TT * TT)) << " points" << endl; } return 0; } int main(int argc, char *argv[]) { cout.setf(ios::fixed, ios::floatfield); cout.precision(2); set<int> cases; bool mainProcess = true; for (int i = 1; i < argc; ++i) { if ( string(argv[i]) == "-") { mainProcess = false; } else { cases.insert(atoi(argv[i])); } } if (mainProcess) { cout << "ORSolitaireDiv2 (600 Points)" << endl << endl; } return run_test(mainProcess, cases, argv[0]); } // CUT end
注意
各位はカクイではなく、カククライ。
三年目の初学者(1問目)
問題
topcoder SRM 600 div2 easy 250
https://community.topcoder.com/stat?c=problem_statement&pm=12824&rd=15712
使用言語
C++
所感
・全探索
・変数名大事。
コード
#include <cstdio> #include <cmath> #include <cstring> #include <ctime> #include <iostream> #include <algorithm> #include <set> #include <vector> #include <sstream> #include <typeinfo> #include <fstream> using namespace std; class TheShuttles { public: int getLeastCost(vector<int> cnt, int baseCost, int seatCost) { int ans = 10e7, Cost_tmp; for (int seat = 1; seat <= 100; seat++) { Cost_tmp = 0; for (int i = 0; i < cnt.size(); i++) { Cost_tmp += cnt[i] % seat == 0 ? cnt[i] / seat * (baseCost + seatCost * seat) : (cnt[i] / seat + 1) * (baseCost + seatCost * seat); } ans = min(ans, Cost_tmp); } return ans; } }; // CUT begin ifstream data("TheShuttles.sample"); string next_line() { string s; getline(data, s); return s; } template <typename T> void from_stream(T &t) { stringstream ss(next_line()); ss >> t; } void from_stream(string &s) { s = next_line(); } template <typename T> void from_stream(vector<T> &ts) { int len; from_stream(len); ts.clear(); for (int i = 0; i < len; ++i) { T t; from_stream(t); ts.push_back(t); } } template <typename T> string to_string(T t) { stringstream s; s << t; return s.str(); } string to_string(string t) { return "\"" + t + "\""; } bool do_test(vector<int> cnt, int baseCost, int seatCost, int __expected) { time_t startClock = clock(); TheShuttles *instance = new TheShuttles(); int __result = instance->getLeastCost(cnt, baseCost, seatCost); double elapsed = (double)(clock() - startClock) / CLOCKS_PER_SEC; delete instance; if (__result == __expected) { cout << "PASSED!" << " (" << elapsed << " seconds)" << endl; return true; } else { cout << "FAILED!" << " (" << elapsed << " seconds)" << endl; cout << " Expected: " << to_string(__expected) << endl; cout << " Received: " << to_string(__result) << endl; return false; } } int run_test(bool mainProcess, const set<int> &case_set, const string command) { int cases = 0, passed = 0; while (true) { if (next_line().find("--") != 0) break; vector<int> cnt; from_stream(cnt); int baseCost; from_stream(baseCost); int seatCost; from_stream(seatCost); next_line(); int __answer; from_stream(__answer); cases++; if (case_set.size() > 0 && case_set.find(cases - 1) == case_set.end()) continue; cout << " Testcase #" << cases - 1 << " ... "; if ( do_test(cnt, baseCost, seatCost, __answer)) { passed++; } } if (mainProcess) { cout << endl << "Passed : " << passed << "/" << cases << " cases" << endl; int T = time(NULL) - 1517574098; double PT = T / 60.0, TT = 75.0; cout << "Time : " << T / 60 << " minutes " << T % 60 << " secs" << endl; cout << "Score : " << 250 * (0.3 + (0.7 * TT * TT) / (10.0 * PT * PT + TT * TT)) << " points" << endl; } return 0; } int main(int argc, char *argv[]) { cout.setf(ios::fixed, ios::floatfield); cout.precision(2); set<int> cases; bool mainProcess = true; for (int i = 1; i < argc; ++i) { if ( string(argv[i]) == "-") { mainProcess = false; } else { cases.insert(atoi(argv[i])); } } if (mainProcess) { cout << "TheShuttles (250 Points)" << endl << endl; } return run_test(mainProcess, cases, argv[0]); } // CUT end