るくすの日記 ~ Out_Of_Range ~

主にプログラミング関係

TopCoder

SRM 563 Div2 hard SpellCardsEasy

[問題文] TopCoder Statistics - Problem Statementカードの並びが与えられる。カード[i]にはlevel[i]とdamage[i]が書いてある。カード[i]を選んだとき、相手にdamage[i]のダメージを与え、カード[i]よりも右に置いてあるカードlevel[i] - 1枚を取り去る。(…

Dynamic Programming 演習(2)

前回(動的計画法(Dynamic Programming)演習 - るくすの日記 ~ Out_Of_Range ~)の続き。今回は該当するDiv2Hardのうち13問解きました。 [Div2](SRM354) 1000:UnsealTheSafe dp[i][j] := i-1番目にjを押すようなパスワードの総数 sum += dp[i - 1][keypad[ny][…

Dynamic Programming 演習

タイトルのまんまです。 TopCoder SRMの過去問から解法に「Dynamic Programming」が含まれている問題をレベルで昇順にソートして解いていきます。 該当するDiv2Medium全18問中15問解きました。(残り3問は、dpでふつう解かないだろうみたいな問題だったので別…

SRM 534 Div2

250: EllysDirectoryListingやるだけ class EllysDirectoryListing { public: vector <string> getFiles(vector <string> files) { int one = 0,two = 0,last = files.size() - 1; rep(i,files.size()){ if(files[i] == ".") one = i; else if(files[i] == "..") two = i; } </string></string>…

SRM 535 Div2

珍しく簡単なセットだった。250: FoxAndIntegers少し大きめにとった class FoxAndIntegers { public: vector <int> get(int AmB, int BmC, int ApB, int BpC) { vector <int> result; for(int a = -100; a <= 100; a++){ for(int b = -100; b <= 100; b++){ for(int c </int></int>…

SRM 536 Div2

250: BinaryPolynomialDivTwoやるだけ pow関数でTCのコンパイラがエラーを吐きまくって謎 class BinaryPolynomialDivTwo { public: int countRoots(vector <int> a) { int p = 0,p2 = 0; rep(i,a.size()){ p += a[i] * (int)pow(0.,i); p2 += a[i] * (int)pow(1.,</int>…

SRM 537 Div2

250: KingXNewBabyやるだけ const char vow[] = {'a', 'e', 'i', 'o','u'}; class KingXNewBaby { public: string isValid(string name) { int ex[100]; memset(ex,0,sizeof(ex)); if(name.size() == 8) rep(i,name.size()) ex[name[i] - 'a']++; int c = 0;…

SRM 538 Div2

300: LeftOrRight300にする必要あるかなあ...左にいってまた右にもどるみたいな操作は必要なさそうだったので、左と右のみに絞ったら通った。(証明はしていない) class LeftOrRight { public: int F(string s){ int res = 0; int now = 0; rep(i,s.size()){ …

SRM 539 Div2

250: PlatypusPaternity変なバグを出して時間がかかってしまった。 class PlatypusPaternity { public: int Can(string fm,string ms,string group){ int ret = 0; rep(i,group.size()){ if(group[i] == 'Y' && fm[i] == 'Y' && ms[i] =='Y') ret++; if(grou…

SRM 540 Div2

250: RandomColoringDiv2やるだけ class RandomColoringDiv2 { public: int getCount(int maxR, int maxG, int maxB, int startR, int startG, int startB, int d1, int d2) { int result = 0; rep(r,maxR){ rep(g,maxG){ rep(b,maxB){ int dr = abs(r - sta…

SRM 541 Div2

250: AkariDaisukiDiv2わーいSRMあかりSRM大好きー class AkariDaisukiDiv2 { public: int countTuples(string S) { int result = 0; for(int x1 = 0; x1 < S.size(); x1++){ for(int x2 = x1 + 1; x2 < S.size() - 1; x2++){ for(int x3 = x2 + 1; x3 < S.s…

SRM 543 Div2

250: EllysTSP訪れる順番は気にしなくて良いので、普通にやるだけ。 class EllysTSP { public: int visit(int s,string p){ int ret = 1; bool flag[100]; memset(flag,0,sizeof(flag)); int now = s; flag[s] = true; while(true){ bool update = false; re…

SRM 545 Div2

250: ANDEquationやるだけ class ANDEquation { public: int restoreY(vector <int> A) { int result; rep(i,A.size()){ int y = A[i]; vector<int>t; rep(j,A.size()){ if(j == i) continue; t.pb(A[j]); } rep(i,t.size() - 1) t[i + 1] = t[i] & t[i + 1]; if(t[t.s</int></int>…

SRM 546 Div2

250: ContestWinnerやるだけ class ContestWinner { public: int getWinner(vector <int> events) { map<int,int>mx; rep(i,events.size()) mx[events[i]] ++; int imx = 0; for(map<int,int>::iterator it = mx.begin();it != mx.end(); ++it) imx = max(imx,(*it).second); mx.cle</int,int></int,int></int>…

SRM 548 Div2

250: KingdomAndDucks やるだけ int kind[100]; class KingdomAndDucks { public: int minDucks(vector <int> duckTypes) { memset(kind,0,sizeof(kind)); int k = 0; rep(i,duckTypes.size()){ if(!kind[duckTypes[i]]) k++; kind[duckTypes[i]]++; } int mx = 0</int>…

SRM 550 Div2

250: EasyConversionMachine無駄な操作を除いた必要最低限の回数に2回ずつの無駄な操作を追加してkにできればPOSSIBLE class EasyConversionMachine { public: string isItPossible(string originalWord, string finalWord, int k) { int need = 0; rep(i,or…

SRM 551 Div2

思いつかないと解けないセットだったと思う。頭の悪い僕にとっては結構難しかった 250: ColorfulBricks使われている文字の種類が2種類以上だと成り立たない。 class ColorfulBricks { public: int countLayouts(string bricks) { int res = 0; int r[26]; me…

SRM 553 Div2

250: PlatypusDuckAndBeaver少し危ない計算量だけど間に合った。 class PlatypusDuckAndBeaver { public: int minimumAnimals(int webbedFeet, int duckBills, int beaverTails) { int result = 0; for(int x = 0; x <= 500; x++){ for(int y = 0; y <= 250;…

SRM 558 Div2

一応本番も出ていましたが、Easyしか通せませんでした....orz解きなおし 250: SurroundingGameEasy誤読すると氏ぬ bool d[100][100]; class SurroundingGameEasy { public: int score(vector <string> cost, vector <string> benefit, vector <string> stone) { memset(d,0,sizeof(d)</string></string></string>…

SRM 554 Div2

250 TheBrickTowerEasyDivTwo並べるだけ class TheBrickTowerEasyDivTwo { public: int find(int redCount, int redHeight, int blueCount, int blueHeight) { int now_h = 0; int C[2] = {blueCount,redCount}; int H[2] = {blueHeight,redHeight}; memset(…

Div2Easy 5連戦

今日は時間があまり無かったので5問だけ解きましたSRM488(Score):231.03そんなに難しくない class TheBoredomDivTwo { public: int find(int n, int m, int j, int b) { int result=n; if(j==b && n

Div2Easy 10連戦

最近TopCoderの成績がひどいので、とりあえずDiv2Easyを確実にとれるようにしようと思ってプラクティスしました。 てことでDiv2Easy 10連戦のソース(プリプロセッサ部分とかもろもろは省略してます)SRM416 map使って解いた class MostCommonLetters { public…