悔しかったので戒めの意を込めて投稿。
成績は３完、D問題で時間切れ。
A 202<s>3</s>
割愛します。
#include<bits/stdc++.h>
using namespace std;
int main () {
string S;
std::cin >> S;
S[S.size()-1]='4';
std::cout << S << std::endl;
}
B Tetrahedral Number
割愛します。
#include<bits/stdc++.h>
using namespace std;
int main () {
int N;
std::cin >> N;
for(int x=0; x<=N; x++){
for(int y=0; y<=N-x; y++){
for(int z=0; z<=N-x-y; z++){
std::cout << x << " " << y << " " << z << std::endl;
}
}
}
}
C Loong Tracking
この問題にまあまあ時間取られたのが今回の大きな敗因。
#include<bits/stdc++.h>
using namespace std;
void move_dragon(std::vector<std::vector<int>> d){
for(int i=d.size(); i>0; i--){
d[i][0] = d[i-1][0];
d[i][1] = d[i-1][1];
}
}
int main () {
int N,Q;
std::cin >> N >> Q;
int query_tmp = 0;
string command;
int part_no = 0;
int move_count = 0;
int x=1;
int y=0;
std::vector<std::vector<int>> MovedPoints;
MovedPoints.push_back({x,y});
for(int q=0; q<Q; q++){
std::cin >> query_tmp;
if(query_tmp == 1){
std::cin >> command;
if(command == "U"){
y++;
}
else if(command == "R"){
x++;
}
else if(command == "D"){
y--;
}
else{
x--;
// std::cout << "Left";
}
MovedPoints.push_back({x,y});
move_count++;
}
else{
std::cin >> part_no;
if(move_count < part_no){
std::cout << part_no-move_count << " 0" << std::endl;
}
else{
std::cout << MovedPoints[move_count-(part_no-1)][0] << " " << MovedPoints[move_count-(part_no-1)][1] << std::endl;;
}
}
}
}
頭の固そうな実装になってしまった。
dequeなるものを使っている他人の解法を見て、
「ああ～そうだよな～」と感心した。
もっと頭良くLIFOの何かを使って実装した方がスマート。
D Loong and Takahashi
愚直にBFSを実装しようとして時間切れ。。
解法は脳内で構築できていただけに悔しい問題だった。
#include <iostream>
#include <vector>
#include <queue>
int dx[3] = { -1, 0, 1 };
int dy[3] = { -1, 0, 1 };
int main()
{
int N;
std::cin >> N;
std::vector<std::vector<std::pair<int, bool>>> Grid(N, std::vector<std::pair<int, bool>>(N));
bool is_found_ans = false;
while (is_found_ans == false) {
for (int row = 0; row < N; row++) {
for (int col = 0; col < N; col++) {
Grid[row][col] = std::make_pair(1, false);
}
}
std::queue<std::pair<int, int>> q;
q.push({ 0, 0 });
Grid[0][0].second = true;
int part_sum_no = 1;
while (0 < q.size()) {
std::pair<int, int> tmp = q.front();
q.pop();
int tmp_row, tmp_col;
bool is_next_que = false;
for (auto x : dx) {
for (auto y : dy) {
if (is_next_que == true) {
continue;
}
if ((x == 0) && (y == 0)) {
continue;
}
if ((x != 0) && (y != 0)) {
continue;
}
tmp_row = tmp.first + x;
tmp_col = tmp.second + y;
if ((tmp_row < 0) || (N <= tmp_row)) {
continue;
}
if ((tmp_col < 0) || (N <= tmp_col)) {
continue;
}
if ((tmp_row == ((N - 1) / 2)) && (tmp_col == ((N - 1) / 2))) {
continue;
}
if (Grid[tmp_row][tmp_col].second == false) {
Grid[tmp_row][tmp_col].second = true;
Grid[tmp_row][tmp_col].first += part_sum_no;
part_sum_no++;
q.push({ tmp_row, tmp_col });
is_next_que = true;
}
}
}
if (part_sum_no >= (N*N) - 1) {
is_found_ans = true;
}
}
}
for (int row = 0; row < N; row++) {
for (int col = 0; col < N; col++) {
if ((row == ((N - 1) / 2)) && (col == ((N - 1) / 2))) {
std::cout << "T" << " ";
}
else {
std::cout << Grid[row][col].first << " ";
}
}
std::cout << std::endl;
}
}
終わりに
反省点は２点。
１点目は、これくらいのコードはササっと書けるようにならなくてはいけない。
２点目は、そもそもコードが長い。
公式解説や他人の参加記ではめちゃくちゃ簡単な解法が載っていたが、自分は実直にBFSで解こうとしていた。
ここら辺の思考力（問題を単純化する能力含む）を鍛えなくてはならないと反省。
コメント