Panasonicの名を関したコンテスト毎回冷えてる（なんで？）
— ボンド@競プロ (@bond_cmprog) March 27, 2021
Bondo416さんのAtCoder Beginner Contest 197（Sponsored by Panasonic）での成績：2742位
パフォーマンス：869相当
レーティング：1445→1399 (-46) :(#AtCoder #ABC197（SponsoredbyPanasonic） https://t.co/GK44sfmRus
A - Rotate
$ S[1]S[2]S[0] $ を出力
提出コード
void solve(){ string S; cin >> S; cout << S[1] << S[2] << S[0] << endl; }
B - Visibility
マス $ (X, Y) $ から上下左右に#にぶつかるまでのマスの個数を数える
提出コード
void solve(){ int H, W, X, Y; cin >> H >> W >> X >> Y; X--,Y--; vector<string> S(H); REP(i,H) cin >> S[i]; int ans = 1; for(int i=X+1;i<H;i++){ if(S[i][Y] == '#') break; ans++; } for(int i=X-1;i>=0;i--){ if(S[i][Y] == '#') break; ans++; } for(int i=Y+1;i<W;i++){ if(S[X][i] == '#') break; ans++; } for(int i=Y-1;i>=0;i--){ if(S[X][i] == '#') break; ans++; } cout << ans << endl; }
C - ORXOR
どの箇所に仕切りを入れるかどうかをbit全探索をする
提出コード
void solve(){ int N; cin >> N; vector<ll> A(N); REP(i,N) cin >> A[i]; ll ans = LINF; REP(i,1<<N){ ll cur = 0; ll sum = 0; REP(j,N){ cur |= A[j]; if(i >> j & 1){ sum ^= cur; cur = 0; } } sum ^= cur; chmin(ans, sum); } cout << ans << endl; }
D - Opposite
正 $ N $ 角形の中心 $ (x, y) $を考える
$ (x, y) = \left(\frac{x_0 + x_{\frac{N}{2}}}{2}, \frac{y_0 + y_{\frac{N}{2}}}{2} \right)$ となるので、$ (x_0 - x, y_0 - y) $ として(x, y)を原点とした時の $ (x_0, y_0) $ を考える
この時、$ (x_1, y_1) $ は $ (x_0, y_0) $ を $ \theta = \frac{2\pi}{N} $ だけ原点を中心に回転させたものとなる
あとはこの座標を求めたあとにもとの座標に戻して上げればいい
提出コード
void solve(){ double N; cin >> N; double x0, y0, x2, y2; cin >> x0 >> y0 >> x2 >> y2; double x = (x2 + x0) / 2.0; double y = (y2 + y0) / 2.0; double x1 = x + (x0 - x)*cos(2.0*PI/N) - (y0 - y)*sin(2.0*PI/N); double y1 = y + (x0 - x)*sin(2.0*PI/N) + (y0 - y)*cos(2.0*PI/N); printf("%.12lf %.12lf\n", x1, y1); }
E - Traveler
色 $ i $ のボールをすべて取り終わったときにどこにいるかを考えると色 $ i $ のボールが置いてある最小の座標と最大の座標のどちらかであるのでその2つのみを考えればいい
そのため次のようなDPを考えればいい
$ dp[i][j] := $ 色 $ i $ のボールをすべて取り終わったときに一番左端 $ (j=0) $ にいる、一番右端にいる$ (j=1) $ ときの最小のコストとしてDPをする
提出コード
void solve(){ ll N; cin >> N; vector<ll> X(N), C(N); map<ll, vector<ll>> mp; Compress<ll> cmp; cmp.add(0); REP(i,N){ cin >> X[i] >> C[i]; cmp.add(C[i]); } cmp.build(); REP(i,N) mp[cmp.get(C[i])].emplace_back(X[i]); for(auto &[k, v] : mp){ sort(v.begin(), v.end()); } mp[0].emplace_back(0); auto f = [&](ll a, ll b) -> ll{ return abs(a - b); }; int sz = mp.size(); vector<vector<ll>> dp(sz+1, vector<ll>(2, LINF)); dp[0][0] = dp[0][1] = 0; for(int i=1;i<sz;i++){ auto curMi = mp[i].front(); auto curMa = mp[i].back(); auto preMi = mp[i-1].front(); auto preMa = mp[i-1].back(); ll dist = f(curMa, curMi); chmin(dp[i][0], dp[i-1][0] + f(preMi, curMa) + dist); // mi -> ma -> mi chmin(dp[i][0], dp[i-1][1] + f(preMa, curMa) + dist); // ma -> ma -> mi chmin(dp[i][1], dp[i-1][0] + f(preMi, curMi) + dist); // mi -> mi -> ma chmin(dp[i][1], dp[i-1][1] + f(preMa, curMi) + dist); // ma -> mi -> ma } cout << min(dp[sz-1][0] + abs(mp[sz-1].front()), dp[sz-1][1]+abs(mp[sz-1].back())) << endl; }
F - Construct a Palindrome
頂点 $ 1 $ と 頂点 $ N $ に置かれた2つのコマが同じ文字の辺を通って合流もしくは隣接した頂点にたどり着くことを考える
$ dist[a][b] := a $ と $ b $ にそれぞれコマがある状態で、かつ同じ文字の辺を通ってきた状態での最短距離としてbfsなどで求める
そうすると偶数長の場合は最終的に同じ頂点にいるので $ 2 \times dist[i][i] $ の最小、奇数長の場合、隣接した頂点にいるので 頂点 $ i $ と辺で繋がっている頂点を $ nv $ とすると $ 2 \times dp[i][nv] + 1 $ の最小が答えとなる
提出コード
int N, M;
cin >> N >> M;
vector<vector<pair<int, int>>> edge(N);
REP(i,M){
int a, b;
char c;
cin >> a >> b >> c;
--a, --b;
edge[a].emplace_back(b, c-'a');
edge[b].emplace_back(a, c-'a');
}
vector dist(N, vector(N, INF));
dist[0][N-1] = 0;
queue<pair<int, int>> q;
q.emplace(0, N-1);
while(!q.empty()){
auto [a, b] = q.front(); q.pop();
for(auto [na, c1] : edge[a]) for(auto [nb, c2] : edge[b]){
if(c1 != c2) continue;
if(dist[na][nb] < INF) continue;
dist[na][nb] = dist[a][b] + 1;
q.emplace(na, nb);
}
}
int ans = INF;
REP(i,N){
chmin(ans, dist[i][i] * 2);
for(auto [nv, c] : edge[i]){
chmin(ans, dist[i][nv] * 2 + 1);
}
}
if(ans == INF) ans = -1;
cout << ans << endl;
}
