Codeforces#143
A. Team
■問題
3つの0か1がn個与えられて、1が2つ以上あるものが何個あるか求めよ。
■解法
数えるだけ
■ソース
#include <cstdio> #include <iostream> #include <algorithm> using namespace std; int main(void) { int n; cin >> n; int ret = 0; for(int i = 0; i < n; i++){ int c = 0; for(int j = 0; j < 3; j++){ int a; cin >> a; if(a) c++; } if(c >= 2) ret++; } cout << ret << endl; }
B. Magic, Wizardry and Wonders
■問題
最後の2つの値をそれを減算した値に置き換えてを繰り返し要素が1つになったときその値がdになるようなn個の要素からなる数列を出力せよ
■解法
dp[幾つ目か][必要な差はいくつか]で無理やりdpした。
奇数項 - 偶数項 = dなんて頭いいこと時間内に思いつかなかった。
■ソース
#include <cstdio> #include <cstring> #include <cmath> #include <iostream> #include <algorithm> using namespace std; int n,d,l; int use[111]; int dp[111][22222]; int solve(int i,int m){ if(dp[i][m + 10000] >= 0){ return dp[i][m + 10000]; } if(i == n){ return (m == 0)?1:0; } for(int j = 1; j <= l; j++){ if(abs(j - m) >= l * n) continue; if(solve(i + 1, j - m)){ use[i] = j; return dp[i][m + 10000] = 1; } } return dp[i][m + 10000] = 0; } int main(void) { cin >> n >> d >> l; memset(dp,-1,sizeof(dp)); if(solve(0,d)){ for(int i = 0; i < n; i++){ cout << use[i] << ((i == n - 1)?'\n':' '); } }else{ cout << -1 << endl; } }
AOJ1072
■問題
r*cあるものを、それぞれ上下左右に移動させたとき場所がかぶることなく全て移動できるかどうか求める。
■解法
すべてを上下左右に移動できるかどうかは、ある一点から上下左右に移動し、他のすべての点を通って最初の点に戻ってこれるかで判定できる。（全ての点を一本の線でなぞれるかみたいな感じ）
しかし、全探索でやるとO(4^rc)なのできつい。
よく考えると線のなぞり方はr=4,c=3の場合
1 2 3 4
12 9 8 5
11 10 7 6
のようにくねくねさせるとできる。
これはどちらかの辺が偶数なら可能なのでr、cが両方奇数かどうか判定するだけで解ける。
rとcの範囲に騙されそうになった。
■ソース
#include <cstdio> #include <iostream> #include <algorithm> using namespace std; int main(void) { while(1){ int r,c; cin >> r >> c; if(!r && !c) break; if(r%2 && c%2){ cout << "no" << endl; }else{ cout << "yes" << endl; } } }
AOJ0120
■問題
幾つかの円を任意の順番で並べたとき必要な幅の最小が箱の幅より小さいかどうかを求める。
■解法
dp[直前に度の円を使ったか][使った円の集合]で横幅を求めて、それがはこの大きさより小さいかを判定する。
2円の中点を繋ぐ線分はr1+r2、2円の中点の高さの差はr1-r2でも止まるので三平方の定理で2円の中点の間の横幅を求めることができるので頑張る。
入力が非常に悪質なのでfgets()とかsscanf()とか使って頑張る。
入力が一番難しい。
■ソース
#include <cstdio> #include <cmath> #include <iostream> #include <algorithm> #include <vector> using namespace std; int n,l; char len[1111]; int r[22]; double dp[22][5555]; double sq(int a){return a*a;} double solve(int af,int used){ if(dp[af][used] >= 0) return dp[af][used]; if(used == (1<<n)-1) return 0; double ret = 4444; for(int i = 0; i < n; i++){ if(af == n) r[af] = r[i]; if( (used & (1<<i)) == 0 ){ ret = min(ret, solve(i, used | (1<<i)) + sqrt(sq(r[i] + r[af]) - sq(r[i] - r[af])) - r[af] + r[i]); } } return dp[af][used] = ret; } int main(void) { while( fgets(len, sizeof(len), stdin) != NULL ){ n=0; vector<char*> d; for(int i = 0; len[i] != '\0'; i++){ if(len[i] == ' '){ d.push_back(len+i+1); n++; } } sscanf(len,"%d",&l); for(int i = 0; i < n; i++){ sscanf(d[i],"%d",&r[i]); } for(int i = 0; i <= n; i++){ for(int j = 0; j < 5555; j++){ dp[i][j] = -1; } } double ret = solve(n,0); if(ret > l) puts("NA"); else puts("OK"); } }
AOJ2022
■問題
入力されたすべての文字列を部分文字列として含む最小の長さの文字列SSSを求める。
複数あったら辞書順で小さいものにする。
■解法
SSSの後ろの10文字と、使ったかどうかをビットで表現したやつを引数に持たせてDPする。
使うやつがSSSの後ろとかぶる場合は被らせたのも試して、SSSの中にもう含まれている文字列は使用済みということにして印を付ける。
また、引数が文字列なので多次元mapを使った。
DPしないとTLE、SSS全部もたせるとMLEする。
string.substr()をめちゃくちゃ使った。
■ソース
#include <cstdio> #include <iostream> #include <algorithm> #include <string> #include <map> using namespace std; typedef pair<string,int> P; int n; string str[11]; string INF; map<P,string> m; int check(string s){ int ret = 0; for(int i = 0; i < n; i++){ if((int)s.find(str[i]) != -1){ ret |= 1<<i; } } return ret; } string solve(string sss,int used){ if(m[P(sss,used)] != "") return m[P(sss,used)]; if(used == (1<<n)-1) return ""; string ret = INF; string temp = ""; int c; for(int i = 0; i < n; i++){ if( (used & 1<<i) == 0) for(int j = 1; j < (int)(min(sss.size(),str[i].size()));j++){ if(sss.substr(sss.size() - j) == str[i].substr(0,j)){ string t = sss + str[i].substr(j); c = check(t); temp = str[i].substr(j) + solve(t.substr(max((int)t.size()-10,0)),(used|1<<i)|c); if(ret.size() == temp.size()){ ret = (ret < temp)?ret:temp; }else{ ret = (ret.size() < temp.size())?ret:temp; } } } string t = sss + str[i]; c = check(t); temp = str[i] + solve(t.substr(max((int)t.size()-10,0)),(used|1<<i)|c); if(ret.size() == temp.size()){ ret = (ret < temp)?ret:temp; }else{ ret = (ret.size() < temp.size())?ret:temp; } } } return m[P(sss,used)] = ret; } int main(void) { for(int i = 0;i < 111; i++) INF += "A"; while(1){ cin >> n; if(!n)break; for(int i = 0; i < n; i++){ cin >> str[i]; } map<P,string> a; m = a; cout << solve("",0) << endl; } }
AtCoder007
A - 帰ってきた器物損壊！高橋君
■問題
破壊した文字と文字列が与えられて、文字列から破壊されたものを取り除いた文字列を出力する。
■解法
やるだけ
■ソース
#include<cstdio> #include<string> #include<iostream> #include<algorithm> using namespace std; int main() { char x; string s; cin >> x >> s; for(int i=0;i<s.size();i++){ if(x!=s[i])cout << s[i]; } puts(""); }
B - 迷子のCDケース
■問題
n個のケースに入ったCDと1個のケースがないCDがあり、入力されたCDとケース無しのCDを交換したあとのケースの状態を求めろ
■解法
入力通り入れ替えするだけ
やるだけ
■ソース
#include<cstdio> #include<string> #include<iostream> #include<algorithm> using namespace std; int main() { int n,m; int cd[111]; cin >> n >> m; for(int i=1;i<=n;i++){ cd[i] = i; } cd[0]=0; for(int i=0;i<m;i++){ int d,id,j; cin >> d; for(j=0;j<=n;j++){ if(cd[j] == d) break; } cd[j] = cd[0]; cd[0] = d; } for(int i=1;i<=n;i++){ cout << cd[i] << endl; } }
C - 節約生活
■問題
視聴できる時間を表した文字列が与えられます。
幾つかのテレビを時間をずらして付けていつでも視聴できるような状態を作るとき必要なテレビの最小の数を求めなさい。
■解法
0分～データの個数分までの間はパターンが繰り返されているのでテレビをつける必要はない。
データ量＋1～データ量＊2分の間で全て視聴できればそれ以降も全て視聴できるといえる。
後は、テレビの付け方を全通り試せば答えを求めることができる。
■ソース
#include<cstdio> #include<string> #include<iostream> #include<algorithm> #include<queue> using namespace std; string w; int watch[22]; int solve(int m){ int i; for(i=m;i<w.size()*2;i++){ if(!watch[i])break; } if(i==w.size()*2){ return 0; } int ret =111; for(int i=m;i<w.size();i++){ queue<int> que; for(int j=i,k=0;j<w.size()*2;j++,k++){ k %= w.size(); if(w[k]=='o' && !watch[j] ){ watch[j]=1; que.push(j); } } ret = min(ret,solve(i+1)+1); int s = que.size(); for(int j=0;j<s;j++){ int q = que.front();que.pop(); watch[q] = 0; } } return ret; } int main() { cin >> w; cout << solve(0) << endl; }
SRM555
255 - XorBoardDivTwo
■問題
'0'と'1'のみで作られた長方形が与えられます。
その長方形の任意の横一列と縦一列の要素を反転させた時、その長方形に含まれる'1'の最大数を求めなさい。
■解法
縦一列、横一列の組み合わせを全通り試す。
一列見ていって'1'だったら-1、'0’だったら+1される。
ただし、選んだ縦と横の交点は反転の反転で元に戻るので無視する。
■ソース
テンプレート省略
int theMax(vector <string> board) { int result; int all = 0; int best = -10000; for(int i=0;i<board.size();i++){ for(int j=0;j<board[0].size();j++){ int temp =0; if(board[i][j] == '1') all++; for(int k=0;k<board[0].size();k++){ if(j==k)continue; if(board[i][k]=='1')temp--; else temp++; } for(int k=0;k<board.size();k++){ if(i==k)continue; if(board[k][j]=='1')temp--; else temp++; } best = max(best,temp); } } result = all + best; return result; }
555 - CuttingBitString
■問題
1と0のみでなる文字列が与えられます。この文字列を5の累乗の2進数ずつ分けていった時、最小何個にわけられますか？
■解法
50文字以下なので5^23までの2進数を求めておく。
後は普通にdpやるだけ
■ソース
直角二等辺三角形みたいなのは気にしてはいけない
int ss; int dp[100]; string sd; string f[23]; int getmin(string S) { int result; for(int i=0;i<100;i++)dp[i]=0; ss = S.size(); sd = S; f[0] = "1"; f[1] = "101"; f[2] = "11001"; f[3] = "1111101"; f[4] = "1001110001"; f[5] = "110000110101"; f[6] = "11110100001001"; f[7] = "10011000100101101"; f[8] = "1011111010111100001"; f[9] = "111011100110101100101"; f[10] = "100101010000001011111001"; f[11] = "10111010010000111011011101"; f[12] = "1110100011010100101001010001"; f[13] = "1001000110000100111001110010101"; f[14] = "101101011110011000100000111101001"; f[15] = "11100011010111111010100100110001101"; f[16] = "10001110000110111100100110111111000001"; f[17] = "1011000110100010101111000010111011000101"; f[18] = "110111100000101101101011001110100111011001"; f[19] = "100010101100011100100011000001001000100111101"; f[20] = "10101101011110001110101111000101101011000110001"; f[21] = "1101100011010111001001101011011100010111011110101"; f[22] = "1000011110000110011110000011001001101110101011001001"; result = solve(0); if(result>100) result = -1; return result; } int solve(int m){ if(dp[m]>0) return dp[m]; if(ss==m)return 0; if(ss<m)return 111111; int res = 111111; for(int i=0;i<23;i++){ int j; for(j=0;j<f[i].size() && m+j<ss;j++){ if(f[i][j]!=sd[m+j])break; } if(j==f[i].size()){ res = min(res,solve(m+j)+1); } } return dp[m] = res; }
●余談
ゾロ目回で、初med＆初2完で嬉しかった。
785 -> 887
灰色脱却を目指したい。
翻訳サイトを使ってやるなら、全体はgoogle翻訳で怪しいとこだけyahoo翻訳にするとわかりやすい。
SRM550
250 - EasyConversionMachine
■問題
'a'と'b'からなる２つの文字列の片方の文字列中の文字をk回交換したときに2つの文字列を等しくできるかどうかを調べる。
■解法
異なる箇所の数の数えて頑張る。
■ソース
#include <cstdio> #include <cstdlib> #include <cmath> #include <climits> #include <cfloat> #include <map> #include <utility> #include <set> #include <iostream> #include <memory> #include <string> #include <vector> #include <algorithm> #include <functional> #include <sstream> #include <complex> #include <stack> #include <queue> using namespace std; static const double EPS = 1e-5; typedef long long ll; class EasyConversionMachine { public: string isItPossible(string originalWord, string finalWord, int k) { string result; for(int i=0;i<originalWord.size();i++){ if(originalWord[i] != finalWord[i]){ k--; } } if(k<0 || k%2) return "IMPOSSIBLE"; else return "POSSIBLE"; } };
550 - RotatingBot
■問題
壁に当たると左に向くやつがあります。
それが入力の通りに進むにはどれだけの面積が必要ですか。
■解法
2回進んで左上にいるところから戻るように２歩、進むように残りの歩数進め、通った場所に行っていないか壁で回転しているかを判定しながら頑張る。
■ソース
int minArea(vector <int> moves) { int result=0; int m[200][200]={0}; int dx[]={1,0,-1,0}; int dy[]={0,-1,0,1}; int s=moves.size(); int l[2]={0}; int x,y; for(int i=0;i<s && i < 4;i++){ if(l[i%2] <= moves[i]){ l[i%2]=moves[i]; } } for(int i=0;i<l[0]+2;i++){ m[i][0] = 1; m[i][l[1]+2] = 1; } for(int i=0;i<l[1]+2;i++){ m[0][i] = 1; m[l[0]+2][i] = 1; } if(s < 2) return (l[0]+1) * (l[1]+1); x=l[0]+1; y=1; m[x][y]=1; for(int i=1;i>=0;i--){ for(int j=0;j<moves[i];j++){ x+=dx[i%4]*-1; y+=dy[i%4]*-1; if(m[x][y]){ return -1; } m[x][y]=1; } } x=l[0]+1; y=1; for(int i=2;i<s;i++){ for(int j=0;j<moves[i];j++){ x+=dx[i%4]; y+=dy[i%4]; if(m[x][y]){ return -1; } m[x][y]=1; } if(i != s-1){ if(!m[x+dx[i%4]][y+dy[i%4]]){ return -1; } } } result = (l[0]+1) * (l[1]+1); return result; }
