(ABC229-A, ABC250-A,ABC250-B)
特定の値を持つマスが辺で隣接しているか
ABC229-A
問題概要
2x2の格子が与えられる。その格子の中の全ての#が辺で隣接しているか。
解答
a=Array.new(2){Array.new(2)}
(0...2).each do |i|
a[i]=gets.chomp.split("").to_a
end
ans="No"
n=0
(0...2).each do |i|
(0...2).each do |j|
if a[i][j]=="#" then
n+=1
end
end
end
if n==3 or n==4 then
ans="Yes"
end
if n==2 then
if a[0][0]=="#" and a[1][1]=="#" then
ans="No"
elsif a[0][1]=="#" and a[1][0]=="#" then
ans="No"
else
ans="Yes"
end
end
puts ans
上がコンテスト中に提出したコード。(2021-11-27 21:12:32)
Cで書いたのが以下。(2024-11-06 22:20:45)
#include<stdio.h>
#include<stdlib.h>
#define N1 4
int main(void){
char* s=(char*)malloc(sizeof(char)*N1);
if (s==NULL){
printf("memory allocation to s failed.\n");
exit(1);
}
char *ts=fgets(s,N1,stdin);
if(ts==NULL){
printf("fgets(s) failed\n");
exit(1);
}
char* s2=(char*)malloc(sizeof(char)*N1);
if (s2==NULL){
printf("memory allocation to sw failed.\n");
exit(1);
}
char *ts2=fgets(s2,N1,stdin);
if(ts2==NULL){
printf("fgets(s2) failed\n");
exit(1);
}
if(*s==35 && *s2==35 || *s==35 && *(s+1)==35 || *(s+1)==35 && *(s2+1)==35 || *s2==35 && *(s2+1)==35){
printf("Yes\n");
exit(0);
}
printf("No\n");
return 0;
}
各マスが#か.かどうかで、4マスでは2^4=16通りのパターンが考えられるが、そのうち、全ての#が辺で隣接しているのは、((0,0),(0,1)), ((0,0),(1,0), ((1,0),(1,1)), ((0,1),(1,1)) が#の場合で、それが満たされていれば他のマスは何でもよい。すなわち、
## #? ?? ?# ?? #? ## ?#の場合である。よって、この4通りの条件のいずれかが満たされているかどうかを調べればよい。
3年前にRubyで書いたときのコードを見てみたら、4隅のマスのうち対角線上の2ヶ所がともに.であれば条件を満たさないとしていた。確かにそう考えてもいい。同じ自分でも時が経つと違う発想をするものだと改めて思う。
辺で隣接する升目の数
ABC250-A
問題概要
h行w列の升目が与えらられる。マス(r,c)に辺で隣接するマスの個数を求めよ。
解答
コンテスト中にはまず以下のコードを書いたのだが、このコードでは15のテストケースのうち5つでWAになった。(2022-05-08 21:20:48)
h,w=gets.chomp.split(" ").to_a.map(&:to_i)
r,c=gets.chomp.split(" ").to_a.map(&:to_i)
ans=4
if (r==1 || r==h) && (c==1 || c==w)
ans=2
elsif (r==1 || r==h) || (c==1 || c==w)
ans=3
end
puts ans
このコードは、以下のように考えて書いた。
- まず、原則として、1つのマスに辺で接する他の辺は上下左右の4つである。
- 例外として、まず、マスが4つの隅のいずれかにあるとき、接するマスは2つになる。
- また、マスが隅ではないが盤面の辺に接しているとき、接するマスは3つになる。
上のコードでは、盤面のサイズが3x3以上であることを前提としているが、制約ではh,wは1以上10以下であるから、縦または横の長さが1である場合も考慮しなければならない。それで書き直して提出したのが以下のコードだが、こちらもWAとなった。(2022-05-08 21:20:48)
h,w=gets.chomp.split(" ").to_a.map(&:to_i)
r,c=gets.chomp.split(" ").to_a.map(&:to_i)
ans=4
if h==1 && w==1
ans=0
elsif (h==1) && (c==1 || c==w)
ans=1
elsif h==1
ans=2
elsif (w==1) && (r=1 || r=h)
ans=1
elsif w==1
ans=2
elsif (r==1 || r==h) && (c==1 || c==w)
ans=2
elsif (r==1 || r==h) || (c==1 || c==w)
ans=3
end
puts ans
このコードでは、以下のように考えている。
それ以外の場合、最初に書いたコードと同じ。
結果は、1つのテストケース(test_05.txt)でWAとなった。これでも結構試行錯誤した末に行きついたもので、A問題にしては難しいと感じた。結局、コンテスト中に正解することができなかった。
今(2025年2月)改めて考えてみても、何が原因か分からない。しかも、間が悪いことに前年の暮れからAtCoderのテストケースが非公開となっており、もはやテストケースを見て原因を探ることができない。
諦めかけたところでもう一度このコードをよく見てみると、二番目の条件式で、== とすべきところが = となっている。そこだけ直して提出したのが以下のコード。(2025-02-26 22:00:38)これでACになった。単純な書き間違いだったのに気付くのに3年弱かかってしまった。
h,w=gets.chomp.split(" ").to_a.map(&:to_i)
r,c=gets.chomp.split(" ").to_a.map(&:to_i)
ans=4
if h==1 && w==1
ans=0
elsif (h==1) && (c==1 || c==w)
ans=1
elsif h==1
ans=2
elsif (w==1) && (r==1 || r==h)
ans=1
elsif w==1
ans=2
elsif (r==1 || r==h) && (c==1 || c==w)
ans=2
elsif (r==1 || r==h) || (c==1 || c==w)
ans=3
end
puts ans
なお、解説を見ると、以下のような方法が示してあった。
- (r,c)が1行目でなければ、上のマスと接しているので、1を加算
- (r,c)がn行目でなければ、下のマスと接しているので、1を加算
- (r,c)が1列目でなければ、左のマスと接しているので、1を加算
- (r,c)がn列目でなければ、右のマスと接しているので、1を加算
これでやってみたのが次のコード。(2025-02-26 22:24:03)
h,w=gets.chomp.split(" ").to_a.map(&:to_i)
r,c=gets.chomp.split(" ").to_a.map(&:to_i)
ans=0
if r!=1
ans+=1
end
if r!=h
ans+=1
end
if c!=1
ans+=1
end
if c!=w
ans+=1
end
puts ans
Cで書いたときには、次のように考えて解いてみた。まず、与えられた盤面の大きさを一回り大きくした、(h+2)*(w+2)の大きさの盤面を作り、全てのマスの数字を0にする。続いて、盤面の一番外側のマスを除いたh*w個のマスの数字を1にする。そして、座標(r,c)の上下左右のマスの数字を足し合わせる。これで、もとの盤面上でマス(r,c)に隣接するマスの数が求められるはずである。それで書いたのが以下のコード。結果は、15件のテストケース中、4件のテストケースでREとなった。(2025-02-26 22:46:13)
int readint(char *s);
#include<stdio.h>
#include<stdlib.h>
#define N1 7
int main(void){
char* s=(char*)malloc(sizeof(char)*N1);
if (s==NULL){
printf("memory allocation to s failed.\n");
exit(1);
}
char *ts=fgets(s,N1,stdin);
if(ts==NULL){
printf("fgets(s) failed\n");
exit(1);
}
int h=readint(s);
int i=0;
while(*(s+i)!=32)i++;
i++;
int w=readint(s+i);
free(s);
char* s2=(char*)malloc(sizeof(char)*N1);
if (s2==NULL){
printf("memory allocation to s2 failed.\n");
exit(1);
}
char *ts2=fgets(s2,N1,stdin);
// printf("%s\n",s2);
if(ts2==NULL){
printf("fgets(s2) failed\n");
exit(1);
}
int r=readint(s2);
i=0;
while(*(s2+i)!=32)i++;
i++;
int c=readint(s2+i);
free(s2);
// printf("h=%d w=%d r=%d c=%d\n",h,w,r,c);
char ans=0;
char* board=(char*)malloc(sizeof(char)*(h+2)*(r+2));
int j;
for(i=0;i<h+2;i++){
for(j=0;j<w+2;j++){
*(board+(w+2)*i+j)=0;
}
}
for(i=1;i<=h;i++){
for(j=1;j<=w;j++){
*(board+(w+2)*i+j)=1;
}
}
/* for(i=0;i<h+2;i++){
for(j=0;j<w+2;j++){
printf("%d",*(board+(w+2)*i+j));
}
printf("\n");
}*/
ans+=*(board+(w+2)*(r-1)+(c));
ans+=*(board+(w+2)*(r)+(c-1));
ans+=*(board+(w+2)*(r)+(c+1));
ans+=*(board+(w+2)*(r+1)+(c));
printf("%d\n",ans);
return 0;
}
int readint(char *s){
int i=0,ret=0;
while(*(s+i)>=48 && *(s+i)<=57){
ret*=10;
ret+=*(s+i)-48;
i+=1;
}
return ret;
}
メモリの範囲外アクセスを疑うが、どこでそれが起きているのか分からない。サンプルのケースでは全てACになっている。テストケースの公開が停止されていることを恨むが、幸いというべきか、この問題では四つの変数がともに10以下なので、全ての組み合わせをしらみつぶしに試しても10^4通りだ。とりあえず、適当な数字を幾つか打ち込んで試してみる。
予想していたよりも早く、h=10,w=10,r=1,c=1 とした時点で実行エラーになった。h=9,w=9 としても同じだ。
ここで、原因は先の3年越しの解決となったrubyのコードと同じ、単純な書き間違いではないかと思い至る。そうして探してみると、見事に、wとすべきところをrとしている所が見つかった。
そこを直して提出したのが以下のコード。これで全てACになった。(2025-03-03 21:21:25)
int readint(char *s);
#include<stdio.h>
#include<stdlib.h>
#define N1 7
int main(void){
char* s=(char*)malloc(sizeof(char)*N1);
if (s==NULL){
printf("memory allocation to s failed.\n");
exit(1);
}
char *ts=fgets(s,N1,stdin);
if(ts==NULL){
printf("fgets(s) failed\n");
exit(1);
}
int h=readint(s);
int i=0;
while(*(s+i)!=32)i++;
i++;
int w=readint(s+i);
free(s);
char* s2=(char*)malloc(sizeof(char)*N1);
if (s2==NULL){
printf("memory allocation to s2 failed.\n");
exit(1);
}
char *ts2=fgets(s2,N1,stdin);
// printf("%s\n",s2);
if(ts2==NULL){
printf("fgets(s2) failed\n");
exit(1);
}
int r=readint(s2);
i=0;
while(*(s2+i)!=32)i++;
i++;
int c=readint(s2+i);
free(s2);
// printf("h=%d w=%d r=%d c=%d\n",h,w,r,c);
char ans=0;
char* board=(char*)malloc(sizeof(char)*(h+2)*(w+2));
int j;
for(i=0;i<h+2;i++){
for(j=0;j<w+2;j++){
*(board+(w+2)*i+j)=0;
}
}
for(i=1;i<=h;i++){
for(j=1;j<=w;j++){
*(board+(w+2)*i+j)=1;
}
}
/* for(i=0;i<h+2;i++){
for(j=0;j<w+2;j++){
printf("%d",*(board+(w+2)*i+j));
}
printf("\n");
}*/
ans+=*(board+(w+2)*(r-1)+(c));
ans+=*(board+(w+2)*(r)+(c-1));
ans+=*(board+(w+2)*(r)+(c+1));
ans+=*(board+(w+2)*(r+1)+(c));
printf("%d\n",ans);
return 0;
}
int readint(char *s){
int i=0,ret=0;
while(*(s+i)>=48 && *(s+i)<=57){
ret*=10;
ret+=*(s+i)-48;
i+=1;
}
return ret;
}
長方形タイルの市松模様
ABC250-B
問題概要
正方形を縦にa個、横にb個並べて一枚としたタイルがある。このタイルを縦横それぞれn枚並べる。各タイルは、#または.に塗られている。左上のタイルの色を.として、このタイル全体からなる模様を出力せよ。
解答
def toggle_flag(flag)
if $flag==false
$flag=true
else
$flag=false
end
end
n,a,b=gets.chomp.split(" ").to_a.map(&:to_i)
$flag=false
n.times do |i|
str=""
n.times do |j|
if $flag==true
c="#"
else
c="."
end
str+=c*b
toggle_flag($flag)
end
a.times do |k|
puts str
end
if n%2==0
toggle_flag($flag)
end
end
上がコンテスト中に提出したコード。よく見るとtoggle_flag関数の引数に意味がなかったが、まあいい。
次に塗るタイルの色が黒か白かを表すフラグを用意する。フラグがtrueなら黒、falseなら白とする。右上のタイルは白なので、初めはフラグはfalseである。
各行の出力用の空文字列を用意し、タイルの横幅分の#か.をまとめて連結。そして連結するごとにフラグを切り替える。こうして一行分の文字列が完成したら、それをタイルの縦の長さ分出力。
続いて、次の行ブロックのタイルの出力に入りたいのだが、その前に、nの偶奇によって処理を分ける必要がある。すなわち、nが偶数であれば、ある行ブロックの最後の列のタイルの色と、次の行ブロックの最初の列のタイルの色は同じなのだが、奇数の場合には、異なる色となる。.なので、nが偶数の場合には、フラグの切り替えを行う。(最後の列のタイルを連結した後にいったんフラグを変えているので、もう一度フラグを切り替えることで、前の行ブロックの最後の列のタイルと同じ色にしている。)
以上の処理をn回繰り返せばよい。
ところで、市松模様では、行番号と列番号の偶奇が同じ場合と異なる場合で色が分かれる。つまり、(行番号、列番号)が(偶数、偶数)の場合と(奇数、奇数)の場合が一つの色となり、(偶数、奇数)の場合と(奇数、偶数)の場合が他方の色となる。これは、行番号+列番号が偶数になる場合(偶数+偶数、奇数+奇数は偶数)と奇数になる場合(偶数+奇数は奇数)とで色が異なると表現することもできる。
だが、その性質を本問のように一文字ずつ市松模様にするのではない場合にどのように使ったらいいのか分からなかったので、コンテスト中には上記のような解法をとった。
解説を見てみてみると、まず、タイルの色を格納したn*n行の行列Aを作り、それをi行j列を塗る際にA[i/a][j/b]の形で参照することで、その座標のタイルの色を得ている。一文字単位では縦がa*n行、横がb*n行なので、i,jをa,bで割った商が、ちょうどその場所の色を示す行列の行数と列数になるのだ。
それでやってみたのが以下のコード。
n,a,b=gets.chomp.split(" ").to_a.map(&:to_i)
tiles=Array.new(n){Array.new(n,"")}
n.times do |i|
n.times do |j|
if (i+j)%2==0
tiles[i][j]="."
else
tiles[i][j]="#"
end
end
end
board=Array.new(n*a){Array.new(n*b,"")}
(n*a).times do |i|
(n*b).times do |j|
board[i][j]=tiles[i/a][j/b]
end
puts board[i].join("")
end
Cで書いたとき、まずはrubyで最初に書いたときと同じように、b文字出力するごとに文字を切り替えるやり方でやってみた。それが以下のコード。(2025-03-05 21:29:25)結果は、18件のテストケース中5件でWAとなった。
int readint(char *s);
char color=46;
void toggle(void){
if(color==46)color=35;
else if(color==35)color=46;
}
#include<stdio.h>
#include<stdlib.h>
#define N1 10
int main(void){
char* s=(char*)malloc(sizeof(char)*N1);
if (s==NULL){
printf("memory allocation to s failed.\n");
exit(1);
}
char *ts=fgets(s,N1,stdin);
if(ts==NULL){
printf("fgets(s) failed\n");
exit(1);
}
int n=readint(s);
int i=0;
while(*(s+i)!=32)i++;
i++;
int a=readint(s+i);
while(*(s+i)!=32)i++;
i++;
int b=readint(s+i);
free(s);
// printf("n=%d a=%d b=%d\n",n,a,b);
int j,k,l;
for(i=0;i<n;i++){
for(j=0;j<a;j++){
for(k=0;k<n;k++){
for(l=0;l<b;l++){
printf("%c",color);
}
toggle();
}
printf("\n");
}
if(n%2==0)toggle();
}
return 0;
}
int readint(char *s){
int i=0,ret=0;
while(*(s+i)>=48 && *(s+i)<=57){
ret*=10;
ret+=*(s+i)-48;
i+=1;
}
return ret;
}
幸いにも、今回はサンプル中でも1件でWAとなっているので、そこを手掛かりにすることができる。そのテストケースでは、
1 4 4
という入力例で、
.... .... .... ....となるべき出力結果が
.... #### .... ####となっている。
何がいけなかったのかを考えてみると、上のコードはRubyで最初に書いたと基本的には同じやり方であるものの、一ヵ所違いがあることに気づく。Rubyで書いたコードでは、上の方法(b文字出力するごとに#と.を切り替える)で1行分の文字列を作った後、それをa回出力しているのに対し、今回Cで書いたコードでは、「b文字出力するごとに#と.を切り替えることをn回繰り返したのち、改行する」ことをa回繰り返しているのである。そのため、nが奇数のとき、本来ならば1つのタイル内では行の最後のマスと次の行の最初のマスが同じ色でなければならないのに、行の最後で色を切り替えたまま次の行に入ってしまい、次の行の最初のマスが別の色になってしまっているのである。
そこを修正するために、一行の処理を終えた後、nが奇数ならばもう一度文字を切り替える処理を入れる。そして、これに伴って、Rubyで書いたコードでの、「nが偶数のとき、行方向にタイルが変わるごとに色を切り替える」処理の代わりに、「行方向にタイルが変わるごとに、常に色を切り替える」処理をすることになる。なぜなら、行の最後のb文字の出力を終えた後に一度文字の切り替えを行い、nが奇数のときだけ各行ごとに文字の切り替えを行い、タイルが変わる行に入る時にまた文字を切り替えることで、タイル行が変わる際、nが偶数ならば2回、nが奇数ならば3回の文字の文字の切り替えが行われることになる。であるから結局、nが偶数のときには、2回の切り替えが行われた結果色は変わらないことになり、新しいタイル行の最初のマスは前のタイル行の最後のマスと同じ色になるからである。
それが以下のコード。(2025-03-05 21:49:41 )
int readint(char *s);
char color=46;
void toggle(void){
if(color==46)color=35;
else if(color==35)color=46;
}
#include<stdio.h>
#include<stdlib.h>
#define N1 10
int main(void){
char* s=(char*)malloc(sizeof(char)*N1);
if (s==NULL){
printf("memory allocation to s failed.\n");
exit(1);
}
char *ts=fgets(s,N1,stdin);
if(ts==NULL){
printf("fgets(s) failed\n");
exit(1);
}
int n=readint(s);
int i=0;
while(*(s+i)!=32)i++;
i++;
int a=readint(s+i);
while(*(s+i)!=32)i++;
i++;
int b=readint(s+i);
free(s);
// printf("n=%d a=%d b=%d\n",n,a,b);
int j,k,l;
for(i=0;i<n;i++){
for(j=0;j<a;j++){
for(k=0;k<n;k++){
for(l=0;l<b;l++){
printf("%c",color);
}
toggle();
}
if(n%2==1)toggle();
printf("\n");
}
toggle();
}
return 0;
}
int readint(char *s){
int i=0,ret=0;
while(*(s+i)>=48 && *(s+i)<=57){
ret*=10;
ret+=*(s+i)-48;
i+=1;
}
return ret;
}
Cで書いたもう一つのコードは、コンテスト中にRubyで書いたときには考えながらも実装できなかった、「市松模様では、「行番号+列番号」の偶奇と色が対応している」という性質を使ったもの。これに、a*n行、b*n列の行、列の番号をそれぞれ a,b で割ったものが、各タイルを1つのマスとしたときの行番号、列番号になる」ということを組み合わせると、以下のようなコードになる。(2025-03-05 22:09:42)
int readint(char *s);
#include<stdio.h>
#include<stdlib.h>
#define N1 10
int main(void){
char* s=(char*)malloc(sizeof(char)*N1);
if (s==NULL){
printf("memory allocation to s failed.\n");
exit(1);
}
char *ts=fgets(s,N1,stdin);
if(ts==NULL){
printf("fgets(s) failed\n");
exit(1);
}
int n=readint(s);
int i=0;
while(*(s+i)!=32)i++;
i++;
int a=readint(s+i);
while(*(s+i)!=32)i++;
i++;
int b=readint(s+i);
free(s);
// printf("n=%d a=%d b=%d\n",n,a,b);
int j;
for(i=0;i<n*a;i++){
for(j=0;j<n*b;j++){
if((i/a+j/b)%2==0)printf("%c",46);
else printf("%c",35);
}
printf("\n");
}
return 0;
}
int readint(char *s){
int i=0,ret=0;
while(*(s+i)>=48 && *(s+i)<=57){
ret*=10;
ret+=*(s+i)-48;
i+=1;
}
return ret;
}
0 件のコメント:
コメントを投稿