AtCoder Regular Contest 024 B - 赤と黒の木
手を動かすと答えが分かる問題だった。
問題
円形にN本の木が並んでる。木はそれぞれ赤または黒の二色である。
それぞれの木は自分の色と両隣の色が同じなら次の日に自分の色が変わる。
何日目に全ての木の色が変わらなくなる日を出力せよ
また木が変化し続けるならば-1を出力せよ
解法
同じ色がいくつ連続しているかを考える3○○○→○●○ 2日
5○○○○○→○●●●○→○●○●○ 3日
7○○○○○○○→○●●●●●○→○●○○○●○→○●○●○●○ 4日
連続数をxと考えてあげると一日ごとに
2ずつ減り連続数xが3未満になったら変化しない
よって求める答えは円形の最長の色の連続数をmax_cntとすると
(max_cnt + 1)/2が答えとなる。
円形の最長の連続数を求めるならば
例えば、001010ならば
001010 + 001010 = 001010001010として数列を倍にして考えればよい
- 1の判定は全て同じ色なら変化し続ける。
コード
#include <map> #include <set> #include <list> #include <cmath> #include <queue> #include <stack> #include <cstdio> #include <string> #include <vector> #include <complex> #include <cstdlib> #include <cstring> #include <numeric> #include <sstream> #include <iostream> #include <algorithm> #include <functional> #define mp make_pair #define pb push_back #define all(x) (x).begin(),(x).end() #define rep(i,n) for(int i=0;i<(n);i++) using namespace std; typedef long long ll; typedef unsigned long long ull; typedef vector<bool> vb; typedef vector<int> vi; typedef vector<vb> vvb; typedef vector<vi> vvi; typedef pair<int,int> pii; const int INF=1<<29; const double EPS=1e-9; const int dx[]={1,0,-1,0},dy[]={0,-1,0,1}; int n; int main(){ cin>>n; string tmp =""; for(int i = 0;i < n;i++){ char c; cin>>c; tmp +=c; } tmp +=tmp; // cout <<"tmp = "<<tmp<<endl; char pre =tmp[0]; int cnt = 1; int max_cnt = 1; for(int i = 1;i < tmp.length();i++){ if(pre == tmp[i]){ cnt++; max_cnt = max(max_cnt,cnt); }else{ max_cnt =max(max_cnt,cnt); cnt = 1; } pre = tmp[i]; } if(cnt == 2*n){ cout <<-1<<endl; return 0; } // cout <<"max_cnt = "<<max_cnt<<endl; cout <<(max_cnt + 1)/2<<endl; return 0; }
AtCoder Regular Contest 024 A - くつがくっつく
寝てたらでるの忘れてたので後日解いた。
問題
二つの数列がL,Rが存在し、LとRの数列からペアを作り、最大のペア数を返す。解法
Lの数列を固定してもう片方の数列Rとペアとなる値を全通り考える。コード
#include <map> #include <set> #include <list> #include <cmath> #include <queue> #include <stack> #include <cstdio> #include <string> #include <vector> #include <complex> #include <cstdlib> #include <cstring> #include <numeric> #include <sstream> #include <iostream> #include <algorithm> #include <functional> #define mp make_pair #define pb push_back #define all(x) (x).begin(),(x).end() #define rep(i,n) for(int i=0;i<(n);i++) using namespace std; typedef long long ll; typedef unsigned long long ull; typedef vector<bool> vb; typedef vector<int> vi; typedef vector<vb> vvb; typedef vector<vi> vvi; typedef pair<int,int> pii; const int INF=1<<29; const double EPS=1e-9; const int dx[]={1,0,-1,0},dy[]={0,-1,0,1}; int L,R; int main(){ cin>>L>>R; vector<int> left; vector<int> right; for(int i = 0;i < L;i++){ int x; cin>>x; left.push_back(x); } for(int i = 0;i < R;i++){ int x; cin>>x; right.push_back(x); } sort(left.begin(),left.end()); sort(right.begin(),right.end()); int cnt = 0; for(int i = 0;i < L;i++){ for(int j = 0;j < R;j++){ if(left[i] == right[j]){ left[i] = 0; right[j] = 0; cnt++; break; } } } cout <<cnt<<endl; return 0; }
SRM622 Div2 MEDIUM BoxesDiv2
本番では問題文の題意が理解できずに苦しんだ。
問題
それぞれ異なる種類のキャンディーの個数からなるcandyCounts数列が与えられ2^i(i >=0)の個のキャンディーがはいる箱がそれぞれ無限個存在する。(1,2,4,8,・・・)
同じ種類のキャンディーは同じ箱の中に入れなければならない,さらにキャンディーの入った二つの箱をより大きい箱にいれることができる。
(大きい箱の容量が二つの箱の容量の合計以上のとき、キャンディーの個数ではない)
全てのキャンディーを一つの箱にいれるのに必要な最小の箱の容量を求めよ。
解法
与えられるキャンディーの個数をx変換する個数をyとする。
2^(j-1)< x <=(2^j = y)個に変換した数列を作成した。
その数列の合計をsumとし,2^(i-1) < sum <=(2^(i) = result)なresultを返した。
コード
#include <map> #include <set> #include <list> #include <cmath> #include <queue> #include <stack> #include <cstdio> #include <string> #include <vector> #include <complex> #include <cstdlib> #include <cstring> #include <numeric> #include <sstream> #include <iostream> #include <algorithm> #include <functional> #include <bitset> #include <fstream> #include <limits.h> #define mp make_pair #define rep(i,n) for(int i=0;i<(n);i++) using namespace std; typedef long long ll; typedef pair<int,int> pii; const int INF=1<<29; const double EPS=1e-9; const int dx[]={1,0,-1,0},dy[]={0,-1,0,1}; class BoxesDiv2 { public: int findSize(vector<int> candy) { int result; sort(candy.begin(),candy.end()); int i; int n = candy.size(); int sum = 0; vector<int> data; for(int i = 0;i < n;i++){ for(int j = 1;;j *=2){ if(candy[i]<=j){ data.push_back(j); break; } } } for(int i = 0;i < n;i++){ // cout <<data[i]<<endl; sum +=data[i]; } for(i = 1;;i *=2){ if(sum <=i){ return i; } } return result; } }; // Powered by Greed 2.0-RC
SRM622 Div2 EASY FibonacciDiv2
SRM622
朝SRM
九時ぐらいに起床したがぐだぐだして始まって五分ぐらいして参戦
easyとmedともに通ったがmedが遅くて微妙な順位
結果
FibonacciDiv2 find Level One 0:05:44.973 Passed System Test 240.29BoxesDiv2 findSize Level Two 0:27:10.034 Passed System Test 301.38
Subsets findSubset Level Three 0:30:11.621 Compiled 0.00
847->887
灰色辛すぎる・・・
問題
F[0] = 0F[1] = 1
F[i] = F[i - 1] + F[i - 2] i>=2
のフィボナッチ数列が定義されている。(0,1,1,2,3,5,8,13,・・・)
ある整数N(1<=N<=1000000)が与えられる。
そのNを+1または-1増減させて、フィボナッチ数にする最小のステップを返せ
解法
Nが大きくないのでフィボナッチ数列を50ぐらいまで列挙して全通りを試して絶対値をとってminをとった。
コード
#include <map> #include <set> #include <list> #include <cmath> #include <queue> #include <stack> #include <cstdio> #include <string> #include <vector> #include <complex> #include <cstdlib> #include <cstring> #include <numeric> #include <sstream> #include <iostream> #include <algorithm> #include <functional> #include <bitset> #include <fstream> #include <limits.h> #define mp make_pair #define rep(i,n) for(int i=0;i<(n);i++) using namespace std; typedef long long ll; typedef pair<int,int> pii; const int INF=1<<29; const double EPS=1e-9; const int dx[]={1,0,-1,0},dy[]={0,-1,0,1}; ll f[60]; class FibonacciDiv2 { public: int find(int N) { int result; f[0] = 0; f[1] = 1; for(int i = 2;i <=50;i++){ f[i] = f[i - 2] + f[i - 1]; // cout <<f[i]<<endl; } ll ans =INF; for(int i = 0;i <=50;i++){ ans = min(ans,abs(N - f[i])); } result = ans; return result; } }; // Powered by Greed 2.0-RC
