Codeforces Round #373 (Div. 2)
A. Vitya in the Countryside
問題文
解法
n=1でもa=0またはa=15のときは増減が分かることに注意して解く。
感想
UPをuPとtypoして落としてしまったので猛省。
コード
#include <bits/stdc++.h> #define rep(i,n) for(int i = 0; i < n; i++) #define PI 3.1415926535897932384626433832795028841971 #define INF 100000000 #define EPS 1e-10 #define MOD 1000000007 using namespace std; typedef long long ll; typedef pair<int,int> P; int n; int a[100]; int main(){ cin >> n; rep(i,n) cin >> a[i]; if(n == 1){ if(a[0] == 0){ cout << "UP" << endl; } else if(a[0] == 15){ cout << "DOWN" << endl; } else{ cout << -1 << endl; } return 0; } bool up = false; if(a[n-2] < a[n-1]) up = true; if(up){ if(a[n-1] != 15){ cout << "UP" << endl; } else{ cout << "DOWN" << endl; } } else{ if(a[n-1] != 0){ cout << "DOWN" << endl; } else{ cout << "UP" << endl; } } }
B. Anatoly and Cockroaches
問題文
解法
目的の文字列の先頭がrの場合とbの場合を試す。
aiのiの偶奇それぞれにおいて本来あるべき文字と異なる文字の数を数え、その最大値を求めればよい。(swapで両方減らせるから)
感想
swapは隣り合うものだけ許されてるのだと勘違いして1WAしたので反省。(この勘違い、たまにする)
コード
#include <bits/stdc++.h> #define rep(i,n) for(int i = 0; i < n; i++) #define PI 3.1415926535897932384626433832795028841971 #define INF 100000000 #define EPS 1e-10 #define MOD 1000000007 using namespace std; typedef long long ll; typedef pair<int,int> P; int n; string str; int main(){ cin >> n; cin >> str; int ans = 0; int a1 = 0, a2 = 0; string s = str; rep(i,n){ if(i%2){ if(s[i]!='r'){ a1++; } } else{ if(s[i]!='b'){ a2++; } } } ans = max(a1,a2); int cnt = 0; s = str; a1 = 0; a2 = 0; rep(i,n){ if(i%2){ if(s[i]!='b'){ a1++; } } else{ if(s[i]!='r'){ a2++; } } } cnt = max(a1,a2); cout << min(ans,cnt); }
C. Efim and Strange Grade
問題文
解法
小数点第一位から順に5以上の数がないかどうかチェックしていき、もし存在したらそこから大きい桁に許されているだけ繰り上げていけばよい。
9のときに繰り上がりがきたら四捨五入しないで繰り上がるということや、9.9のようなときに新たな桁が現れること、整数になることもあるということに気を付ける。
感想
やるだけ。
コード
#include <bits/stdc++.h> #define rep(i,n) for(int i = 0; i < n; i++) #define PI 3.1415926535897932384626433832795028841971 #define INF 100000000 #define EPS 1e-10 #define MOD 1000000007 using namespace std; typedef long long ll; typedef pair<int,int> P; int n, t; string str; char input[200001]; int main(){ cin >> n >> t; scanf("%s",input); str = input; string tmp = "0"; str = tmp+str; bool st = false; bool up = false; bool in = false; int en = str.size(); for(int i = 1; i < str.size(); i++){ if(!st){ if(str[i] != '.'){ continue; } st = true; continue; } if(str[i]-'0' >= 5){ up = true; int j = i; while(str[j]-'0'>=5 && t > 0){ en = j; t--; if(str[j-1] == '.'){ in = true; str[j-2]++; j -= 2; t = 0; } else{ str[j-1]++; j -= 1; } while(str[j] > '9'){ str[j] = '0'; str[j-1]++; j--; } } break; } } if(!st){ rep(i,str.size()){ if(i == 0) continue; printf("%c",str[i]); } return 0; } rep(i,str.size()){ if(i == 0 && str[0] == '0'){ continue; } if(i == en){ break; } if(str[i] == '.' && in == true){ break; } printf("%c",str[i]); } printf("\n"); }
D.
問題文
解法
感想
幻の問題。不可能問題らしい。
これに時間をずっと使っていたのでE解けなくてつらい(解けるとは言ってない)。
コード
E. Sasha and Array
問題文
解法
フィボナッチ数の第n項は行列累乗で求まるので、スターリースカイツリーに行列を乗せれば解ける。
感想
解法自体は思いつくのは一瞬だけどコンテスト中には時間がなすぎた。
今度通す。