ABC339に参加しました。
他の回と比較してB問題がちょっとめんどくさい回だった印象。
D問題が難しそうだったので、E問題を選択して解こうとしていた。
（D問題が水色DiffでE問題が緑Diffなので結果的にこの選択自体は正しかった）
が、E問題は時間内に正解できず、
結局成績は、最低目標の３完。
A TLD
#include<bits/stdc++.h>
using namespace std;
int main(){
std::string S;
std::cin >> S;
std::vector<char> ans;
for(int i=0; i<S.size(); i++){
if(S[i] == '.') ans.clear();
else ans.push_back(S[i]);
}
for(int i=0; i<ans.size(); i++) std::cout << ans[i];
std::cout << std::endl;
}B Langton’s Takahashi
#include<bits/stdc++.h>
using namespace std;
int dx[4] = {0, 1, 0, -1};
int dy[4] = {-1, 0, 1, 0};
int main(){
int H,W,N;
std::cin >> H >> W >> N;
std::vector<std::vector<char>> Grid(H, std::vector<char>(W, '.'));
// for(int h=0; h<H; h++) for(int w=0; w<W; w++) Grid[h][w] = '.';
int now_direction = 0;
int now_h = 0;
int now_w = 0;
for(int n=0; n<N; n++){
if(now_h<0) now_h = H-1;
if(H<=now_h) now_h = 0;
if(now_w<0) now_w = W-1;
if(W<=now_w) now_w = 0;
if(Grid[now_h][now_w] == '.'){
now_direction++;
Grid[now_h][now_w] = '#';
}
else{
now_direction--;
if(now_direction < 0) now_direction = 3;
Grid[now_h][now_w] = '.';
}
now_direction %= 4;
now_h += dy[now_direction];
now_w += dx[now_direction];
// std::cout << now_h << now_w << std::endl;
}
for(int h=0; h<H; h++) {
for(int w=0; w<W; w++) std::cout << Grid[h][w];
std::cout << std::endl;
}
}C Perfect Bus
各（停車）回の累積和を計算し、「累積和の最後尾」-「累積和の最小値」をすると答えが分かる。
#include<bits/stdc++.h>
using namespace std;
int main(){
int N;
std::cin >> N;
std::vector<long long> A(N,0);
for(int n=0; n<N; n++) std::cin >> A[n];
std::vector<long long> Sum(N+1, 0);
for(int n=0; n<N; n++) Sum[n+1]=Sum[n]+A[n];
long long min_val = * min_element(Sum.begin(), Sum.end());
std::cout << Sum[N]-(min_val) << std::endl;
}D Synchronized Players
Player１とPlayer２が(i,j)で合流できる場合の最小移動回数をBFSで求める問題。
Player１とPlayer２が連動して動くので、1Player分の座標情報×2＝4次元のマトリックスを考える点が特徴。
#include <iostream>
#include <vector>
#include <queue>
#include <array>
#define INF (1LL<<30)
int dx[3] = { -1, 0, 1 };
int dy[3] = { -1, 0, 1 };
int main() {
int N;
std::cin >> N;
std::vector<std::vector<char>> S(N, std::vector<char>(N));
int x1 = -1, y1 = -1, x2 = -1, y2 = -1;
for (int row = 0; row < N; row++) for (int col = 0; col < N; col++) {
char c;
std::cin >> c;
S[row][col] = c;
if (c == 'P') {
if (x1 == -1) {
x1 = col;
y1 = row;
}
else {
x2 = col;
y2 = row;
}
}
}
/*
* Player１とPlayer２がシンクロして動き、両者の状態を管理するため４次元のマトリックスを使う
*/
std::vector<std::vector<std::vector<std::vector<int>>>> distance(N,
std::vector<std::vector<std::vector<int>>>(N,
std::vector<std::vector<int>>(N,
std::vector<int>(N, INF))));
distance[y1][x1][y2][x2] = 0;
//BFS
std::queue<std::array<int, 4>> q;
q.push({ x1,y1,x2,y2 });
while (0 < q.size()) {
std::array<int, 4> tmp = q.front(); q.pop();
for (auto x : dx) {
for (auto y : dy) {
if ((x == 0) && (y == 0)) continue;
if ((x != 0) && (y != 0)) continue;//今回はナナメ移動できない
//Player1
int tmp_x1 = tmp[0] + x;
int tmp_y1 = tmp[1] + y;
if ((tmp_x1 < 0) || (N <= tmp_x1)) {
tmp_x1 -= x; tmp_y1 -= y;
}
else if ((tmp_y1 < 0) || (N <= tmp_y1)) {
tmp_x1 -= x; tmp_y1 -= y;
}
else if (S[tmp_y1][tmp_x1] == '#') {
tmp_x1 -= x; tmp_y1 -= y;
}
//Player2
int tmp_x2 = tmp[2] + x;
int tmp_y2 = tmp[3] + y;
if ((tmp_x2 < 0) || (N <= tmp_x2)) {
tmp_x2 -= x; tmp_y2 -= y;
}
else if ((tmp_y2 < 0) || (N <= tmp_y2)) {
tmp_x2 -= x; tmp_y2 -= y;
}
else if (S[tmp_y2][tmp_x2] == '#') {
tmp_x2 -= x; tmp_y2 -= y;
}
if (distance[tmp_y1][tmp_x1][tmp_y2][tmp_x2] == INF) {
//std::cout << tmp_y1 << tmp_x1 << tmp_y2 << tmp_x2 << std::endl;
//std::cout << tmp[1] << tmp[0] << tmp[3] << tmp[2] << std::endl;
distance[tmp_y1][tmp_x1][tmp_y2][tmp_x2] = distance[tmp[1]][tmp[0]][tmp[3]][tmp[2]] + 1;
q.push({ tmp_x1, tmp_y1,tmp_x2, tmp_y2 });
}
}
}
}
int ans = INF;
for (int row = 0; row < N; row++) {
for (int col = 0; col < N; col++) {
ans = std::min(ans, distance[row][col][row][col]);
}
}
std::cout << (ans == INF ? -1 : ans) << std::endl;
}E Smooth Subsequence
コメント