ABC197に参加しました
AtCoderのコンテストに参加した際の結果と考え方、反省点などを書いていきます。
コンテストページはこちら
解いた/挑んだ問題
A問題
問題の概要
長さ文字の文字列が与えられます。
の先頭の文字を末尾に移動したを出力してください
制約
- は英小文字からなる長さ3の文字列
どのように考えたか
文字列の2番目、3番目、1番目で出力すればいいなと思った
結果
・提出したコード
#include<bits/stdc++.h> #include<atcoder/all> #define rep(i, n) for (long long i = 0; i < (long long)(n); i++) #define REP(i,v,n) for(long long i = v; i <= (long long)(n); i++) #define rrep(i,n) for(long long i = n;0 <= (long long)(i); i--) #define RREP(i,n,v) for(long long i = n;v <= (long long)(i); i--) #define all(v) v.begin(), v.end() #define rall(v) v.rbegin(), v.rend() template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; } template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; } using namespace std; using namespace atcoder; using ll = long long; using pi = pair<int, int>; ll pows(ll x, ll n) {ll ret = 1;while (n > 0) {if (n & 1) ret *= x;x *= x;n >>= 1;}return ret;} int main() { string s; cin >> s; cout << s[1] << s[2] << s[0] << endl; return 0; }
間違えなくてよかった
ACまでの時間
ACしたのはコンテスト開始から1分後です。
B問題
問題の概要
縦,横列のマス目があり、いくつかのマスには障害物が置いてあります。
上から番目、左から番目のマスをと表すこととします。
個の文字列が与えられ、の番目はマスを表します。
障害物は # で表され、障害物がない場合は . で表されます。
今マス目にいて、一回まで上下左右に障害物がない限り移動することができます。
到達できるマスの数を出力してください(現在マスを含む)
制約
- は . 及び # からのみなる長さの文字列
- マスに障害物は置かれていない
どのように考えたか
今いるマスから上下左右に一度だけ進めるだけ進んで、進めた数カウントする
結果
一発AC
提出したコード
#include<bits/stdc++.h> #include<atcoder/all> #define rep(i, n) for (long long i = 0; i < (long long)(n); i++) #define REP(i,v,n) for(long long i = v; i <= (long long)(n); i++) #define rrep(i,n) for(long long i = n;0 <= (long long)(i); i--) #define RREP(i,n,v) for(long long i = n;v <= (long long)(i); i--) #define all(v) v.begin(), v.end() #define rall(v) v.rbegin(), v.rend() template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; } template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; } using namespace std; using namespace atcoder; using ll = long long; using pi = pair<int, int>; ll pows(ll x, ll n) {ll ret = 1;while (n > 0) {if (n & 1) ret *= x;x *= x;n >>= 1;}return ret;} int main() { int h,w,x,y,cnt=1; cin >> h >> w >> y >> x; vector<string>arr(h); rep(i,h)cin >> arr[i]; y--,x--; rrep(i,x)if(i && arr[y][i-1] == '.')cnt++;else break; REP(i,x+1,w-1)if(arr[y][i] == '.')cnt++; else break; rrep(i,y)if(i && arr[i-1][x] == '.')cnt++; else break; REP(i,y+1,h-1)if(arr[i][x] == '.')cnt++; else break; cout << cnt << endl; return 0; }
B問題にしては難しくないですか・・・?
ACまでの時間
ACしたのはコンテスト開始から13分後です。
C問題
問題の概要
長さの数列が与えられます。
この数列を1つ以上の空ではない連続した区間に分け、分けた各区間で区間内の数のビット単位ORを計算します。
こうして得られたすべての値のビット単位XORとして考えられる最小値を求めてください。
制約
- 入力は全て整数
どのように考えたか
制約がと小さいのでbit全探索ができそう
連続した区間を2進数の0と1で表現して、数値が変わったら区間を分けていくとよさそう
例) 5は2進数に直すと1001になるので [1] [0,0] [1]に分けられる
これを数列の添え字に直してのようにすることができる
後は分けた区間をXORして最小値を更新していく
結果
2回目でAC
・提出したコード
#include<bits/stdc++.h> #include<atcoder/all> #define rep(i, n) for (long long i = 0; i < (long long)(n); i++) #define REP(i,v,n) for(long long i = v; i <= (long long)(n); i++) #define rrep(i,n) for(long long i = n;0 <= (long long)(i); i--) #define RREP(i,n,v) for(long long i = n;v <= (long long)(i); i--) #define all(v) v.begin(), v.end() #define rall(v) v.rbegin(), v.rend() template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; } template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; } using namespace std; using namespace atcoder; using ll = long long; using pi = pair<int, int>; ll pows(ll x, ll n) {ll ret = 1;while (n > 0) {if (n & 1) ret *= x;x *= x;n >>= 1;}return ret;} int main() { ll n,pos,tmp,sum,ans=1001001001001001; cin >> n; vector<ll>arr(n); rep(i,n)cin >> arr[i]; for(int bit = 0;bit < (1 << n);bit++){ vector<int>res; pos = 1 & bit; tmp = arr[0]; REP(i,1,n-1){ if(pos == ((bit >> i) & 1))tmp |= arr[i]; else { pos = 1 - pos; res.push_back(tmp); tmp = arr[i]; } } res.push_back(tmp); sum = res[0]; REP(i,1,res.size()-1)sum ^=res[i]; chmin(ans,sum); } cout << ans << endl; return 0; }
bit全探索の少し変わった使い方な気がした
ACまでの時間
ACしたのはコンテスト開始から41分後。
結果
コンテスト結果
ABCの3完でした。
D以降は難しくて解けなかったです
パフォーマンス、レーティング変動
今回のパフォーマンスは802、前回より311も上がりまいました。
レーティングはそれに伴い+16の666となりました。
反省点
今回はC問題を早く解くことができず、その後のD問題もうまくいかなかったのでもっと早く解けるようになりたいです。