Q&A
(無意味な文だったため削除)
前提・実現したいこと
https://atcoder.jp/contests/abs/tasks/arc065_a
atcoder begginnersselection第九問、白昼夢です。
問題文
英小文字からなる文字列 S が与えられます。 Tが空文字列である状態から始め、以下の操作を好きな回数繰り返すことで S=T とすることができるか判定してください。
T の末尾に dream dreamer erase eraser のいずれかを追加する。
制約
1≦∣S∣≦10^5
S は英小文字からなる。
入力
入力は以下の形式で標準入力から与えられる。
S
出力
S=T とすることができる場合 YES を、そうでない場合 NO を出力せよ。
入力例 1
erasedream
出力例 1
YES
erase dream の順で T の末尾に追加することで S=T とすることができます。
入力例 2
dreameraser
出力例 2
YES
dream eraser の順で T の末尾に追加することで S=T とすることができます。
入力例 3
dreamerer
出力例 3
NO
発生している問題・エラーメッセージ
oamke@DESKTOP-3PLG0UV ~/kyopuro/begineersselection $ gcc hakutyumu.c hakutyumu.c: In function 'main': hakutyumu.c:16:64: warning: passing argument 1 of 'strcat' from incompatible poi nter type [-Wincompatible-pointer-types] 16 | if(strncmp(s1, dreameraser, 10)==0){*s1=*s1+10; strcat(t, "dream eraser"); printf("%s", t);} | ^ | | | char ** In file included from hakutyumu.c:2: c:\mingw\include\string.h:75:40: note: expected 'char *' but argument is of type 'char **' 75 | _CRTIMP __cdecl __MINGW_NOTHROW char *strcat (char *, const char *); | ^~~~~~ hakutyumu.c:17:63: warning: passing argument 1 of 'strcat' from incompatible poi nter type [-Wincompatible-pointer-types] 17 | else if(strncmp(s1, dreamer, 7)==0){*s1=*s1+7; strcat(t, "dreame r");printf("%s", t);} | ^ | | | char ** In file included from hakutyumu.c:2: c:\mingw\include\string.h:75:40: note: expected 'char *' but argument is of type 'char **' 75 | _CRTIMP __cdecl __MINGW_NOTHROW char *strcat (char *, const char *); | ^~~~~~ hakutyumu.c:18:61: warning: passing argument 1 of 'strcat' from incompatible poi nter type [-Wincompatible-pointer-types] 18 | else if(strncmp(s1, dream, 5)==0){*s1=*s1+5; strcat(t, "dream"); printf("%s", t);} | ^ | | | char ** In file included from hakutyumu.c:2: c:\mingw\include\string.h:75:40: note: expected 'char *' but argument is of type 'char **' 75 | _CRTIMP __cdecl __MINGW_NOTHROW char *strcat (char *, const char *); | ^~~~~~ hakutyumu.c:19:62: warning: passing argument 1 of 'strcat' from incompatible poi nter type [-Wincompatible-pointer-types] 19 | else if(strncmp(s1, eraser, 6)==0){*s1=*s1+6; strcat(t, "eraser" );printf("%s", t);} | ^ | | | char ** In file included from hakutyumu.c:2: c:\mingw\include\string.h:75:40: note: expected 'char *' but argument is of type 'char **' 75 | _CRTIMP __cdecl __MINGW_NOTHROW char *strcat (char *, const char *); |
###実行結果
$ ./a.exe dreameraser nreameraserdreamerasernreameraserdreameraserNO
該当のソースコード
#include <stdio.h> #include <string.h> int main(){ char s[100000]; char *dream="dream"; char *dreamer="dreamer"; char *erase="erase"; char *eraser="eraser"; char *dreameraser="dreameraser"; char *s1; scanf("%s", &s); s1=s; char *t[] = {}; while(1){ if(strncmp(s1, dreameraser, 10)==0){*s1=*s1+10; strcat(t, "dreameraser"); printf("%s", t);} else if(strncmp(s1, dreamer, 7)==0){*s1=*s1+7; strcat(t, "dreamer");printf("%s", t);} else if(strncmp(s1, dream, 5)==0){*s1=*s1+5; strcat(t, "dream");printf("%s", t);} else if(strncmp(s1, eraser, 6)==0){*s1=*s1+6; strcat(t, "eraser");printf("%s", t);} else if(*s1=='\0'){printf("%s", t);printf("YES");break;} else{printf("%s", t);printf("NO");break;} } return 0; }
試したこと
上のコードの方針としては、文字列を比べて等しければ文字列tにその文字列を追加して、その文字数分ポインタに値を足して、繰り返しによって調べ続けるというものです。
文字列tがどうなっているか見るためにprintfで表示させました。
実行結果を見るとなぜか最初の文字がnになっています。なぜでしょうか。また、三回dreameraserと表示された後NOとなっているのがなぜかわかりません。ポインタの使い方が間違っているのでしょうか。
補足情報（FW/ツールのバージョンなど）
ここにより詳細な情報を記載してください。
回答2件
0
ベストアンサー
逆に問うような形になりますが，
char *t[] = {};
これはどういう意図の記述なのでしょうか？
- t の型って何型を想定しているのですか？
- 何やら配列っぽい記述ですが，配列の要素数はいくつになる想定なのですか？
…というのを考えてみては．
（すなわち，自身の意図とコード記述が一致してるのか？っていうのを．）
投稿2021/09/22 08:44
総合スコア11708
正直に言っておくと，
> char *t[] = {};
がコンパイル通って動作までこぎつけられるものなのか…？
その場合，この記述はどういう意味になるのか…？
私は知らない．
知らないけども，これを書いた質問者が意図した意味にはなっていないだろう，と想定するものである．
空文字列tを宣言したくて、やり方がいまいちわかっておらずこうなってしまいました。
コンパイルした際にstrcat関数で警告がでてきたのでtはポインタで表現したほうがよいのかな？と思って*をつけました、、
空文字列を宣言する方法が調べてもよくわからないのですが、サイズを大きくして一番最初の文字を終端文字にすればよいでしょうか？
char t[10000]; t[0]="\0";
でよいでしょうか、、？
あ、
char t[10000]; t[0]='\0';ですね、、。
そうしたら
$ ./a.exe
dreameraser
dreameraserdreameraserNO
と二回dreameraserがでてきてNOになりました。strcatでのポインタの使い方が違うのでしょうか
s,t のサイズが 10000 でOKなのか？（10001であるべきか？） という話もありそうですが，それはそれとして…
正直な感想を申し上げると，
atcoderのようなプログラミングパズルに取り組むのであれば，取り組むのに必要な最低限の基礎を先に学ぶ必要があるのではないか？ と思います．
（少なくとも文法面で苦労しない状態になってから挑戦した方が話が早いのではないかと．）
> *s1=*s1+10;
みたいなのが，どう動くのか？ を把握すると良いでしょう．
（各段階で文字列 s や s1 も出力してみれば，何が起きてるかわかるかもしれません）
> 各段階で文字列 s や s1 も出力してみれば…
問題の答えを求めるだけならば t は不要だけども，
ご自身のコードがどう動いているのか？を確認したくて t を用意しているんですよね？
であれば，同じように，実際今どうなってるの？ というのをいろいろ出力してみれば良いのです．
諸々があなたの意図通りに変化していってるのか？ というのを．
その際，printf の書式指定子が
"%s"
だと複数の表示がひとつながりになってしまって意味不明になるので
"%s\n"
とかして各表示毎に改行するようにするとよいでしょう．
（dreameraserdreameraserNO は，おそらく３つのprintfの結果がつながったものです）
また，各々の出力がコードのどの部分のprintfによるものなのか？ を明確にするように，
"どこの部分かわかる用の文字列：%s\n"
みたく，何か適当な表示を付けて把握できるようにすると良いでしょう．
せっかくの出力結果を自身で誤読しないように工夫しましょう．
本当にそうですよね。基礎から勉強しなおします。
そうですよね、終端文字を考えればsとtのサイズは10001ですよね。
char *s1=&s[0]; printf("%c", *s1);
としたところ*s1はdと表示されたのですが、*s1=*s1+10の値を変更させて表示させたところdからアルファベット順に+10したアルファベットが表示されてしまいました。
これを
for(i=0;i<11;i++){*s1++;}
と改善したところやりたいとおり、入力sの配列の値から11個移動させた文字を表示させることができました。なぜなのでしょうか。
ありがとうございます。改行活用します。
#include <stdio.h>
#include <string.h>
int main(){
int i;
char s[100001];
char *dream="dream";
char *dreamer="dreamer";
char *erase="erase";
char *eraser="eraser";
char *dreameraser="dreameraser";
scanf("%s", &s);
char *s1=&s[0]; printf("s[0]:%c\n", *s1);
char t[100001]; t[0]='\0';
while(1){
if(strncmp(s1, dreameraser, 11)==0){for(i=0;i<11;i++){*s1++;} printf("*s1:%c\n", *s1); strcat(t, "dreameraser"); printf("t:%s\n", t);}
else if(strncmp(s1, dreamer, 7)==0){for(i=0;i<7;i++){*s1++;} printf("*s1:%c\n", *s1); strcat(t, "dreamer");printf("t:%s\n", t);}
else if(strncmp(s1, dream, 5)==0){for(i=0;i<5;i++){*s1++;} printf("*s1:%c\n", *s1); strcat(t, "dream");printf("t:%s\n", t);}
else if(strncmp(s1, eraser, 6)==0){for(i=0;i<6;i++){*s1++;} printf("*s1:%c\n", *s1); strcat(t, "eraser");printf("t:%s\n", t);}
else if(strncmp(s1, erase, 5)==0){for(i=0;i<5;i++){*s1++;} printf("*s1:%c\n", *s1); strcat(t, "erase");printf("t:%s\n", t);}
else if(*s1=='\0'){printf("%s\n", t);printf("YES");break;}
else{printf("%s", t);printf("NO");break;}
}
return 0;
上のように改善したところ
$ gcc hakutyumu.c
oamke@DESKTOP-3PLG0UV ~/kyopuro/begineersselection
$ ./a.exe
erasedream
s[0]:e
*s1:d
t:erase
*s1:
t:erasedream
erasedream
YES
oamke@DESKTOP-3PLG0UV ~/kyopuro/begineersselection
$ ./a.exe
dreameraser
s[0]:d
*s1:
t:dreameraser
dreameraser
YES
oamke@DESKTOP-3PLG0UV ~/kyopuro/begineersselection
$ ./a.exe
dreamerer
s[0]:d
*s1:e
t:dreamer
dreamerNO
と求める結果が得られました。そしてprintfを消して入力例を試したところ、コードは
#include <stdio.h>
#include <string.h>
int main(){
int i;
char s[100001];
char *dream="dream";
char *dreamer="dreamer";
char *erase="erase";
char *eraser="eraser";
char *dreameraser="dreameraser";
scanf("%s", &s);
char *s1=&s[0];
char t[100001]; t[0]='\0';
while(1){
if(strncmp(s1, dreameraser, 11)==0){for(i=0;i<11;i++){*s1++;} strcat(t, "dreameraser"); }
else if(strncmp(s1, dreamer, 7)==0){for(i=0;i<7;i++){*s1++;} strcat(t, "dreamer");}
else if(strncmp(s1, dream, 5)==0){for(i=0;i<5;i++){*s1++;} strcat(t, "dream");}
else if(strncmp(s1, eraser, 6)==0){for(i=0;i<6;i++){*s1++;} strcat(t, "eraser");}
else if(strncmp(s1, erase, 5)==0){for(i=0;i<5;i++){*s1++;} strcat(t, "erase");}
else if(*s1=='\0'){printf("YES");break;}
else{printf("NO");break;}
}
return 0;
}
となり、実行結果は
oamke@DESKTOP-3PLG0UV ~/kyopuro/begineersselection
$ gcc hakutyumu.c
oamke@DESKTOP-3PLG0UV ~/kyopuro/begineersselection
$ ./a.exe
erasedream
YES
oamke@DESKTOP-3PLG0UV ~/kyopuro/begineersselection
$ ./a.exe
dreameraser
YES
oamke@DESKTOP-3PLG0UV ~/kyopuro/begineersselection
$ ./a.exe
dreamerer
NO
と正しい結果が得られました。
しかし、提出したところACを得られなかったので、再考します。
構文自体に問題はないけれども、このやり方だとdreameraseなどがNOとなってしまうので、やり方から再考します。ありがとうございました。
> *s1++;
これ，
(*s1)++;
なのか
*(s1++);
なのか，ご自身で把握できてますか？
文法ををちゃんと把握できているならこのように書かないと思いますので，
「なんとなく書いたらなんかわかんねーけどたまたま」動いた 的な状況になっているのではなかろうか？ と想像します．
＃まぁこれ以降に続きを書くとしたら，お決まりの「まずは基礎からどうの～」という話になりますので省略しますが．
0
解決済みですが面白い問題ですね。dreamer, eraser の語尾 "er" が erase, eraser の先頭２文字と同じなので、単純に４つの文字列で比較すると
dreameraser を dream + eraser とすべきところを deamer + aser と間違うことがある。そこで
dreameraser という文字列を作っておいて、まずこれと比較するようにした・・・惜しい。似たような考慮すべきパターンが他にもあるようです。それがACにならない原因じゃないでしょうか。
もう一つ、文字列 T に strcat() でつないでいく必要があるのか無いのか。判定 YES になら結果は S と同じになるので、判定には文字列をつなぐ必要はないのではないかという事。
でも、つなぐ必要があるとしても、strcat() を使うのは不利です。
strcat(t, "dream") の基本的な動作は、文字列 t の先頭から順に文字列の終端を探して、そこに "dream" 文字列をコピーする…こうして連結します。
質問者は短い文字列で動作確認していますが、最長 100000 文字にもなる可能性があるわけです。t に文字列をつないでいけば、strcat() する都度、終端を探す時間がどんどん伸びていくのは容易に想像できます。
strcat() するのではなく、文字列をつなぐ都度、文字列 t の終端位置を（も）更新する、そうすれば次につなぐときは終端位置から strcpy() するだけ。コード上はちょっとした違いですが、処理するデータによってはこのほうが断然軽くなります。
投稿2021/09/23 08:14
総合スコア1380
文字列Tに関しては，単にprintfデバッグ目的の物なのだと思います．
私の回答のコメント欄で，
> ご自身のコードがどう動いているのか？を確認したくて t を用意しているんですよね？
に対して，特に否定も無いようでしたので．
あなたの回答
tips
プレビュー
