ABC279参加してきた！
Published on 2022-11-27Last Modified 2023-09-22
Table Of Contents
はじめに
今回ABC279に参加してきましたので，その記録です。
今回の成績
まずは今回の成績からです。以下画像です。
AとBしか，解けませんでした！！！！(キース団長並感)
いや，文字列扱う問題多くないですか？？？？？？私は文字列を操作する練習を全然してなかったのでB問題で死ぬほど苦労しました...
今回はあまり語るようなことがないので，サクッと解法紹介と今回の反省のパートに行きたいと思います。
解法
(注意: 筆者はc言語使ってます。)まずはA問題からです。以下問題文です。
これは文字列を扱う練習みたいな問題ですね。「下に尖った部分」というのはvは1箇所，wは2箇所なので，文字列を最初から見ていって，「vの個数」×
1と「wの個数」×
2を足したものをprintf関数で標準出力で出したらオッケーですね。以下AC通ったコードです。
#include <stdio.h>
int main(void) {
char a[100];
scanf("%s", a);
int score = 0;
int i = 0;
while(a[i] != '\0') {
if(a[i] == 'v') {
score = score + 1;
} else if(a[i] == 'w') {
score = score + 2;
}
i++;
}
printf("%i\n", score);
return 0;
}
関係ない話ですが，問題の名前が「wwwvvvvvv」だったり問題文に平気で「尖っている部分」とか書いてあるのが地味にじわじわ来る問題ですね。
お次はB問題です。以下問題です。
この問題は全探索で解きました。簡単に流れを説明すると，まず最初に文字列Tの最初の文字を文字列Sの先頭から探します。見つかったら一文字ずつ後続も一致しているか確認して，もしTが'\0'(終端文字)になるまでずっと一致していたら，Sは条件を満たしていたということが分かるので，適当にフラグを立ててループを抜けます。ここで後続に一致しないものが存在した場合は，また先頭文字が一致するか順に確認していきます。このサイクルをSが終端文字になるまで続けてもフラグがたたなかった場合は，条件を満たさないということが分かります。以下AC通ったコードです。
#include <stdio.h>
int main(void) {
char S[101];
char T[101]; //比較する方
scanf("%s", S);
scanf("%s", T);
int flag = 0;
for(int i = 0; S[i] != '\0'; i++) {
if(T[0] == S[i]) {
int k = i;
int j = 0;
for(; S[k] == T[j] && T[j] != '\0';) {
k++;
j++;
}
if(T[j] == '\0') {
flag = 1;
}
}
}
if(flag == 1) {
printf("Yes\n");
} else {
printf("No\n");
}
return 0;
}
*この問題を通すのに本当に苦労しました。。。*実はこの問題を通すだけで今回1時間8分，WAを6回も出したことで私の順位がボロボロになりました。泣きそうです。
この問題では文字列を扱うときは必然と'\0'の検出が必要になるのですが，それを「whileの条件式で簡単にかけるやろw」とか思ってたらマジで痛い目見ました。とにかくループ用の変数がわちゃわちゃしてしまって，ループを抜けるときの条件式がぐちゃぐちゃになってしまったのが痛すぎました。。。泣きそうです(2回目)
もうwhileなんて使わない(知らんけど)
ちなみに，この問題でつまずいた理由はおそらく配列の余った要素がすべて0であることを見逃していたことだと思います。アホですか？
ラスト，ACは取れなかったもののC問題を紹介しておきます。以下問題です。
この問題は正直知識不足でした。せっかくですので私の行おうとした解法を説明します。
与えられた図形SとTが「列の並べ替え」によって一致すればよいということですので，受け取ったデータをリアルタイムに処理することはできなさそうです。したがって，いったん配列に保持することにしました。この問題では行番号と列番号の情報が重要ですので，二次元配列を用意して代入しました。そして，「並べ替え」によって同じものが作れるということは，「Sのある列」を持ってくると，常に必ず一つ以上「Tのある列」が一致しているという言い換えが可能です。これなら全探索により実装可能だと判断したので，この方針で行きました。実はこの探索方法，ほとんどB問題と同じです。一番ACに近かったコードです。
#include <stdio.h>
int main(void) {
int H, W; //Hは行数，Wは列数
scanf("%d %d", &H, &W);
char buffer;
int flag = 0;
int delflag = 0;
int ans = 0;
char S[H][W];
char T[H][W];
for(int i = 0; H > i; i++) {
for(int j = 0; W > j; j++) {
scanf(" %c", &buffer);
S[i][j] = buffer;
}
}
for(int i = 0; H > i; i++) {
for(int j = 0; W > j; j++) {
scanf(" %c", &buffer);
T[i][j] = buffer;
}
}
for(int i = 0; W > i; i++) {
for(int j = 0; W > j; j++) {
if(S[0][i] == T[0][j]) {
for(int k = 0; H > k; k++) {
if(S[k][i] != T[k][j]) {
flag = 1;
break;
}
}
if(flag != 1) {
for(int l = 0; H > l; l++) {
T[l][j] = 0;
}
delflag = 1;
break;
}
flag = 0;
}
}
if(delflag != 1) {
printf("No\n");
return 0;
}
}
for(int i = 0; W > i; i++) {
if(T[0][i] != 0) {
ans = 1;
break;
}
}
if(ans == 1) {
printf("No\n");
} else {
printf("Yes\n");
}
return 0;
}
このコードで最終的にTLEが2ケースでした。考え方自体は正解を出せるコードみたいです。
公式解説では，私のとった手順と似たようなものでしたが，最後の同じ列が存在するかの判定を「文字列のソート」にて実現していました。私は文字列の扱いに関してほとんど何もわかっていなかったので，選択肢にすらあがらなかったです。次頑張ります。
余談ですが，終了後に私のコードを見た並走者が，あまりのforループの深さにびっくりしていました。こんな頭の悪い全探索しか書けないの正直ね。。
*True Programer* only use for statement and if statement.(逆張り)
終わりに
正直にいうと，今回の結果は非常に悔しかったです。もっとほかの問題に時間をかけられると思っていたし，レーティングもあまり気にしていないとはいえ重要な指標の一つでしょう。「この悔しさをバネに～」みたいな文言めちゃくちゃ嫌いなんですが，今はそんな気分です。来週のABCに向けてできるだけ準備したいと思います。
今回解けなかったC問題はもう少し取り組んでみようと思います。もし解けたら追記します。
長文読んでいただきありがとうございました。