ABC282参加記録
Published on 2022-12-18Last Modified 2023-09-22
Table Of Contents
今週もABC参加してきた
こんにちは，冷凍うどんを食べようとしたら鍋の口が小っちゃくて入らなかったInです。
毎週ABCに参加し続けて，今回のABC282で5回目になりました。今週も結果報告と自分の忘備録を兼ねて記事を残しておきます。
結果報告のコーナー
まずはいつも通り結果報告からです。今回の提出状況はこのような感じでした。
まずB問題で問題文の読み間違えが発生して無駄に悩んだ挙句，C問題で3WAを出して爆死しました。はい。結果的にはABCの三完でした。何とか途中で修正できてよかったです。ちなみにD以降は私にはもうちんぷんかんぷんでした。
今回のコンテストによるレーティング変動は，以下の通りでした。ジャン！
コラ～～～～！！！！！！！
...ということで爆死でした。パフォーマンスは210で，今までで2番目に低い値を記録してしまいました。絶望感漂う中，記事を書いていきたいと思います。
もう終わりだよこの国
問題と解法
どんなふうに問題を解いたかを紹介します。
A問題
問題文は以下の通りでした。
与えられた整数Kの分だけ英大文字を出力する問題です。制約からZよりあとに関しては考えなくてもいいことが分かります。したがって，ASCIIコードを利用してprintf関数で標準出力に出力していけばオーケーです。
もう少し具体的に言うと，ASCIIコード表によると，英大文字は65番にAから始まって，90番にZまで順番に割り当てられています。したがって，ループ毎に1ずつ増やしていけばオーケーです。以下AC通ったコードです。
#include <stdio.h>
int main(void) {
int k;
scanf("%i", &k);
for(int i = 0; k > i; i++) {
printf("%c", 65 + i);
}
return 0;
}
最近のABCは毎回ASCIIコード表を見ながらやってる気がします。次B問題です。
B問題
問題文は以下の通りです。
N人の人が，コンテストに出題される各問題を解けるかどうかのデータが渡されます。参加者から2人を選んで，コンテストの問題をすべて解けるペアを作るとするとき，作ることができるペアの数を調べる問題です。
この時，作ることができるペアとは，「同時に作ることができるペア」ではないことに注意する必要があります。私はこれを勝手に同時に作ることができるペアの数のことだと勘違いして，永遠に悩んでいました。
また，この問題にはもう一つ注意する必要のある点があります。それは，ペアには順序を考えないことです。具体的には，ある一人を選んで，その人が一緒に組むことで全問正解できるようなペアをすべて列挙していくコードで解こうとすると，気を付けないとA-BのペアとB-Aのペアを区別してカウントしてしまうということが起こります。私はこの方針で解きましたが，前述の問題は，二重forループの二重目のループ変数を，一重目のループ変数で初期化することで対処しました。以下AC通ったコードです。
#include <stdio.h>
int main(void) {
int n, m; // nが人，mが問題
scanf("%i %i", &n, &m);
char s[n][31];
for(int i = 0; n > i; i++) {
scanf("%s", &s[i][0]);
}
int ans = 0;
char flag = 0;
for(int i = 0; n > i; i++) {
for(int j = i; n > j; j++) {
if(i == j) {
continue; //同じ番号同士は考えない
}
for(int k = 0; m > k; k++) {
if(s[i][k] == 'x' && s[j][k] == 'x') { //ダメだった
flag = 1;
break;
}
}
if(flag == 0) {
ans++; // 可能ペア発見
} else {
flag = 0; //戻す
}
}
}
printf("%i", ans);
return 0;
}
少し見にくいかもしれません。すみません。途中3重forループがありますが，最初の二つが人を選ぶところと対応しており，三つめが問題をすべて解けるかの判定になっています。
C問題
最後にC問題です。問題文は以下の通りです。
"に挟まれていない部分にのみ違う処理を施して，文字列を得る問題です。
正直，この問題はC問題の中では簡単なほうかなと思います。(簡単というのは，方針が思い浮かびやすいという意味です。)しかし，私はこの問題で大コケしてしまい，*順位が死にました。*結構ガチでショックです。
解法としては，文字列を配列で受け取り，"を発見したら，次の"までそのまま出力するようにするとオッケーです。この分岐の処理をいかに簡単にするかがキモだと思います。
まずは私がWAを出したクソコードを載せます。反面教師です。
#include <stdio.h>
int main(void) {
int n;
scanf("%i", &n);
char s[n];
scanf("%s", &s[0]);
for(int i = 0; n > i; i++) {
if(s[i] == '"') {
printf("%c", s[i]);
for(int j = i + 1; s[j] != '"'; j++) {
if(s[j] == ',') {
printf("%c", '.');
} else {
printf("%c", s[j]);
}
i++;
}
i++;
printf("%c", s[i]);
} else {
printf("%c", s[i]);
}
}
return 0;
}
まずはクソコードその一です。言うまでもなくこのコードの抱える一番の問題点は，とにかくごちゃごちゃしている点です。このコードはprintf関数を5回も使っており，いかに事前にどうやって組むかを考えていなかったかがバレバレです。また，もう一つの重大な欠点は問題の要求と逆の処理をしていることです。問題文の読み違えには気を付けよう！(公開ブログでゆうさくを貼れるほど度胸は無かった)
お次に，これをもう少し修正したけどダメだったコードです。
#include <stdio.h>
int main(void) {
int n;
scanf("%i", &n);
char s[n];
scanf("%s", &s[0]);
for(int i = 0; n > i; i++) {
if(s[i] == '"') {
printf("%c", s[i]);
i++;
for(; s[i] != '"'; i++) {
printf("%c", s[i]);
}
printf("%c", s[i]);
i++;
}
if(s[i] == ',') {
printf("%c", '.');
} else {
printf("%c", s[i]);
}
}
return 0;
}
このコードは，問題ページにあるテストケースは無事に突破しました。しかし，いまだ重大な問題を抱えています。それは*極端な入力に対してバッファーオーバーランが起こりえます。*これはヤバい(確信)
このコードは，最初に"が来たかどうかを判定して，来ていたら次の"までそのまま出力し続けるようにしてあります。これだけ聞くとまともそうですが，一番ダメなのはインクリメントを管理しきれていない点です。ループの途中に分岐点を作っていたりする関係上，コード中のあちこちでインクリメントが発生するせいでバグを追いきれませんでした。
例えば入力が""""だったりすると，余分なインクリメントが発生してバッファの外側に突き抜けます。そして次の"が見つかるまで止まることはありません。うーんこの
最後にAC通ったコードです。
#include <stdio.h>
int main(void) {
int n;
scanf("%i", &n);
char s[n];
scanf("%s", &s[0]);
for(int i = 0; n > i; i++) {
if(s[i] == '"') {
printf("%c", s[i]);
i++;
for(; s[i] != '"'; i++) {
printf("%c", s[i]);
}
printf("%c", s[i]);
continue;
}
if(s[i] == ',') {
printf("%c", '.');
} else {
printf("%c", s[i]);
}
}
return 0;
}
このコードはさっきのコードにcontinue処理を挟むことで(一時的なものですが)さっき挙げた不正なインクリメントを防止しています。
教訓:
インクリメントはわかりやすい場所で管理しよう。continueやbreakをちゃんと使おう。
完走した感想
今回のコンテストはかなり残念な感じになってしまいました。しかしとりあえずC問題まででも解けて良かったです。結構実装の技術的な点でコケることが多いなと感じているので，もっと問題数を解いてデバッグなどに慣れたいです。また，D問題以降は数学的知識や競プロ的な技術がかなり問われる問題かなと(一見)思いました。したがって，大学での数学の勉強などはしっかり頑張りたいです。(願望)
今回の結果はかなり来るものがあるけど，今日体調悪かったから多少はね？
ここまで読んでいただき，ありがとうございました。また次の記事でお会いしましょう。ちなみに一週間後のUECアドベントカレンダーに登録したはいいもののまだ一文字も書いていません(絶望)じゃあね。