はじめに
ABC335に参加したのでその振り返り。
A問
今回のA問は、単純だったが少し悩んだ。
というのもC++の関数について知識がなかったため。
回答内容は以下。
ソースコード
#include<bits/stdc++.h>
using namespace std;
int main(void){
string S;
cin >> S;
S.pop_back();
cout << S << "4" << endl;
}
標準入力からSを受け取り、それの最後の文字を"4"に置き換える。
"2023"→"2024"でなく、文字通り末尾のみ変更すればよい。
末尾のみ削除する関数があったはず、という記憶があったのでググってみたところ
pop_back()関数についての記事を発見。
15分ほどで提出し、AC(正解)。
公式解説にあったpush_back()関数については全く知らなかったため、上記のように出力の際に"4"を結び付けておくようにした。
C++についての知識が欠乏しているので、AtCoder公式が用意してくれている以下教材を学んでいきたいところ。
B問
今回は比較的簡単だった。本番で初めてB問が解けた。 やったね。
回答内容は以下。
ソースコード
#include<bits/stdc++.h>
using namespace std;
int main(void){
int N;
cin >> N;
for(int i = 0; i <= N; ++i){
for(int j = 0; j <= N; ++j){
for(int k = 0; k <= N; ++k){
int l = i + j + k;
if(l <= N){
cout << i << " " << j << " " << k << endl;
}
}
}
}
}
標準入力からNを受け取り、x + y + z ≦ N となるx, y, zを求める。
N ≦ 21、ということで3重ループにして計算させても、リソースへの負担は少量で済む。
つまり全探索でOK。
辞書的に小さい順で組み合わせを出力するのが条件なので、
zが最も内側の入れ子になるようにループを用意してあげればよい。
一番内側のループで変数lを宣言してやり、それがN以下であれば出力するように。
今回のB問はそこまで難しくなかった。
終わって気づいたが、for文内の各変数、x, y, zとそのまま設定した方が可読性が高かったと思う。
C問
初のC問挑戦となった。
過去問でもまだC問は手を付けていなかったため、ぶっつけ本番。
結果から言うと、時間内に回答できなかった。
回答内容は以下。
警告
勿論ですが以下のコードを実行しても解けません！
ソースコード
#include<bits/stdc++.h>
using namespace std;
class Point
{
public:
int x;
int y;
Point() {} // 初期化は何もしない
Point(int x0, int y0)
{
x = x0;
y = y0;
}
Point operator + (const Point& p0) const
{
Point p1;
p1.x = x + p0.x;
p1.y = y + p0.y;
return p1;
}
void answer()
{
cout << x << " " << y << endl;
}
};
int main(void){
int N_numberOfParts;
int Q_numberOfQuery;
cin >> N_numberOfParts >> Q_numberOfQuery;
vector<Point> positionOfParts(N_numberOfParts);
for(int i = 1; i <= N_numberOfParts; ++i){
Point p(i, 0);
positionOfParts.push_back(p);
}
vector<vector<string>> query(Q_numberOfQuery, vector<string>(1));
for (int i = 0; i < Q_numberOfQuery; ++i){
cin >> query[Q_numberOfQuery][0] >> query[Q_numberOfQuery][1];
}
for(int i = 0; i < Q_numberOfQuery; ++i){
if(query[i][0] == "1"){
if(query[i][1] == "R"){
for(int j = N_numberOfParts - 1; j >= 1; --j){
positionOfParts[j - 1] = positionOfParts[j];
}
Point q(1, 0);
positionOfParts[0] = positionOfParts[0] + q;
}else if(query[i][1] == "L"){
for(int j = N_numberOfParts - 1; j >= 1; --j){
positionOfParts[j - 1] = positionOfParts[j];
}
Point q(-1, 0);
positionOfParts[0] = positionOfParts[0] + q;
}else if(query[i][1] == "U"){
for(int j = N_numberOfParts - 1; j >= 1; --j){
positionOfParts[j - 1] = positionOfParts[j];
}
Point q(0, 1);
positionOfParts[0] = positionOfParts[0] + q;
}else if(query[i][1] == "D"){
for(int j = N_numberOfParts - 1; j >= 1; --j){
positionOfParts[j - 1] = positionOfParts[j];
}
Point q(0, -1);
positionOfParts[0] = positionOfParts[0] + q;
}
}
else{
int m = stoi(query[i][1]);
positionOfParts[m].answer();
}
}
return 0;
}
考え方として、Pointというクラスを作成し、各パーツの位置を座標点としてインスタンスで保持させようとした。
以下の記事が参考になった。
あとはクエリの内容を判別し、頭をどの方向へ向かわせるかを決定。
そして残りのパーツの座標をひとつ前のパーツが持っていた情報に更新する……という流れ。
時間内に何とか間に合わせたかったが、時間切れ。
解説を見て
2024/01/09追記
ただ、公式解説によるとdequeなる要素が用いられていた。
ここでもC++の知識がないことが足を引っ張った。
その理解は後回しにするとして、とりあえず自分なりの解法を完成させてみた。
ソースコード
#include <iostream>
#include <vector>
using namespace std;
class Point {
public:
int x;
int y;
Point() : x(0), y(0) {}
Point(int x0, int y0) : x(x0), y(y0) {}
Point operator+(const Point& p0) const {
return Point(x + p0.x, y + p0.y);
}
void answer() {
cout << x << " " << y << endl;
}
};
int main() {
int N_numberOfParts;
int Q_numberOfQuery;
cin >> N_numberOfParts >> Q_numberOfQuery;
vector<Point> positionOfParts;
for (int i = 0; i < N_numberOfParts; ++i) {
Point p(i + 1, 0);
positionOfParts.push_back(p);
}
vector<vector<string>> query(Q_numberOfQuery, vector<string>(2));
for (int i = 0; i < Q_numberOfQuery; ++i) {
cin >> query[i][0] >> query[i][1];
}
for (int i = 0; i < Q_numberOfQuery; ++i) {
if (query[i][0] == "1") {
if (query[i][1] == "R") {
for (int j = N_numberOfParts - 1; j >= 1; --j) {
positionOfParts[j] = positionOfParts[j - 1];
}
Point q(1, 0);
positionOfParts[0] = positionOfParts[0] + q;
} else if (query[i][1] == "L") {
for (int j = N_numberOfParts - 1; j >= 1; --j) {
positionOfParts[j] = positionOfParts[j - 1];
}
Point q(-1, 0);
positionOfParts[0] = positionOfParts[0] + q;
} else if (query[i][1] == "U") {
for (int j = N_numberOfParts - 1; j >= 1; --j) {
positionOfParts[j] = positionOfParts[j - 1];
}
Point q(0, 1);
positionOfParts[0] = positionOfParts[0] + q;
} else if (query[i][1] == "D") {
for (int j = N_numberOfParts - 1; j >= 1; --j) {
positionOfParts[j] = positionOfParts[j - 1];
}
Point q(0, -1);
positionOfParts[0] = positionOfParts[0] + q;
}
} else {
int m = stoi(query[i][1]);
positionOfParts[m - 1].answer();
}
}
return 0;
}
入力例と共に実行してみると、正しい出力例が出た！
やったねと思って提出してみると、残念ながら一部の回答でTLE(実行時間制限超過)。
恐らく各パーツごとにインスタンスを生成してしまっているから、
問題によってはメモリを食ってしまっている模様。
ACになっている回答もあり、それは実行時間・メモリ共に負荷が低かったため、そのように想定。
最近はC問からアルゴリズムを活用しないと解けない、と耳にしたので、
その洗礼を受けた形だった。
ともかく自分なりのupsolveはできた。
振り返り
今回のABCでは、初めて試験時間ずっとエディタとにらめっこしていた。
これまで大抵、問題が解けなくなったことで気分転換に家事など挟んでいた。
それが今回はずっとコーディングに向かい合うことができた。
少し進歩したかもしれない。